Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Think about binary expansion of real numbers. Or look for the duplicate. –  1015 Feb 14 '13 at 21:11
    
@user62268 yeah that works, i posted the same –  Dominic Michaelis Feb 14 '13 at 21:24
1  
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. –  Joe Z. Feb 14 '13 at 21:28

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
2  
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. –  MJD Feb 14 '13 at 22:25

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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