Bijection for a power set function

[Stephen88]

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)

 

[micromass]

OK, so for a you must show both injectivity and surjectivity

For injectivity: You must show that if $\mathbb{N}\setminus A=\mathbb{N}\setminus B$, then A=B

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

Do you agree that this is what you need to show?

 

[Stephen88]

Yes but for part b)I have no ideea

 

[micromass]

Well, for part (b) you must show first that the bijection restricts to

$$f:\{A\subseteq N~\vert~|A|=k\}\rightarrow \{A\subseteq N~\vert~|A|=n-k\}$$

 

[Stephen88]

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?

 

[micromass]

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.

 

[Stephen88]

Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?

 

[micromass]

Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?

Yes, certainly! That's ok!

 

[Stephen88]

Thank you