Post Reply 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Cantor-Bernstein-Schroeder Theorem
04-16-2010, 08:24 PM
Post: #1
Cantor-Bernstein-Schroeder Theorem
Let \(f:A \to B\) and \(g: B \to A\) be injections, then there exists a bijection \(h:A \to B\)
Proof: Let \(C_0 = A\setminus g(B) \), and \(C_{n+1} = g(f(C_n)) \quad (n \ge 0)\) and \(C = \bigcup_{n=0}^{\infty} C_n\), then \[h(x) = \left\{
\begin{array}{c l}
f(x) & x \in C \\
g^{-1}(x) & x \in A\setminus C
\right.\]is the bijection between \(A\) and \(B\).
Since \(x \notin C \Rightarrow x \notin C_0 = C \setminus f(B) \Rightarrow x \in f(B) \Rightarrow h(x) = g^{-1}(x)\) is well defined.
\(h\) is surjective: if \(b \in B \bigcap f( C)\), then \(b \in h©\); otherwise \(b \in B\setminus f( C)\), then \(a = g(b) \notin A\setminus g(B)\).
Since \(b \not\in f© \supset f(C_n)\), \(a = g(b) \not \in g(f(C_n)) = C_{n+1}\). So \(a \not \in C\) and \(h(a)=g^{-1}(g(b)) = b\)
\(h\) is injective: Need only show that \(f( c) = g^{-1}(a)\) for \(c \in C\) and \(a \in A\setminus C\) never happen. Otherwise since \(c \in C\), \(c \in C_n\) for some \(n \in \mathbb{N}\), hence \(g(f( c)) \in C_{n+1} \subset C\). But \(f( c) = g^{-1}(a) \) implies that \(g(f©)=g(g^{-1}(a)) = a \in A\setminus C\) , a contradiction!

Note that the above definition of \(h\) is nonconstructive, in the sense that there exists no general method to decide in a finite number of steps, for any given sets \(A\) and \(B\) and injections \(f\) and \(g\), whether an element \(a\) of \(A\) does not lie in \(C\). For special sets and maps this might, of course, be possible.
Find all posts by this user
Quote this message in a reply
Post Reply 

Forum Jump:

Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication