Cardinality of sets of functions

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

$ 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}^{+})| $