8.2 Countable and Uncountable Sets

Set theory explores the sizes of infinite sets through cardinality. Countable sets match up with natural numbers, while uncountable sets are larger. This distinction forms the foundation for comparing infinities.

Bijections prove countability by mapping sets to natural numbers. For uncountable sets like real numbers, Cantor's diagonalization method shows no such mapping exists. These concepts reveal the surprising complexities of infinity.

Set Theory and Cardinality

Countable vs uncountable sets

Top images from around the web for Countable vs uncountable sets

• 

  Cardinality - Wikipedia View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

• 

  Summary: Classes of Real Numbers | Developmental Math Emporium View original

  Is this image relevant?

• 

  Cardinality - Wikipedia View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

1 of 3

Top images from around the web for Countable vs uncountable sets

• 

  Cardinality - Wikipedia View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

• 

  Summary: Classes of Real Numbers | Developmental Math Emporium View original

  Is this image relevant?

• 

  Cardinality - Wikipedia View original

  Is this image relevant?

• 

  Number Sets View original

  Is this image relevant?

1 of 3

• Countable sets correspond one-to-one with natural numbers or subsets includes finite and countably infinite sets (natural numbers, integers, rational numbers)
• Uncountable sets cannot correspond one-to-one with natural numbers have cardinality greater than natural numbers (real numbers, power set of natural numbers)
• Formal definitions use injective functions $\exists f: A \to \mathbb{N}$ for countable and $\nexists f: A \to \mathbb{N}$ for uncountable
• Cardinality notation uses $\aleph_0$ for countably infinite and $\mathfrak{c}$ for uncountable sets like reals

Bijections for countable sets

• Bijection means one-to-one and onto function establishes countability
• Proving countability requires:
  1. Construct explicit function from set to natural numbers
  2. Show function is injective (one-to-one)
  3. Show function is surjective (onto)
• Common techniques employ list method for countably infinite sets use pairing functions for Cartesian products apply diagonal arguments for unions of countable sets
• Provably countable sets include integers rational numbers algebraic numbers

Advanced Cardinality Concepts

Uncountability of real numbers

• Cantor's diagonalization method proves uncountability of reals:
  1. Assume reals are countable
  2. List all reals between 0 and 1
  3. Construct new number differing from each listed number
  4. Show new number not in list contradicts assumption
• Key proof steps use decimal representation alter digits along diagonal ensure new number differs from every listed number
• Uncountability implies existence of transcendental numbers demonstrates non-enumerability of reals

Cardinality of infinite sets

• Cardinal numbers represent size of infinite sets establish ordering among infinities
• Cardinal arithmetic operations for infinite sets:
  • Addition: $|A \cup B| = \max(|A|, |B|)$
  • Multiplication: $|A \times B| = \max(|A|, |B|)$
  • Exponentiation: $|A^B| > |A|$
• Cantor-Schröder-Bernstein theorem states if $|A| \leq |B|$ and $|B| \leq |A|$, then $|A| = |B|$
• Cardinality comparisons show $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$ and $|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} = \mathfrak{c}$
• Continuum hypothesis posits no set with cardinality between $\aleph_0$ and $\mathfrak{c}$