“Casual Thinking and Hardcore Drinking”

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.

Cantor-Bernstein-Schroeder Theorem: 

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 → 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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s