Equinumerosity

🅟 Mar 06, 2026

  🅤 Jun 10, 2026

Definition 1.

Two sets $X$ and $Y$ are equinumerous, written

\[X \equ Y,\]

if there exists a bijection from $X$ onto $Y$.

$X$ is not a greater set than $Y$, written

\[X \lequ Y,\]

if there exists an injection from $X$ to $Y$.

$X$ is a smaller set than $Y$, written

\[X \lnequ Y,\]

if $X \lequ Y$ and $X \not\equ Y$.


Proposition 1. Reflexivity of $\equ$.

For any set $X$,

\[X \equ X.\]

Proposition 2. Symmetry of $\equ$.

For any sets $X$ and $Y$,

\[X \equ Y \enspace\rimp\enspace Y \equ X.\]

Proposition 3. Transitivity of $\equ$.

For any $X$, $Y$ and $Z$,

\[X \equ Y \,\land\, Y \equ Z \enspace\rimp\enspace X \equ Z.\]

As a corollary of reflexivity, symmetry and transitivity of $\equ$:

Proposition 4.

For any set $X$, $\equ$ is an equivalence relation on $\powerset(X)$.


Proposition 5. Reflexivity of $\lequ$.

For any set $X$,

\[X \lequ X.\]

Proposition 6. Transitivity of $\lequ$.

For any sets $X$, $Y$ and $Z$,

\[X \lequ Y \,\land\, Y\lequ Z \enspace\rimp\enspace X\lequ Z.\]

Proposition 7. Schröder-Bernstein Theorem.

For any sets $X$ and $Y$,

\[X \lequ Y \,\land\, Y\lequ X \enspace\rimp\enspace X\equ Y.\]

Proposition 8.

For any sets $X$ and $Y$, if $X \subseteq Y$, then $X \lequ Y$.

Proof. $\id_X : X \to Y$ is an injection.