3
$\begingroup$

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?

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

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.

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

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.