Schroeder–Bernstein Theorem

Premise:

1. Function f :A → B is into.

2. Function g : B → A is also into.

To prove:

There exists a Bijective function h : A → B i.e. A ~ B.

Intuition:

We look at f ∘ g : B → B that is either identity function or form a circular chain among y ∈ B, and we will use this intuition as a intermediary step or Lemma.

Lemma:

f ∘ g relation is made of types of relationships, circular chains and identities.

Relations in the Chain section of f ∘ g must map to a different element in B (Thus, forming a cirlce) because, otherwise, it would contradict the into-ness of f. If it maps onto itself, then it is not a part of any chain but an identity relationship.

Proof:

Suppose f is not onto.

Thus, B has loner member y0 where no x ∈ A maps to y ∈ B.

This means that y0 is neither in the chain section or identity section of the relationships which contradicts with the lemma, and therefore making f both onto and into function to make A~B.

QED