# $A=\{f \mid f:\mathbb{Z}_+ \to \{0,1\}\}$ is uncountable

Consider the set $A=\{f \mid f:\mathbb{Z}_+ \to \{0,1\}\}.$ I need to show that it is uncountable.

I was trying to find a bijection between $A$ and $\mathbb{R}$ or if I can show that there is no injection from $A$ to $\mathbb{Z}_+$ then also it'll work !

The situation cries out for Cantor's diagonal argument:

Consider any function $s:\mathbb N\to A$ and, for each $n$, call $f_n=s(n)$. Define $f:\mathbb N\to\{0,1\}$ by $f(n)=1-f_n(n)$ for every $n$. Then $f$ is in $A$ but not in $s(\mathbb N)$ (why?). Hence $s$ is not a surjection. This proves that $A$ is uncountable.

• i didn't get how you defined $f_n(n)$ – Bhauryal Aug 25 '13 at 17:26
• it is a classical cantors diagonal arguement. just have in mind that you have some ordering of them and now you construct a sequence which differs at least in one position from every other – Dominic Michaelis Aug 25 '13 at 17:27
• @NeerajBhauryal he assumed $s$ to be such a surjection and $f_n$ the "counting" of $A$. Then he proves, that one can construct an element out of the scope of $s$, so $s$ is no surjection. – AlexR Aug 25 '13 at 17:28
• @AlexR He didn't assume that $s$ is a surjection, just a function – Hagen von Eitzen Aug 25 '13 at 17:43
• @NeerajBhauryal The number $f_n(n)$ is $0$ or $1$ and defined as the image of $n$ by the function $f_n$. – Did Aug 25 '13 at 18:10

Think of binary representation of real numbers in $[0,1]$. (You can write every real number in $[0,1]$ as $$x=\sum_{n=1}^\infty \frac{a_n}{2^n}$$ where $a_n\in\{0,1\}$.

This will give you the idea for a surjection from $A$ to $[0,1]$.

• how can we write irrationals in this expression? – Bhauryal Aug 25 '13 at 17:05
• @NeerajBhauryal irrationals as well as rationals have a unique $p$-adic representation ($\pi = 3.14159\ldots$ for base $10$) – AlexR Aug 25 '13 at 17:07
• @AlexR Unique? Hardly. – Did Aug 25 '13 at 17:09
• @Did give me a second decadic representation of $\pi$... That is: $$\pi = \sum_{k\in\mathbb{Z}} a_k 10^k$$ with $a_k \in \{0, \ldots, 9\} \quad \forall\ k\in\mathbb{Z}$ – AlexR Aug 25 '13 at 17:10
• @DominicMichaelis Nice answer! – dreamer Aug 25 '13 at 17:48

You can identify $A$ with the power set of $\mathbb Z_+$. What do you know about the cardinality of a power set?

• i know that cardinality of $\mathbb{Z}_+$ will me more than continuum, but how do you identify $A$ with power set of $\mathbb{Z}_+$ – Bhauryal Aug 25 '13 at 17:14
• The cardinality of $\mathbb Z_+$ is less than continuum; it's countable. For any set $X$, the power set of $X$ has greater cardinality than $X$, so in particular the power set of $\mathbb Z_+$ is uncountable. The identification is given by indicator functions. – Chris Culter Aug 25 '13 at 17:34
• so yeah i meant power set of $\mathbb{Z}_+$ has cardinality more than continuum – Bhauryal Aug 25 '13 at 19:11

By $\mathbb{Z}_+$ you mean $\mathbb{N} = \{1, 2, \ldots\}$? Then $$\sum_{n\in\mathbb{N}} f(n)2^{-n} \in [0, 1] \subset \mathbb{R}$$ And for the injection $[0,1] \to A$ chose $$T(x)[n] = \lfloor x\cdot 2^n \text{ mod } 2 \rfloor$$ Then you have $|A| = |[0,1]| = |\mathbb{R}|$ q.e.d.

• The first function is not an injection. The second one does not produce $\{0,1\}$-valued sequences. – Did Aug 25 '13 at 17:11
• It sure does, modulus Cauchy-sequences. And $\text{mod}$ is to be taken floored, but I don't know the TeX-code for the floor brackets right now. – AlexR Aug 25 '13 at 17:13
• "modulus Cauchy-sequences"... ?? Care to explain? // LaTeX: try \lfloor and \rfloor. – Did Aug 25 '13 at 17:17
• \lfloor and \floor gives the floor function. How do you know that modulus cauchy sequences doesn't mess up your cardinality? For example if you take the discrete metric only nearly constant sequences are cauchy, so you only have countable many of them – Dominic Michaelis Aug 25 '13 at 17:17
• modulus Cauchy -> $$\sum_{n\in\mathbb{N}} (f(n)-g(n)) 2^{-n} = 0$$ Is that okay by you? @DominicMichaelis modulus reduces the cardinality at most (with the euclidean metric), so $|A| \geq |A/\text{cauchy}|$ if I am correct. – AlexR Aug 25 '13 at 17:18

Consider $g:A\to P(\mathbb{Z_+})$, $g(f)=\cup_{n:f(n)=1}\{n\}$. This is a bijection between $A$ and $P(\mathbb{Z_+})$, and $|P(\mathbb{Z_+})|=|\mathbb{R}|$.

• Isn't $A$ defined to be $2^{\mathbb{Z}_+}$ ? – Dominic Michaelis Aug 25 '13 at 17:30
• No? $A$ is a set of functions. – JLA Aug 25 '13 at 17:32
• How do you define $A^B$ for sets $A,B$ ? – Dominic Michaelis Aug 25 '13 at 17:32
• Maybe what I wrote isn't clear, but I meant $2^S=P(S)$. I'll change it. – JLA Aug 25 '13 at 17:33
• Oh I see, because for me $A^B$ is the set of functions from $B$ to $A$. – Dominic Michaelis Aug 25 '13 at 17:35