Cantor bernstein theorem

  • Thread starter pk1234
  • Start date
  • #1
11
0
Hi guys, I've got some problems with the cantor bernstein theorem. I'm having a hard time with all the proofs I've found, but I've actually come up with a proof myself... it will be no doubt wrong in some part though, so it would be great if you could check it for me and tell me what's wrong with the simple idea I came up with.

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.
 

Answers and Replies

  • #2
jgens
Gold Member
1,581
50
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.
That is not an equivalent statement. Let [itex]f:\mathbb{N} \rightarrow \mathbb{Z}[/itex] be the inclusion and define the map [itex]g:\mathbb{Z} \rightarrow \mathbb{N}[/itex] by setting [itex]g(n) = 3|n| + \mathrm{sgn}(n)[/itex]. Both of these maps are injections, but neither of them is a surjection.
 
  • #3
11
0
Thanks!
 

Related Threads on Cantor bernstein theorem

  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
17
Views
5K
Replies
22
Views
1K
Replies
4
Views
2K
Replies
19
Views
870
Replies
36
Views
8K
Replies
29
Views
2K
Top