# 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?

• Think of each function as a $0,1$ sequence. Those are uncountable by the diagonal argument. – Akash Gaur Jul 3 '19 at 10:24
• Use Cantor's diagonal argument – Peter Jul 3 '19 at 10:25
• G is countable if a bijection exists from ℕ to G. Otherwise G is finite or an uncountable.infinite set. – CopyPasteIt Jul 3 '19 at 10:48
• @CopyPasteIt Depending on the source, finite sets are also sometimes considered countable; in this case, only a surjection from $\mathbb{N}$ is needed. – Dirk Jul 3 '19 at 10:58

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.

• It would have been better if your answer only had one sentence: $\quad$ Define...$\quad$ Cantor would smile if he saw this. (+1) – CopyPasteIt Jul 3 '19 at 11:17

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.

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}$$?