Equinumerous sets, $A \approx B$ and $A \preceq 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 \preceq B$, if there exists an injection $f : A \to B$.
• $A \prec B$ abbreviates: $A \preceq B$ and not $A \approx B$.

• $\approx$ behaves like an equivalence relation. It is reflexive ($\mathrm{id}_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.

• $\preceq$ is reflexive and transitive, for the same reasons, and $A \approx B$ implies both $A \preceq B$ and $B \preceq A$. The converse, that $A \preceq B$ and $B \preceq 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 \preceq 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$, $\preceq$ and $\prec$ alone, so no theory of cardinals is presupposed.