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
    Also $\mathbb R_{++}$ is object-oriented $\mathbb R$2012-09-03