Cantor bernstein theorem


by pk1234
Tags: bernstein, cantor, theorem
pk1234
pk1234 is offline
#1
Jan31-13, 02:25 AM
P: 11
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.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
jgens
jgens is offline
#2
Jan31-13, 10:26 AM
P: 1,623
Quote Quote by pk1234 View Post
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.
pk1234
pk1234 is offline
#3
Jan31-13, 11:07 AM
P: 11
Thanks!


Register to reply

Related Discussions
Are the following 3 statements true and does the cantor-bernstein theorem follow Set Theory, Logic, Probability, Statistics 4
Cantor-schroder-bernstein use in proof Calculus & Beyond Homework 6
Which axioms of ZF are needed for Cantor's theorem? Set Theory, Logic, Probability, Statistics 2
help with Cantor-Schroder-Berstein theorem please! Set Theory, Logic, Probability, Statistics 1