Author |
Topic: Countability of Real Numbers (Read 1850 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Countability of Real Numbers
« on: Nov 18th, 2004, 7:09am » |
 Quote  Modify
|
Any comments on this article?
Note that it was submitted to Elsevier Science (what is it?)
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Countability of Real Numbers
« Reply #1 on: Nov 18th, 2004, 7:57am » |
Quote Modify
|
Surprising how there can be a proof they aren't denumerable, and one that they are 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Countability of Real Numbers
« Reply #2 on: Nov 18th, 2004, 8:31am » |
Quote Modify
|
The earth population is growing and, what is more, computers are becoming every day faster and more uncountable. Sooner or later the task of enumerating the reals should fall in the realm of the possible.
Maybe one day a seti@home-like project will be put to work on that task?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Countability of Real Numbers
« Reply #3 on: Nov 18th, 2004, 9:50am » |
Quote Modify
|
on Nov 18th, 2004, 7:09am, Barukh wrote:| Note that it was submitted to Elsevier Science (what is it?) |
|
It seems to be a publishing house.
on Nov 18th, 2004, 7:57am, towr wrote:| Surprising how there can be a proof they aren't denumerable, and one that they are |
|
Yes, why don't they first debunk the former?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Countability of Real Numbers
« Reply #4 on: Nov 18th, 2004, 12:22pm » |
Quote Modify
|
They don't debunk the former, as such, but they attempt to demonstrate (through theorems 4 and 5) that the same line of reasoning that proves the denumerability of the reals can be modified to show that the rational numbers are denumerable.
I am unable to grasp their arguments for theorem 2 fully, but I have a query about their first theorem...
They claim that all real numbers can be expressed in the form R=a1^a2^a3^..., where ai=(mi1/ni1)^((mi2/ni2)^(mi3/n i3)).
Obviously all rationals, irrational roots, and rational/irrational roots raised to rational/irrational root powers can be expressed, which deals with a certain class of algebraic and transcendental numbers; what about, say, 2[sqrt]2+1? In addition, they argue that as numbers of the form a1^a2 cannot be calculated for the general case, it follows that transcendentals, such as e and [pi], will be expressible in higher forms of these stacked powers. It seems to me that they're making a giant leap and they are not clearly defining R.
What have others made of it so far?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Countability of Real Numbers
« Reply #5 on: Nov 18th, 2004, 2:20pm » |
Quote Modify
|
on Nov 18th, 2004, 7:09am, Barukh wrote:
Note that it was submitted to Elsevier Science (what is it?) |
|
Elsevier seems to have a lot of journals which it publishes, including one called, "Information Processing Letters". 
As for the article, they seem to be 'handwaving' about all reals being represented.
A proof that all reals cannot be represented by their representation:
Suppose each real could be represented in the form given in the paper, then the reals would be countable, but by Cantor's diagonal argument...
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Countability of Real Numbers
« Reply #6 on: Nov 19th, 2004, 7:39am » |
Quote Modify
|
A week later there appeared this.
Some observations (not my own):
1) Among other "interesting" things in this paper, we learn that 0 is transcendental and that an interval of rationals is compact in R.
2) Well, it's certainly a nice-looking paper. While I have no comment on Theorems 1 - 3, it doesn't look to me as if their counterexample in Theorem 4 is legitimate. At the bottom of page 9 they use an analogue of Cantor's work to show that the rationals are nondenumerable, since the Cantor construction would provide a rational, namely 1, that wasn't in the enumeration of the rationals. Far from yielding a contradiction, all this shows is that their proposed enumeration wasn't a list of *all* the rationals. Take
a look at what it would have to be; it would have to look like
this
... , 2/3, ... , 3/2, ... , 3/4, ... , 4/3, ...
(the order of appearance of, say, 2/3 and 3/2 could be reversed, but that's immaterial in generating their intervals). Now note that no element in the first two ellipses could be in (0, 2), no element in the second pair of ellipses could be in the
interval (2/3, 3/2), and so on. In other words, 1 could not
appear anywhere in their list. Whaddya know? The Cantor
construction found a number not in their enumeration, just
as it promised to do.
|
| « Last Edit: Nov 19th, 2004, 7:40am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Countability of Real Numbers
« Reply #7 on: Nov 19th, 2004, 5:27pm » |
Quote Modify
|
They say if you can't dazzle them with brilliance, then baffle them with b*s*. Alas, our brave authors seem to have gotten it backwards and are baffling themselves with b*s*.
I have only managed to decipher part of their fractured logic, but here is what I have figured out so far.
They are claiming that all real numbers can be expressed in the form a^b^c^...^d, where a,b,c,...,d all have form r^s^t, with r, s, t rational.
As first step, they claim that every algebraic number (i.e. every root of a polynomial with integer coefficients) can be expressed in this fashion. I find this unlikely, but will not dispute it, particularly since their argument would work with just the rational (if it worked at all), and the rationals are obviously representable in such a fashion. But where they really fall down is the next step:
Theorem 2 proportedly proves that the set S of all numbers so reprensentable is in fact all of the Reals. They attempt to do this by using Dedekind cuts of the algebraic numbers (a concept which they clearly do not understand). They take an arbitrary cut of S into two sets A & B (this means that A & B are not empty, A[cup]B = S, and every element of A is less than every element of B). They then consider the real number k which must represent the cutting point (i.e. for a [in]A, b[in]B, a[le]k[le]b). Since S is dense, k is uniquely defined by this requirement. They purport to show that k is either in A or in B. If they actually did this, their theorem would be true (and incidently, the same argument would also show that the set Q of rationals would also be the entire reals).
But they spend all of their argument showing that if k is in A, then it is the highest element of A (well, duh!). Having produced the obvious by convoluted logic, they then say the same shows that if k is in S\A = B, then it is the least element of B! (Duh again!). NOW they proclaim this proves the theorem  , having totally failed to realize what they put all their effort into is entirely beside the point of what they needed to prove: that k must be in either A or B, and therefore in S. They failed to consider the one thing they actually needed to show: what if k is not in A or in S\A, because k is not in S?
If the proof of theorem 2 actually worked, it would mean that [bbr] has no dense subsets other than itself (since any dense subset can be used for Dedekind cuts). Since the Rationals are dense, this would provide a much simpler proof of the countability of the Reals!
I haven't looked at theorem 3 yet (which supposedly offers a second proof that S = [bbr], but am quite sure it too is flawed.
|
| « Last Edit: Nov 19th, 2004, 8:07pm by Icarus » |
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
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Countability of Real Numbers
« Reply #8 on: Nov 19th, 2004, 6:49pm » |
Quote Modify
|
Okay, the fall of "Theorem 3": They, by handwaving, assert that there exists a set M2 [subseteq] S (which I will call just M because I am too lazy to put that subscript down every time) which is
(a) Dense in S (between every two elements of S is an element of M.
(b) Has dense compliment (between every two elements of M is an element of S\M).
They are correct about this: the Rationals [bbq] have this property as a subset of S.
As their "proof" progresses, they get to a point where they have M cut into two sets A, B ([phi](-[infty],x)M1 & [phi](x, [infty])M1). So A < B (where the inequality applies to every element of A and B) and A [cup] B = M. They now claim that by (b) there must be an element x [in] S such that A <= x and x <= B. Unfortunately, this does not follow at all. If we chose a [in] A and b [in] B, then (b) tells us there is a s [in] S (and not in M) such that a < s < b. This does not mean though that A <= s or that s <= B, though. It is quite possible that there is another element a' [in] A such that s < a' or an element of B which is less than s.
Once again, the rationals provide a simple counterexample of his proof: the rationals
1) Do not have a greatest or least element.
3) Are separable (i.e. have a countable dense subset - themselves)!
They also have subsets V that are dense and have dense complements. For example, let V be the set of all fractions of the form m/2n. Then
(a) V is dense in [bbq]: for r<s [in] [bbq], choose n such that 2-n < s-r. Since the interval (r,s) is wider than the separation between adjacent fractions of form m/2n, for all m, and since such fractions can be as large or small as possible, at least one must lie within (r,s).
(b) [bbq]\V is dense in [bbq]. Let m/2n and p/2q be distinct elements of V, with n > q. Then we can write p/2q = k/2n, where k=2n-qp. Let u >km be prime. Then (m(1-1/u)+k/u)/2n is not in V and lies between m/2n and k/2n = p/2q.
Now, all the elements of the "proof" of theorem 3 apply to [bbq] and V just as well as they do to S and M. If the theorem were true, we once again have [bbq] = [bbr], and a much simpler proof that [bbr] is countable, and as an added bonus, we no longer have to deal with those nasty irrational numbers like [surd]2 and e and [pi]!
But, alas, for any cut of V into two sets, if I give you two elements, one from each set, and you give me an element of [bbq]\V between them, I can also give you another element of V either in the lower set which is higher than your number, or else in the upper set which is lower than your number. C'est la vie, irrational after all!
|
| « Last Edit: Nov 19th, 2004, 8:04pm by Icarus » |
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
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Countability of Real Numbers
« Reply #9 on: Nov 19th, 2004, 8:03pm » |
Quote Modify
|
No, I am not shamelessly padding my post count!  I am addressing several issues and wanted to break them up.
Their theorem 4 has already been adequately rebuffed by the stuff T&B quoted. In theorem 5, it is evident that they are clueless as to the nature of Cantor's diagonal argument. They claim that the difference between the diagonally created real number x and the sequence element rn is 10-n, and because the limit of 10-n goes to 0, the difference between x and "all other numbers" is zero. This is the sort of reasoning I expect to see from half-baked freshmen responding to the 0.999... thread, not from those who would claim to produce genuine mathematics.
First of all, x does not have a "difference between" it and "all other numbers". It has differences between it and each of the elements of the sequence. And those differences are >0 for every last single element. Therefore it cannot be any of the elements, and so the sequence does not contain x! And since it does not contain x, it cannot be an ennumeration of the entire reals.
Second, contrary to their claims, the difference between x and rn does not have to be 10-n (or even on the order of 10-n). x is constructed to differ from rn in the nth digit, but that does not mean it agrees in any of the other digits. The difference may be significantly greater if x happens to disagree in an earlier digit as well. It can also be somewhat smaller, if rn has higher digits than x in the positions past the nth.
_____________________________________________________
Since they have so badly botched the statement and proof of Cantor's nested intervals argument, and because I find it appealing, I would like to give a (hopefully) clearer account of it:
Theorem (Cantor): For any sequence {rn} of real numbers, and any open interval (a,b), there exists at least one number x [in] (a,b) such that x [notin] {rn}.
Proof:
Note that between any two numbers x < y, there is at least one other number z: x < z < y. In particular, you can let z = (x+y)/2.
We define two sequences {an} and {bn} inductively, so that the sequences have the properties that
(1) a < a1 < a2 < ... < ... < b2 < b1 < b.
(2) For all n, rn [notin] [an, bn].
Initiation step: Let a0=a, b0=b
Induction step: Assume an and bn have been defined.
If rn+1 [in] (an, bn), then let y= rn+1. Else, let y = bn. In either case, an < y [le] bn. Choose an+1, bn+1 so that an < an+1 < bn+1 < y [le] bn.
It is trivial (i.e., I am not going to bother proving it) to see that the sequences {an} and {bn} have the desired properties.
Note that for all k, bk is an upper bound for the set {an}. Let x be the supremum (least upper bound) of {an}. Since x is an upper bound, for all n, an [le]x. Since x is the least upper bound, for all n, x [le] bn. So x is an element of [an, bn] for all n.
For all n, rn [notin] (an, bn), but x [in] [an+1, bn+1] [subset] (an, bn). Therefore x [ne] rn.
I.e. x is not in the sequence {rn}. QED
(The Vlahovics go to great lengths to point out that x need not be any of the numbers an or bn. In fact they fall short. x not only need not be, it cannot be any of these numbers. What is puzzling is that they assume this is some sort of contradiction. There is no claim or use of such an identity anywhere in the proof.)
|
| « Last Edit: Nov 19th, 2004, 8:05pm by Icarus » |
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
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Countability of Real Numbers
« Reply #10 on: Nov 19th, 2004, 9:38pm » |
Quote Modify
|
Just had a look at the second paper T&B linked to. This is unbelievable. They have NO clue as to what Cantor is saying, and yet are so determined to disprove it. So they mix together entirely separate proofs and show that the misbegotten result has a flaw in it! Who would of guessed such a thing!
Here is what they think they are "disproving": If A is a 2-element set, and B is the set of all sequences into A, then B is not countable (there is no sequence in B that included every element of B).
Note that contrary to what the Vlahovics are pretending, A and B are NOT sets of numbers. The use of this version of the argument to show indenumerability of the Real numbers requires a separate second step which they ignore, so that they can throw out a sequence from B, then pretend that the diagonal sequence will be the discarded one, and therefore it won't count!
For some reason, they are using "m" and "w" as the elements of their 2-element set. I don't know if this is something Cantor did, and they are just repeating, or someone else introduced it along the way. But I will continue it:
Theorem (Cantor): Let A = {m, w} be a set of two elements, and let B = { {an} : an [in] A for all n [in] [bbn]} be the set of all sequences in A. Then B is not countable.
Proof: Let E = {ek} be a sequence into the elements of B. Thus each ek is itself a sequence ek = {ekn} into A, and so for all k, n, ekn = m or w.
Define ai = w if eii = m, and ai = m if eii= w. Let a [in] B be the sequence {an}. Clearly, a [ne] ek, since ak [ne] ekk. Hence B has at least one element that does not occur in the sequence E. Since E was arbitrary, there is no sequence of elements of B which included every element of B. I.e., B is not countable. QED.
The Vlahovics were not able to find a flaw here, so they misinterpret the sequences in B as being numbers, label the two constant sequences M = (m, m, m, ...) and W = (w, w, w, ...), and reinterpret B as being the "open interval (M, W)". Why? Because then B doesn't contain the sequences M, W (where as in Cantor's actual theorem - as restated here - B most certainly does contain them).
Now that they have capriciously thrown out two sequences from B, they note that there is nothing preventing the constructed sequence {an} from being W. Horrors! W is not in B! Cantor was clearly wrong!
In fact, as I said, This was only one stage in proving by this means that the Real numbers are not countable. B is not a set of numbers. It is a set of abstract sequences. By its definition, it contains ALL sequences into A, including M and W. The next step in this process is to show that B can be placed in one-to-one correspondence with some subset of the real numbers. In particular, we can map our two element set A to the set {1,2} and interpret the resulting sequences as producing base-4 decimal expressions. (Why base 4 instead of base 2? And why {1,2} instead of {0,1}? Because decimal expressions, in any base, are not always unique. See the 0.999... thread. By making these choices, I avoid any expressions that have alternate forms.)
For instance M maps to the number 0.111...4, and W maps to 0.222...4, both of which are well inside open interval (0,1). In fact all elements of B map uniquely to numbers in (0,1). Which means that (0,1) has at least as many elements as B (there are quite a few elements of (0,1) that do not correspond to any element of B in this way, but every element of B corresponds to exactly one element of (0,1)). Indeed, if you were given an enumeration of all the elements of (0,1) you could use it to produce an enumeration of B, contrary to Cantors theorem above. Therefore, (0,1) is not countable either.
Of course, if your purpose is simply to prove uncountability of (0,1), there is an easier version of Cantor's diagonal argument: Let {ek} be a sequence into (0,1), and let ekn be the nth digit (base 10) to the right of the decimal. For definiteness, if ek has two decimal notations, we use the one with trailing zeros (i.e., terminating). For each k, choose the digit dk to be different from 0, 9, and ekk. Construct d= 0.d1d2.... d [ne] 0, since we did not pick any "0" digits. It is not equal to 1 since we did not pick any "9" digits. It is not equal to ek for any k because it differs from ek in its kth digit - and does so in a fashion that does not allow for alternative decimals expressions for the same number. Thus d is in (0,1) but not in the sequence. So once again, (0,1) is not countable.
|
|
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
|
|
|
kellys
Junior Member
Gender:
Posts: 78
|
|
Re: Countability of Real Numbers
« Reply #11 on: Dec 28th, 2004, 4:52pm » |
Quote Modify
|
Hehe that was a good laugh. In their defense, it looks like Branislav is actually a physicist, and I'm guessing Slavica is a Croatian relative who pressured him into being a coauthor without reading the article. My favorite line is when they try and disprove Cantor,
Quote:| The idea of his proof is that in the arbitrary assumed denumerable set of real numbers, each element of the set, each real number, has to be related by a one-to one correspondence to a natural number, which has a final value. That is, any real number has to take a finite place in that sequence. |
|
Clearly we need to go back over what the definition of a sequence is. In fact, that whole section is priceless.
|
| « Last Edit: Dec 28th, 2004, 6:14pm by kellys » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print