1
$\begingroup$

How can I prove that the set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable?

Edit: This answer came to mind. Is it correct?

This answer just came to mind. By contradiction suppose the set is $\{f_n\}_{n \in \mathbb{N}}$. Define the function $f: \mathbb{N} \to \{0,1\}$ by $f(n) \ne f_n(n)$. Then $f \notin\{f_n\}_{n \in \mathbb{N}}$.

$\endgroup$
  • $\begingroup$ Think about binary expansion of real numbers. Or look for the duplicate. $\endgroup$ – Julien Feb 14 '13 at 21:11
  • $\begingroup$ @user62268 yeah that works, i posted the same $\endgroup$ – Dominic Michaelis Feb 14 '13 at 21:24
  • 1
    $\begingroup$ Your answer that came to mind is correct, and in fact is exactly Cantor's diagonalization argument for the power set of natural numbers being larger than the set of natural numbers itself. $\endgroup$ – Joe Z. Feb 14 '13 at 21:28
2
$\begingroup$

You can proof it by contraposition. I will identify the functions with sequence so $a_{n}$=$a(n)$. Now lets say it's countable, now let $a_{nk}=a_k(n)$ be the $k$-th function. Now we construct the function $$b(k)=\left\{ \begin{array}{rl} 1 & a_{kk}=0\\ 0& a_{kk}=1\end{array}\right.$$ You should be able to do the rest.

$\endgroup$
  • 2
    $\begingroup$ You don't need contraposition. You can do a direct proof that goes like this: Let $f$ be a mapping from $\mathbb N$ to $2^{\mathbb N}$. We can construct an element $b $ of $2^{\mathbb N}$ just as you did: $b(k) = 1-f(k)(k)$, and show that $b$ is not in the range of $f$. Therefore $f$ is not a bijection. But $f$ was completely general, so we have just proved that no mapping from $\mathbb N$ to $2^{\mathbb N}$ is a bijection, QED. $\endgroup$ – MJD Feb 14 '13 at 22:25
8
$\begingroup$

Hint: Show that $\{0,1\}^\mathbb N$ is equinumerous with $\mathcal P(\mathbb N)$ and use Cantor's theorem to conclude there is no bijection between $\mathbb N$ and $\mathcal P(\mathbb N)$.

$\endgroup$
0
$\begingroup$

Hint : use the diadic developpement of elements of $[0,1]$.

$\endgroup$
0
$\begingroup$

Hint: Each function from $\mathbb{N} \to \{0, 1\}$ is isomorphic to a subset of $\mathbb{N}$. Simply count $n \in \mathbb{N}$ to be part of the subset of $f(n) = 1$.

$\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.