# Cardinality of sets of functions

Show that the set $A$ of all functions $f:\mathbb{Z}^{+} \to \mathbb{Z}^{+}$ and $B$ of all functions $f:\mathbb{Z}^{+} \to \{0,1\}$ have the same cardinality.

I am having trouble to define a bijection that would prove this statement. Any hints would be appreciated.

• I think the Cantor-Bernstein-Schroeder theorem might help: the fact that $|B| \leq |A|$ isn't too hard, so we just need $|A| \leq |B|$, simplifying the problem to finding an injection from $A \to B$. For that, perhaps the following $\phi : A \to B$ works: for $f \in A$, let $[\phi(f)](n) = 0$ for all $n = 1,\dots,f(1)$, $[\phi(f)](n) = 1$ for all $n = f(1)+1,\dots,f(1)+f(2)$, and so on... e.g. using sequences to simplify notation, $(1,2,3,\dots)$ will be mapped to $(0,1,1,0,0,0,1,1,1,1,\dots)$. (This is by no means a bijection - nothing maps to $g(n) = 1$, for example.) – Platehead Oct 15 '14 at 11:42
• @Platehead I am a little weary using Cantor-Bernstein-Schroeder (CBS) theorem since this is not part of the book I am currently reading. Not that I don't know about, I do. But, if I were to use CBS then I would have to prove that theorem as well. – comPl9121 Oct 15 '14 at 11:54
• Can you use the fact that if $A$ is not countable and $B$ is countable, then $A\cup B$ and $A$ have the same cardinal? – ajotatxe Oct 15 '14 at 12:45
• @ajotatxe I may be able to use CBS after all. Given your initial solution, I went ahead to show that if $B \subseteq A$ and if there is an injection $f:A \to B$, then $A$ and $B$ have the same cardinality. Now, it is my understanding, and please correct me if I'm wrong, that this result can be used to prove CBS. All that is needed is to establish that injection to image is bijection. Then, as $g:B \to A$ is an injection, we have $g(B) \subseteq A$ and by the result just mentioned, there exists a bijection $h:A \to g(B)$. But since $B$ is equivalent to $g(B)$, the theorem follows. Right? – comPl9121 Oct 15 '14 at 13:18
• I should at this point notify you, @ajotatxe, that the book I am stuck with for this task is Rudin's little blue book. To say its treatment of cardinality is spares would be an understatement. – comPl9121 Oct 15 '14 at 13:24

Let $C$ be the set of all (strictly) increasing functions $\Bbb Z^+\rightarrow\Bbb Z^+$.

First, consider this function $\sigma$ from $A$ to $C$. For each $f$ we define $\sigma(f)=\sigma_f$ defined so: $$\sigma_f(n)=\sum_{j=1}^n f(j)$$ This funtion is bijective. Hence, $\#C=\#A$.

Let's show that indeed, this function is bijective:

Suppose that $\sigma_f=\sigma_g$ and take an arbitrary $n\in\Bbb Z^+$. If $n=1$, then $$f(1)=\sigma_f(1)=\sigma_g(1)=g(1)$$ and if $n\geq2$, then $$f(n)=\sigma_f(n)-\sigma_f(n-1)= \sigma_g(n)-\sigma_g(n-1)=g(n)$$ This proves that $\sigma$ is injective.

Now, take any function $u\in C$ and define: $$f(n)=\left\{ \begin{array}{cl} u(1)&\text{ if }n=1\\ u(n)-u(n-1)&\text{ otherwise} \end{array} \right.$$ It is clear that $f\in A$ and that $u=\sigma_f$ and, hence, $\sigma$ is surjective.

We will now define a function $\phi$ from $B$ to $C$. Take a function $f$ from $B$. If the preimage of $1$ is infinite, let $J$ be this preimage. If not, then the preimage of $0$ is infinite, and let then $J$ be this preimage. Since it is a subset of $\Bbb Z^+$, which is well ordered, we can write $J$ as an increasing sequence: $j_1<j_2<\ldots<j_n<\ldots$
Now, if $J$ is the preimage of $1$, define $\phi(f)=\phi_f$ this way: $$\phi_f(n)=2j_n$$ And if $J$ is the preimage of $0$: $$\phi_f(n)=2j_n+1$$

The function $\phi:f\mapsto\phi_f$ is injective. Hence $\#B\leq\#C$.

To prove that $\phi$ is injective, let's assume that $\phi_f=\phi_g$ and take $n\in\Bbb Z^+$. If the images of $\sigma_f$ are even, then $$f(n)=1\iff 2n \in\phi_f(\Bbb Z^+)\iff 2n \in\phi_g(\Bbb Z^+)\iff g(n)=1$$ and if the images of $\sigma_f$ are odd, $$f(n)=0\iff 2n+1 \in\phi_f(\Bbb Z^+)\iff 2n+1 \in\phi_g(\Bbb Z^+)\iff g(n)=0$$

Since the images of $f$ and $g$ can be only $0$ or $1$, this proves that $\phi$ is injective.

Last, define the function $\delta:f\mapsto\delta_f$ from $C$ to $B$: $$\delta_f(n)=\left\{ \begin{array}{cl} 1&\text{ if }n\in f(\Bbb Z^+)\\ 0&\text{ otherwise} \end{array} \right.$$

This function is injective. Then, $\#C\leq\#B$

So $\#A=\#B=\#C$, q.e.d.

Note: we need this theorem.

• I have just read that you can't use CBS... – ajotatxe Oct 15 '14 at 12:46

you can think of it like this, a function is defined by for each X there is only 1 Y, and both of these functions have the same domains(same in the domain cardinality), the set of all positive integers. in function 1 each positive integer is mapped to another positive integer and for the second each positive integer is mapped to either 1 or 0, however for each element in the domain there can only be one value of Y, so there is one mapping of X -> Y per X(element of the domain) and as the domains are the same it follows the n

Let $$B_0=\{f\in B:\exists n[n\in\Bbb Z^+\wedge\forall m((m\in\Bbb Z^+\wedge m>n)\to f(m)=f(n))]\}$$

Informally, this is the set of the functions of $B$ that are constant from great enough integers, they are all $0$ or all $1$ form some point. This set is countable. If we consider the sequences of zeroes and ones as binary digits (preceeded by '$0.$') this is the set of rational numbers in $[0,1]$. Let $C_1$ the functions $f\in B-B_0$ such that $f(1)=1$. It is clear that $C_1$ and $C_0=B-B_0-C$ have the same cardinality.

Now, define $\sigma:C_1\to A$ as follows:

• $\sigma_f(1)$ is the number of consectutive $1$'s at the beginning.
• $\sigma_f(2)$ is the number of the next consecutive $0$'s
• $\sigma_f(3)$ is the number of the next consecutive $1$'s
• ...

This define a bijection between $C_1$ and $A$.

Since $B=B_0\sqcup C_0 \sqcup C_1$, $A$ and $B$ have the same cardinality, too (this last step assumes the axiom of choice).

$A =$ {$f|f:\mathbb{Z}^{+} \to \mathbb{Z}^{+}$} and $B =${$f|f:\mathbb{Z}^{+} \to \{0,1\}$}

Assert that (1) $|B|$ = $|P(\mathbb{Z}^{+})|$ and (2) $|A|$ = $|P(\mathbb{Z}^{+})|$ and therefore $|A|$ = $|B|$. Proof...

(1) for each $f \in B$ there corresponds a subset of $\mathbb{Z}^{+}$, $\mathbb{Z}_f$ defined by $\mathbb{Z}_f =$ {$z \in \mathbb{Z}^{+} | f(z) = 1$} so there is a bijection between $A$ and $P(\mathbb{Z}^{+})$ and hence $|B|$ = $|P(\mathbb{Z}^{+})|$.

Note for use in (2) that the same proof applies to a set $C$ defined by $C =${$f|f:\mathbb{Z}^{+} \to \{1,2\}$}, and that $C \subset A$, so that $|C| = |P(\mathbb{Z}^{+})| \le |A|$

(2) the set of functions $A$ is a subset of all possible ordered pairs in $\mathbb{Z}^{+}$ X $\mathbb{Z}^{+}$, so that $|A| \le |P(\mathbb{Z}^{+}$ X $\mathbb{Z}^{+})|$, but (a result that is well known), $|P(\mathbb{Z}^{+}$ X $\mathbb{Z}^{+})| = |P(\mathbb{Z}^{+})|$ so that $|A| \le |P(\mathbb{Z}^{+})|$, and we just proved that $|P(\mathbb{Z}^{+})| \le |A|$ so $|A| = |P(\mathbb{Z}^{+})|$