Let $G$ be the set of all functions $g : ℕ \to \{0,1\}$. Prove that $G$ is uncountable.

Question

Question:

Let $G$ be the set of all functions $g : ℕ \to \{0,1\}$. Prove that $G$ is uncountable.

Where I am at so far:

$G$ is countable if a bijection exists from $ℕ$ to $G$. Otherwise $G$ is uncountable.

Thus in order to prove $G$ is uncountable we need to show that there is no bijection from $ℕ$ to $G$.

So let $f$ be any function $f: ℕ \to G$. All we need to show is either

(i) $f$ is not injective

(ii) $f$ is not surjective.

But how would I go about showing either one?

Answer 1

Define $g: \mathbb N \to \{0,1\}$ by $g(n)=1$ if $f(n)(n)=0$ and $g(n)=0$ if $f(n)(n)=1$. This function is not in the range of $f$. Hence $f$ is not surjective.

Answer 2

For any g with in G, g is a function g : ℕ --> {0,1}. Thus g is a sequence and so we can visualise it as such. For example, (0, 1, 1, 0,...) means there is a function in G such that it maps 1 to 0, 1 to 1, 2 to 1, 3 to 1 etc.

Now, let f : ℕ --> G be a function.

Consider the following table:

\begin{array}{|c|} \hline ℕ & f(n) \\ \hline 1& b_1^1& b_1^2& b_1^3& b_1^4& b_1^5& ... \\ \hline 2& b_2^1& b_2^2& b_2^3& b_2^4& b_2^5& ... \\ \hline 3& b_3^1& b_3^2& b_3^3& b_3^4& b_3^5& ... \\ \hline 4& b_4^1& b_4^2& b_4^3& b_4^4& b_4^5& ... \\ \hline 5& b_5^1& b_5^2& b_5^3& b_5^4& b_5^5& ... \\ \hline & & &\\ \hline. & & &\\ \hline. & & &\\ \hline. \end{array}

Now construct the sequence C = ($c_1$, $c_2$, $c_3$, $c_4$, $c_5$,...) where

$C_i$ = \begin{cases} 1, & \text{if $b_i^i$ = 0} \\ 0, & \text{if $b_i^i$ = 1} \end{cases}

Thus it is evident to see that C differs from f(n) at the $n^t$$^h$ term in the sequence by 1 for all n.

Thus it is evident to see that C is not in our table and so there is no natural number which maps to it. Thus f is not surjective and so cannot be bijective. This means it is not countable and so it is uncountable.

Answer 3

I'll just add another point of view. There is a pretty direct bijection between $G$ and $\mathcal{P}(\mathbb{N})$, the powerset of $\mathbb{N}$ in the following way:

Take $N\in \mathcal{P}(\mathbb{N})$ i.e. $N\subset \mathbb{N}$ and now construct a function $f \in G$ i.e. $f:\mathbb{N}\to \{0,1\}$ as follows.

$$ f(n)=\begin{cases} 1 ~\text{if} ~n\in N\\0~ \text{else} \end{cases} $$.

This gives a injective function $F:\mathcal{P}(\mathbb{N}) \to G$ with inverse

\begin{eqnarray} F^{-1}:G &\to& \mathcal{P}(\mathbb{N})\\ f &\mapsto& f^{-1}(1). \end{eqnarray}

In fact this shows that for any set $A$ the set $G$ of functions from $A\to \{0,1\}$ has the same cardinality as $\mathcal{P}(A)$, hence the notation $\vert\mathcal{P}(A)\vert=2^{\vert A\vert}$ which leads to the infamous formulation of the continuum hypothesis: $\aleph_1=2^{\aleph_0}$?