Results 1 to 3 of 3

Thread: equivalence functions

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    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
    Last edited by Plato; Dec 8th 2009 at 01:35 PM. Reason: Change font.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,796
    Thanks
    2827
    Awards
    1
    Quote Originally Posted by rebecca View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence relation and Functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 4th 2011, 12:08 PM
  2. Equivalence relation and Functions
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Dec 1st 2010, 07:36 PM
  3. equivalence relations and functions
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 25th 2010, 01:31 AM
  4. Equivalence Relations and Functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 18th 2009, 04:34 AM
  5. Equivalence Relations and Functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 15th 2009, 11:48 PM

Search Tags


/mathhelpforum @mathhelpforum