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.