# Bijection for a power set function

1. Aug 20, 2011

### Stephen88

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

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. Aug 20, 2011

### 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?

3. Aug 20, 2011

### Stephen88

Yes but for part b)I have no ideea

4. Aug 20, 2011

### 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\}$$

5. Aug 20, 2011

### 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?

6. Aug 20, 2011

### micromass

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.

7. Aug 20, 2011

### Stephen88

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

8. Aug 20, 2011

### micromass

Yes, certainly!! That's ok!

9. Aug 20, 2011

Thank you