Who Proved the Schroder-Bernstein Theorem and How?

  • Context: Graduate 
  • Thread starter Thread starter Sammywu
  • Start date Start date
Click For Summary

Discussion Overview

The discussion centers on the Schroder-Bernstein theorem, its origins, and various proofs associated with it. Participants explore the theorem's implications regarding one-to-one and onto mappings between sets, while also questioning the validity of certain proofs and providing their own interpretations and examples.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants express confusion about the theorem, particularly regarding the existence of a bijection between certain sets, such as [-1,1] and (-1,1).
  • One participant attributes the first proof of the theorem to Friedrich Schroeder and Felix Bernstein, mentioning a proof involving 'chains'.
  • Another participant provides a specific example of a bijection between (0,1) and [0,1], suggesting that the lack of a continuous bijection may be the source of confusion.
  • Several participants share their own proofs or approaches, including the use of disjoint sets and chains to establish bijections.
  • One participant critiques a proposed proof, arguing that the defined function does not cover all elements of N, providing a counterexample using the natural numbers.
  • Corrections and clarifications are made regarding the definitions and steps in the proofs, indicating ongoing refinement of ideas.
  • Another proof is mentioned that constructs sequences of sets and defines a function that is shown to be one-to-one and onto, highlighting similarities and differences with previous approaches.

Areas of Agreement / Disagreement

Participants do not reach consensus on the validity of certain proofs or the existence of bijections in specific cases. Multiple competing views and interpretations of the theorem and its proofs remain present throughout the discussion.

Contextual Notes

Some proofs presented contain logical errors or assumptions that are not universally accepted. The discussion reflects a variety of interpretations and approaches to the theorem, with participants actively questioning and refining each other's contributions.

Who May Find This Useful

Readers interested in set theory, mathematical proofs, and the foundations of mathematics may find the exploration of the Schroder-Bernstein theorem and its various proofs relevant.

Sammywu
Messages
273
Reaction score
0
Do anyone 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.
 
Physics news on Phys.org
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.
 
Matt, Thanks. Good example.

All the proofs I have thought are falwed. Do you know where I can find a good proof?
 
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.
 
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.
 
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.
 
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.
 
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'.
 
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'.
 
  • #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}.
 
  • #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.
 

Similar threads

Undergrad Contrapositive of theorem and issue with proof
  • · Replies 5 ·
Replies
5
Views
2K
MHB Definition of $S_n$ for Cantor-Schröder-Bernstein Theorem
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Homemorphism in quotient topology
  • · Replies 5 ·
Replies
5
Views
1K
Graduate Uncertainties on Bayes' theorem
  • · Replies 19 ·
Replies
19
Views
2K
MHB Proving Onto and 1-1 Properties of Function Compositions
  • · Replies 4 ·
Replies
4
Views
2K
Graduate Question about existence of path-lifting property
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Understanding extinction probability in simple GWP
  • · Replies 1 ·
Replies
1
Views
2K
Graduate A global version of the implicit function theorem
  • · Replies 0 ·
Replies
0
Views
703
Undergrad An easy proof of Gödel's first incompleteness theorem?
  • · Replies 16 ·
Replies
16
Views
3K
Graduate Understanding: double of conformally flat manifold is conformally flat
  • · Replies 1 ·
Replies
1
Views
2K