Let $A,B$ be some sets such that $|A|=a, |B|=b$. Prove $\binom{a}{b}=|P_b(A)|$ is a well defined expression.

Question

Let $A,B$ be some sets such that $|A|=a, |B|=b$. Prove $\binom{a}{b}=|P_b(A)|$(=the set of all subsets of A of cardinality $b$) is a well defined expression.

Hello all. In this question I need to show that the equality $\binom{a}{b}=|P_b(A)|$ holds for all sets $A\neq A' \land |A|=|A'|=a, B\neq B'\land |B|=|B'|=b $. I don't really know how to show it, I thought about doing some tricks with the binomial theorem but I guess it has nothing to do with that. Would love to get your help... thanks in advance :)

Answer 1

I think that what is meant is something closer to the following:

Suppose that $A$ and $A'$ have the same cardinality and $B$ and $B'$ have the same cardinality.

I'm going to change your notation slightly and try to define $$ \binom{a}{b}=\left|P_B(A)\right| $$ where $P_B(A)$ is the set of all subsets of $A$ whose cardinality is the same as $B$.

The goal is to show that $$\left|P_B(A)\right|=\left|P_{B'}(A')\right|.$$

Since $A$ and $A'$ have the same cardinality, there is some bijection $f:A\rightarrow A'$. Similarly, there is a bijection $g:B\rightarrow B'$.

To show that this notion is well-defined, we construct a bijection between $P_B(A)$ and $P_{B'}(A')$. Suppose that $C$ is a subset of $A$ with the same cardinality as $B$. Then, we show the following:

• $f(C)$ is a subset of $A'$.

• $f(C)$ has the same cardinality as $C$.

• If $f(C)=f(C')$ then $C=C'$ (injectivity).

The first statement is easy to prove since $f(C)=\{f(c):c\in C\}$ and the codomain of $f$ is $A'$, so $f(c)\in A'$.

Since $f$ is a bijection, the restriction of $f$ to $C$, denoted $f|_C$, is also a bijection onto its image. In fact, $f|_C$ is injective because $f$ is injective (skipping details). On the other hand, maps are always surjective onto their images. Therefore $f|_C:C\rightarrow f(C)$ is a bijection, since $B$ and $B'$ have the same cardinality, if $f(C)$ and $B'$ have the same cardinality if and only if $C$ and $B$ have the same cardinality.

Finally, we need to show injectivity. If $C\not=C'$, then there is some $x\in C\setminus C'$ (or vice versa). Due to injectivity of $f$, $f(x)\in f(C)$ but $f(x)\not\in f(C')$ (skipping details). Therefore, we have an injective map from subsets of $A$ of cardinality equal to that of $B$ to subsets of $A'$ with cardinality equal to that of $B'$.

By inserting the details and using that the argument for $f^{-1}$ is identical, you get that the identification is well-defined.

Answer 2

Using binomial theorem could work. You could also consider the "definition" (or interpretation) of the number $\binom{a}{b}$:

$\binom{a}{b}$ is the number of ways to choose $b$ elements from a set with $a$ elements.

This is, in a very literal sense, the number of subsets of size $b$ from a set of size $a$. This is clear if you are willing to accept this interpretation of the binomial coefficient.

On the other hand, if you want to prove it completely what you would need to show is basically that the binomial coefficient represents what it says it does: the number of subsets of size $b$ from a set of size $a$. This is a standard reasoning when you're first introduced to the binomial coefficient, and the approach is something as follows (try to think about it first, put the pointer on the space below if you need help):

To choose $b$ elements out of a set of $a$ elements, first we determine which elements will we choose, in order (i.e. which is the first, which is the second, and so on). For this we have $n\cdot (n-1)\cdots (n-r+1)$ possibilities. Now, since the order doesn't really matter when it comes to choosing a subset, we have to divide by the number of permutations of $r$ elements, which is $r!$. The result is $\frac{n\cdot (n-1)\cdots (n-r+1)}{r!}$, which is the binomial coefficient $\binom{a}{b}$.