Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is an extension of my last question I guess. If I'm not following protocol in that regard I sincerely apologize!

Basically, I'm considering the set of all functions from the positive integers to itself, and the set of all functions from the positive integers to the set {0,1}. I want to show that they have the same cardinality, but wanting to show it isn't helping me do it! One injection is simple inclusion, but I can't find the other. Any tips/hints?

share|cite|improve this question
up vote 3 down vote accepted

Explicit injections are overrated. You actually have the knowledge to finish on your own, without writing this injection...

You already know that every function from $\mathbb Z^+$ to itself is a subset of the countable set $\mathbb Z^+\times\mathbb Z^+$. In particular this means that the collection of all functions from the positive integers to itself is a subset of $\mathcal P(\mathbb{Z^+\times Z^+})$.

Now you can use the fact that $\mathbb{|Z^+\times Z^+|=|Z^+|}$ and conclude that the power sets are equipotent, and therefore $\left|2^{\mathbb Z^+}\right|=\left|\mathbb{\left(Z^+\right)^{Z^+}}\right|$, as wanted.

If you still insist on finding this injection, let $\varphi\colon\mathbb{Z^+\times Z^+\to Z^+}$ be a bijection.

Now map $f\colon\mathbb Z^+\to\mathbb Z^+$ to the following function $G_f\colon\mathbb Z^+\to\{0,1\}$: $$G_f(\varphi(a,b))=1\iff (a,b)\in f$$

Show that $G_f$ is an injective function, it's not too hard but requires some element chasing and bookkeeping.

share|cite|improve this answer
Hmm, I'm having a bit of trouble filling in the logic that connects the first part of your last sentence to the stuff after the "therefore." (after your edit, it's a middle sentence.) – AsinglePANCAKE Sep 3 '12 at 0:18
@AsinglePANCAKE: The set of all functions is a subset of the power set of a countable set. Therefore its cardinality is less or equal to that of $\mathcal P(\mathbb Z^+)$. On the other hand it is not smaller since, as you pointed out, we have the obvious inclusion. Therefore equality ensues. – Asaf Karagila Sep 3 '12 at 0:21
Wait, so you're saying that the power set of Z+ and the set of all functions from Z+ to {0,1} are the same thing? – AsinglePANCAKE Sep 3 '12 at 0:31
@AsinglePANCAKE: Yes. The bijection between them is easy to achieve: characteristic functions. $A\mapsto \chi_A$, where $\chi_A(x)=1\iff x\in A$. – Asaf Karagila Sep 3 '12 at 0:37
Thanks! Literally just proved the bijection a few seconds before you answered. – AsinglePANCAKE Sep 3 '12 at 0:39

Your Answer


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.