Naive Set Theory: Cardinality

Equinumerosity


We've established quite a bit about sets so far, but we haven't yet touched on the topic of the size of a set. Our intuition tells us that the size of a set is the number of elements in it. For example, the size of $A = \{a, b, c\}$ is $3$ because it has $3$ elements in it. This definition works well for sets whose elements we can count, but breaks down as soon as we encounter sets of infinite size. For example, what is the size of the set of the natural numbers, $\mathbb{N}$? We might say that $\mathbb{N}$ is of infinite size, but then we run into trouble when we discover that there are somehow even more real numbers than natural numbers. It is precisely because our loose, intuitive understanding of concepts of "size" and "more" break down that we need more precise mathematical definitions. We owe a great debt to the centuries of mathematicians whose beard stroking and brow furrowing have illuminated our path forward, which begins with the concept of equinumerosity.

Two sets are equinumerous to one another if there exists a bijection between them. For example, the set $A = \{a, b, c\}$ is equinumerous to the set $B = \{1, 2, 3\}$ because there exists a bijective function $f : A \rightarrow B$ where $f(a) = 1$, $f(b) = 2$, and $f(c) = 3$. We express that two sets $A$ and $B$ are equinumerous by writing $A \approx B$.

The concept of equinumerosity is clever, because it captures the idea of "this set has as many elements as that set" without needing to rely on an objective, third party counting mechanism. Our intuition, guided by years of primary schooling, tells us to count the number of elements in one set, count the number of elements in the other set, and then declare that the two sets have the same size only when those two numbers line up. Equinumerosity cuts out the middle man of numbers and instead lines up each element of one set with one from the other. If each element belongs to a unique pairing, the two sets have the same "size." 


Problems

  1. Show that equinumerosity fulfills the same characteristics of an equivalence relation. Namely, show that equinumerosity is:

    • Reflexive: For any nonempty set $A$, $A \approx A$.

    • Symmetric: If $A \approx B$, then $B \approx A$.

    • Transitive: If $A \approx B$ and $B \approx C$, then $A \approx C$.

    • Reflexive: For any nonempty set, the identity function $I: A \rightarrow A$ is a bijection between $A$ and itself, thus $A \approx A$.

    • Symmetric: If $A \approx B$, then by definition there exists a bijection $f : A \rightarrow B$. Because $f$ is a bijection, its inverse $f^{-1} : B \rightarrow A$ exists and is itself a bijection, thus $B \rightarrow A$.

    • Transitive: Assume $A \approx B$ and $B \approx C$. Then there exists bijections $f : A \rightarrow B$ and $g : B \rightarrow C$. Then the composition $f \circ g : A \rightarrow C$ is a bijection, and thus we can conclude that $A \approx C$.

    Show Answer
  2. Show that every nonempty set is equinumerous to itself.

    If $A$ is a nonempty set, then the identity $I_A : A \rightarrow A$ is a bijection from $A$ to itself. Therefore $A$ is equinumerous to itself.

    Show Answer
  3. Show that the set of natural numbers, $\mathbb{N}$, is equinumerous to the set of squares of natural numbers, $\{0, 1, 4, 9, 16, \ldots\}$, which for this example we call $S$.

    Define the function $f : \mathbb{N} \rightarrow S$ as $f(x) = x^2$. We must show that $f$ is bijective. By definition, $f$ is surjective, as $S$ is precisely the set of all squares of natural numbers. To show that $f$ is injective, assume $f(a) = f(b)$ for some $a, b \in \mathbb{N}$. Then $a^2 = b^2$, so $a = b$. Thus $f$ is injective and therefore also bijective, so we conclude that $\mathbb{N} \approx S$.

    Show Answer
  4. Pigeonhole Principle: Prove that no natural number is equinumerous to a proper subset of itself.

    One set is equinumerous to another if there exists a bijection between the two. To show that no such bijection exists, we show that every injective function from $n \in \mathbb{N}$ into itself is also surjective.

    We proceed by induction. Define the set $S$ as

    $$S = \{ n \in \mathbb{N} : \text{ any injective function from } n \text{ into } n \text{ has codomain } n \}.$$

    Base case: The set $0=\varnothing$ is in $S$, as every injective function from $0$ into $0$ is itself empty, thus its codomain is empty.

    Inductive step: Assume $k \in S$, and let $f$ be an injective function from $k^+$ into $k^+$. Then there are two cases to consider. The first is where $k$ is closed under $f$. Note that the restriction $f|k$ is injective, since the restriction of an injection is an injection. Since $k \in S$, $f|k$ must have codomain $k$. Since $f$ is injective, the only possible value for $f(k)$ is then $k$. Hence the codomain of $f$ is $\{k\} \cup k = k^+$. In the second case, $k$ is not closed under $f$, so $f(p) = k$ for some $p < k$. Here we define a new function, $g$, where $g(p) = f(k)$, $g(k) = k$, and $g(x) = f(x)$ where $x$ is neither $p$ nor $k$. Therefore by the first case, $g$ is bijective. Because its codomain is the same as that of $f$, we conclude that $f$ is also bijective. Therefore in either case, $k \in S$ implies $k^+ \in S$, so the result follows by induction.

    Show Answer