Tilted Forum Project Discussion Community  

Go Back   Tilted Forum Project Discussion Community > The Academy > Tilted Knowledge and How-To


 
 
LinkBack Thread Tools
Old 09-14-2003, 06:48 PM   #1 (permalink)
Riiiiight........
 
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....
dimbulb is offline  
Old 09-16-2003, 07:49 AM   #2 (permalink)
Insane
 
Location: The Internet
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.
__________________
rm -f /bin/laden
Sapper is offline  
Old 09-16-2003, 10:37 AM   #3 (permalink)
Riiiiight........
 
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.
dimbulb is offline  
Old 09-16-2003, 11:42 AM   #4 (permalink)
Sky Piercer
 
CSflim's Avatar
 
Location: Ireland
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.

Code:

N  -  Z
-------
0  :  0
1  :  1
2  : -1
3  :  2
4  : -2
5  :  3
6  : -3
7  :  4
8  : -4  
.
.
.
...etc.
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.

Code:

N  -  R
0  :  0.789412334...
1  :  0.200000141...
2  :  0.319859632...
3  :  0.333333333...
4  :  0.999406180..
5  :  0.840369747...
6  :  0.897863254...
7  :  0.470940646...
8  :  0.789789789...
.
.
.
...etc
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:
Code:
N  -  R
0  :  0.789412334...
1  :  0.200000141...
2  :  0.319859632...
3  :  0.333333333...
4  :  0.999406180..
5  :  0.840369747...
6  :  0.897863254...
7  :  0.470940646...
8  :  0.789789789...
.
.
.
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?
__________________

Last edited by CSflim; 09-16-2003 at 11:53 AM..
CSflim is offline  
Old 09-16-2003, 11:59 AM   #5 (permalink)
Riiiiight........
 
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)
dimbulb is offline  
Old 09-16-2003, 12:49 PM   #6 (permalink)
Sky Piercer
 
CSflim's Avatar
 
Location: Ireland
what IS your question?
Are you looking for a proof of the Cantor-Schroder-Bernstein Theorem?
Have you tried Ask Jeeves?
__________________
CSflim is offline  
Old 09-16-2003, 01:05 PM   #7 (permalink)
Sky Piercer
 
CSflim's Avatar
 
Location: Ireland
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
__________________
CSflim is offline  
Old 09-16-2003, 05:14 PM   #8 (permalink)
Riiiiight........
 
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.
dimbulb is offline  
Old 09-16-2003, 05:16 PM   #9 (permalink)
Riiiiight........
 
It's just fascinating that such an obvious result, is non-trivial to prove.
dimbulb is offline  
Old 09-17-2003, 03:05 PM   #10 (permalink)
Sky Piercer
 
CSflim's Avatar
 
Location: Ireland
You should probably try a more specialist website.
sciforums.com has a maths baord. Try there.
__________________
CSflim is offline  
Old 09-18-2003, 04:09 PM   #11 (permalink)
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.
thechao is offline  
Old 09-18-2003, 06:56 PM   #12 (permalink)
Crazy
 
Location: Switzerland
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?
__________________
Didn't remember how intense love could be... Thank you B.
Grothendieck is offline  
Old 09-19-2003, 06:07 AM   #13 (permalink)
Riiiiight........
 
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...
dimbulb is offline  
Old 10-21-2003, 01:06 PM   #14 (permalink)
 
KnifeMissile's Avatar
 
Location: Waterloo, Ontario
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?
KnifeMissile is offline  
Old 10-21-2003, 01:35 PM   #15 (permalink)
Crazy
 
Location: Switzerland
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.
__________________
Didn't remember how intense love could be... Thank you B.

Last edited by Grothendieck; 10-21-2003 at 01:39 PM..
Grothendieck is offline  
Old 10-21-2003, 04:22 PM   #16 (permalink)
 
KnifeMissile's Avatar
 
Location: Waterloo, Ontario
Quote:
Originally posted by Grothendieck
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).
KnifeMissile is offline  
Old 10-21-2003, 05:13 PM   #17 (permalink)
Riiiiight........
 
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
Quote:
Every real number is negative, 0, or positive. The law is sometimes stated as "For arbitrary real numbers a and b, exactly one of the relations a < b, a = b, a > b holds" (Apostol 1967, p. 20).

I'm guessing that you have to take either one of them as an axiom, and the other automatically follows...
dimbulb is offline  
Old 10-21-2003, 05:18 PM   #18 (permalink)
Riiiiight........
 
http://mathworld.wolfram.com/CardinalComparison.html

Quote:
For any sets A and B, their cardinal numbers satisfy |A|<=|B| iff there is a one-to-one function f from A into B (Rubin 1967, p. 266; Suppes 1972, pp. 94 and 116). It is easy to show this satisfies the reflexive and transitive axioms of a partial order. However, it is difficult to show the antisymmetry property, whose proof is known as the Schröder-Bernstein theorem. To show the trichotomy property, one must use the axiom of choice.
dimbulb is offline  
Old 11-03-2003, 05:37 PM   #19 (permalink)
Crazy
 
Location: Switzerland
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.
__________________
Didn't remember how intense love could be... Thank you B.

Last edited by Grothendieck; 11-03-2003 at 05:42 PM..
Grothendieck is offline  
Old 11-03-2003, 11:18 PM   #20 (permalink)
Addict
 
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).
phukraut is offline  
 

Tags
cantorschroderbernstein, theorem

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT -8. The time now is 06:14 PM.

Tilted Forum Project

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Search Engine Optimization by vBSEO 3.6.0 PL2
© 2002-2012 Tilted Forum Project

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360