Cardinal Numbers - Countable and Uncountable Cardinals, Cantor's Diagonal Process

Introduction to Cardinal Numbers

In mathematics, a cardinal number is a number that answers the question "how many?" It is a generalization of the natural numbers used to measure the size of sets. For finite sets, the cardinal number is simply the number of elements in the set. For example, the set {apple, banana, cherry} has a cardinal number of 3.

The concept of cardinal numbers becomes particularly interesting when dealing with infinite sets. Georg Cantor pioneered the study of infinite sets and their cardinalities, introducing the idea that there are different "sizes" of infinity. This is a departure from our everyday intuition, where we tend to think of infinity as a single, unbounded quantity.

Equinumerosity

Before we can compare the sizes of infinite sets, we need a precise way to determine if two sets have the same size. For finite sets, this is straightforward: two sets have the same size if they have the same number of elements. For infinite sets, we use the concept of equinumerosity.

Two sets, A and B, are said to be equinumerous (or have the same cardinality) if there exists a bijection (a one-to-one and onto function) between them. A bijection is a function f: A → B such that:

• Injective (One-to-one): For any distinct elements a₁, a₂ in A, f(a₁) ≠ f(a₂).
• Surjective (Onto): For every element b in B, there exists at least one element a in A such that f(a) = b.

If a bijection exists between two sets, they are considered to have the same cardinality. We denote the cardinality of a set A as |A|. So, if A and B are equinumerous, then |A| = |B|.

Countable Sets

A set is called countably infinite if it is equinumerous to the set of natural numbers, ℕ = {1, 2, 3, ...}. This means that we can establish a bijection between the set and ℕ. In other words, we can list all the elements of a countably infinite set in an infinite sequence, without missing any element.

The cardinality of a countably infinite set is denoted by ℵ₀ (aleph-null).

Examples of Countable Sets:

• The set of Natural Numbers (ℕ): This is the defining set for countability. The bijection is simply the identity function f(n) = n. |ℕ| = ℵ₀.
• The set of Integers (ℤ): The set of integers is {..., -2, -1, 0, 1, 2, ...}. It might seem larger than ℕ, but we can create a bijection. Consider the following ordering: 0, 1, -1, 2, -2, 3, -3, ... This list enumerates all integers. The function that maps ℕ to ℤ can be defined as: f(1) = 0 f(2) = 1 f(3) = -1 f(4) = 2 f(5) = -2 and so on. This demonstrates that ℤ is countably infinite, so |ℤ| = ℵ₀.
• The set of Even Natural Numbers: {2, 4, 6, 8, ...}. We can define a bijection f: ℕ → {2, 4, 6, ...} by f(n) = 2n. This shows that the set of even numbers has the same cardinality as the set of all natural numbers, ℵ₀. This is a counter-intuitive result: a proper subset of an infinite set can have the same cardinality as the set itself.
• The set of Rational Numbers (ℚ): The set of rational numbers consists of all numbers that can be expressed as a fraction p/q, where p and q are integers and q ≠ 0. It might appear that there are "more" rational numbers than integers, but Cantor proved that ℚ is also countably infinite.

Demonstrating the Countability of Rational Numbers

To show that ℚ is countable, we can arrange all positive rational numbers in an infinite grid and then traverse this grid in a specific order to create a single list.

Consider the grid where the row index represents the numerator and the column index represents the denominator:

We can traverse this grid diagonally: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, ...

This diagonal traversal creates a sequence of all positive rational numbers. However, some numbers appear multiple times (e.g., 1/1 = 1, 2/2 = 1, 3/3 = 1; 1/2, 2/4 = 1/2). To get a list of unique rational numbers, we simply skip duplicates.

The sequence of unique positive rational numbers starts like this: 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, ...

This sequence can be mapped to the natural numbers, showing that the set of positive rational numbers is countable. By including 0 and negative rational numbers, we can also show that the set of all rational numbers ℚ is countably infinite, with cardinality ℵ₀.

Uncountable Sets

A set is called uncountable if it is not countable. This means that there is no bijection between the set and the set of natural numbers ℕ. Such sets are "larger" than the set of natural numbers; they contain more elements.

The first example of an uncountable set, famously demonstrated by Cantor, is the set of real numbers, ℝ.

Cantor's Diagonal Process (or Diagonal Argument)

Cantor's diagonal process is a powerful proof technique used to show that certain infinite sets are uncountable. It works by assuming that such a set *is* countable and then constructing an element that is not in the assumed enumeration, thus leading to a contradiction.

Let's use Cantor's diagonal process to prove that the set of real numbers in the interval [0, 1] is uncountable.

Proof:

1. Assumption: Assume, for the sake of contradiction, that the set of real numbers in [0, 1] is countable. This means we can list all real numbers in this interval in an infinite sequence: r₁, r₂, r₃, ..., r_n, ...
2. Representation: Each real number r_n in this list can be represented by its decimal expansion. For simplicity, we will use infinite decimal expansions, padding with trailing zeros if necessary (e.g., 0.5 = 0.5000...). r₁ = 0.d₁₁d₁₂d₁₃d₁₄... r₂ = 0.d₂₁d₂₂d₂₃d₂₄... r₃ = 0.d₃₁d₃₂d₃₃d₃₄... r₄ = 0.d₄₁d₄₂d₄₃d₄₄... ... r_n = 0.d_n1d_n2d_n3d_n4... where each d_ij is a digit from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
3. Constructing the Diagonal Number: Now, we construct a new real number, let's call it 'x', which is also in the interval [0, 1]. We define the digits of 'x' by looking at the "diagonal" of the list. Let x = 0.b₁b₂b₃b₄... The digit b_n is chosen such that it is different from the n-th digit of the n-th number in our list (d_nn). A common way to do this is: If d_nn = 1, then set b_n = 2. If d_nn ≠ 1, then set b_n = 1. (Alternatively, one can choose b_n ≠ d_nn and ensure b_n is not 0 or 9 to avoid issues with non-unique decimal representations like 0.5000... = 0.4999..., though the method above avoids this by picking 1 or 2).
4. The Contradiction: Our newly constructed number 'x' is a real number between 0 and 1. However, 'x' cannot be present in our assumed list r₁, r₂, r₃, ... Why? - 'x' is not equal to r₁ because its first digit (b₁) is different from the first digit of r₁ (d₁₁). - 'x' is not equal to r₂ because its second digit (b₂) is different from the second digit of r₂ (d₂₂). - In general, 'x' is not equal to r_n because its n-th digit (b_n) is different from the n-th digit of r_n (d_nn).
5. Conclusion: We have constructed a real number 'x' in [0, 1] that is not in the list. This contradicts our initial assumption that we could list *all* real numbers in [0, 1]. Therefore, the set of real numbers in [0, 1] is uncountable.

Since the interval [0, 1] is uncountable, any set containing it, such as the set of all real numbers ℝ, must also be uncountable.

Cardinality of the Continuum

The cardinality of the set of real numbers (ℝ) is denoted by 'c' or ℵ₁ (under the Continuum Hypothesis, which is independent of the standard axioms of set theory). This 'c' represents the "cardinality of the continuum."

Cantor's diagonal process proves that c > ℵ₀. This means that the infinity of the real numbers is strictly larger than the infinity of the natural numbers. There are fundamentally "more" real numbers than there are natural numbers, integers, or rational numbers.

The diagonal argument is a cornerstone of set theory and has profound implications for understanding the nature of infinity.

Countable vs. Uncountable Infinity

Countable Infinity (ℵ₀): Refers to the size of sets that can be put into a one-to-one correspondence with the natural numbers (ℕ). Examples include ℕ, ℤ, ℚ. We can "count" these elements, even though the counting process goes on forever.

Uncountable Infinity (c): Refers to the size of sets that are strictly larger than the set of natural numbers. They cannot be put into a one-to-one correspondence with ℕ. The classic example is the set of real numbers (ℝ). We cannot even list them in an infinite sequence.

Further Cardinalities

Cantor's work established that there isn't just one size of infinity but an infinite hierarchy of infinities. For any set A, the power set of A (the set of all subsets of A), denoted P(A), always has a strictly larger cardinality than A itself. That is, |P(A)| > |A|.

For example:

• |P(ℕ)| = |ℝ| = c. This means the set of all subsets of natural numbers has the same cardinality as the set of real numbers.
• |P(ℝ)| > |ℝ|. This gives us an even larger infinity.

This leads to an endless sequence of ever-larger cardinal numbers: ℵ₀, ℵ₁, ℵ₂, ...