Back to the index. Or to the chambers

This article has 17 links. View as Cloud or List.

Proof Simple Algebraic System Order Group Number Infinite Surjective Induction Multivalued Function Finite Function Set Theory Inverse Image Converse Theorem Even Number Sequence Discrete Valuation Ring Complete Sound

No pages link here.

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Schroeder Bernstein Theorem Proof

Let and be two nonempty sets; and let there be, in addition, two one-one functions $f:A\rightarrowtail B$ and $g:B\rightarrowtail A$ . We propose to show that and are equinumerous i.e., bijective.

Consider the notation:

$\displaystyle g^{-1}(x),$	if	$\displaystyle x\in g(B)$
$\displaystyle f^{-1}(g^{-1}(x)),$	if	$\displaystyle g^{-1}(x)\in f(A)$
$\displaystyle g^{-1}(f^{-1}(g^{-1}(x))),$	if	$\displaystyle f^{-1}(g^{-1}(x))\in g(B)$
$\displaystyle .....$

Define, for each $x\in A$ , the order of it, denoted by $\circ(x)$ , to be the number of such preimage(s) which exist. In a similer way, we'd be able to define the order of an element $y\in B$ , i.e., by considering the sequence $f^{-1}(y),g^{-1}(f^{-1}(y)),...$ .

Now define, for each $x\in A$ ,

$\displaystyle \phi(x):$	$\displaystyle =$	$\displaystyle f(x),\quad \circ(x)=\infty$
	$\displaystyle =$	$\displaystyle f(x),\quad \circ(x)=2n,$ for some $\displaystyle n\in\omega$
	$\displaystyle =$	$\displaystyle b,\quad \circ(x)=2n+1,i.e.,\exists b\in B : g(b)=x$

Notice that if the order is infinite, $\phi(x)=f(x)$ is also infinite. Because, otherwise would have to have a finite order. On the other hand, if $y\in B$ and $\circ(y)$ is infinite, then $f^{-1}(y)$ exists and has an infinite order; call the latter one . This means, $\phi$ maps the infinite order elements of bijectively onto the infinite order elements of .

Next, if $\circ(x)=2n$ , then the order of is sheer . Similer to the above para, if for $y\in B$ , the order is , as the order is non-zero, $f^{-1}(y)$ exists and it must have order . To formally show it you need a tedious inductive reasoning!

Last, if $\circ(x)=2n+1$ , then the order is $\ge 1$ , and so, $g^{-1}(x)$ exists and the order of $g^{-1}(x)$ is sheer (looking upon $g^{-1}(x)$ as an element of ). Conversely, similer to above, if there is an element of order in , take and the order of is indeed . All that you need to convince a sceptic is a long, tedious, involved induction!!

What we learn from what precedes is that the one-one function $\phi$ maps the infinite order elements onto infinite order elements, odd order onto odd order, and even order onto even order; a simple set theory reveals that $\phi$ is a one-one map from onto . This completes the proof.

1	Simple Algebraic System
1	Proof
1	Sequence
1	Surjective
1	Set Theory
1	Function
1	Finite
1	Inverse Image
1	Even Number
1	Infinite
1	Converse Theorem
1	Induction
1	Multivalued Function
1	Number
1	Order Group
2	Discrete Valuation Ring
3	Complete Sound