Thread Rating:
• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 Cantor-Bernstein-Schroeder Theorem
04-16-2010, 08:24 PM
Post: #1
 elim Moderator     Posts: 578 Joined: Feb 2010 Reputation: 0
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 \end{array} \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.
 « Next Oldest | Next Newest »

Forum Jump: