Cantor-Schroder-Bernstein Theorem
 

stupid theorem, and I don't need to be able to prove this, just use its results. but i've been trying to prove this for some time now.

Assume S and T are infinite sets.

if|S|<=|T| and |T|<=|S|, then |S|=|T|

|S| is the cardinality of the set S.

basically, you need to establish a bijection between S and T, while using the fact that there exists an injection from S to T and there exists an injection from T to S.

in plain words, if S is bigger than or equal in size to T, and if T is bigger than or equal in size to S, then S and T are the same size.....

ahhhh.... the mind boggling concept of infinity....

This begs the question: why not represent the sets of infinity in terms of "x" and "y" to simplify the concept?

What really gets me is the fundamental mathematic functions in relation to infinity. Ie. inf * inf = inf, when infinity exists and does not exist is what boggles my mind. :D :p

Well, it depends on what you mean by infinity.
As mindboggling as it sounds, there are different sizes of infinity.
(big infinity, or small infinity,... kidding... )

so the smallest "size" or cardinality of an infinite set is the size of the natural numbers (positive integers). This is countably infinite.

and Power set of X =set that contains all subsets of X, can be shown to be bigger than the size of X. This is uncountably infinite.

so there are infinite sets that are bigger than others.

I can answer the question to the different "sizes" in a fairly straight forward way.

All you need to do is take the sets N, Z and R.

N = Natural numbers, i.e. the numbers that we count with, positive whole numbers. 0,1,2,3,4,5,6,7,8,9...
Z = Integers: Positive whole numbers, zero and negative whole numbers. ...-4,-3,-2,-1,0,1,2,3,4...
R = Real numbers: All numbers that can be plotted on the number line:
-4.5, 2.7, 0.00001, pi, e, phi, etc.

Now as we can see N, Z and R are all infinite sets. The question is, are they all the same size?

Well compare N and Z. Surely Z is bigger, seeing as how it contains everything in N plus a whole lot more? Surely Z is twice as big? Well actually N and Z are the same size.

We can "count" all of the integers, by pairing them off with natural numbers.

you can continue this list for as long as you like, and you will always have a Natural Number to pair off to an Integer, i.e. both sets are the same size.

Now, the question remain, can we do the same thing for R? Actually we can't.
We can prove this.

Assume that R is countable. We will set up a list, pairing each N to an R. We needn't use any particular order for R.
In fact, just for simplicity, lets limit ourselves to just real numbers between 0 and 1.

We now have a list which is infinitely long. We now need to prove that there exists a Real number (lying between 0 and 1) which is not on this list.

Easily done:
We construct a new number, which is not on our list as such:
0.709309249...
we now add 1 to each digit, (letting 9+1=0)
0.810410350...
This number is necessarily not on our list, as it differs from each entry by at least one digit!
If we add this number to our list, we will be in no better of a position.
Hence we can see that N is the same size as Z, but smaller than R, even though they are all infinitely big!

dimbulb, I can see that you already knew this, but I think that it's a great proof to use to show people who refuse to accept that there is such a thing as "big infinity" and "small infinity" ;).
Plus I think that itt also makes it easier to "visualise" the different "infinities".

As for your original post...what exactly is your question? Are you looking for a proof of this theorem?
"stupid theorem, and I don't need to be able to prove this,"
Didn't quite get what you're asking? Is it that, you don't "need" to be able to prove it, but that you would like to?

Someone answer my question!!!

ok, i've also simplified it to an equivalent theorem. If you can prove this, the Shroder-Bernstein is easy to prove.

if A3 is a proper subset of A2, which is a proper subset of A1 , and |A1|=|A3| (or A1~A3), then |A1|=|A2|. ( or A1~A2~A3)

what IS your question?
Are you looking for a proof of the Cantor-Schroder-Bernstein Theorem?
Have you tried Ask Jeeves?

I did a search, and found this link, which has a proof to the Cantor-Schroder-Bernstein Theorem. I didn't read it, so I can't tell how useful it is.
http://math.dartmouth.edu/~doyle/doc...ree/three.html

i've seen variations of the proof. but only glimpses of it. Its been my pet project for the past week or so. Just wanted to see if anyone else has a take on it.

It's just fascinating that such an obvious result, is non-trivial to prove.

You should probably try a more specialist website.
sciforums.com has a maths baord. Try there.

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.

dimbulb, the proof is tricky, but there are good expositions. see e.g.

Yiannis Moschovakis
Notes on set theory
Springer, 1994.

The trick is to keep track of the path of an element when the two injections are followed. If you want to find a proof by yourself, try distinguishing those points on S that have infinite, and those that have finite such trajectories.

BTW, I don't see where your reformulation helps?

Well, there exists a bijection between S and a subset of T, T1(call the f), and a bijection between T and a subset of S,S1 (call it g).

Restrict g, so that its domain is f(S). so there is a bijection between f(S) and g(f(S)). lets call the set g(f(S))

observe that g(f(S)) is a proper subset of S1, so lets call g(f(S)) S2.

so we have a bijection between S and f(S), and a bijection between f(S) and S2. Thus S ~S2.
S2 is a proper subset of S1 which is a proper subset of S. So if you can prove that S~S1, and since there is a bijection between S1 and T, you can obtain a bijection between S and T.

I've solved the problem without using my reformulation, but using the above principle of obtaining bijections between a set and its proper subset.

took me a while, and finally got it. It occured to me while i was reading a proof for my reformulation..heh...

You know, this is probably not the answer everyone is looking for but I believe that there is a trichotomy axiom for the cardinality of sets, much like for the real numbers.

So, practically by definition, if |A|=<|B| and |B|=<|A|, then |A|=|B|. I use =< to not confuse it with the implication sign.

Anyway, in case you're unfamilar with the trichotomy axiom, it states that any two elements, x and y, must have exactly one of the following relationships: x < y, x = y, or x > y. This cannot be proven for the real numbers and, instead, is taken as an axiom. Perhaps the same can be said for set cardinality?

Nope KnifeMissle. The "trichotomy" theorem is the definition of a total order. It can and is and must be proven in both the case of set theory, and the real numbers. The Cantor-Bernstein theorem is *exactly* the proof in the case of sets.

While I can't say for sets, please double check your assertion to the set of real numbers. Doing a google search, I can find references to the trichotomy property, or the trichotomy law, but no one refers to it as a theorem nor does anyone provide a proof. Indeed, it seems hard to construct one. I really do remember it being an axiom of the real numbers, much like the least upper bound axiom (or principle).

You need the Cantor-Bernstein in sets because of how you define the "equality" or the order of sets.

A set A has greater than or equal cardinality than another set B iff there exists an injection from B into A.

two sets have equal cardinality iff there exists a bijection between the 2 sets.

so to prove the equality of cardinalities, you have to establish the existence of a bijection.

I think the order axioms result from the definitions of the reals as an ordered fields, and the theorem than can be proved from the ordered axioms is that a number is either positive, negative or 0.

from Mathworld http://mathworld.wolfram.com/TrichotomyLaw.html
I'm guessing that you have to take either one of them as an axiom, and the other automatically follows...

http://mathworld.wolfram.com/CardinalComparison.html

I'm sorry I didn't reply to this earlier KnifeMissile. Try reading the beginning of any *serious* book on Analysis. A lot of books do introduce real numbers by the axioms, but others take the time to construct them from the rationals, for instance by means of Cauchy series.

Here's a definition of the order on real numbers: Given two real numbers x and y, say that x<=y if there is another real number z such that y-x=z*z. If there is no such z, say that x>y. Equal if their equal. Now what you would have to prove with this approach (which isn't the best, I'm just giving you something you might not find in the books), is that if x<y, then y>x. :)

By the way, the "least upper bound principle" is what is also called the "existence of suprema", and this too is proven in serious books. The reason I'm not giving you precise references is that I'm from Switzerland and know the German much better than the English literature.

Here's a resumee: If you want to get to the applications of real numbers quickly, you can introduce real numbers by axioms. But this is only cutting corners, and mathematicians know how to prove that the real numbers constructed by one of the standard procedures (Dedekind cuts, or Cauchy sequences) actually fulfill those axioms, and what's more, are completely characterised by them.

for a development of the real numbers from sequences, see Elementary Classical Analysis by Marsden and Hoffman, Chapter 1. The construction of the reals requires the Field Axioms, the Order Axioms, and the concept of completeness (if an ordered field obeys the monotone sequence property; which means that every monotone increasing sequence bounded above in an ordered field converges).