Tilted Forum Project Discussion Community - View Single Post - Cantor-Schroder-Bernstein Theorem

thechao · 09-18-2003, 04:09 PM

Okay. Here's my stab at it. Probably lots of holes, its been a while.

[D1] Imagine two sets T, S s.t. there is a mapping M : T -> S, 1-1, onto, but there is no mapping ~M : S -> T, 1-1, onto, we define this as |S| < |T|.

[1]
Consider |T| < |S|, consider the mapping M : S -> T, 1-1 and onto. Assume there is no 1-1, onto mapping ~M : T -> S. There exists some s of S, s.t. M(s) !of T, this is trivial. Call this the "one out" lemma.

[2]
Consider |T| < |S|, it is trivial to construct a mapping M : S -> T, 1-1 and onto. Simply take each element t of T and index it by a unique s: t[s] of T (this is NOT an ordering). The indexing function defines M(s) = t. N.B. M(s) has at least "one out" element by above lemma.

[3]
Consider |T|=|S|, then there is a mapping M : S -> T, 1-1 and onto and the inverse mapping ~M : S -> T is trivial to construct, e.g. M(s) = t, then ~M(t) = ~M(M(s)) = s, thus ~M(t) = s. Call this the "inversion lemma", nontrivial, see next. Corollary, if |T|=|S|, then there does not exist some element t of T s.t. there is no s of S s.t. M(s) != t and vice versa. Assume |T|=|S|, and M : T -> S, 1-1 and onto, but there is some s of S s.t. there is no t of T s.t. M(t) = s. This is a "one out" element. By definition this is a mapping, M : T -> S s.t. |T|<|S| ><.

[4]
Consider S,T s.t. |S| <= |T| and |S| != |T|, show that |S| < |T|. Since |T| >= |S| we can create a mapping M : T -> S, 1-1, onto. Assume there does not exist a "one out". Then that means for all t of T, M(t) = s, for some s of S, and if M is 1-1 and onto, then M(t1) = s1 and M(t2) = s2 and if t1!=t2, then s1!=s2. However, we can then construct some mapping ~M : S -> T, 1-1 and onto, then ~M(M(t)) = t for all t of T and M(~M(s)) = s for all s of S, then |S|=|T| ><, thus |S|<|T|.

[5]
Imagine two sets S, T s.t. |S| <= |T| and |T| <= |S| but |S| != |T|, then that means there is no mapping, M : S -> T, 1-1, onto. Thus there exists some t of T s.t. there is no s of S, M(s) = t. However, |T| < |S|, which means there is some mapping ~M(t) = s which could exist >< This means for each s of S there exists one, and only one t of T such that M(s) = t and consequently ~M(t) = s, QED.

09-18-2003, 04:09 PM	#11 (permalink)
thechao Upright Location: Houston	Okay. Here's my stab at it. Probably lots of holes, its been a while. [D1] Imagine two sets T, S s.t. there is a mapping M : T -> S, 1-1, onto, but there is no mapping ~M : S -> T, 1-1, onto, we define this as \|S\| < \|T\|. [1] Consider \|T\| < \|S\|, consider the mapping M : S -> T, 1-1 and onto. Assume there is no 1-1, onto mapping ~M : T -> S. There exists some s of S, s.t. M(s) !of T, this is trivial. Call this the "one out" lemma. [2] Consider \|T\| < \|S\|, it is trivial to construct a mapping M : S -> T, 1-1 and onto. Simply take each element t of T and index it by a unique s: t[s] of T (this is NOT an ordering). The indexing function defines M(s) = t. N.B. M(s) has at least "one out" element by above lemma. [3] Consider \|T\|=\|S\|, then there is a mapping M : S -> T, 1-1 and onto and the inverse mapping ~M : S -> T is trivial to construct, e.g. M(s) = t, then ~M(t) = ~M(M(s)) = s, thus ~M(t) = s. Call this the "inversion lemma", nontrivial, see next. Corollary, if \|T\|=\|S\|, then there does not exist some element t of T s.t. there is no s of S s.t. M(s) != t and vice versa. Assume \|T\|=\|S\|, and M : T -> S, 1-1 and onto, but there is some s of S s.t. there is no t of T s.t. M(t) = s. This is a "one out" element. By definition this is a mapping, M : T -> S s.t. \|T\|<\|S\| ><. [4] Consider S,T s.t. \|S\| <= \|T\| and \|S\| != \|T\|, show that \|S\| < \|T\|. Since \|T\| >= \|S\| we can create a mapping M : T -> S, 1-1, onto. Assume there does not exist a "one out". Then that means for all t of T, M(t) = s, for some s of S, and if M is 1-1 and onto, then M(t1) = s1 and M(t2) = s2 and if t1!=t2, then s1!=s2. However, we can then construct some mapping ~M : S -> T, 1-1 and onto, then ~M(M(t)) = t for all t of T and M(~M(s)) = s for all s of S, then \|S\|=\|T\| ><, thus \|S\|<\|T\|. [5] Imagine two sets S, T s.t. \|S\| <= \|T\| and \|T\| <= \|S\| but \|S\| != \|T\|, then that means there is no mapping, M : S -> T, 1-1, onto. Thus there exists some t of T s.t. there is no s of S, M(s) = t. However, \|T\| < \|S\|, which means there is some mapping ~M(t) = s which could exist >< This means for each s of S there exists one, and only one t of T such that M(s) = t and consequently ~M(t) = s, QED.