Class 19: Uncountable Sets

Countable and Uncountable Sets

Definition. A set $S$ is countably infinite if and only if there exists a bijection between $S$ and $\mathbb{N}$.

Definition. A set $S$ is uncountable, if there exists no bijection between $S$ and $\mathbb{N}$.

The power set of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$: $$ B \in \textrm{pow}(A) \iff B \subseteq A. $$

For all finite sets $S$, $|pow(S)| = 2^{|S|}$.

# #

For all sets $S$, $|pow(S)| > |S|$.

#

Prove $pow(\mathbb{N})$ is uncountable.

#

$\text{bitstrings} = \forall n \in \mathbb{N} . {0, 1}^n$.

#

Ordinal and Cardinal Numbers

$\omega$ is the smallest infinite ordinal. The first ordinal after $0, 1, 2, \cdots$.

What is the difference between an ordinal and cardinal number?

##

What should $2\omega$ mean?

##

Is $\text{InfiniteBitStrings} = {0, 1}^\omega$ countable?

#

Prove the number of real numbers in the interval $[0, 1]$ is uncountable.

# # #

What set is bigger than $\mathbb{R}$?

#

Aleph-naught: $\aleph_0 = |\mathbb{N}|$ is the smallest infinite cardinal number.

How is $\omega$ different from $\aleph_0$?

##

$$2^{\aleph_0} = |pow(\mathbb{N})| = | [0, 1] | = | \mathbb{R} | = | \text{InfiniteBitStrings} | $$

What is necessary to conclude that it is not possible to settle the question of whether $\aleph_1 = 2^{\aleph_0}$ with the ZFC axioms?