Who is Schroder Bernstein?

[Sammywu]

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.

[matt grime]

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.

[Sammywu]

Matt, Thanks. Good example.

All the proofs I have thought are falwed. Do you know where I can find a good proof?

[matt grime]

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.

[Sammywu]

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.

[matt grime]

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.

[Sammywu]

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.

[Sammywu]

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'.

[Sammywu]

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'.

[Sammywu]

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}.

[Sammywu]

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.