The above quote is one of the many reasons I love FOM/Casey. Anyways, Casey wanted us to work on proving a theorem as part of our homework this weekend, and I am 75% I figured it out last night.
If ∃ injective functions f : A → B and g : B → A, then ∃ a bijection b: A → B.
Okay, so first of all we’re assuming that those two injections exist, and we’re trying to prove that those two injections mean that a bijection exists.
For f : A → B to exist, there must be at least as many outputs as there are inputs so that f(a)=f(b) ⇒ a=b can be true. If there were more inputs than there were outputs, every input would not have a unique output, and would therefore not be an injection. So, based on this |A| ≥ |B|.
But, there exists another injection g:B → A, which means that |B|≥|A| based on the same reasoning above.
For both of these functions to be injective, we need to combine |A|≥|B| and |B|≥|A|, which means that only way both injections could be true is if |A| = |B|.
For a function to be bijective in between two sets, they have to satisfy onto and one-to-one. For one-to-one, as said before, there needs to be at least as many inputs as outputs. There can be more outputs not mapped to with injectivity. But with onto, all outputs must be mapped to, so there must be at least as many inputs for all outputs. This means that for a bijection to exist, |A| must equal |B|.
Hey! We just proved that it does if there are two injections in existence!
I think this proves this, right? Word. Happy Saturday ya’ll.