Equinumerous sets, $A\approx B$ and $A⪯B$

Let $A$ and $B$ be sets (Injection, surjection, bijection for the terminology).

• $A$ and $B$ are equinumerous, written $A\approx B$, if there exists a bijection $f:A\to B$.
• $A$ is dominated by $B$, written $A⪯B$, if there exists an injection $f:A\to B$.
• $A\prec B$ abbreviates: $A⪯B$ and not $A\approx B$.

• $\approx$ behaves like an equivalence relation. It is reflexive (${\mathrm{i}\mathrm{d}}_A$ is a bijection), symmetric (the inverse of a bijection is a bijection) and transitive (a composition of bijections is a bijection). The careful statement is that these three properties hold for all sets, and that $\approx$ restricted to any set of sets is an equivalence relation on that set. It is not a relation on "the set of all sets", which does not exist; the reflexivity, symmetry and transitivity statements are schemas about arbitrary sets, which is all any argument below uses.

• $⪯$ is reflexive and transitive, for the same reasons, and $A\approx B$ implies both $A⪯B$ and $B⪯A$. The converse, that $A⪯B$ and $B⪯A$ together give $A\approx B$, is a theorem and not a triviality: it is The Schröder-Bernstein theorem, and it is proved without any use of choice.

• Subsets. $A\subseteq B$ implies $A⪯B$, since the inclusion map is injective. The reverse fails badly for infinite sets: the successor map $\sigma$ is a bijection $\mathbb{N}\to \mathbb{N}\setminus \{0\}$, being injective and never zero (The von Neumann naturals form a Peano system) and hitting every nonzero natural (Every nonzero natural number is a successor), so $\mathbb{N}\approx \mathbb{N}\setminus \{0\}$ and a proper subset can be equinumerous with the whole.

• $\approx$ is the library's substitute for "has the same number of elements", stated without introducing cardinal numbers. Everything on this page is phrased with $\approx$, $⪯$ and $\prec$ alone, so no theory of cardinals is presupposed.