Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Who is Schroder Bernstein?

  1. Mar 2, 2004 #1
    Do any one know about this Schroder-Bernstein theorem?

    Who is this person?

    Where was this theorem originally proved?

    The theorem says as long as there is a one-to-one map from X to Y and a one-to-one map from Y to X, there will be a one-to-one and onto map from X to Y.

    I see somethings wrong in this theorem. I have seen two different proofs; bothe of them embeded with logic errors.

    The theorem is published in many discreet math. book. I can't see how you can make a one-to-one and onto map from [-1,1] to (-1,1), but it's very easy to make a one-to-one map from one to another in this case.
     
  2. jcsd
  3. Mar 2, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Friedrich Schroeder and Felix Bernstein, mathematicians who gave the first proof of this result.

    One proof is very nice, involving 'chains'. If i need to i'll write it out for you.

    I think the reason why you can't see a bijection between (0,1) and[0,1] is because you are looking for a continuous one, and obviously that can't happen.


    Here's a bijection. Let x_i be any countable sequence of distinct elements of (0,1); define a map from [0,1] to (0,1) by

    0-->x_1

    1--->x_2

    x_i--->x_{i+2}

    x---> x other wise

    a clear bijection.
     
  4. Mar 2, 2004 #3
    Matt, Thanks. Good example.

    All the proofs I have thought are falwed. Do you know where I can find a good proof?
     
  5. Mar 2, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    here's the proof from the book (cohen)

    assume M and N are disjoint sets and there injections f and g from M to N and N to M resp.

    let m be in M, consider the images under repeatedly applying f then g then f...

    case 1. eventually we hit m again and have a loop

    case 2. this continues indefinitely with no looping at all.

    in case 2 find preimages, when they exist and get a chain goin backwards

    a. this carries on indefinitely and we have a double infinite chain


    b it stops with an element of M having no preimage

    c it stops at an element of N having no preimage.


    thus there exactly 4 types of chain, and every element in M and N lies in exactly one of these types of chains.

    we can now define a bijection between M and N by stating in case 1, 2a and 2b an element in M is sent to the next element in the chain and, in case 2c it is sent to the previous element in the chain.
     
  6. Mar 2, 2004 #5
    In your hints and other sources, I use this one; it seems to work.

    1). Let f: M -> N as 1-1, g: N -> M as 1-1.

    2). Let N_0 = N - f(M), M_0 = g(N_0). N_i+1 = f(M_i) and M_i+1 = g(N-i) for all i =0, 1, 2, 3 ... n, ... .

    3). Denote N' as union of all N_i for i from 0, 1, 2, 3, ... to infinite maximum.

    4). Denote M' as union of all M_i for i from 0, 1, 2, 3, ... to infinite maximum.

    5). Now, we can see N divided as two parts, N' and N - N'.

    6). Define h: N -> M as inverse of f ( denoted as 1/f) when n belongs to N -N' and as g when n belongs to N.

    7) We need to prove h as 1-1 and onto.

    8). 1-1: For every n1 and n2 belong to N, we shall look in them as three different cases: a) n1 and n2 belong to N-N', b) n1 and n2 belong to N', c) n1 belongs to N-N' and n2 belong to N.

    For 8.a) and 8.b), h(n1) not= h(n2) as long as n1 not = n2 because both 1/f and g are 1-1.

    For 8.c), we need to prove it is not possible that h(n1) = h(n2). Let's say h(n1)=h(n2)=m. Let's say n2 belongs to N_i, i as 0, 1, 2, 3 or some n. m=g(n2), so m belongs to M_i. f(m) belongs to N_i+1. f(m)=f(h(n1))=f(1/f(n1)) = n1. n1 belongs to N_i+1 then. This conflicts to that n1 belongs to N - N'.

    9) onto: For any m belong to M, we can divide them into two cases. m belongs to an M_i or m does not belong to any M_i.

    a). If m belongs to M_i, there is a n in N_i such that g(n)=m. Sine n belongs to N', so h(n)=g(n)=m.

    b). If m does not belong to any M_i, consider n =f(m). Since m does not belong to any M_i, n does not belong to any N_i+1, for i as 0,1,2,3 ... . So n does not belong to N_1, N_2 , N_3, ... . Well, n can not belong to N_0 either, Because Y_0 is Y-f(M) and n as f(m) is not in Y-f(M). We can say now n belongs to N-N'. h(n)=(1/f)(n)=m.

    I will double check this proof.
     
  7. Mar 2, 2004 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    the h you define is not a function on N. There is no reason for an element of N to lie in the image of f or the set N'.

    example N=M='the naturals' to itself, f=g= 'x-->x+1',

    then N' ={2,3,4,...} and 1 in N is not in N' nor does f^{-1} of 1 exist either.
     
  8. Mar 2, 2004 #7
    Matt,

    Correction to this part. A typo.

    2). Let N_0 = N - f(M), M_0 = g(N_0). N_i+1 = f(M_i) and M_i+1 = g(N_i+1) for all i

    To your

    N' ={1, 3, 5, 7 , 9 , ... }, because N_0 = {1). M_0={2}. N_1={3), M_1={4}, ... .

    N-N' = {2, 4, 6, 8, 10, ... }.

    h(y)=y+1 if y is odd and y-1 if y is even.
     
  9. Mar 2, 2004 #8
    Sorry. Another typo.

    6). Define h: N -> M as inverse of f ( denoted as 1/f) when n belongs to N -N' and as g when n belongs to N'.
     
  10. Mar 2, 2004 #9
    Correct another typo:

    8). 1-1: For every n1 and n2 belong to N, we shall look in them as three different cases: a) n1 and n2 belong to N-N', b) n1 and n2 belong to N', c) n1 belongs to N-N' and n2 belong to N'.
     
  11. Mar 3, 2004 #10
    Another example to show the concept of my proof.

    Take M=(-1,1), N=[-1,1] and f and g defined as x/2.

    Basically, N is divided as two sets: First one is [-1, -1/2] U [1/2, 1] U [-1/4, -1/8] U [1/8, 1/4] U [-1/16, -1/32] U [1/32, 1/16] U ... . The second one is (-1/2, -1/4) U (1/4, 1/2) U (-1/8, -1/16) U (1/8, 1/16) U ... U ... U {0}.

    Define h : N -> M as x/2 when m belongs to the first part and 2x when m belongs to the second part.

    An interesting fact is you can see the first part as a chain of closed segments and the second part as a chain of open sets except {0}.
     
  12. Mar 3, 2004 #11
    I looked at another proof. This is interesting. Similar idea as what I did but different twist.

    First, he made C_0 as g(B). B has a 1-1 and onto map to C_0, clearly.

    Two sequences of sets are then constructed: M_0 = M, C_0 = C, M_i+1 = g(f(M_i)) and C_i+1 = C_i.

    The function k: A -> C is then defined as g(f(x)) if x belongs to any A_i - C_i, and x otherwise.

    the fundtion k is then proved to be 1-1 and onto.

    This tastes different from my proof, but it's the same idea except it also shows that a subset of M is equivalent to the mainset M. Note my N_i is similar to his idea of A_i - C_i.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?