- #1

- 11

- 0

The theorem:

If there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B.

My proof of an equivalent statement-

If there exist injective functions f : A → B and g : B → A between the sets A and B, then f is surjective.

By contradiction:

f is not surjective. Then there exists a b [itex]\in[/itex] B, such that b [itex]\notin[/itex] f(A).

Let C be the set of g({ f(A) [itex]\bigcup[/itex] b }). Then C [itex]\subseteq[/itex] A, and f(A) [itex]\subset[/itex] g^-1(C). Because both C and g^-1(C) contain the same amount of elements (because g is injective), from f(A) [itex]\subset[/itex] g^-1(C) we get A [itex]\subset[/itex] C, which is a contradiction with C [itex]\subseteq[/itex] A.