1. ## equivalence functions

Hi,
Can i get an example for equivalence function (bijection) between those sets?

a) K, N. N is the set of natural numbers, and K is the set of natural numbers which are power of 2.

b) p(N), {0, 1}^N. p(N) is, of course, the power set of N.

Thanks for any kind of help

2. K, N. N is the set of natural numbers, and K is the set of natural numbers which are power of 2.
Well, what would you say is a bijection between $\{0,1,2,3,\dots\}$ and $\{2^0,2^1,2^3,\dots\}$?

p(N), {0, 1}^N. p(N) is, of course, the power set of N.
An element of $\{0,1\}^{\mathbb{N}}$ is a function $f:\mathbb{N}\to\{0,1\}$. Equivalently, it is an infinite sequence of 0's and 1's: $f(0), f(1), f(2),$...

Given a set $A\subseteq\mathbb{N}$, consider the so-called characteristic function of $A$. This function equals 1 on elements of $A$ and equals 0 otherwise. A set and its characteristic function are basically the same thing in the sense that one can be unambiguously reconstructed from the other.

This is true not only for $\mathbb{N}$ but for any set, finite or infinite.

3. Originally Posted by rebecca
Can i get an example for equivalence function (bijection) between those sets?
b) p(N), {0, 1}^N.
If $A\in \mathcal{P}(\mathbb{N})$ then define the indicator function $
I_A :\mathbb{N} \mapsto \{ 0,1\} \;,\,I_A (n) = \left\{ {\begin{array}{rl}
1 & {,\,n \in A} \\ 0 & {,\,n \notin A} \\ \end{array} } \right.$
.

You must show that $\left( {\forall A \in \mathcal{P}(\mathbb{N})} \right)\left[ {I_A \in \{ 0,1\} ^{\mathbb{N}} } \right]$.

Then show that $\Phi : \mathcal{P}(\mathbb{N}) \mapsto \{ 0,1\} ^\mathbb{N} \;,\,\Phi (A) = I_A$ is a bijection.