Combinatorics: Understanding proofs involving the bijective principle(BP)

Question

When we are trying to prove a statement using the bijective principle, it is clear that the goal is show that two sets are equivalent in cardinality. The following proof of example 1.5.3 starts with two sets A and B where A resembles the set from the proposition and set B contains r-combinations of Y, where the cardinality of Y will be n-r+1 choose r. So it seems we want to relate sets A and B by some bijective function, hence showing that |A| = |B|. It then follows that |A| is equal to n-r+1 choose r.

I believe I have a good understanding of this proof, however the action of creating a function for the proof seems strange. Some questions I have are:

1. If we were unable to find a function that relates these two sets bijectively, then does it follow that the proposition must be false?

2. Is there more than one possible way to create a bijective function within a proof?

3. Is the creation of the function that maps A to B (whether it be bijective, injective or surjective depending on what you are proving) that is really the key to the proof? In general, are there instances were two seemingly unrelated sets can be connected by the creation of some mapping function and then used to prove some proposition?

Answer 1

1. No, being unable to find it never proves the nonexistence of it. However, if you can prove there does not exist a bijection, then you can prove that the two sets have different cardinality.

2. Yes, unless you're dealing with sets of size $0$ or $1$, you can find a different bijection simply by swapping two values around. For example, if $x\neq x'$ and $f(x)=y$ and $f(x')=y'$, then the function $g$ such that $g(x)=y'$ and $g(x')=y$ and $g(z)=f(z)$ for all $z\neq x,x'$ is also a bijection.

3. It is, since cardinality is defined in terms of function mappings: $A$ and $B$ have the same cardinality $|A|=|B|$, when there exists a bijection $A\to B$. There is however an easier way to show equality of cardinality: if we have injective functions $A\to B$ and $B\to A$, then $|A|=|B|$ (this is known as the Cantor-Schröder-Bernstein Theorem). So instead of a bijection, we could give two injections as well.

Answer 2

Q: If we were unable to find a function that relates these two sets bijectively, then does it follow that the proposition must be false?

A: No, it doesn't. If you cannot find a function it doesn't mean there are no such functions. Maybe they're just too difficult to find.

Q: Is there more than one possible way to create a bijective function within a proof?

Absolutely, if sets $A$ and $B$ are both of cardinality say $n$, then there are $n!$ bijective functions that you can use for the proof by bijection.

Q: Is the creation of the function that maps A to B (whether it be bijective, injective or surjective depending on what you are proving) that is really the key to the proof?

If you are using bijections in your proof then you must use bijective mappings in general. The key is finding another set:

1. that you can find a bijection with (not injections or surjection)
2. that is easily countable

If you find a trivial bijection between the set in question and another set, then it might not be easy to enumerate the second set which is eventually of no use.

Q: In general, are there instances were two seemingly unrelated sets can be connected by the creation of some mapping function and then used to prove some proposition?

Unrelated sets can be mapped to each other bijectively only if they are of same cardinality. Even then, finding a useful mapping might not be trivial.