Bijection for a power set function

  • Thread starter Stephen88
  • Start date
  • #1
33
0

Homework Statement



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.
b)C(n,k)=C(n,n-k).



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)
 

Answers and Replies

  • #2
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
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?
 
  • #3
33
0
Yes but for part b)I have no ideea :frown:
 
  • #4
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
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]
 
  • #5
33
0
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?
 
  • #6
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
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

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?

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?

The rest looks ok.
 
  • #7
33
0
Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?
 
  • #8
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?

Yes, certainly!! That's ok!
 
  • #9
33
0
Thank you
 

Related Threads on Bijection for a power set function

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
997
  • Last Post
Replies
2
Views
798
  • Last Post
Replies
4
Views
927
  • Last Post
Replies
2
Views
925
Replies
4
Views
4K
Top