1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cantor bernstein theorem

  1. Jan 31, 2013 #1
    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.
  2. jcsd
  3. Jan 31, 2013 #2


    User Avatar
    Gold Member

    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.
  4. Jan 31, 2013 #3
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Cantor bernstein theorem
  1. Cantor's comb (Replies: 5)

  2. Cantor's alpha one (Replies: 10)