Proving $\binom{n}{k}=\binom{n}{n-k}$ using set theory?

Question

Let $N$ be a set of $n$ items. Define a grouping to be some subset of $N$.

Let $A$ be the set of all groupings of $k$ items from $N$.

Let $B$ be the set of all groupings of $n-k$ items from $N$.

Namely, if $|A|=|B|$ then we have $\binom{n}{k}=\binom{n}{n-k}$.

For $|A|=|B|$, we must have there exists a bijection from $A$ to $B$. Let us define a function $f:A \rightarrow B$ such that $f(a)=b$ if $a \cup b = N$

We first show $f$ is injective. Take $a_1,a_2 \in A$ and assume $f(a_1)=f(a_2)=b$. This means $a_1 \cup b = N = a_2 \cup b$, i.e. $a_1=a_2=N-b$. So, $f$ is injective.

We now show $f$ is surjective. Take $b \in B$ and consider $a=N-b$. Since $|N-b|=n-(n-k)=k$, we have $|a|=k$ so $a \in A$. We note $f(a)=b$ because $a\cup b=(N-b)\cup b=b$.

Since $f$ is injective and surjective, it is bijective. So $|A|=|B|$, and as such we have $\binom{n}{k}=\binom{n}{n-k}$ QED.

Is this proof correct?

Answer 1

The problem in this proof is with the definition of $f(a)$:

$f(a)=b$ if $a \cup b = N$

However, how do we even know that such a $b\in B$ exists? The fact that this function is well-defined must be proven rigorously. Therefore, I think this alternative definition would be better:

$f(a)=b$ if $b=N-a$

Now, we will prove $b=N-a \in B$: Since $a\in A$, we know that $|a|=k$. Furthermore, it is given that $|N|=n$. Therefore, since $a$ and $N$ are finite sets, $|N-a|=|N|-|a|=n-k$. Thus, $|b|=|N-a|=n-k$, so $b \in B$. This proves that $f(a)=N-a$ is a well-defined function from $A$ to $B$.

Using this new definition, I will now modify your proof as follows:

We first show $f$ is injective. Take $a_1,a_2 \in A$ and assume $f(a_1)=f(a_2)=b$. This means $b=N-a_1$ and $b=N-a_2$. Thus, $a_1=N-b$ and $a_2=N-b$. Therefore, $a_1=a_2=N-b$. So, $f$ is injective.

We now show $f$ is surjective. Take $b \in B$ and consider $a=N-b$. Since $|N-b|=n-(n-k)=k$, we have $|a|=k$ so $a \in A$. We note $f(a)=b$ because $a=N-b$ implies $b=N-a$.