Berkeley CS70

Uncountably infinite. We use Cantor's Diagonalization Proof:

Let \(\mathscr{F}=\{f\mid f:\mathbb{N}\to \mathbb{N}\}\). If we can construct a bijection from \(\mathbb{N}\) to \(\mathscr{F}\), then consider

Consider the function \(g:\mathbb{N}\to \mathbb{N}\) where \(g(i)=f_i(i) +1\) for all \(i\in \mathbb{N}\). We claim that \(g\) is not in our list of functions, because \(f_n(\cdot)\) and \(g(\cdot)\) differ in the \(n\)-th argument, so the original set is uncountably infinite.

The idea is to restrict both the length of the string and the characters we are allowed to use:

a. List all strings containing only characters in \(\{a_1\}\) with length at most \(1\).

b. List all strings containing only characters in \(\{a_1,a_2\}\) with length at most \(2\) and have not been listed before.

c. Proceed onwards.

We can prove that our enumeration is complete, and each string appears exactly once in the listing.

Consider a subset, which is the set of infinite-length strings containing only as and bs. We construct a bijection from this subset to \(\mathbb{R}[0,1]\) by replacing as with 0s and bs with 1s, which produces a unique binary number, e.g.

So the set is uncountably infinite.