1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bijection for a power set function

  1. Aug 20, 2011 #1
    1. The problem statement, all variables and given/known data

    Let N={1,2.....n} .Define the Power set of N,P(N).
    a) show that the map f:P(N)->P(N)
    defined by taking A to belong to P(N) to N\A is a bijection.

    3. The attempt at a solution
    Now the power set is defined by P(N)=2^n and a bijection is a one-to-one function that is both injective and surjective . The domain and range have the same cardinality since we are using the power set of N.and f:N->N is bijective maybe a logical consequence will be that f:P(N)->P(N) is also bijective
    Also |N\A|=n-|A| where | | represents the number of elements in a set.
    Ineed help in solving a ) and b)
  2. jcsd
  3. Aug 20, 2011 #2
    OK, so for a you must show both injectivity and surjectivity

    For injectivity: You must show that if [itex]\mathbb{N}\setminus A=\mathbb{N}\setminus B[/itex], then A=B

    For surjectivity, you must show that for all [itex]A\subseteq \mathbb{N}[/itex], there is a [itex]B\in \mathbb{N}[/itex] such that [itex]\mathbb{N}\setminus B=A[/itex].

    Do you agree that this is what you need to show?
  4. Aug 20, 2011 #3
    Yes but for part b)I have no ideea :frown:
  5. Aug 20, 2011 #4
    Well, for part (b) you must show first that the bijection restricts to

    [tex]f:\{A\subseteq N~\vert~|A|=k\}\rightarrow \{A\subseteq N~\vert~|A|=n-k\}[/tex]
  6. Aug 20, 2011 #5
    We assume that N \ A = N \ B. We show A=B by showing that A ⊆ B and also B ⊆ A. To prove A ⊆ B, let x be an element of A. Then x is not an element of N \ A, and thus x is not an element of N \ B. Thus x is in B. (Showing B ⊆ A is similar.)

    For surjectivity: Let B = N \ A.=> |B|=n-|A|=>|A|=n-|B|=>A=N\B

    For part b)Using par a) we see that and restricting the doman of F to k elements then the image under this function F will be n-k since again the function is defined on N\A.

    Is this ok?
  7. Aug 20, 2011 #6
    Well, B=N\A is the right thing to choose. But saying |A|=n-|B| doesn't necessarily imply A=N/B.
    Can you prove directly that B=N\A implies A=N\A?

    The rest looks ok.
  8. Aug 20, 2011 #7
    Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?
  9. Aug 20, 2011 #8
    Yes, certainly!! That's ok!
  10. Aug 20, 2011 #9
    Thank you
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook