Class 18: Spooky Infinities
Schedule
Problem Set 7 is due Friday (27 Oct) at 6:29pm.
Exam 2 is two weeks from today (November 9, in class). We will post more information about Exam 2 soon.
Links
Logicomix: An epic search for truth, comic book by Apostolos Doxiadis and Christos H. Papadimitrou.
Last year, there was a Problem Set ω - you can see some examples of student’s work. (Note that having a PS ω does not imply any limit on the number of regular problem sets, since there are infinitely many natural numbers before ω!)
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.