0
$\begingroup$

So, I am going through David Mazur’s Combinatorics: A Guided Tour and I came across this exercise question:

Give a bijective proof: The number of subsets of [n] equals the number of n-digit binary numbers.

So, I know how to go about the proof - create two sets and a function to map between them, then prove that the function is bijective and then use the bijective principle to show that the two sets have the number of elements.

The part I am having trouble with is defining a function between the two sets.

Suppose A is the set of all subsets on [n] and B is the set of all n-digit binaries. Then I define f:A->B but by what relationship?

If anyone could point me toward how to think through this function definition it would be of great help! Thanks in advance :)

$\endgroup$
3
  • 2
    $\begingroup$ Hint: What if you mark with a $1$ in the $i-$th position of the string if and only if $i$ is in the set that you are looking at? $\endgroup$
    – Phicar
    Jun 8, 2020 at 23:08
  • $\begingroup$ @Phicar sorry I don’t understand the formatting you used. What does $1$ mean? $\endgroup$ Jun 8, 2020 at 23:31
  • $\begingroup$ $1$ is a symbol from $\{0,1\}$ the alphabet of the binary numbers. $\endgroup$
    – Phicar
    Jun 9, 2020 at 0:48

2 Answers 2

1
$\begingroup$

Well, how many $n$ digit binary numbers are there? $2^n$.

How do you know? Well, each digit place we have two choices, $0$ or $1$. So for $n$ places each with $2$ choices we have $2^n$ choices.

How many subset of $[n]$ are there? $2^n$.

How do you know? Well, well when creating a subset of $[n]$ we have a choice to make for each element $[n]$; we can choose to put it in the subset we are creating or to leave it out. For each element there are $2$ choose and there are $n$ chooses to make so there are $2^n$ possible ways of making the choices and each one creates a unique subset

......

Okay, so "making" a binary number and "making" a subset you make a series of binary choices. So we ought to be able to make bijection by matching up every choice we made for a string with a choice we made for a set:

$f:$ strings to $P([n])$ via $f(string)=$ the set where for every place value, $k$ that has a $1$ the set $f(string)$ will contain $k$ as an element and for every place value, $j$ that has a $0$ the set $f(string)$ will not contain $j$ as an element.

......

That ought to do it and it "obvious and clear to a dope it must be bijective" because... well, every thing we do to make a string is perfectly matched to everything we do to make a set.

But..... there's not a math teach in the world who will accept something that informal.

......

But if we represent a string as $s=[s_1,s_2,s_3......,s_n]$ where each $s_i$ is either $0$ or $1$ then we want the set of indexes $k$ where $s_k = 1$ or in other words:

$f([s_1,s_2,s_3......,s_n]) = \{k| s_k = 1\}$

I'll leave it to you to prove formally it is a bijection.

$\endgroup$
1
  • $\begingroup$ Thanks so much!! This makes perfect sense $\endgroup$ Jun 8, 2020 at 23:41
0
$\begingroup$

I'd also prove this via the bijective map approach. Along those lines --

Hint: Look at some smaller cases, say, {1, 2} or {1, 2, 3}, and take their power set. Observe how many subsets there are in such cases; i.e., how many sets are in the power set of [n] vs. how many n-digit bitstrings are there? Can you think of a way you can map from these subsets to appropriate n-digit binaries?

$\endgroup$
1
  • $\begingroup$ Well that’s the exact part I’m having trouble with. I have tried to find a way to map these subsets to the n digit binary but nothing I come up with seems to make sense $\endgroup$ Jun 8, 2020 at 23:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .