Cardinality and Infinite Sets

Cardinality is a measure of the “number of elements” of a set. For finite sets, this is just a natural number, but for infinite sets, things become more complex.

Equinumerosity

Two sets $A$ and $B$ have the same cardinality, $|A| = |B|$, if there exists a bijection $f: A \to B$.

A set is countably infinite if it has the same cardinality as the natural numbers $\mathbb{N}$. Surprisingly, the set of rational numbers $\mathbb{Q}$ is countable, while the set of real numbers $\mathbb{R}$ is not.

def count_to_infinity(limit):
  # Demonstrating that Even numbers are equinumerous to Natural numbers
  # f(n) = 2n
  evens = [(n, 2*n) for n in range(limit)]
  return evens

print("Mapping N to Evens (First 5):")
for pair in count_to_infinity(5):
  print(f"n={pair[0]} maps to even={pair[1]}")

Cantor’s Diagonal Argument

Georg Cantor proved that the cardinality of the real numbers (the Continuum, $\mathfrak{c}$) is strictly greater than the cardinality of the natural numbers ($\aleph_0$). He used a technique called diagonalization.

import random

def cantors_diagonal(rows):
  """Given a list of decimal expansions, create a number that isn't in the list."""
  new_number = "0."
  for i in range(len(rows)):
      # Take the i-th digit of the i-th row and change it
      digit = int(rows[i][i+2]) # offset for "0."
      new_digit = (digit + 1) % 10
      new_number += str(new_digit)
  return new_number

sequences = ["0.12345", "0.55555", "0.98765", "0.11111", "0.00000"]
print(f"Generated number not in list: {cantors_diagonal(sequences)}")

Cantor’s Theorem

Cantor’s Theorem states that for any set $A$, the cardinality of its power set $\mathcal{P}(A)$ is strictly greater than the cardinality of $A$: $|A| < |\mathcal{P}(A)|$ This results in an infinite hierarchy of infinities: $\aleph_0, \aleph_1, \aleph_2, \dots$