Cardinality: Applications

We want to introduce the concept of cardinality to describe the size of a set. According to Theorem 6(6) in this article, we know that for any finite set $A$ , there exists a unique natural number $n$ such that $A \sim N_{< n}$ . We call $n$ as the number of elements of the set $A$ . Therefore, it is natural to define the cardinality of a finite set as its number of elements. Clearly, two finite sets have the same cardinality if and only if these two sets are equinumerous.

Similarly, the concept of cardinality can be extended to infinite sets. However, since infinite sets do not have a specific "number of elements", it is not as straightforward to rigorously define the cardinality of them. However, we can still choose some infinite sets and specially assign a cardinality to them. Thus, we can define cardinality as follows.

Definition 1: Cardinality

The cardinality of a finite set is defined as its number of elements. Specially, we define the cardinality of $N$ as $ℵ_{0}$ , and the cardinality of $R$ as $c$ . We use $| A |$ to denote the cardinality of $A$ .

Nevertheless, by analogy with finite sets, two sets have the same cardinality if and only if they are equinumerous (i.e., in a one-to-one correspondence). Additionally, if one set precedes another, we say that the cardinality of the first set is less than that of the second. Thus, we can define the equivalence and partial order in terms of cardinalities.

Definition 2: Equivalence and Partial Order

We define the equivalence relation $=_{c}$ and the partial order $\leq_{c}$ on caidinalities as
$=_{c} . . = {(| A |, | B |) ∣ A \sim B}$ $\leq_{c} . . = {(| A |, | B |) ∣ A ≼ B}$

Since $\sim$ is an equivalence relation and $≼$ is a total order, $=_{c}$ and $\leq_{c}$ are equivalence and total order respectively. If $| A | =_{c} | B |$ , we say $A, B$ have the same cardinality. Similarly, if $| A | \leq_{c} | B |$ , we say the cardinality of $A$ is less than the cardinality of $B$ . In the future, if no confusion arises, we will always denote $=_{c}$ as $=$ , and $\leq_{c}$ as $\leq$ .

Let us further examine the addition, multiplication, and exponentiation of cardinal numbers. According to Corollary 1 in this article, the sum of the cardinalities of two disjoint finite sets equals the cardinality of their union, the product of the cardinalities of two finite sets equals the cardinality of their Cartesian product, and the exponentiation of the cardinalities of two finite sets equals the cardinality of their power. Following these patterns, we can similarly define addition, multiplication, and exponentiation for arbitrary sets.

Definition 3: Binary Operations

The addition, multiplication, and exponentiation of cardinalities are defined as
$+_{c} (| A |, | B |) = | A \times {0} ⊔ B \times {1} |$ $\times_{c} (| A |, | B |) = | A \times B |$ $P (| A |, | B |) = | A^{B} |$

By convention, when no ambiguity arises, we may also write $+_{c} (| A |, | B |)$ as $| A | +_{c} | B |$ or $| A | + | B |$ , $\times_{c} (| A |, | B |)$ as $| A | \times_{c} | B |$ or $| A | \times | B |$ , $P (| A |, | B |)$ as ${| A |}^{| B |}$ . Hereafter, unless otherwise specified, we will always use the notations $| A | + | B |$ , $| A | \times | B |$ , and ${| A |}^{| B |}$ .

For example, using the notations defined above, since we have discussed that $2^{N} \sim R$ , it follows that $c = | R | = | 2^{N} | = 2^{ℵ_{0}}$ .

Next, we will prove the inclusion-exclusion principle for finite sets.

Theorem 1: Inclusion-Exclusion Principle

If $A$ , $B$ are finite sets, then:
$| A \cup B | = | A | + | B | - | A \cap B |$

Since $A = (A ∖ B) ⊔ (A \cap B)$ , we have $| A | = | A ∖ B | + | A \cap B |$ . Also, since $A \cup B = (A ∖ B) ⊔ B$ , we have $| A \cup B | = | A ∖ B | + | B |$ . Therefore, $| A \cup B | = | A | + | B | - | A \cap B |$ . $Q.E.D.$

By repeatedly applying Theorem 1, we can also extend the inclusion-exclusion principle to the union of $n$ sets. We will not elaborate further here.

In the second half of this section, we will calculate the cardinalities of some important sets.

Theorem 2:

$| N | = | Z | = | Q | = ℵ_{0}$

Since $f : N \to Z, n \mapsto \frac{n + 1}{2} [2 ∤ n] - \frac{n}{2} [2 ∣ n]$ is a bijection from $N$ to $Z$ , it follows that $N \sim Z$ , i.e., $| N | = | Z |$ . Let $g : N^{2} \to Q, (m, n) \mapsto \frac{m}{n}$ ; it is evident that $g$ is a surjection. Therefore, $N ≼ Q ≼ N^{2} \sim N$ . By antisymmetry, we have $Q \sim N$ . Thus, $| N | = | Z | = | Q | = ℵ_{0}$ . $Q.E.D.$

Theorem 3:

$| R | = | C | = c$

Since $f : R^{2} \to C, (a, b) \mapsto a + b i$ is a bijection from $R^{2}$ to $C$ , it follows that $C \sim R^{2} \sim R$ , i.e., $| R | = | C | = c$ . $Q.E.D.$

If we denote the set of all prime numbers as $P$ , then we have

Theorem 4: Euclid's theorem

$| P | = ℵ_{0}$

Assume $| P | < ℵ_{0}$ . Let $n$ be the number of elements of $P$ , $P$ can be written as ${p_{1}, \dots, p_{n}}$ . Let
$N . . = \prod_{i = 1}^{n} p_{i} + 1$ Obviously, $N$ is greater than any prime number in $P$ , so $N$ must be composite. Therefore there exists a natural number $m$ such that
$p_{m} ∣ N = \prod_{i = 1}^{n} p_{i} + 1$ Then $p_{m} ∣ 1$ , which leads to a contradiction. Therefore, $| P | \geq ℵ_{0}$ . On the other hand, since $P \subseteq N$ , we have $| P | \leq ℵ_{0}$ . By antisymmetry, we conclude that $| P | = ℵ_{0}$ . $Q.E.D.$

If $x$ is a real root of a polynomial with integer coefficients, then $x$ is called an algebraic number. Next, we will prove that the cardinality of the algebraic set $A$ is also $ℵ_{0}$ .

Theorem 5:

$| A | = ℵ_{0}$

Since $A . . = ⋃_{p \in Z [x]} {x \in R ∣ p (x) = 0}$ according to Corollary 2 in this article, $| Z [x] | = | Z | = ℵ_{0}$ . Since $A$ is a union of countably many countable sets, $| A | \leq ℵ_{0}$ . On the other hand, since $N \subseteq A$ , we have $| A | \geq ℵ_{0}$ . By antisymmetry, we conclude that $| A | = ℵ_{0}$ . $Q.E.D.$

We will now prove a somewhat counterintuitive theorem: the set of all sequences of natural numbers is equinumerous with the set of all sequences of real numbers. Equivalently, this means $| N^{\infty} | = | R^{\infty} |$ .

Theorem 6:

$| N^{\infty} | = | R^{\infty} | = c$

$| N^{\infty} | = {ℵ_{0}}^{ℵ_{0}} = 2^{ℵ_{0}} = c$ $| R^{\infty} | = (2^{ℵ_{0}})^{ℵ_{0}} = 2^{ℵ_{0}^{2}} = 2^{ℵ_{0}} = c$ $Q.E.D.$

The last two theorems we prove require some preliminaries in calculus.

Theorem 7:

Let $a < b$ , and let $C [a, b]$ denote the set of all continuous functions on $[a, b]$ . Then:
$| C [a, b] | = c$

We can define
$S . . = {f ↾ Q ∣ f \in C [a, b]}$ Let
$φ : C [a, b] \to S, f \mapsto f ↾ Q$ Therefore,
$φ^{- 1} : S \to C [a, b], f \mapsto {(c, lim_{x \to c} f (x)) | c \in [a, b]}$ $\Rightarrow | C [a, b] | = | S | \leq | R^{Q} | = c$ On the other hand, since there exists a function $ψ$ such that
$ψ : R \to C [a, b], n \mapsto {(c, n) ∣ c \in [a, b]}$ and $ψ$ is clearly injective, it follows that $| C [a, b] | \geq c$ . By antisymmetry, we obtain $| C [a, b] | = c$ . $Q.E.D.$

Theorem 8:

Let $a < b$ , and let $R [a, b]$ denote the set of all Riemann integrable functions on $[a, b]$ . Then:
$| R [a, b] | = 2^{c}$

Let $φ : R [a, b] \to R [0, 1], f (x) \mapsto f ((b - a) x + a)$ , then $ψ$ is clearly a bijection from $R [a, b]$ to $R [0, 1]$ . Hence, $| R [a, b] | = | R [0, 1] |$ . Let $f \in R [0, 1]$ , and let $C$ be the Cantor set on $[0, 1]$ . Then we can define
$g . . = f ↾ ([0, 1] ∖ C)$ $\Rightarrow {g ⊔ h ∣ h \in R^{C}} \subseteq R [0, 1]$ $\Rightarrow 2^{c} = c^{c} = | R^{C} | = | {g ⊔ h ∣ h \in R^{C}} | \leq | R [0, 1] |$ Since $R [0, 1] \subseteq R^{[0, 1]}$ , we also have $| R [0, 1] | \leq c^{c} = 2^{c}$ . Thus, by antisymmetry, we get $2^{c} = | R [0, 1] | = | R [a, b] |$ . $Q.E.D.$

Therefore, based on Theorem 7 and Theorem 8, it is easy to determine the cardinality of some sets of functions with conditions that are weaker than continuity or stronger than Riemann integrability.