TheoremBase

Counting through Bijections, Injections and Surjections

A bijection preserves finiteness and the number of elements; an injection into a finite set, and a surjection from a finite set, bound the number of elements from the appropriate side.

Statement

In the setting of Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices, let AA and BB be sets and f:A→Bf:A\to B a map, let finite sets be as in Finite Sets (i) and #\# as in The Number of Elements of a Finite Set (i).

Bijections. If ff is bijective and AA is finite, then BB is finite and #B=#A\#B=\#A.

Injections. If ff is injective and BB is finite, then AA is finite and #A≤#B\#A\le\#B.

Surjections. If ff is surjective and AA is finite, then BB is finite and #B≤#A\#B\le\#A.

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…