Cardinalities of Sets

Numerically Equivalent Sets

In the classical era, “size” was a property primarily associated with finite collections, where the terminal result of a counting process provided an absolute value. However, the necessity of defining “size” for infinite collections demanded a more sophisticated definition. This transition challenged the ancient axiom that “the whole is greater than the part,” a principle that proved insufficient when applied to the non-finite.

The historical tension surrounding this development is most clearly seen in the intellectual progression from Galileo Galilei to Bernhard Bolzano and Richard Dedekind. In his 17th-century works, Dialogue Concerning the Two Chief World Systems and Discourses and Mathematical Demonstrations Concerning Two New Sciences, Galileo observed a “bothersome” property of the infinite: a bijective correspondence could be established between the set of positive integers $\mathbb{N}$ and the set of their squares $S = \{1, 4, 9, \dots\}$. Galileo recognized that despite the existence of many integers that are not squares, there appeared to be “as many” squares as there are integers. He concluded that while the number of squares was not less than the number of integers, the two sets could not be considered “equal” in the traditional sense, as the correspondence between a set and its proper subset felt inherently paradoxical.

By the 19th century, Bernhard Bolzano began to normalize this phenomenon. In his work Paradoxes of the Infinite, Bolzano expressed comfort with the fact that infinite sets could be numerically equivalent to their proper subsets. It was Richard Dedekind who eventually synthesized these observations into a formal definition. During the late 19th century, Dedekind transformed Galileo’s paradox into a defining characteristic: a set $S$ is infinite if and only if it contains a proper subset that can be put in one-to-one correspondence with $S$.

In abstract mathematics, we replace the intuitive process of counting with the formal mechanism of “pairing” to determine cardinality. For finite sets, cardinality ($|S|$) is the number of elements in the collection. However, for a general theory applicable to all sets, we define numerical equivalence.

Proof

• Reflexivity: For any set $A$, the identity function $i_A: A \to A$ is bijective, thus $A \approx A$.
• Symmetry: If $|A| = |B|$ via bijection $f$, then $f$ has an inverse $f^{-1}: B \to A$ which is also bijective, ensuring $|B| = |A|$.
• Transitivity: If $|A| = |B|$ and $|B| = |C|$ via bijections $f$ and $g$ respectively, then the composition $g \circ f: A \to C$ is bijective. Thus, $|A| = |C|$.

Denumeral Sets

This requires a bijective mapping $f: \mathbb{N} \to A$, allowing us to list the elements of $A$ as an infinite sequence $\{a_1, a_2, a_3, \dots\}$ where each $a_i = f(i)$.

Proof

We can construct a bijection $f: \mathbb{N} \to \mathbb{Z}$ by listing elements as $0, 1, -1, 2, -2, \dots$.

Formally, this is defined by the function:

$$f(n) = \frac{1 + (-1)^n(2n - 1)}{4}$$

The alternating sign provided by $(-1)^n$ allows the function to oscillate between the positive and negative integers, ensuring that zero and all positive/negative integers are mapped exactly once, confirming that $\mathbb{Z}$ is no “larger” than $\mathbb{N}$ despite containing it as a proper subset.

Proof

Let $A = \{a_1, a_2, \dots\}$ and $B \subseteq A$. We define

$$S = \{i \in \mathbb{N} : a_i \in B\}$$

By the Well-Ordering Principle, $S$ has a least element $i_1$, and we set $b_1 = a_{i_1}$.

Inductively, we define $i_{k+1}$ as the minimum element of $S - \{i_1, i_2, \dots, i_k\}$ and set $b_{k+1} = a_{i_{k+1}}$.

This inductive selection creates a list $\{b_1, b_2, \dots\}$ that bijectively maps $\mathbb{N}$ to $B$, proving $B$ is denumerable.

Uncountable Sets

The conceptual breakthrough of the uncountable set demonstrated that the real number line possesses a magnitude that cannot be exhausted by any list.

Proof

The proof employs the Cantor Diagonal Argument.

If we assume $(0, 1)$ is denumerable, we could list its elements as

$$\{a_1, a_2, a_3, \dots\}$$

in decimal form:

$$a_1 = 0.a_{11}a_{12}a_{13}\dots a_2 = 0.a_{21}a_{22}a_{23}\dots a_3 = 0.a_{31}a_{32}a_{33}\dots$$

We construct a number $b = 0.b_1b_2b_3\dots$ by defining each digit $b_i = 4$ if $a_{ii} = 5$, and $b_i = 5 if a_{ii} \neq 5$.

This ensures $b$ differs from every $a_n$ in at least the $n$-th decimal place. Crucially, by avoiding the digit $9$, we ensure $b$ is not an “alternate expansion” (such as $0.499\dots$ being equal to $0.500\dots$), guaranteeing $b$ is a unique real number in $(0, 1)$ not present on the list. This contradiction proves $(0, 1)$ is uncountable.

To prove that two different infinite sets possess the same cardinality, we must demonstrate a bijective functional mapping between them.

Proof

Let us define a function $f$ as follows:

$$f(x) = \frac{x}{1 - |x|}$$

To verify its bijective nature, we first prove it is one-to-one.

If $f(a) = f(b)$, we consider the case where $f(a) > 0$ (implying $a, b > 0$). Then

$$\frac{a}{1-a} = \frac{b}{1-b} \implies a - ab = b - ab \implies a = b$$

A similar logic applies for $a, b < 0$.

Next, we prove it is onto.

For any $r \in \mathbb{R}$, if $r > 0$, we find $x = \frac{r}{1+r} \in (0, 1)$ such that $f(x) = r$. If $r < 0, x = \frac{r}{1-r} \in (-1, 0)$ maps to $r$.

Thus, $f$ is bijective.

Comparing Cardinalities of Sets

In advanced set theory, identifying equivalent structures across disparate notations is essential for deep analysis. A instance of this is the relationship between the power set $\mathcal{P}(A)$, that is the collection of all subsets of $A$, and the function space $2^A$, which denotes the set of all functions mapping from $A$ to the codomain $\{0, 1\}$.

Proof

To establish this equivalence, we define a bijection

$$\phi: P(A) \to 2^A$$

For any subset $S \subseteq A$, we map $S$ to a specific indicator function (or characteristic function) $f_S \in 2^A$.

We define this mapping $\phi(S) = f_S$, where for each $x \in A$:

$$f_S(x) = \begin{cases} 1 & \text{if } x \in S \\ 0 & \text{if } x \notin S \end{cases}$$

Consider the case where $A = \{a, b\}$. The power set $P(A)$ contains $2^{|A|} = 4$ elements. The mapping is illustrated in the following table:

|Subset $S \in P(A)$|Function $f_S \in 2^A$|Formal Mapping Details| |$\emptyset$|$f_1$|$\{(a, 0), (b, 0)\}$| |${a}$|$f_2$|${(a, 1), (b, 0)}$| |${b}$|$f_3$|${(a, 0), (b, 1)}$| |${a, b}$|$f_4$|${(a, 1), (b, 1)}$|

Verification of Bijection:

Injectivity:

Assume $\phi(S) = \phi(T)$. This implies $f_S = f_T$, and thus $f_S(x) = f_T(x)$ for all $x \in A$. By the definition of the indicator function, $x \in S$ if and only if $x \in T$, necessitating that $S = T$.

Surjectivity:

Given any function $f \in 2^A$, we define the set $S = \{x \in A : f(x) = 1\}$. It follows immediately that $f_S = f$, proving that every function in $2^A$ is the image of a subset in $P(A)$.

Cantor’s Theorem and the Hierarchy of Infinity

Proof by Contradiction

Assume there exists a bijective function $g: A \to P(A)$. For every $x \in A$, let $g(x) = A_x$, where $A_x \subseteq A$.

Define a specific subset $B \subseteq A$ as $B = \{x \in A : x \notin A_x\}$. Since $g$ is assumed to be surjective, there must exist some $y \in A$ such that $g(y) = B$.

Let us analyze the membership of $y$ in $B$:

• If $y \in B$, then by the definition of $B$, $y \notin A_y$. Since $A_y = B$, this implies $y \notin B$, a contradiction.
• If $y \notin B$, then $y \notin A_y$. By the definition of $B$, this implies $y \in B$, also a contradiction.

Thus, no such $y$ can exist, and the assumption of a bijection is false.

The implication says that there is no largest set. One can always construct a larger infinity by taking the power set of a set, leading to an infinite progression of cardinalities.

The Aleph Null, the Continuum, and the Continuum Hypothesis

The cardinality of denumerable sets, such as $\mathbb{N}$, is denoted by $\aleph_0$ or “aleph null”. Any set in a one-to-one correspondence with $\mathbb{N}$ has cardinality $\aleph_0$.

Conversely, the cardinality of the real numbers $\mathbb{R}$ is termed the continuum, denoted by $c$. As established, $\aleph_0 < c$.

The Continuum Hypothesis (CH) represents one of the most significant questions in the foundations of mathematics. It posits that there is no set $S$ such that $\aleph_0 < |S| < c$. The resolution of this hypothesis reveals the limits of axiomatic systems:

• Kurt Gödel (1931) proved that CH is consistent with the standard axioms of set theory and cannot be disproved.
• Paul Cohen (1963) proved that CH is independent of those same axioms and cannot be proved.

Thus, CH is undecidable within. While we know $|P(\mathbb{N})| > \aleph_0$, investigating sets with cardinality greater than $c$ requires powerful tools.

The Schröder-Bernstein Theorem

For any $x \in A$, we define $f^1(x) = f(x)$, and for $n \ge 2$, $f^n(x) = f(f^{n-1}(x))$.

We define a specific subset $B’ \subseteq B$ as:

$$B' = \{f^n(x) : x \in A - B, n \in \mathbb{N}\}$$

By defining $C = (A - B) \cup B’$ and using the restriction $f_1: C \to B’$, we can construct a bijective function $h: A \to B$ by mapping elements of $C$ via $f$ and elements of $D = B - B’$ via the identity function $i_D$.

This recursive sequence $f^1(x), f^2(x), f^3(x), \dots$ is what essentially allows us to “rearrange” the set into a bijection.