Cardinality

Overview

For any set , the cardinal number of $A$ (denoted $\text{card}A$), is the least ordinal equinumerous to $A$. Therefore:

• For any sets $A$ and $B$, $\text{card}A=\text{card}B$ iff $A\approx B$.
• For a finite set $A$, $\text{card}A$ is the natural number $n$ for which $A\approx n$.

Equinumerosity

We say set $A$ is equinumerous to set $B$, written $A\approx B$, if and only if there exists a one-to-one function from $A$ onto $B$.

Power sets

No set is equinumerous to its power set. This is typically shown using a diagonalization argument. For any set $A$, ${}^{A}2\approx \mathcal{P}(A)$.

Equivalence Concept

For any sets $A$, $B$, and $C$:

• $A\approx A$;
• if $A\approx B$, then $B\approx A$;
• if $A\approx B$ and $B\approx C$, then $A\approx C$.

Notice though that $\{⟨A,B⟩\mid A\approx B\}$ is not an equivalence relation since the equivalence concept of equinumerosity concerns all sets.

Finiteness

A set is finite if and only if it is equinumerous to a natural number. The cardinal number of such a set is a finite cardinal. Otherwise we say the set is infinite. The cardinal number of such a set is an infinite cardinal.

Pigeonhole Principle

No natural number is equinumerous to a proper subset of itself. More generally, no finite set is equinumerous to a proper subset of itself. Likewise, any set equinumerous to a proper subset of itself must be infinite.

Arithmetic

Addition

Let $\kappa$ and $\lambda$ be any cardinal numbers. Then $\kappa +\lambda =\text{card}(K\cup L)$, where $K$ and $L$ are any disjoint sets of cardinality $\kappa$ and $\lambda$, respectively.

Multiplication

Let $\kappa$ and $\lambda$ be any cardinal numbers. Then $\kappa \cdot \lambda =\text{card}(K\times L)$, where $K$ and $L$ are any sets of cardinality $\kappa$ and $\lambda$, respectively.

Exponentiation

Let $\kappa$ and $\lambda$ be any cardinal numbers. Then ${\kappa }^{\lambda }=\text{card}{(}^{L}K)$, where $K$ and $L$ are any sets of cardinality $\kappa$ and $\lambda$, respectively.

Ordering

A set $A$ is dominated by a set $B$, written $A⪯B$, if and only if there is a one-to-one function from $A$ into $B$. In other words, $A⪯B$ if and only if $A$ is equinumerous to some subset of $B$. Then

Furthermore,

Schröder-Bernstein Theorem

For any sets $A$ and $B$, if $A⪯B$ and $B⪯A$, then $A\approx B$.

Order-Preservation Properties

For cardinal numbers $\kappa$, $\lambda$, and $\mu$,

• If $\kappa \le \lambda$, then $\kappa +\mu \le \lambda +\mu$;
• If $\kappa \le \lambda$, then $\kappa \cdot \mu \leq \lambda \cdot \mu;,
• If $\kappa \le \lambda$, then ${\kappa }^{\mu }\le {\lambda }^{\mu }$;
• If $\kappa \le \lambda$ and not both $\kappa$ and $\mu$ equal zero, then ${\mu }^{\kappa }\le {\mu }^{\lambda }$.

Countable Sets

A set $A$ is countable if and only if $A⪯\omega$. That is, if and only if $\text{card}A\le {\mathrm{\aleph }}_0$.

Union

A countable union of countable sets is countable. More generally, if every member of a set $A$ has cardinality $\kappa$ or less, then

Sequences

Let $A$ be a set. A sequence in $A$ is a function from some natural number into $A$. Let $\text{Sq}(A)$ be the set of all sequences in $A$:

The length of a sequence is its domain.

Alephs

Infinite cardinals are described using alephs.

Continuum Hypothesis

The continuum hypothesis states that there are no sets with cardinality between ${\mathrm{\aleph }}_0$ and $2^{{\mathrm{\aleph }}_0}$. The generalized continuum hypothesis states that for any infinite cardinal $\kappa$, there is no cardinal number between $\kappa$ and $2^{\kappa }$.