Today I Learned

Some of the things I've learned every day since Oct 10, 2016

2: Corrolaries to the Cantor-Schröder-Bernstein Theorem

Given two sets A, B, there exists an injection F: A \rightarrow B if and only if there exists a surjection G: B \rightarrow A. This can easily be proved in a constructive manner.

Given this, the Cantor-Schröder-Bernstein Theorem — which states that there exists a bijection between two sets A,B if and only if there exist mutually bijective functions F: A \rightarrow B, G: B \rightarrow A — has a couple obvious corrolaries:

  • There exists a bijection between two sets A,B if and only if there exist mutually surjective functions F: A \rightarrow B, G: B \rightarrow A. (In terms of cardinality: |A| = |B| iff |A| \geq |B| and |B| \geq |A|.)
  • There exists a bijection between two sets A,B if and only if there exists an injective function F: A \rightarrow B as well as a surjective function G: A \rightarrow B. (In terms of cardinality, |A| = |B| iff |A| \geq |B| and |A| \leq |B|.)
Advertisements

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

%d bloggers like this: