Bijection for a power set function

In summary, the power set of N is 2^n and a bijection is a one-to-one function that is both injective and surjective. Additionally, |N\A|=n-|A| where | | represents the number of elements in a set.
  • #1
Stephen88
61
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)
 
Physics news on Phys.org
  • #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?
 
  • #3
Yes but for part b)I have no ideea :frown:
 
  • #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]
 
  • #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?
 
  • #6
Stephen88 said:
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
Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?
 
  • #8
Stephen88 said:
Cand I do something like this? B=N\A=> N\B=N\(N\A)=>N\B=A?

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

1. What is a bijection for a power set function?

A bijection for a power set function is a function that maps each element in a set to a unique subset of that set. In other words, every element in the set is paired with a different subset of the set, and every subset of the set is paired with a different element in the set.

2. What is the purpose of a bijection for a power set function?

The purpose of a bijection for a power set function is to establish a one-to-one correspondence between a set and its power set. This allows us to compare the size of a set to the size of its power set, and also provides a way to generate all possible subsets of a given set.

3. How is a bijection for a power set function defined?

A bijection for a power set function is defined as a function that takes in an element from a set and maps it to a subset of that set. This function must be both injective (or one-to-one) and surjective (or onto), meaning that each element in the set is mapped to a unique subset, and every subset of the set is mapped to by at least one element.

4. What is an example of a bijection for a power set function?

An example of a bijection for a power set function is the function f: {1, 2, 3} → {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, where each element in the set {1, 2, 3} is mapped to a unique subset of the set.

5. How is a bijection for a power set function useful in mathematics and computer science?

In mathematics and computer science, a bijection for a power set function is useful for counting the number of elements in a set and its power set, as well as for solving problems involving combinations and permutations. It is also used in algorithms and data structures for efficient storage and retrieval of subsets of a set.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
4
Views
460
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
4
Views
898
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
950
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
Back
Top