Mathematics 243 – Mathematical Structures A “bijective proof” that {1, 2, …, n} has 2^{n} subsets September 27, 2017

Background

Recall that a couple of days ago we showed by mathematical induction that for all n ≥ 1, {1, 2, …, n} has 2^{n} subsets. Today we want to see an explicit bijection between the subsets and a set of 2^{n} integer values, so we can see that we are directly “counting the subsets.” It will show the same result we already know, but by a different method that does not use induction. Mathematicians often look for different proofs of results because having more than one way to prove something often reveals interesting connections or relationships that might not be visible otherwise! The sort of proof we will see in this discussion is called a bijective proof in the area of mathematics known as combinatorics – the subject of the MATH 357 course offered every other year in the mathematics major here.

Questions

(A) To study subsets of {1, 2, …, n}, with enough thought, you might come up with an idea like this: Every subset S can be described by giving a vector v_{S} = (v_{1}, v_{2}, …, v_{n}) where for each i, 1 ≤ i ≤ n,

v_{i} = \{ \begin{matrix}1 & if i ∈ S \\ 0 & if i ∉ S \end{matrix}

(You might also think 1 = “true” and 0 = “false” for the truth value of the statement i ∈ S.) Write out the 8 subsets S of {1, 2, 3} and their corresponding vectors v_{S}.

(B) Let S be the set of all subsets of {1, 2, …, n} and Let V be the set of all length-n vectors with entries either 0 or 1. Prove that the mapping V : S → V defined by V (S) = v_{S} is a bijection (injective and surjective).

(C) How many possible length-n vectors with all entries 0 and 1 are there? (For now, just

“figure out” what the answer should be. We’ll sketch a possible proof next.) (D) Here’s a way to “count” the set V that you might not have thought of. For each vector

v = (v_{1}, …, v_{n}) ∈ V, define an integer N(v) by the rule

N(v) = v_{1} + v_{2} · 2 + v_{3} · 2^{2} + ⋯ + v_{n}2^{n−1}

What are the N(v_{S}) for the 8 vectors you found in part (A)? (E) The mapping N : V → N defined by the formula in part B defines a bijection between

V and the subset {0, 1, …, 2^{n} − 1} in N. Explain why using the notion of the base-2 or binary representation of integers. If you have not seen this before, look it up online to see the idea (the Wikipedia article “Binary Number” is a good source). Explain this in your own words.

(F) To wrap things up, notice we have a bijection between the subsets S and the vectors V given by part (B). Then, in turn, there is a bijection between V and the set {0, 1, …, 2^{n}−1} given by part (E). Explain why this shows there is a bijection between S and the set {0, 1, …, 2^{n} − 1}. (Hint: Think composition of functions.)