Let $G$ be the set of all functions $g : ℕ \to \{0,1\}$. Prove that $G$ is uncountable. 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?
 A: 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. 
A: 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.
A: 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}$?
