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.

Is the set of all functions from $\mathbb{N}$ to $\lbrace 0,1\rbrace$ countable or uncountable ? I have no idea on how to start. Any hint or guide will be much appreciated.

share|improve this question
1  
Hint: Use Cantor's diagonal argument. Assume the set of all function form $\mathbb{N}$ to $\{0,1\}$ is countable, and derive the contradiction. –  tetori Jan 26 '13 at 17:21
1  
Hint: Find a bijection with the powerset. For any set $S$ and any map $f\colon S\to P(S)$, $f$ fails to be onto because it misses $\{x\in S\mid x\notin f(S)\}$. –  Hagen von Eitzen Jan 26 '13 at 17:22
    
@HagenvonEitzen: Find bijection between powerset and what ? –  Idonknow Jan 26 '13 at 17:26
    
@Idonknow ... a bijection between the poswerset of $\mathbb N$ and the set of functions from $\mathbb N$ to $\{0,1\}$, cf. Asaf's answer. –  Hagen von Eitzen Jan 27 '13 at 11:08
add comment

2 Answers

up vote 5 down vote accepted

Hint: You can think of each function as a binary representation; then use Cantor's diagonal argument to show that it can't be countable.

Set up a table like $$\begin{align}&a_{11}a_{12}a_{13}\ldots\\ &a_{21}a_{22}a_{23}\ldots\\ &a_{31}a_{32}a_{33}\ldots \end{align}$$ where each $a_{ij}\in\{0,1\}$, and use the diagonal argument with the $a_{jj}$.

share|improve this answer
    
What is binary representation? –  Idonknow Jan 26 '13 at 17:39
1  
You can think of the function as assigning a position, so for example, you could have $$1_10_20_30_4\ldots$$ as possible representation (the binary says that only zeroes and ones are present). Here, the subscripts represent what number mapped to that image, i.e., $1\mapsto 1$, $2\mapsto 0$, and so on. –  Clayton Jan 26 '13 at 17:43
    
I still don know how to proceed. –  Idonknow Jan 26 '13 at 17:49
    
I've edited my answer for hopefully a more-clear hint. –  Clayton Jan 26 '13 at 17:56
    
Sorry, I'm still very blur. –  Idonknow Jan 26 '13 at 18:10
show 6 more comments

Hint: Show that the function $F\colon\{0,1\}^\mathbb N\to\mathcal P(\mathbb N)$ defined by $F(f)=\{n\in\mathbb N\mid f(n)=1\}$ is a bijection.

Use Cantor's theorem to show that $\mathcal P(\mathbb N)$ is uncountable and deduce the same on $\{0,1\}^\mathbb N$.

share|improve this answer
add comment

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.