2
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    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.)2012-09-03
  • 0
    @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.2012-09-03
  • 0
    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?2012-09-03
  • 0
    @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$.2012-09-03
  • 0
    Thanks! Literally just proved the bijection a few seconds before you answered.2012-09-03
  • 0
    Also $\mathbb R_{++}$ is object-oriented $\mathbb R$2012-09-03