6.3 Comparing set sizes and Cantor's theorem

Comparing set sizes is a key concept in set theory. It introduces cardinality, which measures how many elements are in a set. This applies to both finite and infinite sets, allowing us to compare their sizes.

Cantor's theorem is a game-changer. It proves that a set's power set (all its subsets) is always bigger than the original set. This leads to mind-bending ideas about different levels of infinity.

Cantor's Theorem and Diagonalization

Power Set and Cantor's Theorem

Top images from around the web for Power Set and Cantor's Theorem

• 

  Cantor's theorem - Wikipedia View original

  Is this image relevant?

• 

  Cantor's Theorem - Mathonline View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Cantor's theorem - Wikipedia View original

  Is this image relevant?

• 

  Cantor's Theorem - Mathonline View original

  Is this image relevant?

1 of 3

Top images from around the web for Power Set and Cantor's Theorem

• 

  Cantor's theorem - Wikipedia View original

  Is this image relevant?

• 

  Cantor's Theorem - Mathonline View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Cantor's theorem - Wikipedia View original

  Is this image relevant?

• 

  Cantor's Theorem - Mathonline View original

  Is this image relevant?

1 of 3

• Cantor's theorem states that for any set $A$, the power set of $A$, denoted as $\mathcal{P}(A)$, always has a greater cardinality than the set $A$ itself
  • In other words, there is no surjective function from $A$ to $\mathcal{P}(A)$
  • This holds true for both finite and infinite sets
  • Cantor's theorem is a fundamental result in set theory that establishes the existence of different levels of infinity
• The power set of a set $A$ is the set of all subsets of $A$
  • For a finite set with $n$ elements, the power set has $2^n$ elements
  • For example, if $A = \{1, 2, 3\}$, then $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$

Diagonalization Argument

• The diagonalization argument is a proof technique used to demonstrate Cantor's theorem
  • It shows that for any proposed bijection between a set $A$ and its power set $\mathcal{P}(A)$, there always exists a subset of $A$ that is not mapped to by any element of $A$
• The diagonalization argument proceeds as follows:
  1. Assume, for contradiction, that there exists a bijection $f: A \to \mathcal{P}(A)$
  2. Define a subset $B \subseteq A$ as follows: for each $a \in A$, $a \in B$ if and only if $a \notin f(a)$
  3. The set $B$ is a well-defined subset of $A$, so it must be an element of $\mathcal{P}(A)$
  4. However, $B$ cannot be the image of any element $a \in A$ under the function $f$, leading to a contradiction
• The diagonalization argument is named after the diagonal entries in a table representation of the proposed bijection, which are used to construct the contradictory subset $B$

Comparing Set Sizes

Cardinality and Equipotent Sets

• Cardinality is a measure of the size of a set, denoted as $[|A|](https://www.fiveableKeyTerm:|a|)$ for a set $A$
  • Two sets $A$ and $B$ have the same cardinality if there exists a bijection (a one-to-one correspondence) between them
  • Sets with the same cardinality are called equipotent or equinumerous
  • For finite sets, cardinality is simply the number of elements in the set
  • For example, the sets $\{a, b, c\}$ and $\{1, 2, 3\}$ are equipotent, as they both have a cardinality of 3
• Comparing the sizes of infinite sets is more complex and requires the concept of cardinality
  • Two infinite sets are equipotent if there exists a bijection between them
  • For example, the set of natural numbers $\mathbb{N}$ and the set of even natural numbers are equipotent, as there exists a bijection $f(n) = 2n$ between them

Continuum Hypothesis

• The continuum hypothesis is a statement about the possible cardinalities of infinite sets
  • It states that there is no set with a cardinality strictly between the cardinality of the natural numbers (denoted as $\aleph_0$) and the cardinality of the real numbers (denoted as $\mathfrak{c}$, the cardinality of the continuum)
  • In other words, the continuum hypothesis asserts that there is no intermediate cardinality between the smallest infinite cardinal ($\aleph_0$) and the cardinality of the real numbers ($\mathfrak{c}$)
• The continuum hypothesis was introduced by Georg Cantor but was later shown to be independent of the standard axioms of set theory (ZFC)
  • This means that both the continuum hypothesis and its negation are consistent with the axioms of ZFC
  • The independence of the continuum hypothesis was proven by Kurt Gödel (consistency) and Paul Cohen (independence) in the 20th century

Infinite Cardinal Numbers

Aleph Numbers and the Continuum

• Aleph numbers, denoted as $\aleph_0, \aleph_1, \aleph_2, \ldots$, represent the cardinalities of infinite sets
  • $\aleph_0$ (aleph-null) is the smallest infinite cardinal number and represents the cardinality of the natural numbers $\mathbb{N}$
  • $\aleph_1$ is the next larger cardinal number, and its existence is guaranteed by Cantor's theorem
  • The continuum hypothesis states that the cardinality of the real numbers, denoted as $\mathfrak{c}$, is equal to $\aleph_1$
• The cardinality of the continuum (the real numbers $\mathbb{R}$) is often denoted as $\mathfrak{c}$
  • It is known that $\mathfrak{c} = 2^{\aleph_0}$, which means that the cardinality of the real numbers is equal to the cardinality of the power set of the natural numbers
  • The value of $\mathfrak{c}$ is at least $\aleph_1$, but the continuum hypothesis asserts that $\mathfrak{c} = \aleph_1$

Power Set Cardinality and Cantor's Theorem

• For any infinite cardinal number $\kappa$, the power set of a set with cardinality $\kappa$ has a cardinality of $2^\kappa$
  • This is a consequence of Cantor's theorem, which states that the power set of a set always has a greater cardinality than the set itself
  • For example, the cardinality of the power set of the natural numbers is $2^{\aleph_0} = \mathfrak{c}$
• Cantor's theorem and the properties of power set cardinalities lead to the existence of an infinite hierarchy of infinite cardinal numbers
  • Each cardinal number has a power set with a strictly greater cardinality, leading to a never-ending sequence of larger and larger infinities
  • This hierarchy of infinities is a fundamental concept in set theory and has profound implications for the foundations of mathematics