# Bijection for a power set function

## 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
Staff Emeritus
Homework Helper
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?

Yes but for part b)I have no ideea

micromass
Staff Emeritus
Homework Helper
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\}$$

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
Staff Emeritus
Homework Helper
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.

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

micromass
Staff Emeritus