wu :: forums
wu :: forums - BERNSTEIN'S THEOREM

Welcome, Guest. Please Login or Register.
Jan 16th, 2022, 11:17am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   general
   wanted
(Moderators: towr, ThudnBlunder, Eigenray, william wu, Icarus, Grimbal, SMQ)
   BERNSTEIN'S THEOREM
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: BERNSTEIN'S THEOREM  (Read 2927 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
BERNSTEIN'S THEOREM  
« on: Oct 11th, 2002, 2:06pm »
Quote Quote Modify Modify

  So, I was reading a different proof of the Schroder-Bernstein theorem than the one I knew, and stumbled.
 
   You'll recall that the SB theorem states that, given two sets A,B, if there exists a one-to-one mapping f from A to a subset B' of B, and also a one-to-one mapping g from B to a subset A' of A, then there exists a one-to-one mapping from A to B. In symbols (where C denotes "is a subset of"):
 
There exists f : A -> B' C B, f 1-to-1
There exists g : B -> A' C A, g 1-to-1
----------------------------
Hence there is h : A -> B, h 1-to-1
 
or in cardinal notation, where a = card(A), b = card(B):
 
a <= b, b <= a --> a = b.
 
The proof I'm reading, due to Peano and Zermelo (independently), is basically as follows:
 
Let A' = g(B), B' = f(A), basically as defined above. But also let A" = g(B') = g(f(A)). Let A ~ B denote equipotence between sets (the fact that there exists a one-to-one mapping from one to the other). Clearly, A" ~ A. Now decompose A into the 3 disjoint subsets P, Q, R as follows:
 
P = A"
Q = A'\A" (the elements of A' not in A")
R = A\A'.
 
We have P U Q = A', P U Q U R = A ~ A" = P. Because B ~ A', it will be enough to show that P U Q ~ P.
 
   Let F denote g o f, that is, F(x) = g(f(x)) for all x in A, and, for each subset X of A, define X* = F(X) U Q. We say that X is normal if X* C X.
 
   Now, here comes the stumbling block: "it is readily seen that all sets X* are normal", writes the author of the article (which is actually about something else). I don't see it quite so clearly. If O is the empty set, the O* = F(O) U Q = Q. From the above statement, we must conclude that Q is normal. But that will happen iff Q* = F(Q) U Q C Q, which in turn will happen iff F(Q) C Q. But F(Q) is entirely contained in P (since P is the image of F), and we have P inter Q = O, by construction!  
 
   I came up with a further example of the falsity of this affirmation; suppose that A = B = N, the set of natural numbers (zero included). Suppose further that f(n) = g(n) = 2n, for all n in N. Then A' = B' = the set of even numbers, and F(n) = g(f(n)) = g(2n) = 4n, so A" = the set of numbers divisible by four. To ease visualization:
 
A = B = {0,1,2,3,4,...} (naturals)
A' = B' = {0,2,4,6,...} (even numbers)
A" = P = {0,4,8,12,16,...} (numbers divisible by 4)
Q = A'\A" = {2,6,10,14,...} (even numbers not divisible by 4)
R = {1,3,5,7,...} (odd numbers)
 
I will show that there exists X, a subset of A, such that X* is NOT normal. It is actually very simple. Consider X = {0}. Then
 
X* = F({0}) U Q = {0} U Q = {0,2,6,10,...};
 
but
 
X** = (X*)* = F(X*) U Q; since 2 is in X*, 8 is in F(X*), and hence in X**. But it is easy to see that 8 is NOT in X*, therefore NOT(X** C X*), therefore X* is NOT normal.
 
   Fortunately, the proof does not depend on the hypothesis that X* is normal for all X; it is sufficient that there exist some subset U of A such that U* = U, which I have been able to prove independently.
 
   But I was left curious: am I blatantly missing something here, or is the article wrong?
 
Note: The article is by Leonard Gillman, and was published on the "American Mathematical Monthly", in the June-July edition of 2002.
IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Re: BERNSTEIN'S THEOREM  
« Reply #1 on: Nov 12th, 2002, 4:58pm »
Quote Quote Modify Modify

Unless there was something in the article that you didn't mention, obviously you are not missing something, since both your counterexamples clearly contradict the claim. Is it possible that he meant "For all normal sets X, X* is normal"? That one is "readily seen"!
IP Logged

"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board