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 $\displaystyle \{0,1,2,3,\dots\}$ and $\displaystyle \{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 $\displaystyle \{0,1\}^{\mathbb{N}}$ is a function $\displaystyle f:\mathbb{N}\to\{0,1\}$. Equivalently, it is an infinite sequence of 0's and 1's: $\displaystyle f(0), f(1), f(2),$...

Given a set $\displaystyle A\subseteq\mathbb{N}$, consider the so-called characteristic function of $\displaystyle A$. This function equals 1 on elements of $\displaystyle 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 $\displaystyle \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 $\displaystyle A\in \mathcal{P}(\mathbb{N})$ then define the indicator function $\displaystyle 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 $\displaystyle \left( {\forall A \in \mathcal{P}(\mathbb{N})} \right)\left[ {I_A \in \{ 0,1\} ^{\mathbb{N}} } \right]$.

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