Cantor's Diagonal Proof: FLAWED!
Mark Adkins
My earlier argument against Cantor's diagonal proof was invalid: I've
satisfied myself that in the real number system the only dual decimal
expansions (i.e., the only pairs of different decimal expansions
which define the same limit point on a line) are those which
eventually continue with an infinite number of nines or an infinite
number of zeroes in sequence; e.g., .24559871249999999... and
.2455987125000000... are dual; and these are easily avoided in
diagonal constructions (if not impossible to construct diagonally).
The duals are also countable.
HOWEVER, I've discovered what seems to be a different logical flaw
in Cantor's diagonal argument. "This time for sure..."
We begin Cantor's process as usual by asserting the existence of a
putative list of all reals for the sake of the reductio ad absurdum
argument. Then we begin constructing a diagonal number, say, to
1,000 digits.
Since we have assumed from the start that the list is a complete
list of all numbers (whether such an assumption is true or not
then remains to be seen), we know that at some future step n, which
may be 10,000 steps beyond the current one, or 1,000,000 steps or
1,000,000,000 steps beyond it, there will be a real number on the
list which is identical out to n digits to the diagonally constructed
number at the current step. For example, at the 1,000th step, we
have a diagonally constructed number such as:
.24639194...0973 [contains 1,000 digits and "3" is the last]
whereas at some future step n > 1,000 we have a number on the
list which is identical to this out to 1,000 digits:
.24639194...0973... [is infinite but is identical to the number above
out to the second elipses]
Of course, when we complete n steps of diagonal construction, we will
also have produced a diagonal number which is different from the list
number at step n (and from every list number preceding it). However,
because we have assumed from the start that the list is complete, we
know that at some future step -- call it step n+m -- there is another
list number which is identical to the diagonally constructed number
at step n out to n digits.
Now it should be obvious that for any partially constructed diagonal
number, there is a real number on the list which is identical to it
to the same precision as the partial diagonal.
The usual reasoning is that because the fully constructed diagonal
number is infinite, it must therefore be different from *every* list
number in at least one decimal place, and thus the initial assumption
that the list is complete was false: therefore, there is no list
containing all reals, and since the concept of "countable" is a priori
synonymous with "listable", the conclusion drawn is that the set of all
reals is uncountable.
However, it is clear that at any finite step n the list is "ahead" (in
the sense described above) of the diagonally constructed number. Then,
at *every* finite step n the list is "ahead" of the diagonally
constructed number. There are aleph_0 digits in the diagonal number,
since this is the cardinality of the natural numbers indexing the
individual steps in its construction, but there is no omega-th digit
since there is no natural number omega (omega being an ordinal and
aleph_0 being the corresponding cardinal); there are also aleph_0
numbers on the putatively complete list of reals, though there is no
omega-th list number since each of those is indexed with a natural
number as well.
But if the list somewhere contains (to n digits of precision) the
partially constructed diagonal number having n digits at EVERY finite
step n, and there are no other steps, then the list must *always* be
ahead of the diagonal. In other words, any such list which is infinite
*and* assumed to contain every real number WILL contain EVERY number
which it is possible to diagonally construct from the list.
Then, the correct conclusion is not the usual one (that it is possible
to diagonally construct an infinite number which is not contained in
the list), but rather, that IT IS IMPOSSIBLE TO DIAGONALLY CONSTRUCT
AN INFINITE NUMBER FROM SUCH A LIST WHICH IS DIFFERENT FROM EVERY
NUMBER IN THE LIST.
This may appear to be nonsense, since one can continue the diagonal
construction process indefinitely. That is, there is no finite step n
beyond which we cannot continue the diagonal process to step n+1. But
at step n+1, just as at step n, the "partially constructed diagonal
number" will ACTUALLY have an infinite decimal expansion of the
following general form:
.xxxxxxxx...xxxx000000000...
where it is understood that the first elipses represents an arbitrarily
large but finite number of digits, and the final elipses represents an
infinite continuation of zeroes.
That this is true is obvious from the fact that every real number has
an infinite decimal expansion of one sort or another. For example,
the natural number "1", which is a real number (the naturals being
a subset of the reals) is understood to have an infinite decimal
expansion: 1.000000000...
Thus, the number constructed at the 1,000th step as described in the
example above would have an infinite decimal expansion like this:
.24639194...0973000000000... [1,000 digits through the final "3" then
followed by an infinite number of zeroes.]
So that somewhere ahead of the 1,000th number on the putative list of
all reals, there is not only a real number which is identical to this
out to the 1,000th digit, but there is a real number which is *exactly*
the same as this to infinite precision. That is, at the 1,000th step
what we have actually constructed through the diagonal process is
the rational number .24639194...0973000000000... and somewhere else
on the list (beyond the 1,000th list number) is this exact same
rational number.
Now, when we started with the assumption that the list of reals
from which diagonal construction would proceed was a complete list
of reals, we guaranteed that this would not theoretically exclude
any class of real numbers. For example, we know that such a list
will contain irrationals as well as rationals, and there is thus
an a priori assumption (true or false) that it contains all of the
irrationals, since these are a subset of the set of all reals.
Since we know that the rationals are listable, and the purpose of
Cantor's diagonal construction is to demonstrate that the set of
all reals is not listable, then we know that the diagonally
constructed number *must* be irrational: we know we can construct
a list guaranteed to contain all rationals, and therefore such a
list would contain the diagonal number if it were rational: therefore
it must be irrational.
Then there are actually TWO logical possibilities:
(1) The diagonally constructed number is an irrational different from
any irrational in the list, and therefore the list is not complete
as originally assumed.
(2) IT IS IMPOSSIBLE TO CONSTRUCT AN IRRATIONAL NUMBER FROM SUCH A
LIST USING THE DIAGONAL METHOD.
Note that we have demonstrated that at *every* finite step, the
so-far constructed diagonal number is a rational with infinite
decimal expansion of the form .xxxxxxxx...xxx00000000...; that this
is true for all finite steps and that there are no other steps.
Then since no irrational is diagonally constructed at any step,
no irrational is diagonally constructed.
So, instead of constructing a single irrational number which is only
partially complete at each finite step, Cantor's diagonal process
never actually constructs an irrational, but actually constructs an
infinite list of rational numbers each of which has the infinite
decimal expansion .xxxxxxx...xxx0000000... (where it is understood
that the first elipses represents an arbitrarily large but finite
number of digits, whereas the second elipses continues the zeroes
forever). But since we know we can construct a list of all rationals,
then the putatively complete list of all reals contains all of the
rationals: thus, every one of the rational numbers constructed by the
diagonal process at every step will be contained by the putative list
of all reals and will in fact constitute a proper subset of this list.
Q.E.D.
Note: if it is not already clear, each step n in the Cantor diagonal
process produces a rational number having n digits. The first such
number (restricting ourselves to the unit interval for clarity) will
have the form: .x0000000... and the second such number will have the
form .xx0000000... and so on.
Richard Carr
:Date: Mon, 21 Sep 1998 01:10:33 -0400 (EDT)
:From: Mark Adkins <adk...@cyberspace.org>
:Cc: Mark Adkins <adk...@grex.cyberspace.org>
:Newsgroups: sci.math
:Subject: Cantor's Diagonal Proof: FLAWED!
:
:"Hey Rocky, watch me pull a rabbit out of my hat..."
:
:My earlier argument against Cantor's diagonal proof was invalid: I've
:satisfied myself that in the real number system the only dual decimal
:expansions (i.e., the only pairs of different decimal expansions
:which define the same limit point on a line) are those which
:eventually continue with an infinite number of nines or an infinite
:number of zeroes in sequence; e.g., .24559871249999999... and
:.2455987125000000... are dual; and these are easily avoided in
:diagonal constructions (if not impossible to construct diagonally).
:The duals are also countable.
:
:HOWEVER, I've discovered what seems to be a different logical flaw
:in Cantor's diagonal argument. "This time for sure..."
This isn't going to turn into a James Harris type thread is it. At least
he's nominally trying to prove something which canbe proven, not something
which, assuming consistency, can't.
:
:We begin Cantor's process as usual by asserting the existence of a
I see you're using the axiom: "if I write in capitals then everyone will
be convinced that I am right" as employed by JJ (regarding Sollog) etc.
:
:This may appear to be nonsense, since one can continue the diagonal
This is obvious.
:no irrational is diagonally constructed.
This is false. Any irrational number is the limit of a set of rational
numbers, since the rational numbers are dense in R. In particular we can
take the sequence of truncated decimal approximations to an irrational
number and the limit is irrational.Similarly the number constructed
diagonally is also irrational.
:
:So, instead of constructing a single irrational number which is only
:partially complete at each finite step, Cantor's diagonal process
:never actually constructs an irrational, but actually constructs an
:infinite list of rational numbers each of which has the infinite
:decimal expansion .xxxxxxx...xxx0000000... (where it is understood
:that the first elipses represents an arbitrarily large but finite
:number of digits, whereas the second elipses continues the zeroes
Yes, but they form a Cauchy sequence in R, which is complete, and
therefore converge to a real number r. This real number must be irrational
and not on the list (as it differs from the nth member of the list at
stage n for each n and, since the list has type omega, it therefore
differs from every member of the list.)
:forever). But since we know we can construct a list of all rationals,
:then the putatively complete list of all reals contains all of the
:rationals: thus, every one of the rational numbers constructed by the
:diagonal process at every step will be contained by the putative list
:of all reals and will in fact constitute a proper subset of this list.
:
:Q.E.D.
:
:Note: if it is not already clear, each step n in the Cantor diagonal
:process produces a rational number having n digits. The first such
:number (restricting ourselves to the unit interval for clarity) will
:have the form: .x0000000... and the second such number will have the
:form .xx0000000... and so on.
:
The point is this- omega, although an infinite ordinal, is such that every
initial segment is finite. Assume the reals are countable. Then they can
be ordered in type omega, so we do so, say {r_n: n<omega}, which contains
all the rationals. It is important to use type omega. Using a higher type,
like omega+1 will not work, as we could get the last member of the list as
our real number since the type of the digits in a number fully decimally
expanded is omega (counting terminating 0's). This doesn't matter since
any countable set can be ordered in type omega, not always definably
admittedly but nonetheless, it can be done.
Apply the diagonal process, avoiding 0's and 9's if you like to get a real
number r, which is the limit of the rational approximations obtained in
the diagonal proces. Since r_n differs from r in the nth decimal place
then r is not in the list (so r cannot be rational). This means that {r_n:
n<omega} is not closed in R, since the accumulation point r, is not in it.
There is no reason to suppose that it should be either. Nonetheless, r
does exist, it is the limit of a Cauchy sequence- the rational
approximations- in R, which is complete.
Another way to do this is to use Cantor's theorem that the power set of a
set X never injects into X. To this end, if f were a function from P(X)
into X, then R={f(A):A is in P(X) and f(A) is not an element of A} which
exists by a subset axiom satisfies f(R) is an element of R iff f(R)=f(B)
for some subset B of X for which f(B) is not an element of B. If f(R) is not
an element of R, then f(R) is an element of R. This is a contradition.
Thus f(R) is an element of R then we get a B as above and we must have B
not equal to R so that f is not injective.
In particular, P(N) cannot inject into N. Since R is bijective with P(N) R
cannot inject into N. Thus N and R must have different cardinalities.
Since N injects into R, we have that R is uncountable.
(To get a bijection between R and P(N) first biject R with (0,1) using
f(r)=(tan^{-1}(r)+pi/2)/pi. We can inject (0,1) into P(N) by using dyadic
representation and setting f(sum i_n/2^n)={n:i_n=1} where the sum is from
1 to infinity over i and where, w.l.o.g. we take the terminating expansion
should the choice arise. So we can inject R into P(N). We can inject P(N)
into R by sending A to sum i_n/2^n where i_n=1 if n is in A and 0
otherwise if A does not contain a final initial segment of N and to
2+sum i_n/2^n with i_n as before, if A does contain a final initial
segment of N. Then by the Schroder-Bernstein theorem, R and P(N) have the
same cardinality. Of course, we only need to have an injection from P(N)
to R and to know that P(N) is uncountable.
Jeroen Bruijning
>"Hey Rocky, watch me pull a rabbit out of my hat..."
... and goes on to expose a "flaw" in the Cantor proof of the uncountability
of R.
Now, philosophically speaking one can have an uneasy feeling about the
Cantor process. There is something about reasoning about "infinite
constructions" that one may feel is not quite right. There is nothing
against exploring these ideas, indeed, important mathematicians like Brouwer
have taken that road.
It is important however to realize that one is then essentially questioning
the very definition of the mathematical reasoning employed. This you cannot
do from within the system. In other words, even if you feel that the Cantor
result is "wrong", there is no way to refute the proof using standard
mathematical arguments. In standard mathematics the Cantor proof works,
however you may dislike it. (Please understand that so-called non-standard
analysis as in Robinson's book is actually perfectly standard mathematics.
One can get confused very easily here.)
Let me just for the sake of the discussion explain the mathematical flaw in
your attack. From the correct observation that at no finite stage in the
process you can be sure that the number "constructed" is nowhere in the
list, you deduce that "in the end" it will not have been "constructed"
either. This is an invalid inference. Why? Because the process defines all
digits of a perfectly passable real number that's not in the list, that's
why. Nothing wrong with the reasoning here except that the outcome
apparently offends your intuition. But that is why we have strict reasoning
in mathematics, to learn more than intuition alone can tell us.
(I pass over the use of the word "constructed" which suggests all kinds of
things that are not mathematically relevant. It would be better to use the
word "defined" in this instance. I also gloss over a number of minor faults
in the argument, such as that all the rationals will be in the list just
because they form a countable set, and that at any finite stage one actually
has constructed a number whereas on, in fact, has defined only a number of
digits.)
But all of this diverts the attention from this: if you want to expose a
flaw in Cantor's proof, forget it. You won't.
If you want to explore why Cantor's proof offends your intuition, go ahead.
But realize that what you try to do is not expose errors in mathematical
statements or reasoning, but instead attack the definition of mathematical
reasoning itself. This is very interesting and heroic, but please realize
that it is very difficult to do this in a meaningful way. Some of the finest
mathematical minds have struggled with this, without too much success (or at
least recognition) so far. It is not difficult to feel uneasy about issues
involving infinity, but it is exceedingly difficult to ask the RIGHT
questions, and even more difficult to come up with meaningful answers.
In any case to have a chance of doing something meaningful one needs very
good knowledge of existing mathematics in the first place(Brouwer did very
deep and important things in classical mathematics before he published his
intuistionistic ideas). You can't attack what you don't understand. After
that, one needs to learn how Brouwer and others have sought for
alternatives. Only then one can have any hopes of coming up with meaningful
ideas. There is no substitute for hard work, alas.
So if you are serious about this, and serious about being taken seriously,
you have much work to do. I should also add that you need to be a real
genius.
See you a few years from now. Otherwise, enjoy but forego all ambition of
being mathematically relevant.
Greetings, Jeroen.
Mark Adkins
diagonal proof -- that the diagonal process actually produces a
countably infinite set of rationals and not an irrational missing from
the putatively complete list of all reals -- the following obvious
problem suggests itself:
Every infinite decimal expansion is either rational or irrational.
The "fully completed diagonal number" is an infinite decimal expansion.
Is it rational or irrational? If it is rational, then it is on the
putative list of all reals because the set of all rationals is
listable: but it cannot be on that list because it is different from
each member of that list in at least one decimal place. Therefore it
would seem to be irrational, in which case the putatively complete list
of reals is not actually complete. To make this even clearer, start
with a list of all rationals (but *only* rationals).
But there is a fly in this ointment!
Is the "fully completed diagonal number" random or algorithmic? Any
pseudo-random number generator will produce a number which eventually
repeats, and every pseudo-random number generator is algorithmic; but
if the number eventually repeats, it is rational. Then, the diagonal
construction process must be genuinely random rather than equivalent
to a pseudo-random number generator. But if we specify an actual list
of all rationals in binary expansion, then every digit of the diagonally
produced number is uniquely determined at each step: if the nth digit of
the nth binary expansion is a 1, then add a 0 to the diagonal
construction, and if it is a 0, add a 1. There is no choice. Then the
diagonal construction process can't be random and the produced number
must be pseudo-random and therefore rational.
At this point, somebody might object: pi is finitely describable, but
it doesn't eventually repeat, therefore we have an example of a random
number which is produced by an algorithm. But in fact, all algorithms
compute some number which is the same as pi to an arbitrarily large
but finite amount of precision, after which this number diverges from
pi. If it were possible to produce all the digits of pi and only the
digits of pi in sequence from an algorithm, then we could use an
algorithm to generate an inexhaustible random sequence of zeroes and
ones (in binary expansion) -- a random sequence of heads and tails --
since pi never repeats. (We could argue about the randomness of
nameable subsequences of pi, but you see my point.)
In order to construct a list of all rationals, we must say how to
produce a specific ordering of the set of all rational binary
expansions, because the concept of ordering is inherent in the concept
of "list". There are no unordered lists, though there can be unordered
sets. Also, without a specified ordering of the set of all rational
binary expansions, the instruction "if the nth digit of the nth number
is a 1, add a 0 to the diagonal construction, and if it is a 0, add a 1"
has no meaning, because there is no nth binary expansion defined, and
thus "the nth digit of the nth binary expansion" is also undefined.
Lists of all rationals must be constructed by initially specifying the
rationals as ratios of two integers p/q. This is because p/q is finite
whereas .3333333... or .1283745454545... aren't. If you limit yourself
to decimal (or in our case, binary) expansions, then even if it were
possible to construct an actual list of these guaranteed to contain all
rational expansions, you will never finish specifying any such number
in the list, and you will never be able to move to the next step in
the construction of the diagonal number. If you begin with expressions
of rationals as ratios of two integers, not only can you produce a
comprehensive list ("list" implying a specific ordering of the set of
all rationals), then it also isn't necessary to compute each rational
to infinite precision: just compute it to n digits at the nth step of
diagonal construction and move on. Thus, you begin with an algorithm
which is guaranteed not to overlook any rationals, and you produce
the first element, which is an integer ratio p/q, then you compute
p/q as a binary expansion to n digits of precision (at this first step,
1 digit), then you write the opposite binary number in the nth place
of the diagonal number (at the first step, the first place). Wash,
rinse, repeat.
This is where the fly in the ointment appears. Every computation
producing the binary expansion of an integer ratio p/q to n digits
of precision at step n of the diagonal process, is truncated and
therefore has a full binary expansion ending with an infinite sequence
of zeroes, whereas we know that there are rational numbers which do
not end with an infinite sequence of zeroes. But now look what's
happened: you've replaced a complete list of all rationals expressed
in integer ratios p/q, with an INCOMPLETE list of rationals expressed
in truncated binary expansions.
What you're actually producing your diagonal number from, then, is
an incomplete but infinite list of rationals, i.e., an infinite
proper subset of the rationals. Then, when you construct a diagonal
number which is different from every member of *this* list in at least
one place, you are actually producing a rational number which is not
on the list, not an irrational number.
There is no way around this: every diagonal number is a constructively
produced number. In order to constructively produce a diagonal number,
you must specify a list of numbers from which to construct it, so that
the outcome of each step is defined. If the list is to be a complete
listing of rationals, then you have to produce an ordering of the set
of all rationals, since a priori a list is an ordered set. (Note
that the list thereby produced is a well-ordered set: the list has a
first member, and each member in turn can be indexed with a distinct
natural number taken in sequence; then since the naturals are
well-ordered, so is the list indexed to them, since any subset defines
a subset of the naturals, and every such subset of naturals has a first
element.) Since the diagonal process works from rational expansions
rather than ratios of integers, you must then compute rational
expansions from ratios of integers. But any rational expansion from
which a digit of the diagonal number is constructed is a truncated
rational expansion (i.e., computed only to n digits), and such a number
has a full expansion ending with an infinite sequence of zeroes.
In proofs claiming to demonstrate the uncountability of the irrationals,
one never gets around to specifying an actual list: one merely specifies
a set (the set of all rationals) and orders a finite number of elements
from this set in order to demonstrate the reductio ad absurdum argument.
But one cannot actually construct a "fully complete diagonal number"
this way. The only way to construct a fully complete diagonal number
is to specify an ordering of the set of all rationals, and then the
number produced diagonally is a rational number because the constructive
list of binary expansions from which the diagonal is fully constructed
is a list of truncated rationals and therefore is an infinite but
incomplete list of rationals.
Jeroen Bruijning
Mark Adkins wrote in message ...
>P.S. With regard to my second attempt to demonstrate a flaw in Cantor's
>diagonal proof -- that the diagonal process actually produces a
>countably infinite set of rationals and not an irrational missing from
>the putatively complete list of all reals -- the following obvious
>problem suggests itself:
Do you ever read replies to your postings?
Anyway, in my previous reply I stated that within standard mathematics you
will never shoot a hole in Cantor's proof. I will now substantiate that
statement by showing where you are wrong. This will be my last such attempt.
In the first place, your argument seems to rest partly on the assumption
that a "Cantor listing" of the reals must contain the rationals. In reality,
this is of no interest at all. What Cantor shows is that, whatever infinite
list of reals you start with, there exists a real that is not on that list.
Note the word "exist". Nowhere in the proof it is suggested that the list is
the result of the execution of some algorithm, nor that there is an
effective way of coming up with a real that is not on the list. If there is
no algorithm to produce the list, there will very likely be no algorithm to
produce the exception. In mathematics often we assume the "existence" of
some entity, and then prove the "existence" of some other entity from that.
Only in special and uncommon approaches to mathematics one expects and
demands "computability" in order for a result to be accepted. This is
exactly what you are implicitly doing. In classical mathematics, "existance"
and its consequences are undefined but central concepts. If you don't like
that you place yourself outside main stream mathematics. No intrinsic
problem with that, as explained in my previous post, but important to
realize in order not to enter in debate that can have no outcome. Classical
mathematics looks very consistent so far and there is nothing in your
postings that suggest that you will be able to show otherwise (just my
opinion of course).
To further disappoint you, note also that a constructivist version of
Cantors proof also works. Suppose we have an algorithm that produces a list
of reals. By this I mean that the algorithm can give me the m-th digit of
the n-th entry on the list. Then the standard reasoning gives us an
algorithm to produce a number (i.e. any desired digit of that number) that
demonstrably is not on the list. QED. (This is only an outline of a proof,
to be sure. Of course you will have to define precisely what an "algorithm"
is, how you can construct new algorithms from old ones, etc.)
As an aside, what makes you say that no algorithm will give you all of Pi?
In fact, it is very easy to define an algorithm that produces any desired
digit of Pi, e, or many other reals (but not all of them). Just sum the
beginning of a suitable series with rational terms that produces Pi and you
are done. It is easy to know how far you must go for a given digit to be
certain.
Some small comments, relating to the above:
>
>Every infinite decimal expansion is either rational or irrational.
>The "fully completed diagonal number" is an infinite decimal expansion.
>Is it rational or irrational? If it is rational, then it is on the
>putative list of all reals because the set of all rationals is
>listable:
Nowhere in the proof it is claimed that the rationals are all in the list.
See above.
[snip]
>
>Is the "fully completed diagonal number" random or algorithmic? Any
>pseudo-random number generator will produce a number which eventually
>repeats, and every pseudo-random number generator is algorithmic; but
>if the number eventually repeats, it is rational. Then, the diagonal
>construction process must be genuinely random rather than equivalent
>to a pseudo-random number generator. But if we specify an actual list
>of all rationals in binary expansion, then every digit of the diagonally
>produced number is uniquely determined at each step: if the nth digit of
>the nth binary expansion is a 1, then add a 0 to the diagonal
>construction, and if it is a 0, add a 1. There is no choice. Then the
>diagonal construction process can't be random and the produced number
>must be pseudo-random and therefore rational.
Pi is an example of a computable number that is non-repeating. Seemingly,
this is what you mean by "random".
>
>At this point, somebody might object: pi is finitely describable, but
>it doesn't eventually repeat, therefore we have an example of a random
>number which is produced by an algorithm. But in fact, all algorithms
>compute some number which is the same as pi to an arbitrarily large
>but finite amount of precision, after which this number diverges from
>pi.
Not true.
>If it were possible to produce all the digits of pi and only the
>digits of pi in sequence from an algorithm, then we could use an
>algorithm to generate an inexhaustible random sequence of zeroes and
>ones (in binary expansion) -- a random sequence of heads and tails --
>since pi never repeats. (We could argue about the randomness of
>nameable subsequences of pi, but you see my point.)
I see your point, but it is not valid. We can indeed use an algorithm to
produce an inexhaustible non-repeating sequence of zeroes and ones
(presumably, that is, because this is effectively a claim about Pi of which
I do not know the truth; but for the argument this is immaterial because the
claim does hold for the decimal expansion of Pi). But such a sequence,
non-repeating as it may be, is not "random" in an essential sense because it
can be concisely defined. You confuse randomness (not precisely defined in
this context, to be sure) with non-repeatability.
[snip]
>In proofs claiming to demonstrate the uncountability of the irrationals,
>one never gets around to specifying an actual list: one merely specifies
>a set (the set of all rationals) and orders a finite number of elements
>from this set in order to demonstrate the reductio ad absurdum argument.
>But one cannot actually construct a "fully complete diagonal number"
>this way. The only way to construct a fully complete diagonal number
>is to specify an ordering of the set of all rationals, and then the
>number produced diagonally is a rational number because the constructive
>list of binary expansions from which the diagonal is fully constructed
>is a list of truncated rationals and therefore is an infinite but
>incomplete list of rationals.
Are you implying here that there cannot be a complete listing of the
rationals? That would show that the rationals are uncountable. Talking about
a surprising result!
I will not repeat my advice. Read my previous posting.
Best of luck,
Jeroen.
Norman D. Megill
Jeroen Bruijning <J.Bru...@research.kpn.com> wrote:
>
>
>To further disappoint you, note also that a constructivist version of
>Cantors proof also works. Suppose we have an algorithm that produces a list
>of reals. By this I mean that the algorithm can give me the m-th digit of
>the n-th entry on the list. Then the standard reasoning gives us an
>algorithm to produce a number (i.e. any desired digit of that number) that
>demonstrably is not on the list. QED. (This is only an outline of a proof,
>to be sure. Of course you will have to define precisely what an "algorithm"
>is, how you can construct new algorithms from old ones, etc.)
>
proves. As described, it simply shows that no algorithm exists
for generating all reals, not that they are uncountable.
--Norm
Dr. Michael Albert
Somewhere this discussion became a discussion of "What is infitinity"
or some similar philosophical/foundation issue, and I don't have much
to say there.
Just for a few students who may be watching, I wanted to clarify
something.
It is certaintly *not* true that any well ordered set has the
same *cardinality* as the rationals. There exist well orderings
of sets much larger than the rationals. I believe the contrary
remark was attributed to me by a misreading of a previous post.
Note that the concept of cardinality between sets (ie., there
exists a 1-1 correspondence between elements of the sets) is
different from the concept of ordinality between well
ordered sets (ie., that there esists a 1-1 correspondence which
PRESEVES THE ORDERING).
Thus, it you take the integers and add an element at +infinity, the
set still has the same *cardinality*, but a different *ordinality*.
Secondly, I mentioned that one can show that there exists an
uncountable, well ordered set without using the axiom of choice.
An outline of this is in an excercise in Chapter#1 of Munkre's
_Topology_. A subtle point, but it is *not* clear that this implies
that the reals can be well ordered without using the axiom of choice.
Just because a set is "bigger" than countable doesn't make it
big enough to "hold" all the reals. Indeed the question of whether
there is a cardinal number between the inetegers and the reals is,
the question to which the Continum Hypothesis is addressed,
and that is known to be yet another independent axiom. I am not
sure if the particular well ordered set whose construction is
found in Munkre's is "big enough" to hold the reals. I suspect that
it isn't unless one assumes some form of the Continuum Hypothesis
(hey, let's vote on whether the well ordered set in Munkree's has
cardinality greater than or equal to the continuum!!!!! :-)
Just wanted to clarify.
Best wishes,
Mike
Jeroen Bruijning
Norman D. Megill <n...@shore.net> schreef in artikel
<6u5vm2$c...@northshore.shore.net>...
> In article <Ezn5L...@news.research.kpn.com>,
> Jeroen Bruijning <J.Bru...@research.kpn.com> wrote:
> >
> >
> >To further disappoint you, note also that a constructivist version of
> >Cantors proof also works. Suppose we have an algorithm that produces a
list
> >of reals. By this I mean that the algorithm can give me the m-th digit
of
> >the n-th entry on the list. Then the standard reasoning gives us an
> >algorithm to produce a number (i.e. any desired digit of that number)
that
> >demonstrably is not on the list. QED. (This is only an outline of a
proof,
> >to be sure. Of course you will have to define precisely what an
"algorithm"
> >is, how you can construct new algorithms from old ones, etc.)
> >
> I'm not sure what you are claiming that the constructivist version
> proves. As described, it simply shows that no algorithm exists
> for generating all reals, not that they are uncountable.
>
> --Norm
>
>
I left a lot out of the discussion. The version of constructivism I
referred to will only recognize the existence of a mapping if its
construction can be described. "Existence" is meaningless if one cannot
show a construction. In that sense the reals are uncountable since no
bijection with N "exists", i.e., can be constructed, as the argument shows.
Jeroen.
Norman D. Megill
Jeroen Bruijning <jer...@parklane.demon.nl> wrote:
>See below.
>
>Norman D. Megill <n...@shore.net> schreef in artikel
><6u5vm2$c...@northshore.shore.net>...
>> In article <Ezn5L...@news.research.kpn.com>,
>> Jeroen Bruijning <J.Bru...@research.kpn.com> wrote:
>> >
>> >
>> >Cantors proof also works. Suppose we have an algorithm that produces a
>list
>> >of reals. By this I mean that the algorithm can give me the m-th digit
>of
>> >the n-th entry on the list. Then the standard reasoning gives us an
>> >algorithm to produce a number (i.e. any desired digit of that number)
>that
>> >demonstrably is not on the list. QED. (This is only an outline of a
>proof,
>> >to be sure. Of course you will have to define precisely what an
>"algorithm"
>> >is, how you can construct new algorithms from old ones, etc.)
>> >
>> proves. As described, it simply shows that no algorithm exists
>> for generating all reals, not that they are uncountable.
>>
>referred to will only recognize the existence of a mapping if its
>construction can be described. "Existence" is meaningless if one cannot
>show a construction. In that sense the reals are uncountable since no
>bijection with N "exists", i.e., can be constructed, as the argument shows.
>
constructed? We can't construct a list of all non-halting programs,
but such a list would be a subset of the set all programs, which are
countable.
--Norm
Jeroen Bruijning
Norman D. Megill wrote in message
>>> I'm not sure what you are claiming that the constructivist version
>>> proves. As described, it simply shows that no algorithm exists
>>> for generating all reals, not that they are uncountable.
>>>
>>I left a lot out of the discussion. The version of constructivism I
>>referred to will only recognize the existence of a mapping if its
>>construction can be described. "Existence" is meaningless if one cannot
>>show a construction. In that sense the reals are uncountable since no
>>bijection with N "exists", i.e., can be constructed, as the argument
shows.
>>
>I'm still confused. Something is uncountable because it can't be
>constructed? We can't construct a list of all non-halting programs,
>but such a list would be a subset of the set all programs, which are
>countable.
>
>--Norm
>
That's an interesting question and I will answer it to the best of my
knowledge. I am not an expert on "strict" forms of mathematics like
intuitionism, although I was exposed to it a bit during my studies (as a
general topologist by the way, and more than a few years ago).
The question is answered by evading it, in a sense. Just as a mapping only
"exists" if it can be constructed, one can only speak of a "set" if a recipe
for constructing it can be given. That means that the definition you give,
although classically valid, is meaningless in many more strict mathematical
systems. In other words, the "set" you mention simply doesn't exist in such
a system.
Any "valid" subset of the set of all programs in such a system will by
definition be constructible, and by an obvious argument therefore countable.
In such a system you would have "less" sets, "less" mappings, and very
likely "less" theorems. Indeed, many classical valid theorems do not hold
intuitionistically although other proofs go through.
Maybe a real expert on this newsgroup could give a better explanation and
clear away possible misunderstandings?
Best regards,
Jeroen.
BatchBiz
This is a dangerous area, but perhaps somebody can explain why this argument
that the reals are countable is wrong.
The integers are countable (of course)
Rationals are defined as ordered pairs of integers and are countable.
Real numbers are defined by a "Dedekind section" of the rationals. For each
real number there is a rule assigning rationals to the segment U or L
Each possible rule can be defined in a finite string in some language,
perhaps English or perhaps some special "Dedekind Section Definition Language."
Arrange all such rules by length alphabetically. This list of rules is
countable, but it is in 1:1 correspondence with the reals. I deduce the reals
are countable!
Cantor's Procedure
Cosider the ordered list S of all possible strings of characters in "Dedekind
Section Definition Language." Associate with it the list L, where, if S(n) is
a valid Dedekind section L(n) is the real number produced by S(n). If S(n) is
not valid define L(n)=0.
Consider applying Cantor's procedure to set L. "Apply Cantor's procedure to
set L" is a definition of a Dedekind section, a finite string in "DSDL". It
will be in listt S, say in position 'M". If S(M) is valid then there is a
paradox about the value at L(M). Therefore, S(M) is not a valid procedure;
L(M)=0.
This proves that "Apply Cantor's procedure to set L" is not a valid
procedure. Generallizing, there are sets to which Cantor's procedure cannot be
applied!
Thus I have two conclusions:-
Reals are countable.
Cantor's procedure cannot be applied to all lists.
Dick Batchelor
"Make a fast friend - adopt a greyhound"
Dick Batchelor
"Orchids grow free where CAIOS reigns"
Jeroen Bruijning
BatchBiz wrote in message <19980922234521...@ng57.aol.com>...
>
BatchBiz wrote in message <19980922234521...@ng57.aol.com>...
>
>This is a dangerous area, but perhaps somebody can explain why this
argument
>that the reals are countable is wrong.
I see two problems with your argument, the first being the most important:
> Real numbers are defined by a "Dedekind section" of the rationals. For
each
>real number there is a rule assigning rationals to the segment U or L
OK for the idea, but what is a "rule"? You assume:
> Each possible rule can be defined in a finite string in some language,
>perhaps English or perhaps some special "Dedekind Section Definition
>Language."
Here is the crux. Why do you assume that this can be done? I see no reason
why. You are right that in itself this would lead to a proof of countability
of the reals. But the burden of proof is on you, i.e., to define such a
language and prove that it is capable of describing any real!
You continue by giving a second reasoning:
> Cosider the ordered list S of all possible strings of characters in
"Dedekind
>Section Definition Language." Associate with it the list L, where, if S(n)
is
>a valid Dedekind section L(n) is the real number produced by S(n). If S(n)
is
>not valid define L(n)=0.
> Consider applying Cantor's procedure to set L. "Apply Cantor's procedure
to
>set L" is a definition of a Dedekind section, a finite string in "DSDL".
It
>will be in listt S, say in position 'M". If S(M) is valid then there is a
>paradox about the value at L(M). Therefore, S(M) is not a valid procedure;
>L(M)=0.
> This proves that "Apply Cantor's procedure to set L" is not a valid
>procedure. Generallizing, there are sets to which Cantor's procedure
cannot be
>applied!
You prove here that no list of expressions in language S can map onto the
full set of reals, using Cantor's argument. So far, OK. Then you conclude
that Cantor's construction does not apply to L. But this rests on two
assumptions: (1) S does list all reals, which sort of begs the question (see
above), and (2) the expression "Apply Cantor's procedure to set L" is an
expression in DSDL. Why is this true? Again, you will have to give a precise
definition of DSDL and how it maps onto Dedekind cuts to finish the
argument.
It is an interesting argument that reminds of the paradox "let N be the
smallest natural number that cannot be defined in less than 100 characters".
This expression "defines" a number of less than 100 characters! The problem
is the same: one has to define the language and its interpretation and then
one has fixed the interpretation of the sentence and cannot arbitrarily
given its "natural" interpretation anymore.
Hope this clarifies things.
Best regards,
Jeroen.
Mark Adkins
produce a list of all reals, then I'll demonstrate that the
impossibility of such a list proves nothing about the cardinality of
the reals.
The diagonal process divides R into an infinite number of disjoint
subsets each containing an infinite number of reals, plus a disjoint
singleton containing the diagonal number. The union of these sets,
then, is R.
It is easiest to see this by considering a list of binary rather
than decimal expansions. If the first digit of the first list number
is a 1, then the first digit of the diagonal number is a 0. This
has divided R into two disjoint sets: the set of all real numbers
beginning with a 1, and the set of all real numbers beginning with
a 0. It's easy to see that each set has an infinite number of
members. The next step of the diagonal process will divide the
set of all reals beginning with 0 into two subsets: the set of all
reals beginning with 00, and the set of all reals beginning with
01. Each of these is infinite. After aleph_0 steps, there will be
aleph_0 disjoint subsets each containing an infinite number of
members, and there will also be the disjoint singleton containing the
diagonal number. The union of all these is R.
Now, if you assume that the cardinality of the reals is 2^aleph_0,
then it is clear that each of the aleph_0 subsets will contain
2^aleph_0 members. But instead, we are going to assume that the
cardinality of the reals is aleph_0. This is only to show that
the diagonal process is consistent with such an assumption, not
to claim that aleph_0 (or any other transfinite cardinal) is the
cardinality of the reals.
Then the diagonal process will divide R into aleph_0 disjoint subsets
each containing aleph_0 members, plus the singleton which is the
diagonal number.
If we add the singleton to one of these sets, then we have aleph_0
disjoint subsets of aleph_0 elements each, whose union is R. (Adding
the singleton to a set with cardinality aleph_0 produces a set with
cardinality aleph_0, since transfinite cardinal addition dictates that
aleph_0 + 1 = aleph_0.) It's easy to see that the cardinality of the
set which is the union of such sets is aleph_0 * aleph_0 = aleph_0
which is consistent with our assumption about the cardinality of R for
purposes of this exercise.
Because each of these sets contains aleph_0 members, we can order each
set into a list. A diagonal number constructed from one of these lists
will not be on that list, but since the union of these sets is R, we
know that this diagonal number will be present on another one of these
lists. The same is true for any diagonal number constructed from any
of these lists.
It might seem as though we should be able to combine all of these lists
into one giant list of all reals, and since the union of these sets has
cardinality aleph_0, the cardinality of such a list would be aleph_0.
The problem is that a "list" is not only an ordered set, but an ordered
set whose elements are indexed to the natural numbers, beginning with 1
and continuing in sequence.
Let's say we begin our attempt to create our giant list by ordering
the lists side by side (with spaces between). This is feasible since
there are aleph_0 lists. We then decide to take the first number of
every list in order, putting these on our giant list in sequence, and
then start on the second row (taking the second number of every list
in order).
The problem is that there are aleph_0 first numbers since there are
aleph_0 lists. When we collect the first number from each list in
turn, these receive a natural index number in sequence:
1,2,3,...
Then when we start on the second row, the second number of the first
list will be added in sequence to our giant list, but since all of the
natural numbers have been used, it will be indexed by the ordinal number
omega. Thus, after collecting the second element of every list, the
sequenced members of our giant list will be indexed like this:
1,2,3,...,omega, omega+1, omega+2, omega+3,...
Note that the cardinality of our giant list so far is still just
aleph_0, since there are aleph_0 first list-numbers and aleph_0
second list-numbers, and transfinite cardinal addition dictates that
aleph_0 + aleph_0 = aleph_0. It's just that they are indexed with
transfinite ordinals in addition to the natural ordinals. Each of
the transfinite ordinals expresses the order of a single list element
relative to all others, just as each natural ordinal does.
Since there are aleph_0 lists, then no matter how we try to take
a single number from each list, we will have the same problem. We
also have the same problem if we order the lists vertically and
call this our giant list.
Of course, this is not a list as conventionally defined. It is
certainly not the sort of list that Cantor's diagonal process works
from. If we tried to use the diagonal process on such a list, we
wouldn't get real numbers: we'd get numbers like this:
3.1415926...46927...
where the 4 after the first ellipsis is the omega-th digit in the
number. Note however that this number has aleph_0 digits, the same
quantity of digits in a real number. (The first part of this number
is pi, and the second part could be anything -- I picked the initial
sequence of digits "46927" at random.) We *could* call this a
hyperreal or a surreal number, and say it labeled a point on a
geometric line which was between pi and any other real-numbered point
greater than pi, but we could also just ignore it.
At any rate, the fact that there is no comprehensive list of reals
does not prove that the cardinality of the reals is any greater than
the cardinality of the naturals. Every diagonal number constructed
from one of our partial lists of reals is on one of the other partial
lists. Each partial list contains aleph_0 distinct real numbers, and
there are aleph_0 partial lists. The union of these is R, which would
then have a cardinality of aleph_0 consistent with our initial
assumption.
I want to be very clear here about what I'm asserting. I'm not
asserting that the cardinality of the reals is in fact aleph_0. I'm
asserting that Cantor's diagonal proof is not sufficient in itself
to demonstrate that the cardinality of the reals is greater than
aleph_0. The diagonal process is also consistent with an assumption
that the cardinality of the reals is 2^aleph_0. I suspect, in fact,
that it is consistent with any assumption about the transfinite
cardinality of the reals.
Mike McCarty
BatchBiz <batc...@aol.com> wrote:
)
)This is a dangerous area, but perhaps somebody can explain why this argument
)that the reals are countable is wrong.
) The integers are countable (of course)
) Rationals are defined as ordered pairs of integers and are countable.
) Real numbers are defined by a "Dedekind section" of the rationals. For each
)real number there is a rule assigning rationals to the segment U or L
) Each possible rule can be defined in a finite string in some language,
)perhaps English or perhaps some special "Dedekind Section Definition Language."
[snip]
Nope. This is incorrect. What you are defining here is the computable
numbers. They are, of course, countable.
You gave a variation on the more usual argument which goes this way:
I will make a list of all reals in this way: I will list the
reals in lexicographic order, using the decimal expansion. I
insist that the expansions not end in 9999999999... to
enforce uniqueness. Here's the list
0.0000..
0.1000...
0.2000...
...
0.9000...
0.1100...
0.1200...
...
0.1900...
0.2100...
Since this list eventually exhausts all digit strings, it must be
complete.
The problem is, of course, that it exhausts all digit strings which
eventually end in 000.... It leaves out all the truly infinite strings
like
0.14159265358979323...
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for DSC. <- They make me say that.
Wayne Hacker
>
> "Hey Rocky, watch me pull a rabbit out of my hat..."
[clip]
> Since we have assumed from the start that the list is a complete
> list of all numbers ...
[clip]
Let me assume YOUR argument is flawed. Since your argument is flawed it
makes little or no sense. This proves conclusively that Cantor was
correct and ...
Virgil
Bruijning" <jer...@parklane.demon.nl> wrote:
> Here is the crux. Why do you assume that this can be done? I see no reason
> why. You are right that in itself this would lead to a proof of countability
> of the reals. But the burden of proof is on you, i.e., to define such a
> language and prove that it is capable of describing any real!
I thought the point of making the assumption was to show it could NOT be done.
This is perfectly legitimate if you accept the law of the excluded middle.
Virgil
(Mike McCarty) wrote:
> I will make a list of all reals in this way: I will list the
> reals in lexicographic order, using the decimal expansion. I
> insist that the expansions not end in 9999999999... to
> enforce uniqueness. Here's the list
You cannot even list the rationals in this kind of "lexicographic" order,
since between any two of them, in this order, there are infinitely many
others.
The rationals can be put into a sequential order in a lot of different
ways, but not in any way that preserves their usual numerical order.
One of the standard ways is:
Assume that each rational is expressed as a fraction in lowest terms
(integers have denominator 1).
First list those fractions x/y for which |x| + |y| =1, in numerical order
( the only one is 0/1)
Next list those fractions x/y for which |x| + |y| =2, in numerical order
( they are -1/1 and 1/1)
Next list those fractions x/y for which |x| + |y| =3, in numerical order
(they are -2/1, -1/2, 1/2, 2/1)
and so on in the obvious continuation.
Mike McCarty
I POINTED OUT SPECIFICALLY THAT THIS ARGUMENT WAS SPECIOUS, AND GAVE IT
AS AN EXAMPLE OF THE TYPE OF INCORRECT ARGUMENT BEING GIVEN BY THE
POSTER I RESPONDED TO.
In article <vmhjr-23099...@ftc-0402.ppp.frii.com>,
Virgil <vm...@frii.com> wrote:
)In article <6ub2ee$95r$1...@relay1.dsccc.com>, jmcc...@sun1307.spd.dsccc.com
)(Mike McCarty) wrote:
)
)> I will make a list of all reals in this way: I will list the
)> reals in lexicographic order, using the decimal expansion. I
)> insist that the expansions not end in 9999999999... to
)> enforce uniqueness. Here's the list
)
)You cannot even list the rationals in this kind of "lexicographic" order,
)since between any two of them, in this order, there are infinitely many
)others.
[snip]
I never made any such claim, and object to your quoting me out of
context in this way.
This is extremely rude, and I'd like an apology.
Dave Seaman
>This is a dangerous area, but perhaps somebody can explain why this argument
>that the reals are countable is wrong.
> The integers are countable (of course)
Yes.
> Rationals are defined as ordered pairs of integers and are countable.
Yes.
> Real numbers are defined by a "Dedekind section" of the rationals. For each
>real number there is a rule assigning rationals to the segment U or L
This is where your argument goes wrong. A Dedekind cut is a pair of
sets (A,B) such that
1. A and B are nonempty.
2. A U B = Q
3. For every a in A and for every b in B, it follows that a < b.
4. A has no largest element.
Nowhere in the definition is anything stated about there being a "rule"
for deciding whether a given rational x belongs to A or to B. In fact,
there are lots more Dedekind cuts than there are rules for describing
them.
> Each possible rule can be defined in a finite string in some language,
>perhaps English or perhaps some special "Dedekind Section Definition Language."
True, but it only shows that the constructible reals are countable.
Most of the reals are not describable or constructible.
> Arrange all such rules by length alphabetically. This list of rules is
>countable, but it is in 1:1 correspondence with the reals. I deduce the reals
>are countable!
No, the constructible reals are countable. That means there is a
bijection between the natural numbers and the constructible reals. It
does not, however, mean that we can actually *construct* such a
bijection.
>Cantor's Procedure
> Cosider the ordered list S of all possible strings of characters in "Dedekind
>Section Definition Language." Associate with it the list L, where, if S(n) is
>a valid Dedekind section L(n) is the real number produced by S(n). If S(n) is
>not valid define L(n)=0.
Ok in principle, but there is no algorithm for deciding whether S(n) is
valid or not, such that the algorithm gives the correct answer for all
possible n.
> Consider applying Cantor's procedure to set L. "Apply Cantor's procedure to
>set L" is a definition of a Dedekind section, a finite string in "DSDL". It
>will be in listt S, say in position 'M". If S(M) is valid then there is a
>paradox about the value at L(M). Therefore, S(M) is not a valid procedure;
>L(M)=0.
It's not a "definition of a Dedekind section," because there is no
algorithm that can produce the list L.
> This proves that "Apply Cantor's procedure to set L" is not a valid
>procedure. Generallizing, there are sets to which Cantor's procedure cannot be
>applied!
On the contrary, "apply Cantor's procedure to set L" is perfectly
valid. It produces a Dedekind cut that is not in L, but the real
number that is represented by that cut is, of course, not
constructible. No contradiction.
> Thus I have two conclusions:-
> Reals are countable.
Constructible reals are countable.
> Cantor's procedure cannot be applied to all lists.
Cantor's procedure *can* be applied to all lists, but not every list can be
produced by an algorithm.
--
Dave Seaman dse...@purdue.edu
++++ stop the execution of Mumia Abu-Jamal ++++
++++ if you agree copy these lines to your sig ++++
++++ see http://www.xs4all.nl/~tank/spg-l/sigaction.htm ++++
BatchBiz
>) Real numbers are defined by a "Dedekind section" of the rationals. For
>each
>)real number there is a rule assigning rationals to the segment U or L
>) Each possible rule can be defined in a finite string in some language,
>)perhaps English or perhaps some special "Dedekind Section Definition
>Language."
>
>[snip]
>
>Nope. This is incorrect. What you are defining here is the computable
>numbers. They are, of course, countable.
>
goodie. Dedekind's DEFINITION of a real number depends on a rule to separate
the rationals into sets U and L. I f you don"t have a rule, you don"t have a
number.
This definition will include the computable numbers but it seems to me will
also include at least some non-computable numbers.
Dick Batchelor
Clark
-snip-
> It is important however to realize that one is then essentially questioning
> the very definition of the mathematical reasoning employed. This you cannot
> do from within the system. In other words, even if you feel that the Cantor
> result is "wrong", there is no way to refute the proof using standard
> mathematical arguments. In standard mathematics the Cantor proof works,
> however you may dislike it. (Please understand that so-called non-standard
> analysis as in Robinson's book is actually perfectly standard mathematics.
> One can get confused very easily here.)
>
I'm interested in this idea of 'the very definition of
mathematical reasoning'. Is there more to the notion than
'reasoning acceptable to the mathematical community at large'? If
so, how easy is it to characterise it? And, further, given such a
characterisation, how much sense can be made of justifying the
characterisation? (Is there a justification of your definition
which escapes the charge of amounting to no more than 'acceptable
to mathematicians' in its turn, in other words?) And so on. You
get the idea? How soon before you hit bottom, as it were?
That seems a lot of questions, but most are just amplifications
of the first one. I'm not sure it's one of your 'RIGHT' questions
- probably not. Still, I'd be grateful for any answers or
comments.
Bob
Jeroen Bruijning
Virgil wrote in message ...
Well, I understood differently. Normally one uses words like "assume" in
such a context.
In case you are right, perhaps the original poster can clarify his wording
in which case I will again try to refute the proof (I still happen to
believe that the reals are uncountable :-))
Jeroen.
Jeroen Bruijning
clarify the confusion.
Thanks, Jeroen.
BatchBiz <batc...@aol.com> schreef in artikel
<19980923204043...@ng55.aol.com>...
Dave Seaman
>Bruijning" <jer...@parklane.demon.nl> wrote:
>> Here is the crux. Why do you assume that this can be done? I see no reason
>> why. You are right that in itself this would lead to a proof of countability
>> of the reals. But the burden of proof is on you, i.e., to define such a
>> language and prove that it is capable of describing any real!
>I thought the point of making the assumption was to show it could NOT be done.
>This is perfectly legitimate if you accept the law of the excluded middle.
This is what happens when you quote a paragraph that begins, "Here is
the crux, ..." and you snip the preceeding paragraph that stated
precisely what the "crux" was.
That all-important paragraph that was snipped contained the assertion
that for every Dedekind cut there was some "rule" that could be stated
as a finite string of symbols in some language, defining the cut. That
is indeed the "crux," and it is precisely where the flaw in that
argument lies.
Dave Seaman
BatchBiz <batc...@aol.com> wrote:
>I refer to my texts on real analysis - Hardy, "Real Analyssis", an oldie bur
>goodie. Dedekind's DEFINITION of a real number depends on a rule to separate
>the rationals into sets U and L. I f you don"t have a rule, you don"t have a
>number.
> This definition will include the computable numbers but it seems to me will
>also include at least some non-computable numbers.
> Dick Batchelor
A "rule" could take the form of a monotonic increasing function
f: Q -> {0,1} such that f^(-1)(0) and f^(-1)(1) are nonempty. If
f(x) = 0, then x is in L. Otherwise, it's in U. What's the problem?
No problem arises unless you assume the rule can be effectively stated
in a finite number of symbols.
ull...@math.okstate.edu
batc...@aol.com (BatchBiz) wrote:
>
> This is a dangerous area, but perhaps somebody can explain why this argument
> that the reals are countable is wrong.
> The integers are countable (of course)
Nope - there is no such "rule" for most reals. (Um, "rule"
is a little ambiguous, but for most reals there is no such rule
an the sense you explain below.)
> Each possible rule can be defined in a finite string in some language,
> perhaps English or perhaps some special "Dedekind Section Definition
Language."
> Arrange all such rules by length alphabetically. This list of rules is
> countable, but it is in 1:1 correspondence with the reals. I deduce the reals
> are countable!
This proves that the set of reals for which there is such
a rule is countable. Which is true. But that's a small subset
of the reals.
David C. Ullrich
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
BatchBiz
>
>Could you perhaps quote Hardy's definition, in context? That might help
>clarify the confusion.
>
>Thanks, Jeroen.
>
Hardy's explanation is rather long-winded; it' a text book not a research
paper. He defines a "section" and then says:-
"Let us then suppose that P and Q are two properties which are mutually
exclusive and one of which is possessed by everypositive rationall number.
Further let us suppose that any number which possesses P is less than any which
possess Q. Thus P might be the property 'x^2<2' and Q thproperty 'x^2>2'. We
call the numbers which possess P the lower class L and those which possess Q
the upper class R. ...There are sections which do not correspond to any
rational number. ..."
And finally defining:-
'"a SECTION OF THE POSITIVE RATIONAL NUMBERS IN WHICH BOTH CLASSES EXIST AND
THE LOWER CLASS HAS NO GREATEST MEMBER IS CALLED A POSITIVE REAL NUMBER.""
(Sorry about the caps; I hit Caps Lock by mistake)
My logic is:-
1. To have a real number you have to have a section of the rationals; there is
no other way to get a real number.
2. To have a section you have to have P and Q.
3. Properties P and Q must be definable in a finite string in some language.
(The examples given are trivially short: 'x^2>2')
4 All possible strings can be written in a countable list.
Thus, the number of reals(defined by Dedekind Section) is not greater than
the number of defining P's.
Conclusion: the number of reals is countable.
Dick Batchelor
BatchBiz
>
>That all-important paragraph that was snipped contained the assertion
>that for every Dedekind cut there was some "rule" that could be stated
>as a finite string of symbols in some language, defining the cut. That
>is indeed the "crux," and it is precisely where the flaw in that
>argument lies.
>
Dedekind Section could be infinite. How could you ever us an 'infinite' rule
to decide whether to put a rational number in class U or L? You might just as
well define a real as an 'infinite' string of digits; a concept that doesn't
make sense when you think about it, and that Dedekinds definition got away
from.
BatchBiz
>> Real numbers are defined by a "Dedekind section" of the rationals. For
>each
>>real number there is a rule assigning rationals to the segment U or L
>
>sets (A,B) such that
>
> 1. A and B are nonempty.
> 2. A U B = Q
> 3. For every a in A and for every b in B, it follows that a < b.
> 4. A has no largest element.
>
>Nowhere in the definition is anything stated about there being a "rule"
>for deciding whether a given rational x belongs to A or to B. In fact,
>there are lots more Dedekind cuts than there are rules for describing
>them.
>
assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
Mark Adkins
more explicitly. (In that argument, I demonstrated that Cantor's
diagonal proof was perfectly consistent with the assumption that the
cardinality of the reals was aleph_0.)
Cantor assumed that because the nonexistence of a bijection between
two finite sets indicates a difference in cardinality, that the same
thing is true for two infinite sets. That assumption is the flaw in
his proof.
True, if the cardinality of the reals was greater than that of the
naturals, that would prevent a bijection too. But Cantor's diagonal
proof doesn't demonstrate such a difference in cardinalities.
Before we go on, we need to define some terms clearly. The naturals
are a well-ordered set. This means that, in addition to following
the order properties which define simply ordered sets like the reals,
e.g., given two distinct numbers p and q, either p<q or p>q, every
subset of the naturals has a first element. So, the set of all
naturals itself has a first element, and any proper subset has a first
element. For example, the subset of all natural numbers greater than
5 has a first element, 6. This is obviously not true for simply
ordered sets like the reals, where for example the subset of all real
numbers greater than 5 has no first element.
A LIST, as the term was used in Cantor's diagonal proof, is an ordered
set whose elements are indexed with the natural numbers (and only the
natural numbers). All lists are well-ordered sets, because the natural
numbers are well-ordered. However, the inverse is NOT true: there are
well-ordered sets which are not lists. For example, a set indexed to
ordinals like this: {1,2,3,...omega, omega+1, omega+2,...} is
well-ordered, but it is not a list because its elements are not
(strictly) indexed with the natural numbers. (Note however that the
cardinality of a set indexed with transfinite ordinals is still no
greater than the cardinality of the naturals, this being aleph_0.)
Of course, the rational numbers are only simply-ordered yet there
is a bijection from them into the naturals. There are two reasons,
however, why this is so. First, this act of bijection is actually
the specification of a LIST of all rationals -- a list in this context
being an ordered set whose elements are indexed exclusively with the
natural numbers. One cannot create a list of all rationals which
preserves the linear order of the rationals. That is, the rationals
as they are ordered on a line have a specific ordering, but this
ordering defines no list because it is a case of simple-ordering rather
than well-ordering. In order for a bijection between the rationals
and the naturals to be possible, we must create a well-ordering of the
rationals. The usual way to do this is to express the rationals as
integer ratios p/q. Then, because the integers are well-ordered, it is
possible to well-order the rationals expressed as integer ratios p/q.
You can then convert them to decimal or binary expansions later. Note
however that this does not preserve the linear order of the rationals.
The second reason why a bijection is possible between the set of all
rationals and the set of all naturals, is that it is not only possible
to well-order the set of all rationals this way, but it is possible
to well-order them in a way that indexes them to the natural numbers
exclusively, i.e., a bijection between these sets creates a LIST of
all rationals.
Then, in order for a bijection between the set of all reals and the set
of all naturals to exist, we must not only well-order all the reals,
but well-order them in a way that indexes them exclusively to the
naturals, i.e., we must create a LIST of all reals. Since the
irrationals cannot be expressed as integer ratios, well-ordering the
set of all reals is a little trickier than well-ordering the set of
all rationals. The linear order of the reals is defined, but their
linear order is simply-ordered.
Even though I know of no *algorithm* for well-ordering the reals
(but then, I haven't researched the problem), Zermelo proved that if
we accept the axiom of choice we can well-order any set, including
the reals. HOWEVER -- and this is the important part -- it is not
possible to well-order the reals such that they are indexed exclusively
to the natural numbers. Therefore, no bijection exists between the set
of all reals and the set of all natural numbers, i.e., there is no LIST
of all reals.
This was illustrated in my latest argument. There, the reals were
assumed to have cardinality aleph_0 and were divided via the diagonal
process into aleph_0 sets each containing aleph_0 distinct binary
expansions, and the union of these sets was R. Then, we well-ordered
the elements of each set, i.e., we created a LIST from each set by
numbering its elements with the natural numbers. (How to do that in
each case wasn't important, and at minimum, we can always fall
back on the axiom of choice if we wish, though other participants in
this newsgroup have given reference to proofs of the possibility of
universal well-ordering of sets which don't use AC.)
Then it was shown that, though it was possible to create a single
giant, comprehensive, well-ordered set by combining the elements of
all of these partial lists of reals (and I gave several examples of
ways to do this), it *wasn't* possible to index the elements of this
comprehensive list of reals exclusively to the natural numbers. Thus,
it was *not* possible to create a LIST of all reals.
In conclusion, Cantor's diagonal proof was shown to be perfectly
consistent with the assumption that the cardinality of reals was
aleph_0, and even under this assumption no list of all reals was
possible, i.e., no bijection from the set of all reals to the set
of all natural numbers was possible. The reason was not a difference
in cardinalities, because a priori there was no such difference. The
reason is that even though there was a way to well-order the set of
all reals, there was no way to index the elements of this well-ordered
set exclusively with natural numbers, i.e., there was no way to create
a LIST of all reals.
Jeroen Bruijning
BatchBiz wrote in message <19980924141658...@ng58.aol.com>...
>
>>
>>Could you perhaps quote Hardy's definition, in context? That might help
>>clarify the confusion.
>>
>>Thanks, Jeroen.
>>
>
>Hardy's explanation is rather long-winded; it' a text book not a research
>paper. He defines a "section" and then says:-
> "Let us then suppose that P and Q are two properties which are mutually
>exclusive and one of which is possessed by everypositive rationall number.
>Further let us suppose that any number which possesses P is less than any
which
>possess Q. Thus P might be the property 'x^2<2' and Q thproperty 'x^2>2'.
We
It is probably immaterial for the thrust of the argument, but I don't
understand why P and Q satisfy the conditions above: -4 is a member of Q
whereas 0 is a member of P, yet 0 < -4 is false! Also, neither P nor Q are
posessed by every positive rational number (1 is a member of P and 2 is a
memver of Q). Or do I suffer from delusions?
>call the numbers which possess P the lower class L and those which possess
Q
>the upper class R. ...There are sections which do not correspond to any
>rational number. ..."
> And finally defining:-
> '"a SECTION OF THE POSITIVE RATIONAL NUMBERS IN WHICH BOTH CLASSES EXIST
AND
>THE LOWER CLASS HAS NO GREATEST MEMBER IS CALLED A POSITIVE REAL NUMBER.""
>(Sorry about the caps; I hit Caps Lock by mistake)
>
> My logic is:-
>1. To have a real number you have to have a section of the rationals;
there is
>no other way to get a real number.
>2. To have a section you have to have P and Q.
>3. Properties P and Q must be definable in a finite string in some
language.
I all boils down to the notion of "property". Although the example is a
formula, I do not think that it is intended that it alway be a formula (or a
finite string in any finite alphabet, for that matter). It is more often
seen that people loosely use the word "property" as capable of denoting any
subset.
As an example, take a number that is not the root of an equation
(polynomial). Pi is known to be such a number. A fortiori, Pi is not
rational. Take P to be the property of being < Pi, and Q the property of
being > Pi. They satisfy the conditions and the corresponding section, not
accidently, is identified with the number Pi. Yet there is no formula
associated with these properties.
Is this interpretation acceptable to you?
Jeroen Bruijning
BatchBiz wrote in message <19980924142430...@ng58.aol.com>...
>
>>
>>That all-important paragraph that was snipped contained the assertion
>>that for every Dedekind cut there was some "rule" that could be stated
>>as a finite string of symbols in some language, defining the cut. That
>>is indeed the "crux," and it is precisely where the flaw in that
>>argument lies.
>>
>I agree that this is the crux, but I do not see how the 'rule' defining a
>Dedekind Section could be infinite. How could you ever us an 'infinite'
rule
>to decide whether to put a rational number in class U or L? You might just
as
>well define a real as an 'infinite' string of digits; a concept that
doesn't
>make sense when you think about it, and that Dedekinds definition got away
>from.
I can sympathize with your resistance to accept non-finitely expressible
"rules" for defining Dedekind cuts, but there is nothing in classical
mathematics that demands that such a rule exists.
However, there are schools in mathematics that indeed do not accept
definitions that are not "decidable" in a certain sense. Intuitionism, for
example, will not accept real numbers that are the result of a "cut" where
it is undecidable for each rational on which side it lies. For example, the
"cut" defined by (in shorthand):
x<0 | x>0 if there exist 10^10 consecutive 7's in the decimal expansion of
Pi
x<1 | x >1 otherwise
does not define a real number, since there is no way to determine on which
side 1/2 lies. One puzzling thing with this is that tomorrow this suddenly
might become a well-defined number, either 0 or 1, in case somebody solves
the condition.
I conclude that at heart you may not be a classical mathematician. You are
free to make your choice, however do not confuse it with declaring that
Dedekind cuts without a decidable rule are invalid. They are, classically.
Jeroen.
Jeroen Bruijning
BatchBiz wrote in message <19980924142844...@ng58.aol.com>...
>
>>> Real numbers are defined by a "Dedekind section" of the rationals. For
>>each
>>>real number there is a rule assigning rationals to the segment U or L
>>
>>This is where your argument goes wrong. A Dedekind cut is a pair of
>>sets (A,B) such that
>>
>> 1. A and B are nonempty.
>> 2. A U B = Q
>> 3. For every a in A and for every b in B, it follows that a < b.
>> 4. A has no largest element.
>>
>>Nowhere in the definition is anything stated about there being a "rule"
>>for deciding whether a given rational x belongs to A or to B. In fact,
>>there are lots more Dedekind cuts than there are rules for describing
>>them.
>>
>Please give an example of a Dedekind cut for which there is no rule for
>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
OK, take a variation of the example from my previous post. One simply
defines a real number the decimal expansion of which is unknown:
x<0 | x>0 if the Goldbach conjecture is true
x<1 | x>1 otherwise
Does there exist a rule to decide on which side of the cut 1/2 is lying?
Jeroen.
BatchBiz
>>>
>>>Could you perhaps quote Hardy's definition, in context? That might help
>>>clarify the confusion.
>>>
>>>Thanks, Jeroen.
>>>
>>
>>Hardy's explanation is rather long-winded; it' a text book not a research
>>paper. He defines a "section" and then says:-
>> "Let us then suppose that P and Q are two properties which are mutually
>>exclusive and one of which is possessed by everypositive rationall number.
>>Further let us suppose that any number which possesses P is less than any
>which
>>possess Q. Thus P might be the property 'x^2<2' and Q thproperty 'x^2>2'.
>We
>
>
>It is probably immaterial for the thrust of the argument, but I don't
>understand why P and Q satisfy the conditions above: -4 is a member of Q
positive.
>whereas 0 is a member of P, yet 0 < -4 is false! Also, neither P nor Q are
>posessed by every positive rational number (1 is a member of P and 2 is a
>memver of Q). Or do I suffer from delusions?
>
Every positive rational number possesses either property P or property Q (Q=
~P). No number possesses both P and ~P. I don't know why Hardy introduces two
properties; It would seem simpler to use P and ~P.
There are "rules" for defining numbers such as 'pi'. For 'pi' the following
would be a very clumsy one.
I know there is an infinite series thsums to 'pi' - something like 'pi'/4 =
1+1/2+.... The property P would be:-
for (n=1 to infinity)
do;
if x < sum from 1 to n( series for 'pi")
then TRUE [x belongs to L]
end;
The property P doesn't have to be a simple formula; it could be anything.
I'm really not a good person to explain this; please refer to your books on
Real Analysis.
>
>Is this interpretation acceptable to you?
>
>>(The examples given are trivially short: 'x^2>2')
>
>>4 All possible strings can be written in a countable list.
>> Thus, the number of reals(defined by Dedekind Section) is not greater
>
Dick
Virgil
(BatchBiz) wrote:
> My logic is:-
> 1. To have a real number you have to have a section of the rationals;
there is
> no other way to get a real number.
> 2. To have a section you have to have P and Q.
> 3. Properties P and Q must be definable in a finite string in some language.
> (The examples given are trivially short: 'x^2>2')
> 4 All possible strings can be written in a countable list.
> Thus, the number of reals(defined by Dedekind Section) is not greater than
> the number of defining P's.
>
> Conclusion: the number of reals is countable.
To have a section, you must have the sets U and L, but why do you need
properties P and Q?
If you insist on complete constructability, every construction must be
completed in a finite number of steps, so every constructable set is
FINITE and the number of such constructions is FINITE. How do you justify
infinite sets?
William Hughes
> Please give an example of a Dedekind cut for which there is no rule for
> assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
Please construct for me an non-constructable real. This is going to
be difficult.
However. There are countable number of rules. There are
an uncountable number of reals. Every real is described
by a Dedekind cut.. There must be at least one Dedekind cut for
which there is no rule. This should be good enough even
for someone from Missouri.
-William Hughes
Mark Adkins
the validity of my latest argument (that Cantor's diagonal proof is
consistent with an assumption that the cardinality of the reals is
aleph_0, and that a bijection from the set of all reals to the set of
all naturals is impossible under such an assumption because it is
impossible to create a well-ordered set of all reals which is indexed
exclusively with the natural numbers). In fact, the correction makes
the argument strong by fixing a mistake which otherwise threatened to
undermine it. THIS MESSAGE CONTAINS AN IMPORTANT CONCLUSION REGARDING
USE OF THE AXIOM OF CHOICE.
You will recall that I began by demonstrating how the diagonal process
divides R into aleph_0 disjoint subsets each containing an infinite
number of distinct binary expansions (the union of which is therefore
R), and that under the assumption that the cardinality of R is aleph_0,
each of these subsets will contain aleph_0 elements.
So far, so good, but when I said in my original post that each of these
subsets could be ordered into a list, I made the type of error I have
been trying to correct, and carried this error forward in subsequent
posts. Due to the mixed nature of the binary expansions constituting
the elements of these subsets and the fact that they are not even
linearly ordered, there will be no algorithm for well-ordering them and
the axiom of choice must be used to do so.
The axiom of choice permits you to take one element each from a group of
subsets A, B, C,... and put them in turn into a well-ordered set X by
indexing them to ordinals, continuing until every element of every subset
A,B,C,... has been added to X. However, this does not mean that in every
case these ordinals will be exclusively natural numbers: in some cases
the well-ordering will result in the use of transfinite ordinals, in
which case it is not a *list* in the way this term was used in Cantor's
proof.
This means that in order to use the axiom of choice to well-order a
set you must first define a group of subsets. For example, in my
illustration, the diagonal process divided R into aleph_0 disjoint
subsets each containing aleph_0 elements (under the assumption that
this is also the cardinality of R). I then claimed that each of
these could be well-ordered into a list. Then it was possible (or
seemed possible) to create a well-ordered set R by taking an element
from each of these in turn until all the elements of every subset had
been collected, though this inevitably led to a well-ordering which
used transfinite ordinals.
One of these subsets in my illustration was the set of all distinct
binary expansions beginning with the digit 1. That of course is an
unordered set. In order to well-order this set, you would then need
to define the subsets you would use in applying the axiom of choice.
But this time you can't use the diagonal process to do this, because
the diagonal number will begin with 0 and this will not subdivide the
set of all reals beginning with 1. You could define a set of subsets
consisting of each distinct element of the set, but then you must
specify each distinct element of the set, i.e., in applying the
axiom of choice, you must say which of these you are picking in turn.
(In fact, no matter what you take for subsets, you must specify
distinct elements of each in using AC.)
The problem is that even though "the set of all distinct binary
expansions beginning with 1" is a perfectly well defined set, you
must still specify *individual* members of this set before you can
choose them using AC. Furthermore, you must specify individual
members of this set in a way that permits you to insure that you
have specified them all, since we want to well-order the whole
set. But if most of these binary expansions are random, then
the only way to specify them is to write out random infinite
sequences of digits. Now you not only have the problem of making
sure that any given sequence of digits you write out IS random -- an
impossible task since you never finish writing -- but you have to
make sure that you account for *all* such sequences beginning with
the digit 1 since you want to well-order the entire set -- another
impossible task. In fact, you couldn't always be sure that what you
thought were distinct random sequences of digits really were, since
the only way to determine that a pair of such sequences are distinct
is to compare them digit by digit: another impossible task since the
number of digits in each is infinite and two such sequences might
start out with an arbitrarily large finite sequence of identical
digits before diverging -- or they might never diverge -- and
you couldn't tell which was actually the case.
So, even though in theory you can use AC to well-order any set,
before you can use AC you have to make sure you can individually
specify all elements of the set.
This means that you not only *can't* well-order the set of all binary
expansions beginning with 1 (or any of the other such subsets created
by the diagonal process in the illustration I gave earlier), but IN
FACT you can't even create a well-ordered set R by picking elements
in turn (until all the elements have been picked) from each of the
aleph_0 subsets in my earlier illustration; because as you pick
elements of each in turn, you must specify the element you are
picking from each unordered set, and you can't do this for all
elements.
In other words, EVEN THOUGH YOU CAN USE AC TO WELL-ORDER THE
INDIVIDUALLY SPECIFIED ELEMENTS OF ANY SET, YOU CAN'T USE AC THIS
WAY UNLESS YOU CAN INDIVIDUALLY SPECIFY ALL ELEMENTS OF THE SET.
This might seem paradoxical, since the criteria for membership in
"the set of all binary expansions beginning with 1" is perfectly
well-defined, but there is a difference between specifying a set and
individually specifying all of the elements of that set. ZERMELO'S
PROOF THAT, USING AC, YOU CAN WELL-ORDER ANY SET, THUS IMPLICITLY
*ASSUMES* THAT IT IS POSSIBLE TO INDIVIDUALLY SPECIFY ALL OF THE
ELEMENTS OF ANY SET IN ORDER TO CHOOSE BETWEEN THEM -- BUT THIS
IS A FALSE ASSUMPTION. Naming well-defined criteria for
membership in a set does not necessarily individually specify all
of the elements of that set. Proofs that AC universally allows
the well-ordering of sets necessarily deal in generalities, but
AC, because a priori it involves distinct *choices*, requires
more than generalities to actually use.
This is why it is impossible, regardless of the cardinality of
the reals, to well-order the set of all reals. Since well-ordering
is a necessary (but not sufficient) prerequisite for constructing a
list, there is no list of all reals either. If R were well-orderable,
and the cardinality of R was aleph_0, then if AC could be used on R,
it seems it should be possible to construct a list R. But elements
of a list are individually specifiable: we can name any natural
number and there is a way to name the element indexed to that
number in a definite and unique way as a result of a bijection.
Since R is not well-orderable (because it is not possible
to actually use AC on R), there can be no list R regardless of the
cardinality of R.
William Hughes
> I am from Mo also but even if there is a countable number
> of basic rules can't they be used in group to form new rules
> in such a way that there is no end to the number of rules.
There is no end the the number of rules. The point is that
(in theory) we can number the rules
rule 1, rule 2, rule 3 ...
and be certain that for any given rule, the rule must be on this list.
We can't make a list of reals
real 1, real 2, real 3 ...
and be certain that for any given real, the real must be on this list.
In fact, given any such list, it is possible to show
that there is a real number not on the list.
-William Hughes
graham...@hotmail.com
Somebody please give me a number (between 0 and 1) which is not on the
following list:
0.0000...
0.1000...
0.2000...
0.3000...
0.4000...
0.5000...
0.6000...
0.7000...
0.8000...
0.9000...
0.0100...
0.1100...
0.2100...
0.3100...
0.4100...
...
0.9999...
The diagonal is 0.0000... Changing each digit I could get 0.9999... Cantor
suggests this is not on the list, but it clearly is. I posted a binary
version of this already, and again the reason that Cantor is wrong is that
when the list has N columns, it has 10^N rows, no matter what N is. This
means there are ALWAYS MORE ROWS THAN COLLUMNS, because 10^N increases way
faster than N, so the diagonal only samples a small portion of the first few
rows, and the rest of the rows are free to contain a match to our number!
- GLYPH
Mike McCarty
Mark Adkins <adk...@cyberspace.org> wrote:
)Let me see if I can express the conclusions of my latest argument a bit
)more explicitly. (In that argument, I demonstrated that Cantor's
)diagonal proof was perfectly consistent with the assumption that the
)cardinality of the reals was aleph_0.)
)
)Cantor assumed that because the nonexistence of a bijection between
)two finite sets indicates a difference in cardinality, that the same
)thing is true for two infinite sets. That assumption is the flaw in
)his proof.
No, this was not an assumption, it was a *definition*.
[rest snipped due to fatal flaw]
If you are going to post enormous amounts of information like this, then
it would save a lot of time if you checked the first little bit for
correctness when the rest hangs on it.
Mike McCarty
BatchBiz <batc...@aol.com> wrote:
)
)>
)>Could you perhaps quote Hardy's definition, in context? That might help
)>clarify the confusion.
)>
)>Thanks, Jeroen.
)>
)
)Hardy's explanation is rather long-winded; it' a text book not a research
)paper. He defines a "section" and then says:-
) "Let us then suppose that P and Q are two properties which are mutually
)exclusive and one of which is possessed by everypositive rationall number.
)Further let us suppose that any number which possesses P is less than any which
)possess Q. Thus P might be the property 'x^2<2' and Q thproperty 'x^2>2'. We
)call the numbers which possess P the lower class L and those which possess Q
)the upper class R. ...There are sections which do not correspond to any
)rational number. ..."
) And finally defining:-
) '"a SECTION OF THE POSITIVE RATIONAL NUMBERS IN WHICH BOTH CLASSES EXIST AND
)THE LOWER CLASS HAS NO GREATEST MEMBER IS CALLED A POSITIVE REAL NUMBER.""
)(Sorry about the caps; I hit Caps Lock by mistake)
)
) My logic is:-
)1. To have a real number you have to have a section of the rationals; there is
)no other way to get a real number.
)2. To have a section you have to have P and Q.
)3. Properties P and Q must be definable in a finite string in some language.
[snip]
This is where you and classical mathematics part ways.
Mike McCarty
BatchBiz <batc...@aol.com> wrote:
)
)>) Real numbers are defined by a "Dedekind section" of the rationals. For
)>each
)>)real number there is a rule assigning rationals to the segment U or L
)>) Each possible rule can be defined in a finite string in some language,
)>)perhaps English or perhaps some special "Dedekind Section Definition
)>Language."
)>
)>[snip]
)>
)>Nope. This is incorrect. What you are defining here is the computable
)>numbers. They are, of course, countable.
)>
)I refer to my texts on real analysis - Hardy, "Real Analyssis", an oldie bur
)goodie. Dedekind's DEFINITION of a real number depends on a rule to separate
)the rationals into sets U and L. I f you don"t have a rule, you don"t have a
)number.
)
) This definition will include the computable numbers but it seems to me will
)also include at least some non-computable numbers.
) Dick Batchelor
I started to respond to this, but the more I read it I don't understand
it. Not all rules can be written down.
So?
Mike McCarty
)>that for every Dedekind cut there was some "rule" that could be stated
)>as a finite string of symbols in some language, defining the cut. That
)>is indeed the "crux," and it is precisely where the flaw in that
)>argument lies.
)>
)I agree that this is the crux, but I do not see how the 'rule' defining a
)Dedekind Section could be infinite. How could you ever us an 'infinite' rule
)to decide whether to put a rational number in class U or L? You might just as
)well define a real as an 'infinite' string of digits; a concept that doesn't
)make sense when you think about it, and that Dedekinds definition got away
)from.
) Dick Batchelor
There are cuts which cannot be described by *any* rule, since they correspond
to non-computable reals.
Mike McCarty
<graham...@hotmail.com> wrote:
)
)
)Somebody please give me a number (between 0 and 1) which is not on the
)following list:
)
)0.0000...
)0.1000...
)0.2000...
)0.3000...
)0.4000...
)0.5000...
)0.6000...
)0.7000...
)0.8000...
)0.9000...
)0.0100...
)0.1100...
)0.2100...
)0.3100...
)0.4100...
)...
)0.9999...
I can give you one. sqrt(2) is not on your list. Every number on your list
is rational.
)The diagonal is 0.0000... Changing each digit I could get 0.9999... Cantor
Well, one *could*. Here is the way I would generate a number not on your
list, using a "diagonal" technique.
If the digit is less than or equal to 5, then the new digit is 6. If the
digit is greater than 5, then the new digit is 4. This always changes a
digit, and cannot have even one 9 or one 0 in it, hence no ambiguity.
)suggests this is not on the list, but it clearly is. I posted a binary
)version of this already, and again the reason that Cantor is wrong is that
)when the list has N columns, it has 10^N rows, no matter what N is. This
)means there are ALWAYS MORE ROWS THAN COLLUMNS, because 10^N increases way
)faster than N, so the diagonal only samples a small portion of the first few
)rows, and the rest of the rows are free to contain a match to our number!
You need to read what I just wrote carefully and understand it.
One needs to take more care when working with binary, but even then the
problems are not insurmountable. But why insist on doing things in a
difficult base?
Mike McCarty
Mike McCarty <jmcc...@sun1307.spd.dsccc.com> wrote:
)In article <6uemnk$eto$1...@nnrp1.dejanews.com>,
) <graham...@hotmail.com> wrote:
))
))
))Somebody please give me a number (between 0 and 1) which is not on the
))following list:
))
))0.0000...
))0.1000...
))0.2000...
))0.3000...
))0.4000...
))0.5000...
))0.6000...
))0.7000...
))0.8000...
))0.9000...
))0.0100...
))0.1100...
))0.2100...
))0.3100...
))0.4100...
))...
))0.9999...
)
)I can give you one. sqrt(2) is not on your list. Every number on your list
Sorry, this should have been sqrt(2)/2.
BatchBiz
>>>>real number there is a rule assigning rationals to the segment U or L
>>>
>>>sets (A,B) such that
>>>
>>> 1. A and B are nonempty.
>>> 2. A U B = Q
>>> 3. For every a in A and for every b in B, it follows that a < b.
>>> 4. A has no largest element.
>>>
>>>Nowhere in the definition is anything stated about there being a "rule"
>>>for deciding whether a given rational x belongs to A or to B. In fact,
>>>there are lots more Dedekind cuts than there are rules for describing
>>>them.
>>>
>>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
>
>
>defines a real number the decimal expansion of which is unknown:
>
>x<0 | x>0 if the Goldbach conjecture is true
>x<1 | x>1 otherwise
>
>Does there exist a rule to decide on which side of the cut 1/2 is lying?
The numbers that can be defined by Dedekind section are not limited to
computable numbers. I could define a number whose digit 'n' is 0 if Turing
machine stops, 1 otherwise. This number is not computable, but there is a
Dedekind section that defines it. PLEASE don't ask me to spell out the rule for
it; it's much too complicated for me.
Let me call your number 'z.' The rule for the section is
"For any rational number x, if x>z, x belongs to U, else x belongs to L'
If 'z' is very difficult to compute, or even non-computable makes no
difference; the Dedekind section defines it.
You can't win my challenge if I understand the concept of number correctly.
If you can define the numer, the definition can be converted into a Dedekind
section I want to divide the reals into two groups; those for which a
definition existed and those for which no definition exists. I take the ones
with a definition and give you the rest. My set is countable so you should
have many more than me. However, if I ask you for one of your number you
cannot give me even one; if you try you have to giveme a definition of the
number and I say "Hey; that number has a definition; it's one of mine!"
Thanks for your interest in the problem, but my doubts are not yet resolved.
Dick Batchelor
>
>Jeroen.
>
>
>
>
>
>
>
>
David A. Scott
In a previous article, whu...@atlsci.com (William Hughes) says:
>BatchBiz wrote:
>
>> Please give an example of a Dedekind cut for which there is no rule for
>> assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
>
>Please construct for me an non-constructable real. This is going to
>be difficult.
>
>However. There are countable number of rules. There are
>an uncountable number of reals. Every real is described
>by a Dedekind cut.. There must be at least one Dedekind cut for
>which there is no rule. This should be good enough even
>for someone from Missouri.
>
> -William Hughes
>
>
I am from Mo also but even if there is a countable number
of basic rules can't they be used in group to form new rules
in such a way that there is no end to the number of rules.
Sorry I jumped in.
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
for the version with a real key of voer one million bytes.
also scott16u.zip and scott4u.zip
Alan Morgan
>the validity of my latest argument
You got that right.
Alan
Jeroen Bruijning
BatchBiz wrote in message <19980924214244...@ng55.aol.com>...
>
>Jeroen Bruijning wrote:
>>
>>>Please give an example of a Dedekind cut for which there is no rule for
>>>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
>>
>>
>>OK, take a variation of the example from my previous post. One simply
>>defines a real number the decimal expansion of which is unknown:
>>
>>x<0 | x>0 if the Goldbach conjecture is true
>>x<1 | x>1 otherwise
>>
>>Does there exist a rule to decide on which side of the cut 1/2 is lying?
>I don't understand the number you have defined. Let me try to answer
anyway.
The rest of your reply I don't understand. Let me try to define the number z
again to see if that resolves the issue. The cut corresponding to z is:
L = { x in Q | Q < 0 } if the Goldbach conjecture is true
L = { x in Q | Q > 1 } if the Goldbach conjecture is false
R = { x in Q | Q < 1 } if the Goldbach conjecture is true
R = { x in Q | Q > 1 } if the Goldbach conjecture is false
Classically, z is a well defined number and (classically) one can prove (z =
0 OR z = 1) (but nobody knows wheter it is 0 or 1 because that would settle
the Goldbach conjecture).
(If you are uncomfortable with a rational number as example, take sqrt(2)
and sqrt(3) instead of 0 and 1.)
Now, z is a well defined number, yet are you sure that there is a rule to
tell you on which side of the cut 1/2 is lying?
I hope that at lease this makes clear the definition of z.
Maybe this takes away your doubts. If not, it could be interesting to
continue the discussion but I would then like to have a mathematically
precise definition of "rule" first.
Best regards,
Jeroen.
>
> Dick Batchelor
>>
>>Jeroen.
>>
>>
>>
>>
>>
>>
>>
>>
>
>
feld...@bsi.fr
batc...@aol.com (BatchBiz) wrote:
>
> Jeroen Bruijning wrote:
> >
> >BatchBiz wrote in message <19980924142844...@ng58.aol.com>...
> >>
> >>>> Real numbers are defined by a "Dedekind section" of the rationals. For
> >>>each
> >>>>real number there is a rule assigning rationals to the segment U or L
> >>>
> >>>This is where your argument goes wrong. A Dedekind cut is a pair of
> >>>sets (A,B) such that
> >>>
> >>> 1. A and B are nonempty.
> >>> 2. A U B = Q
> >>> 3. For every a in A and for every b in B, it follows that a < b.
> >>> 4. A has no largest element.
> >>>
> >>>Nowhere in the definition is anything stated about there being a "rule"
> >>>for deciding whether a given rational x belongs to A or to B. In fact,
> >>>there are lots more Dedekind cuts than there are rules for describing
> >>>them.
> >>>
> >>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
> >
> >
> >OK, take a variation of the example from my previous post. One simply
> >defines a real number the decimal expansion of which is unknown:
> >
> >x<0 | x>0 if the Goldbach conjecture is true
> >x<1 | x>1 otherwise
> >
> >Does there exist a rule to decide on which side of the cut 1/2 is lying?
> I don't understand the number you have defined. Let me try to answer anyway.
> computable numbers. I could define a number whose digit 'n' is 0 if Turing
> machine stops, 1 otherwise. This number is not computable, but there is a
> Dedekind section that defines it. PLEASE don't ask me to spell out the rule for
> it; it's much too complicated for me.
> Let me call your number 'z.' The rule for the section is
> "For any rational number x, if x>z, x belongs to U, else x belongs to L'
> If 'z' is very difficult to compute, or even non-computable makes no
> difference; the Dedekind section defines it.
> You can't win my challenge if I understand the concept of number correctly.
> If you can define the numer, the definition can be converted into a Dedekind
> section I want to divide the reals into two groups; those for which a
> definition existed and those for which no definition exists. I take the ones
> with a definition and give you the rest. My set is countable so you should
> have many more than me. However, if I ask you for one of your number you
> cannot give me even one; if you try you have to giveme a definition of the
> number and I say "Hey; that number has a definition; it's one of mine!"
You are now in Richard's paradox : in the same sense, "short" definitions
(say, in less than 100 words) are in finite number , so there are integers
not in those definitions, yet "the smallest integer not given by a 100-words
or less definition" has this sentence as definition, and it is a short one...
> Thanks for your interest in the problem, but my doubts are not yet resolved.
>
I can understand that: Richard's (or Berri's) paradoxes are always very hard
to manage :-)
> Dick Batchelor
> >
> >Jeroen.
graham...@hotmail.com
jmcc...@sun1307.spd.dsccc.com (Mike McCarty) wrote:
> In article <6uemnk$eto$1...@nnrp1.dejanews.com>,
> <graham...@hotmail.com> wrote:
> )
> )
> )
> )0.0000...
> )0.1000...
> )0.2000...
> )0.3000...
> )0.4000...
> )0.5000...
> )0.6000...
> )0.7000...
> )0.8000...
> )0.9000...
> )0.0100...
> )0.1100...
> )0.2100...
> )0.3100...
> )0.4100...
> )...
> )0.9999...
>
Please prove this. You may be right.
> )The diagonal is 0.0000... Changing each digit I could get 0.9999... Cantor
>
> Well, one *could*. Here is the way I would generate a number not on your
> list, using a "diagonal" technique.
>
> If the digit is less than or equal to 5, then the new digit is 6. If the
> digit is greater than 5, then the new digit is 4. This always changes a
> digit, and cannot have even one 9 or one 0 in it, hence no ambiguity.
This yields 0.666666... which I maintain is on the list.
> )suggests this is not on the list, but it clearly is. I posted a binary
> )version of this already, and again the reason that Cantor is wrong is that
> )when the list has N columns, it has 10^N rows, no matter what N is. This
> )means there are ALWAYS MORE ROWS THAN COLLUMNS, because 10^N increases way
> )faster than N, so the diagonal only samples a small portion of the first few
> )rows, and the rest of the rows are free to contain a match to our number!
>
> You need to read what I just wrote carefully and understand it.
>
> One needs to take more care when working with binary, but even then the
> problems are not insurmountable. But why insist on doing things in a
> difficult base?
I find there is no more care needed when using binary. I find it easier to
work with, actually. Remember that 10 is not magical, we just happened to
have 10 fingers.
- GLYPH
Dave Seaman
Virgil <vm...@frii.com> wrote:
>In article <19980924141658...@ng58.aol.com>, batc...@aol.com
>(BatchBiz) wrote:
>> My logic is:-
>> 1. To have a real number you have to have a section of the rationals;
>there is
>> no other way to get a real number.
Agreed.
>> 2. To have a section you have to have P and Q.
Not necessarily. You need an L and U. You could trivially define a P
and Q in terms of L and U.
>> 3. Properties P and Q must be definable in a finite string in some language.
>> (The examples given are trivially short: 'x^2>2')
Can you quote from Hardy where he says the properties must be definable
in a finite string? The fact that he didn't give any infinitely long
examples is probably attributable to the printing costs.
>> 4 All possible strings can be written in a countable list.
>> Thus, the number of reals(defined by Dedekind Section) is not greater than
>> the number of defining P's.
>> Conclusion: the number of reals is countable.
The number of reals defined by finitely-describable Dedekind sections is
countable.
>To have a section, you must have the sets U and L, but why do you need
>properties P and Q?
You don't. If you have U and L, you can derive P and Q, or conversely.
It doesn't matter which comes first.
>If you insist on complete constructability, every construction must be
>completed in a finite number of steps, so every constructable set is
>FINITE and the number of such constructions is FINITE. How do you justify
>infinite sets?
The set of even integers is infinite and is also constructible. If you
hand me any integer, I can determine in finite time whether it is even
or not.
A set is constructible if there is a finite decision procedure for
determining whether any given integer belongs to the set. If we are
talking about constructible reals, we can represent each one by the
Goedel number of a Turing machine that computes it, which is an
integer. A Turing machine computes a real number x if, for each n,
running the Turing machine with input n produces the n-th digit of x.
--
Dave Seaman dse...@purdue.edu
++++ stop the execution of Mumia Abu-Jamal ++++
++++ if you agree copy these lines to your sig ++++
++++ see http://www.xs4all.nl/~tank/spg-l/sigaction.htm ++++
Robert Low
>> )Somebody please give me a number (between 0 and 1) which is not on the
>> )following list:
>> )
>> )0.0000...
>> )0.1000...
>> )0.2000...
>> )0.3000...
>> )0.4000...
>> )0.5000...
>> )0.6000...
>> )0.7000...
>> )0.8000...
>> )0.9000...
>> )0.0100...
>> )0.1100...
>> )0.2100...
>> )0.3100...
>> )0.4100...
>> )...
>> )0.9999...
The last line there is a little misleading. But never mind, the construction
you have in mind seems pretty clear. In particular, note that because
of the way you have built the list, if n is any positive integer,
the nth number in your list has zeros in all places after the nth.
(And in quite a few of the places before it, too.)
>> I can give you one. sqrt(2) is not on your list. Every number on your list
>> is rational.
>
>Please prove this. You may be right.
Consider the nth number on your list. It has fewer than n leading
non-zero digits. Therefore it is rational. This is true for every
value of n. Therefore every number your list included is rational.
>This yields 0.666666... which I maintain is on the list.
Tell me where it appears on the list. If it's on the list, it
appears at the nth position, for some finite value of n. But
the number in the nth position has fewer than n non-zero
digits in it. Your list contains only terminating decimal
expansions.
It's probably the fact that you've stuck in that
'0.9999...' in the final place without stopping to think
about it that has misled you.
Dave Seaman
Jeroen Bruijning <jer...@parklane.demon.nl> wrote:
>BatchBiz wrote in message <19980924214244...@ng55.aol.com>...
>>Jeroen Bruijning wrote:
>>>>Please give an example of a Dedekind cut for which there is no rule for
>>>>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
I have often wondered: is everyone from Missouri an atheist?
Never mind...
It depends on what you mean by a "rule". Do you mean something that
can be used to arrive at a yes-or-no answer in finite time for all
questions of the form "is q a member of L?", where q may be any given
rational number? If that's what you mean, then there are only
countably many rules, but there are uncountably many reals. Clearly,
there must be some reals that have no such rule.
[obscure notation snipped]
>The rest of your reply I don't understand. Let me try to define the number z
>again to see if that resolves the issue. The cut corresponding to z is:
>
>L = { x in Q | Q < 0 } if the Goldbach conjecture is true
>L = { x in Q | Q > 1 } if the Goldbach conjecture is false
>
>R = { x in Q | Q < 1 } if the Goldbach conjecture is true
>R = { x in Q | Q > 1 } if the Goldbach conjecture is false
I don't understand this notation either. Is Q supposed to represent
the set of rationals? If not, then what does "x in Q" mean, exactly.
If Q *is* the rationals, then what does "Q < 0" or "Q > 1" mean?
>Classically, z is a well defined number and (classically) one can prove (z =
>0 OR z = 1) (but nobody knows wheter it is 0 or 1 because that would settle
>the Goldbach conjecture).
Then z is a constructible real. It is defined by a finite rule; we
just don't happen to know which rule it is.
>(If you are uncomfortable with a rational number as example, take sqrt(2)
>and sqrt(3) instead of 0 and 1.)
>
>Now, z is a well defined number, yet are you sure that there is a rule to
>tell you on which side of the cut 1/2 is lying?
Absolutlely, a rule exists. I can't tell you which rule it is, but I
can narrow it down to two possibilities.
>I hope that at lease this makes clear the definition of z.
You might say that z has been "defined" but not necessarily "specified"
by that rule. It's specified iff GC is decidable.
>Maybe this takes away your doubts. If not, it could be interesting to
>continue the discussion but I would then like to have a mathematically
>precise definition of "rule" first.
It's an informal term and does not have a precise definition. Here is
an example of a rule, unlike the one above, that does not correspond in
any way to a finite decision procedure (a computable function):
We know the constructible reals are a countable set. In fact, each
constructible real can be represented by an integer representing the
Goedel number of some Turing machine.
We know that not all Turing machines halt. In general, it is not
possible to decide whether TM_k will halt when started with input n.
We'll say that TM_k computes a real number if, for each n, TM_k(n)
halts and produces an integer in [0,9], representing the k-th digit of
a number.
Given an integer k, we cannot, in general, decide whether TM_k computes
a real number according to this definition. That would require solving
the halting problem, which we know is impossible.
Although we can't actually compute it, we can conclude that there is a
list CR(0), CR(1), ... of all the computable reals. Specifically, let
CR(0) be the least integer k such that TM_k computes a real number
according to the definition above. Let CR(1) be the least k > CR(0)
such that TM_k computes a real number, and in general let CR(n+1) be
the least k > CR(n) such that TM_k computes a real number.
I can now write down a "rule" for specifying a number x. For each k > 0,
we find the k-th computable real and compute its k-th digit
T_CR(k)(k). If that number is a 5, we let the k-th digit of x be a 6.
Otherwise, we let the k-th digit of x be a 5.
Then x is a real number, but there is no Turing machine that computes
it. It is specified by a "rule", but the "rule" does not correspond to
a computational procedure. That's because there is no computation that
can produce CR(k) for each k.
Therefore, x is a nonconstructible real. If (L,U) is the Dedekind cut
for x, then there is no rule that can be expressed in a finite number
of symbols for determining whether a given rational q belongs to L or
to U.
graham...@hotmail.com
Okay. That makes sense when the list is finite, but what happens when the
list is infinitely long?
> >This yields 0.666666... which I maintain is on the list.
>
> Tell me where it appears on the list. If it's on the list, it
> appears at the nth position, for some finite value of n. But
> the number in the nth position has fewer than n non-zero
> digits in it. Your list contains only terminating decimal
> expansions.
The number 0.6666... is at position (10^aleph_0)*6/9. This is 2/3 of the way
down the list. If the list is infinitely long, there will be infinite digits
before termination.
> It's probably the fact that you've stuck in that
> '0.9999...' in the final place without stopping to think
> about it that has misled you.
Could be. But why should this number not be the last number on the list,
considering the fact that the list is infinitely long?
Tapio Hurme
After following this thread - a moment, would you like - please-consider
this:
1) Every number is an infinite string of digits. It is any number is a
combination of infinite place holders before and after any decimal point(s)
and every place holder can have (in 10-base system) one of the following
alternatives, i.e. digits:
0,1,2,3,4,5,6,7,8, and 9.
2) If some "cut" or a diagonal can result in such a combination of place
holders that have no the symbols, i.e. digits, mentioned above, then you
have proofed that Cantor´s diagonal string (= a new number) was not included
in the original list.
Note: you can only use digits 0,1,2,3,4,5,6,7,8, and 9 in any order and in
any place holder.
3) The well ordering depends on the order and on the content of the place
holder.
4) Write it, i.e. your diagonal down now here:
________________________________
What is your conclusion? Did you use some of the digits:0,1,2,3,4,5,6,7,8,
and 9 in any place holder?
A) If yes - Cantor´s Diagonal proof flawed.
B) If not - congratulations! Then you have proofed Cantor´s Diagonal Theory.
Tapio
Dave Seaman
Jeroen Bruijning <jer...@parklane.demon.nl> wrote:
>I can sympathize with your resistance to accept non-finitely expressible
>"rules" for defining Dedekind cuts, but there is nothing in classical
>mathematics that demands that such a rule exists.
True.
>However, there are schools in mathematics that indeed do not accept
>definitions that are not "decidable" in a certain sense. Intuitionism, for
>example, will not accept real numbers that are the result of a "cut" where
>it is undecidable for each rational on which side it lies.
An example would be something like: x is the number whose n-th digit is
1 if TM_n(n) halts, and 0 otherwise. In other words, start running
Turing Machine number n with an input of n. If it ever halts, set the
digit to 1. If it doesn't halt, set the digit to 0. This is a "rule"
that does not correspond to a finite decision procedure.
>For example, the
>"cut" defined by (in shorthand):
>
>x<0 | x>0 if there exist 10^10 consecutive 7's in the decimal expansion of
>Pi
>x<1 | x >1 otherwise
>
>does not define a real number, since there is no way to determine on which
>side 1/2 lies. One puzzling thing with this is that tomorrow this suddenly
>might become a well-defined number, either 0 or 1, in case somebody solves
>the condition.
If I understand you correctly, then this is a cut that is defined by a
rule, and a finite one at that. We just don't happen to know which
rule it is. The definition of a computable real says a rule (or a TM
or whatever you are using to specify numbers) has to exist, but it
doesn't say we have to have a rule for finding out which rule (or TM,
etc.) is the applicable one.
If somebody finds 10^10 consecutive 7's tomorrow, it doesn't mean the
value of the number has changed. It's still the same number as before,
and it still has a finite rule for computing it. The only thing that's
changed is that we now know which rule it is.
An old riddle, dating from the time when Australia was considered to be
an island rather than a continent, goes:
Q. What was the biggest island before Australia was discovered?
A. Australia.
Jeroen Bruijning
Dave Seaman wrote in message <6ugcq7$g...@seaman.cc.purdue.edu>...
>In article <906701782.7804....@news.demon.nl>,
>Jeroen Bruijning <jer...@parklane.demon.nl> wrote:
>
>>BatchBiz wrote in message <19980924214244...@ng55.aol.com>...
>
z
>>again to see if that resolves the issue. The cut corresponding to z is:
>>
>>L = { x in Q | Q < 0 } if the Goldbach conjecture is true
>>L = { x in Q | Q > 1 } if the Goldbach conjecture is false
>>
>>R = { x in Q | Q < 1 } if the Goldbach conjecture is true
>>R = { x in Q | Q > 1 } if the Goldbach conjecture is false
>
>I don't understand this notation either. Is Q supposed to represent
>the set of rationals? If not, then what does "x in Q" mean, exactly.
>If Q *is* the rationals, then what does "Q < 0" or "Q > 1" mean?
Oops. That should read:
L = { x in Q | x < 0 } if the Goldbach conjecture is true
L = { x in Q | x > 1 } if the Goldbach conjecture is false
R = { x in Q | x < 1 } if the Goldbach conjecture is true
R = { x in Q | x > 1 } if the Goldbach conjecture is false
where Q, as you guessed, stands for the rationals.
>
>>Classically, z is a well defined number and (classically) one can prove (z
=
>>0 OR z = 1) (but nobody knows wheter it is 0 or 1 because that would
settle
>>the Goldbach conjecture).
>
>Then z is a constructible real. It is defined by a finite rule; we
>just don't happen to know which rule it is.
>
Classically, yes. Intuitionistically, no. Whether it is an example
acceptable to the original poster entirely depends on what he understands a
"rule" to be.
[snip]
>>Maybe this takes away your doubts. If not, it could be interesting to
>>continue the discussion but I would then like to have a mathematically
>>precise definition of "rule" first.
>
>It's an informal term and does not have a precise definition.
It is difficult to reason about what is a real, based upon the requirement
that it must be definable using a rule, without defining what a rule is. Of
course, the question was aimed at the original poster.
Good example. Hope it satisfies whatever the original poster calls a "rule".
Jeroen Bruijning
Jeroen.
Clark wrote in message <36099D0F...@pophost.eunet.be>...
>Jeroen Bruijning wrote:
>-snip-
>> It is important however to realize that one is then essentially
questioning
>> the very definition of the mathematical reasoning employed. This you
cannot
>> do from within the system. In other words, even if you feel that the
Cantor
>> result is "wrong", there is no way to refute the proof using standard
>> mathematical arguments. In standard mathematics the Cantor proof works,
>> however you may dislike it. (Please understand that so-called
non-standard
>> analysis as in Robinson's book is actually perfectly standard
mathematics.
>> One can get confused very easily here.)
>>
>-snip-
>
>I'm interested in this idea of 'the very definition of
>mathematical reasoning'. Is there more to the notion than
>'reasoning acceptable to the mathematical community at large'? If
>so, how easy is it to characterise it? And, further, given such a
>characterisation, how much sense can be made of justifying the
>characterisation? (Is there a justification of your definition
>which escapes the charge of amounting to no more than 'acceptable
>to mathematicians' in its turn, in other words?) And so on. You
>get the idea? How soon before you hit bottom, as it were?
>
>That seems a lot of questions, but most are just amplifications
>of the first one. I'm not sure it's one of your 'RIGHT' questions
>- probably not. Still, I'd be grateful for any answers or
>comments.
>
>Bob
BatchBiz
JEROEM bTUIJNING WROTE:->
>>>
>
>>>>Please give an example of a Dedekind cut for which there is no rule for
>>>>assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
>>>
>>>
>>>defines a real number the decimal expansion of which is unknown:
>>>
>>>x<1 | x>1 otherwise
>>>
>>I don't understand the number you have defined. Let me try to answer
>anyway.
>
>
>again to see if that resolves the issue. The cut corresponding to z is:
>
>L = { x in Q | Q < 0 } if the Goldbach conjecture is true
>L = { x in Q | Q > 1 } if the Goldbach conjecture is false
>
>R = { x in Q | Q < 1 } if the Goldbach conjecture is true
>R = { x in Q | Q > 1 } if the Goldbach conjecture is false
>
>0 OR z = 1) (but nobody knows wheter it is 0 or 1 because that would settle
>the Goldbach conjecture).
>
>and sqrt(3) instead of 0 and 1.)
>
>Now, z is a well defined number, yet are you sure that there is a rule to
>tell you on which side of the cut 1/2 is lying?
>
'property', as used by Hardy would be a better term). The number you nave
defined will be either 0 or 1 depending on whether the Goldbach conjecture is
true or false. At present we don't know which.
The Dedekind section is our only tool for defining real numbers. If one can
determine whether a particular 'x' belongs to U or Lthe number is computable.
If one cannot do this the number is non-computable.
>
>Maybe this takes away your doubts. If not, it could be interesting to
>continue the discussion but I would then like to have a mathematically
>precise definition of "rule" first.
>
>Best regards,
>
>Jeroen.
>
Thanks again
Dick
"Make a fast friend - adopt a greyhound"
Dick Batchelor
"Orchids grow free where CAIOS reigns"
BatchBiz
William Hughes writes:>
>> Please give an example of a Dedekind cut for which there is no rule for
>> assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
>
>be difficult.
>
>However. There are countable number of rules. There are
>an uncountable number of reals. Every real is described
>by a Dedekind cut.. There must be at least one Dedekind cut for
>which there is no rule. This should be good enough even
>for someone from Missouri.
>
> -William Hughes
are an uncountable number of reals; this is the point under discussion. I
continue to maintain that for every real there is a Dedekind section, for every
Dedekind section there is a rule and the number of rules is countable.
Thanks for you interest.
Dave Seaman
>
>0.0000...
>0.1000...
>0.2000...
>0.3000...
>0.4000...
>0.5000...
>0.6000...
>0.7000...
>0.8000...
>0.9000...
>0.0100...
>0.1100...
>0.2100...
>0.3100...
>0.4100...
>...
>0.9999...
Any irrational number will do. By the way, 0.9999... is not on the
list, because it has infinitely many predecessors. A list is a mapping
defined on the natural numbers, and each natural number is finite.
It is clear that each number on your list has only finitely many
nonzero digits. In particular, the first ten entries have at most one
nonzero digit, the first 100 have at most 2 nonzero digits, and in
general, the first 10^n entries have at most n nonzero digits. This
holds for each n. Therefore, no entry in your list has infinitely many
nonzero digits. Again, the 0.9999... that you claim is there does not
occupy a finitely-numbered position on the list, and therefore it is
not on the list.
>The diagonal is 0.0000... Changing each digit I could get 0.9999... Cantor
>suggests this is not on the list, but it clearly is. I posted a binary
>version of this already, and again the reason that Cantor is wrong is that
>when the list has N columns, it has 10^N rows, no matter what N is. This
>means there are ALWAYS MORE ROWS THAN COLLUMNS, because 10^N increases way
>faster than N, so the diagonal only samples a small portion of the first few
>rows, and the rest of the rows are free to contain a match to our number!
What is the number of the row that contains 0.9999...?
What is the number of a row that does not have a diagonal entry?
Your "always more rows than columns" argument is based on the
assumption that we are talking about finite digit strings, which is
incorrect. If you attempt to extend this argument to infinite digit
strings, you get the result that 10^aleph_0 is greater than aleph_0,
which is (a) a true statement, and (b) by a truly amazing coincidence,
exactly identical to what we wanted to prove in the first place --
namely, that there is no countable list of all possible real numbers.
Therefore, your attempt at defeating the diagonal argument has
backfired by producing the very result that you were desperately trying
to avoid.
Jeroen Bruijning
Dave Seaman <a...@seaman.cc.purdue.edu> schreef in artikel
<6ugk6e$g...@seaman.cc.purdue.edu>...
> In article <906668625.906.0...@news.demon.nl>,
> Jeroen Bruijning <jer...@parklane.demon.nl> wrote:
> >I can sympathize with your resistance to accept non-finitely expressible
> >"rules" for defining Dedekind cuts, but there is nothing in classical
> >mathematics that demands that such a rule exists.
>
> True.
>
> >However, there are schools in mathematics that indeed do not accept
> >definitions that are not "decidable" in a certain sense. Intuitionism,
for
> >example, will not accept real numbers that are the result of a "cut"
where
> >it is undecidable for each rational on which side it lies.
>
> An example would be something like: x is the number whose n-th digit is
> 1 if TM_n(n) halts, and 0 otherwise. In other words, start running
> Turing Machine number n with an input of n. If it ever halts, set the
> digit to 1. If it doesn't halt, set the digit to 0. This is a "rule"
> that does not correspond to a finite decision procedure.
>
> >For example, the
> >"cut" defined by (in shorthand):
> >
> >x<0 | x>0 if there exist 10^10 consecutive 7's in the decimal expansion
of
> >Pi
> >x<1 | x >1 otherwise
> >
> >does not define a real number, since there is no way to determine on
which
> >side 1/2 lies. One puzzling thing with this is that tomorrow this
suddenly
> >might become a well-defined number, either 0 or 1, in case somebody
solves
> >the condition.
>
> If I understand you correctly, then this is a cut that is defined by a
> rule, and a finite one at that. We just don't happen to know which
> rule it is. The definition of a computable real says a rule (or a TM
> or whatever you are using to specify numbers) has to exist, but it
> doesn't say we have to have a rule for finding out which rule (or TM,
> etc.) is the applicable one.
>
> If somebody finds 10^10 consecutive 7's tomorrow, it doesn't mean the
> value of the number has changed. It's still the same number as before,
> and it still has a finite rule for computing it. The only thing that's
> changed is that we now know which rule it is.
>
> An old riddle, dating from the time when Australia was considered to be
> an island rather than a continent, goes:
>
> Q. What was the biggest island before Australia was discovered?
>
> A. Australia.
>
You are quite right, in classical mathematics. But not in some other
systems. The interpretation of "exists" for example can differ, like when
one insists that a function only "exists" if an effective process can be
identified to compute it (to an arbitrary degree). In such a system the
number z is not proven to be well defined until the process has been
described.
A rather extreme form of assuming that things "exist" is the Axiom of
Choice. It is not for nothing that it is often mentioned explicitly if used
in a proof. This illustrates already that even the classical mathematical
community may differ as to what assumtions are allowable.
My post was intended to highlight that issues like "existence" need not be
taken for granted, that other approaches than the classical one can be
taken seriously, and that arguments may have different outcome depending on
the choice made. Even in a serious mathematical setting.
The quotation about Australia is illustrative. Intuitionists might not
agree with Australia existing before it was discovered. Rather strange if
one thinks about the "physical" world, but perhaps less strange when
applied to a mental construct like the reals? Or do the reals exist
independent from our thinking? And what is the meaning of the preceding
sentence, especially the word "exist"? Questions, questions...
I just want to point out that these ideas cannot be discarded offhand.
Serious mathematicians have experimented with these ideas. (As have, alas,
many crackpots).
Jeroen.
Jon P LeVitre
>> >> )Somebody please give me a number (between 0 and 1) which is not on the
>> >> )following list:
>> >> )
>> >> )0.0000...
>> >> )0.1000...
>> >> )0.2000...
>> >> )0.3000...
>> >> )0.4000...
>> >> )0.5000...
>> >> )0.6000...
>> >> )0.7000...
>> >> )0.8000...
>> >> )0.9000...
>> >> )0.0100...
>> >> )0.1100...
>> >> )0.2100...
>> >> )0.3100...
>> >> )0.4100...
>> >> )...
>> >> )0.9999...
>The number 0.6666... is at position (10^aleph_0)*6/9. This is 2/3 of the way
>down the list. If the list is infinitely long, there will be infinite digits
>before termination.
How about this, Note that each real in the list (.zyxwv...)
occupies the ...vwxyz'th position in the list (for example,
.41 is in position 14). Also note that each position number
is a Natural.
The real .666... can not be in the list, because ...666 is not
a natural number.
If that doesn't convince you, then please tell me where the reals
.575757... and .757575... appear in the list (relative to each other
and .666...). What about pi/10 and pi-3?
jonl
Mike McCarty
<graham...@hotmail.com> wrote:
)In article <6ueo2l$579$1...@relay1.dsccc.com>,
) jmcc...@sun1307.spd.dsccc.com (Mike McCarty) wrote:
)> In article <6uemnk$eto$1...@nnrp1.dejanews.com>,)> )Somebody please give me a number (between 0 and 1) which is not on the
)> )following list:
)> )
)> )0.0000...
)> )0.1000...
)> )0.2000...
)> )0.3000...
)> )0.4000...
)> )0.5000...
)> )0.6000...
)> )0.7000...
)> )0.8000...
)> )0.9000...
)> )0.0100...
)> )0.1100...
)> )0.2100...
)> )0.3100...
)> )0.4100...
)> )...
)> )0.9999...
)>
)> I can give you one. sqrt(2) is not on your list. Every number on your list
)> is rational.
)
)Please prove this. You may be right.
I *did* prove it. Every number in your list is rational. Every one of
them is a terminating decimal, hence rational. Since 1/sqrt(2) is not
rational, it is not on your list.
)> )The diagonal is 0.0000... Changing each digit I could get 0.9999... Cantor
)>
)> Well, one *could*. Here is the way I would generate a number not on your
)> list, using a "diagonal" technique.
)>
)> If the digit is less than or equal to 5, then the new digit is 6. If the
)> digit is greater than 5, then the new digit is 4. This always changes a
)> digit, and cannot have even one 9 or one 0 in it, hence no ambiguity.
)
)This yields 0.666666... which I maintain is on the list.
It does not generate 0.6666..., if by that you mean an unterminating
string of 6s, unless every one of the numbers on the "list" you gave
doesn't have any digits over 5. That means that you haven't even listed
all the rationals, let alone all the reals.
)> )suggests this is not on the list, but it clearly is. I posted a binary
)> )version of this already, and again the reason that Cantor is wrong is that
)> )when the list has N columns, it has 10^N rows, no matter what N is. This
)> )means there are ALWAYS MORE ROWS THAN COLLUMNS, because 10^N increases way
)> )faster than N, so the diagonal only samples a small portion of the first few
)> )rows, and the rest of the rows are free to contain a match to our number!
)>
)> You need to read what I just wrote carefully and understand it.
)>
)> One needs to take more care when working with binary, but even then the
)> problems are not insurmountable. But why insist on doing things in a
)> difficult base?
)
)I find there is no more care needed when using binary. I find it easier to
)work with, actually. Remember that 10 is not magical, we just happened to
)have 10 fingers.
Binary is more difficult to work with IN THIS CONTEXT, because there is
no way to avoid the 0.0001011011111111... vs 0.00011000000...
representational quirk. In base 4 or higher, it is possible to avoid it.
I said nothing about 10 at all, let alone it being magical.
What an irritating and supercilious post.
Robert Low
<graham...@hotmail.com> wrote:
>The number 0.6666... is at position (10^aleph_0)*6/9. This is 2/3 of the way
>down the list. If the list is infinitely long, there will be infinite digits
>before termination.
If your list is not indexed by omega, then it has nothing to do
with Cantor's proof.
Mike McCarty
BatchBiz <batc...@aol.com> wrote:
)
)William Hughes writes:>
)>> Please give an example of a Dedekind cut for which there is no rule for
)>> assigning the rationals to U and L. " I'm from Missouri; SHOW ME"
)>
)>Please construct for me an non-constructable real. This is going to
)>be difficult.
)>
)>However. There are countable number of rules. There are
)>an uncountable number of reals. Every real is described
)>by a Dedekind cut.. There must be at least one Dedekind cut for
)>which there is no rule. This should be good enough even
)>for someone from Missouri.
)>
)> -William Hughes
) Great! You've understood my point. However, you can't just declare that there
)are an uncountable number of reals; this is the point under discussion. I
)continue to maintain that for every real there is a Dedekind section, for every
)Dedekind section there is a rule and the number of rules is countable.
What we have here, is failure to communicate.
Please define "rule" as you use it.
I suspect that you are using it in an unusual manner.
Mark Adkins
starts out by asking the seemingly innocuous question, "Is it possible
to construct a repeating diagonal number even if you want to?" and ends
by demonstrating that the diagonal process is inherently paradoxical.
First, let me distinguish between two types of repeating real numbers:
(a) the kind that eventually repeats a single digit forever; (b) the
kind that repeats some arbitrarily large but finite sequence of digits
forever.
Since binary expansions absolutely determine the diagonal number at
each step of construction, I'm going to use decimal expansions because
these give the constructor latitude. That is, if the nth digit of
the nth list number is a "7", that still leaves nine other decimal
digits to choose from, and we want to be able to *choose* to construct
a repeating diagonal number -- if that's possible.
Let's deal with type (a) repeaters first, by using the example of
numbers which end in an infinite sequence of nines (.392899999...)
It should be clear that in order to be able to construct such a
number diagonally, it must be the case that after some arbitrarily
large but finite number of steps, no subsequent list number has a 9
in its nth digit, because at step n of the diagonal construction
process, the nth digit of the diagonal number must be different from
the nth digit of the nth list number.
Any putative list of all reals (from which the Cantor proof works)
could at least contain all the rationals. There are an infinite number
of rationals with a 9 in their nth digit but which do not themselves
end in all nines. Then, since there are an infinite number of these
for every n, there is no way to order a list so that no such number
appears on the list after an arbitrarily large but finite number of
steps. Therefore, there is no way to construct a diagonal number which
ends in all nines from any such list.
Pick any decimal number from 0 to 8 as the infinitely repeating digit,
and the same argument holds. Then there is no way to construct a
diagonal number which is a type (a) repeater of any sort, from a list
containing all of the rationals, whether this list purports to be a
complete list of all reals or not. Note that this logic holds for
binary expansions as well.
Now we can examine whether it is possible to choose to construct a
diagonal number which is a type (b) repeater. To simplify matters,
let's not pretend to construct a list of all reals at all, but merely
a list of all rationals -- something we all agree is possible.
We know that any type (b) repeater eventually repeats some arbitrarily
large but finite sequence of digits. Every such cyclic number has a
period defined by the length of the repeating sequence. A number such
as .298312121212... is a period-2 repeater: that is, given any digit
in the repeating sequence, that digit will always reappear after 2
more digits. For example, given the digit 1 in the repeating
sequence above, this digit will always repeat every second digit
subsequently, and the same thing is true for the digit 2. Every
type (b) repeater is a period-i repeater, where i is some natural
number.
If we are trying to construct a diagonal number which is a type (b)
repeater, then at some point the diagonal number must enter a
repeating sequence of period-i. The first digit of the diagonal's
repeating sequence will appear at some particular step n of the
diagonal construction process.
Using the period-2 repeater above as an example of a diagonal type (b)
repeater we might try to create, we can see that at step 5 of the
diagonal process, the diagonal number will enter a cycle of period-2.
Then, the digit 1 must reappear in the diagonal at every subsequent
step n such that n = 5+(2*c) where c is any natural number, and the
digit 2 must appear at step 6 and at every subsequent step n such that
n = 6+(2*c). We will assume that the first six digits of the diagonal
are consistent with the list of rationals from which they are
constructed. It therefore becomes critical that the 7th digit of the
7th list number is not a 1, because if it is we can't choose 1 for the
7th digit of our diagonal number, and then we have to abandon our
attempt to create a type (b) repeating diagonal using this template.
In general, it is critical that the digit 1 does not appear as the nth
digit of a list number at any step n of the diagonal process such that
n = 5+(2*c), and also critical that the digit 2 does not appear as the
nth digit of a list number at any step n such that n = 6+(2*c).
There are an infinite number of rational numbers with a 1 in their nth
digit, and the same is true for rational numbers with a 2 in their nth
digit. However, there are also an infinite number of steps in the
diagonal process, and there is no theoretical reason why a list of all
rationals could not be arranged so that when list numbers with a 1 in
their nth digit appear in the list, they only occupy list positions
indexed to n such that n = 6+(2*c); and that when list numbers with a 2
in their nth digit appear in the list, they only occupy list positions
indexed to n such that n = 5+(2*c). Of course, they would not occupy
all such positions, since otherwise the list would not contain numbers
with other values (such as 0 or any of 3 through 9) in their nth
digits, so you must understand that when I say that they will only
appear in those list positions, I mean just that, and not that they
will always appear in those list positions.
To simplify matters further, let's stipulate that our list of rationals
will exclude integer ratios p/q such that p<0, q<0, p=0, p>q, or p=q.
This will insure that every rational decimal expansion on our list is
unique (as opposed to the expansions from 1/1 and 2/2, or 2/1 and 4/2,
etc.), that all decimal expansions will lie within the open unit
interval (0,1), and that therefore our diagonal number will also lie
within this interval: this will eliminate pesky problems like
determining decimal point placement for the diagonal number or
determining its sign. Then the list will consist of all rational
numbers in the open unit interval (0,1).
NOW WE HAVE A REAL PROBLEM ON OUR HANDS. (No pun intended.)
By design, our list contains every rational number in the interval
(0,1), and the diagonal number is also in this interval. We have
constructed a diagonal number which is different in its decimal
expansion in at least one digit from the decimal expansion of every
number on our list. But the diagonal number repeats and is therefore
rational. Then our list of all rationals in the unit interval must
contain the diagonal number: but this is a paradox. To make matters
worse, the diagonal number is a cyclic repeater, so we know that by
any definition it is truly distinct from the decimal expansion of
every other rational number, since duals must either end in all zeroes
or all nines.
Note that this paradox is not necessarily eliminated by switching to
base two. A particular list of binary expansions will uniquely
determine the diagonal number constructed from this list, but there
are an infinite number of ways to order (list) the rational numbers.
Until someone can prove either that it is possible or impossible
for an ordering to determine a repeating binary expansion, the
question remains open.
Jeroen Bruijning
Mark Adkins wrote in message ...
Yes.
Therefore, there is no way to construct a diagonal number which
>ends in all nines from any such list.
No.
[rest deleted because irrelevant]
Jeroen.
ull...@math.okstate.edu
Mark Adkins <adk...@cyberspace.org> wrote:
> Here's another argument against Cantor's diagonal proof.
Does the word "spam" mean anything to you? How about
"#^$@ing spam"? So far it appears you've posted this new
one in at least three places.
I guess if you _are_ determined to make a fool of
yourself so persistently it shouldn't be any surprise
that you're determined to advertise the fact - never
mind.
Mark Adkins
cyclicly repeating numbers and a claimed paradox in the diagonal process.
Any rational which eventually ends in "12121212..." will always prevent
a diagonal using the same cyclic ending no matter where you place it
on the list. Something similar is true for any cyclic repeater, so
in fact it isn't possible at all to construct a repeating diagonal
number of any sort even if you want to, using the diagonal process,
so the whole "paradox" collapses.
I suppose this has been pointed out by someone else by now.
Rob Scharein
>
> This is a dangerous area, but perhaps somebody can explain why this argument
> that the reals are countable is wrong.
> The integers are countable (of course)
> Rationals are defined as ordered pairs of integers and are countable.
> Real numbers are defined by a "Dedekind section" of the rationals. For each
> real number there is a rule assigning rationals to the segment U or L
> perhaps English or perhaps some special "Dedekind Section Definition Language."
> Arrange all such rules by length alphabetically. This list of rules is
> countable, but it is in 1:1 correspondence with the reals. I deduce the reals
> are countable!
All this proves is that the computable real numbers are countable, which
is
certainly true. However, there are an uncountable number of reals that
could not be defined in any finite string in such a "Dedekind Section
Definition Language".
rob scharein
dept of computer science
university of british columbia
Erland Gadde
> There are an infinite number of rational numbers with a 1 in their nth
> digit, and the same is true for rational numbers with a 2 in their nth
> digit. However, there are also an infinite number of steps in the
> diagonal process, and there is no theoretical reason why a list of all
> rationals could not be arranged so that when list numbers with a 1 in
> their nth digit appear in the list, they only occupy list positions
> indexed to n such that n = 6+(2*c); and that when list numbers with a 2
> in their nth digit appear in the list, they only occupy list positions
> indexed to n such that n = 5+(2*c). Of course, they would not occupy
> all such positions, since otherwise the list would not contain numbers
> with other values (such as 0 or any of 3 through 9) in their nth
> digits, so you must understand that when I say that they will only
> appear in those list positions, I mean just that, and not that they
> will always appear in those list positions.
You mean that it is always possible to list the rationals in (0,1) in such
a way that whenever a 1 occurs on the diagonal, the list number n of the
rational in question (= the position number of the digit) satisfies 6+2c,
for some c, and whenever a 2 occurs on the diagonal, n=5+2d for some d.
To me, it seems in no way obvious that such a list should be possible,
and actually, your argument below shows that such a list is impossible!
If you actually can prove that there exists such a list (for example, by
explicitly constructing one), then you will obtain a contradiction, but
I'm sure you can't prove this!
> By design, our list contains every rational number in the interval
> (0,1), and the diagonal number is also in this interval. We have
> constructed a diagonal number which is different in its decimal
> expansion in at least one digit from the decimal expansion of every
> number on our list. But the diagonal number repeats and is therefore
> rational. Then our list of all rationals in the unit interval must
> contain the diagonal number: but this is a paradox.
Regards,
Erland Gadde
Tapio Hurme
Erland Gadde wrote in message ...
>In article <Pine.SUN.3.96.980926...@grex.cyberspace.org>,
>Mark Adkins <adk...@cyberspace.org> wrote:
(snip)
You are very much concentrated in the decimal numbers.
The decimal point is "mark" to devide two infinite long parts: before and
after the decimal point.
IFF Cantor愀 diagonal works after the decimal point resulting "new" numbers,
it should work also with the integers (only) because of the symmetry for
example.
Can you create or produce any new integers? NO- you cannot. All the integers
already exist though you cannot write them down - well, it dares so long. So
Cantor does not work.
Tapio
Arthur L. Rubin
>
> Erland Gadde wrote in message ...
> >In article <Pine.SUN.3.96.980926...@grex.cyberspace.org>,
> >Mark Adkins <adk...@cyberspace.org> wrote:
>
> (snip)
>
> You are very much concentrated in the decimal numbers.
> The decimal point is "mark" to devide two infinite long parts: before and
> after the decimal point.
> IFF Cantor愀 diagonal works after the decimal point resulting "new" numbers,
> it should work also with the integers (only) because of the symmetry for
> example.
Have you been talking with Archimedes Plutonium? Conventional real
numbers only
have a finite number of places before the decimal point.
--
Arthur L. Rubin 216-...@mcimail.com
Tapio Hurme
Arthur L. Rubin <216-...@mcimail.com> wrote in message
>Have you been talking with Archimedes Plutonium? Conventional >real
>numbers only
>have a finite number of places before the decimal point.
I have not dicussed with AP. Let愀 assume we have a finite number of
places - as you reminded. What about if the same number is infinite?
It only means that the rest of the places after the "finite" are filled with
zeros. Therefore you may say all the numbers are infinite. We just use the
"short" notation and the purpose is to omit those symbols in the string that
are unnecessary to repeat. Before and after. Shortly number 9 would be
written also ........00000009.0000....
"Love potion #9"
Tapio
Mark Adkins
asserting that Cantor's diagonal proof is flawed, let me ask anyone
reading this to please explain to me why the fact that there is no
list of all reals proves that the cardinality of the reals is greater
than the cardinality of the naturals.
Look what actually happens: you start with a list of reals having
cardinality aleph_0 (because all lists have this cardinality if you
define a list as something indexed to the natural numbers, as Cantor
does). Then you produce a diagonal number from this list which is
different in at least one digit from every number on the list:
therefore the diagonal is not on the list.
At this point the usual reaction is to say that this demonstrates
that there is no bijection from the reals to the naturals and that
therefore the reals are of greater cardinality than the naturals.
However, what you actually have are two sets: the original list,
and a singleton consisting of the diagonal number produced from
that list. Since the countable sum of countable sets is countable,
then the union of those two sets is countable; specifically,
aleph_0 + 1 = aleph_0.
Furthermore, you can create a new list containing this union as
follows: for the first element of the new list, take the diagonal
number constructed from the old list. Then take each element of
the old list in sequence. Then you have a new list containing
all of them. True, you can now create a new diagonal number from
this new list, but so what? The cardinality will remain unchanged
and the new number is listable. This will remain true no matter
how many times you create new diagonal numbers this way.
Then, Cantor's diagonal proof only demonstrates that no list of
reals is complete. It doesn't demonstrate how to create a set of
unlistable reals: it doesn't give a single example of an unlistable
real. It doesn't demonstrate how to create a set of reals whose
cardinality is provably greater than that of the naturals: nor does
it demonstrate that there is any such set. How then does it
demonstrate what it claims to?
I'd appreciate email copies of any public replies to this.
Erland Gadde
Mark Adkins <adk...@cyberspace.org> wrote:
> Then, Cantor's diagonal proof only demonstrates that no list of
> reals is complete. It doesn't demonstrate how to create a set of
> unlistable reals: it doesn't give a single example of an unlistable
> real. It doesn't demonstrate how to create a set of reals whose
> cardinality is provably greater than that of the naturals: nor does
> it demonstrate that there is any such set. How then does it
> demonstrate what it claims to?
When we say that a set A has greater cardinality than a set B, we mean,
_by definition_, that there is an injection from B to A, but no bijection
from B to A. Since there is certainly an injection from N (naturals) to
R (reals) (just take the inclusion map from N into R), and since Cantor's
diagonal argument shows that there is no bijection from N to R, it follows
that R has greater cardinality than N.
To say that there is no complete list of reals is the same thing as saying
that there is no bijection from N to R, because if there was such a
bijection f:N->R, this would give such a complete list: Simply define
the list as: f(0),f(1),f(2),f(3),....
The purpose of the diagonal argument is certainly not to construct a
"set of unlistable reals", whatever that would mean (given any countable
set of reals, it is certainly possible to put it on some list), but just to,
just as you say, show that no list of reals is complete, whence there
is no list of all reals.
Regards,
Erland Gadde
Robert Hill
> Maybe I'm going about this the wrong way. Very well, instead of
> asserting that Cantor's diagonal proof is flawed, let me ask anyone
> reading this to please explain to me why the fact that there is no
> list of all reals proves that the cardinality of the reals is greater
> than the cardinality of the naturals.
Because it's the _definition_ of cardinality that if two sets cannot be put
in one-to-one correspondence, then they are of different cardinalities.
Cantor's argument shows that any attempt to put the (set of all) reals into
one-one correspondence with the (set of all) natural numbers must fail.
> Look what actually happens: you start with a list of reals having
> cardinality aleph_0 (because all lists have this cardinality if you
> define a list as something indexed to the natural numbers, as Cantor
> does). Then you produce a diagonal number from this list which is
> different in at least one digit from every number on the list:
> therefore the diagonal is not on the list.
A fine summary of the argument.
> At this point the usual reaction is to say that this demonstrates
> that there is no bijection from the reals to the naturals and that
> therefore the reals are of greater cardinality than the naturals.
This is not just the usual reaction, but correct.
> However, what you actually have are two sets: the original list,
> and a singleton consisting of the diagonal number produced from
> that list. Since the countable sum of countable sets is countable,
> then the union of those two sets is countable; specifically,
> aleph_0 + 1 = aleph_0.
This is true but irrelevant.
> Furthermore, you can create a new list containing this union as
> follows: for the first element of the new list, take the diagonal
> number constructed from the old list. Then take each element of
> the old list in sequence. Then you have a new list containing
> all of them. True, you can now create a new diagonal number from
> this new list, but so what? The cardinality will remain unchanged
> and the new number is listable. This will remain true no matter
> how many times you create new diagonal numbers this way.
Exactly so. We are not trying to change the cardinality by this means.
> Then, Cantor's diagonal proof only demonstrates that no list of
> reals is complete.
That's all we're trying to demonstrate, because that's enough to
prove that the reals are uncountable.
> It doesn't demonstrate how to create a set of
> unlistable reals:
You don't need to "create" such a set. The set of all reals is already such
a set. That's what we've just proved, by assuming the opposite and deriving
a contradiction.
> it doesn't give a single example of an unlistable real.
The argument is not attempting to prove the existence of an unlistable
real. This is fortunate, because there's no such thing as an unlistable
real. If you have a favourite real, or for that matter a finite or countable
collection of favourite reals, then we can easily arrange for the list
to include them. But we can't include (anywhere near) _all_ reals in the
list at the same time.
> It doesn't demonstrate how to create a set of reals whose
> cardinality is provably greater than that of the naturals: nor does
> it demonstrate that there is any such set.
Before we apply this argument, we are already assuming (or, in a properly
axiomatic treatment, have already proved) that there is such a thing as the
set of all reals. So we don't have to construct any "other" uncountable
set of reals.
> How then does it
> demonstrate what it claims to?
It shows that any countable set of reals does not contain all the reals.
But there is a set which contains all the reals.
Therefore this set of all the reals is not countable.
> I'd appreciate email copies of any public replies to this.
(I seem to have broken my usual oath not to join one of these
interminable threads.)
--
Robert Hill
University Computing Service, Leeds University, England
"Though all my wares be trash, the heart is true."
- John Dowland, Fine Knacks for Ladies (1600)
Mike McCarty
)
)Erland Gadde wrote in message ...
)>In article <Pine.SUN.3.96.980926...@grex.cyberspace.org>,
)>Mark Adkins <adk...@cyberspace.org> wrote:
)
)(snip)
)
)You are very much concentrated in the decimal numbers.
)The decimal point is "mark" to devide two infinite long parts: before and
)after the decimal point.
OH NO! Not Tapio's infinite decimal integers again!
)IFF Cantor愀 diagonal works after the decimal point resulting "new" numbers,
)it should work also with the integers (only) because of the symmetry for
)example.
)
)Can you create or produce any new integers? NO- you cannot. All the integers
)already exist though you cannot write them down - well, it dares so long. So
)Cantor does not work.
)
)Tapio
)
)
ull...@math.okstate.edu
"Tapio Hurme" <hurm...@dlc.fi> wrote:
>
> Erland Gadde wrote in message ...
> >Mark Adkins <adk...@cyberspace.org> wrote:
>
> (snip)
>
> You are very much concentrated in the decimal numbers.
> IFF Cantor愀 diagonal works after the decimal point resulting "new" numbers,
>
> Can you create or produce any new integers? NO- you cannot. All the integers
Right. And IF it works for the reals and the integers it follows
that it must work for the frogs. Can you produce a new frog? No you
can't.
Oh wait, maybe frogs and numbers are not the same thing, so
it could work in one case but not the other. Hey! Maybe real numbers
and integers are not the same thing. Let's see, a real has infinitely
many digits after the decimal point, while an integer has only
finitely many digits. Maybe this makes a difference?
No, that can't be it.
ull...@math.okstate.edu
Mark Adkins <adk...@cyberspace.org> wrote:
> Maybe I'm going about this the wrong way. Very well, instead of
> asserting that Cantor's diagonal proof is flawed, let me ask anyone
> reading this to please explain to me why the fact that there is no
> list of all reals proves that the cardinality of the reals is greater
> than the cardinality of the naturals.
Because that's the definition? (Well, that the definition
of "the reals are uncountable", in any case.)
> Look what actually happens: you start with a list of reals having
> cardinality aleph_0 (because all lists have this cardinality if you
> define a list as something indexed to the natural numbers, as Cantor
> does). Then you produce a diagonal number from this list which is
> different in at least one digit from every number on the list:
> therefore the diagonal is not on the list.
>
> At this point the usual reaction is to say that this demonstrates
> that there is no bijection from the reals to the naturals and that
> therefore the reals are of greater cardinality than the naturals.
>
> However, what you actually have are two sets: the original list,
> and a singleton consisting of the diagonal number produced from
> that list. Since the countable sum of countable sets is countable,
> then the union of those two sets is countable; specifically,
> aleph_0 + 1 = aleph_0.
>
> Furthermore, you can create a new list containing this union as
> follows: for the first element of the new list, take the diagonal
> number constructed from the old list. Then take each element of
> the old list in sequence. Then you have a new list containing
> all of them. True, you can now create a new diagonal number from
> this new list, but so what? The cardinality will remain unchanged
> and the new number is listable. This will remain true no matter
> how many times you create new diagonal numbers this way.
>
> Then, Cantor's diagonal proof only demonstrates that no list of
> reals is complete. It doesn't demonstrate how to create a set of
> unlistable reals: it doesn't give a single example of an unlistable
> real. It doesn't demonstrate how to create a set of reals whose
> cardinality is provably greater than that of the naturals: nor does
> it demonstrate that there is any such set. How then does it
> demonstrate what it claims to?
It does not demonstrate the existence of an "unlistable
real". Nobody has claimed that it does.
_Any_ real appears on _some_ list. It's not true that there
exists a list on which every real appears. You still seem to think
that these two statements are contradictory. They're not.
"Ex Ay P(x,y)" is a much stronger statement than "Ay Ex P(x,y)".
> I'd appreciate email copies of any public replies to this.
I'd appreciate you're stopping this nonsense. So we're even.
Mike McCarty
)asserting that Cantor's diagonal proof is flawed, let me ask anyone
)reading this to please explain to me why the fact that there is no
)list of all reals proves that the cardinality of the reals is greater
)than the cardinality of the naturals.
Definition: Two sets have the same cardinality iff there exists a
bijection between them.
Definition: The cardinality of a set A is greater than the cardinality
of a set B iff there exist 1-1 mappings from B into A, but no 1-1
mappings from B onto A.
Proposition: The cardinality of the reals is greater than the
cardinality of the non-negative integers.
[Proof left to the reader.]
)Look what actually happens: you start with a list of reals having
)cardinality aleph_0 (because all lists have this cardinality if you
)define a list as something indexed to the natural numbers, as Cantor
)does). Then you produce a diagonal number from this list which is
)different in at least one digit from every number on the list:
)therefore the diagonal is not on the list.
)
)At this point the usual reaction is to say that this demonstrates
)that there is no bijection from the reals to the naturals and that
)therefore the reals are of greater cardinality than the naturals.
)
)However, what you actually have are two sets: the original list,
)and a singleton consisting of the diagonal number produced from
)that list. Since the countable sum of countable sets is countable,
)then the union of those two sets is countable; specifically,
)aleph_0 + 1 = aleph_0.
What you actually have is a contradiction. You assumed that the list was
complete. You showed that this led to contradiction. You must retract
one of the hypotheses. Which one do you retract?
)Furthermore, you can create a new list containing this union as
)follows: for the first element of the new list, take the diagonal
Of course.
)number constructed from the old list. Then take each element of
)the old list in sequence. Then you have a new list containing
)all of them. True, you can now create a new diagonal number from
)this new list, but so what? The cardinality will remain unchanged
)and the new number is listable. This will remain true no matter
)how many times you create new diagonal numbers this way.
)
)Then, Cantor's diagonal proof only demonstrates that no list of
)reals is complete. It doesn't demonstrate how to create a set of
)unlistable reals: it doesn't give a single example of an unlistable
Not necessary.
)real. It doesn't demonstrate how to create a set of reals whose
Not necessary.
)cardinality is provably greater than that of the naturals: nor does
)it demonstrate that there is any such set. How then does it
)demonstrate what it claims to?
)
)I'd appreciate email copies of any public replies to this.
What is so difficult about this? Let me give you a similar proof.
Consider sqrt(2). Assume sqrt(2) is rational, sqrt(2) = a/b with b > 0
and gcd(a,b) = 1. 2 = a^2/b^2, so a^2 = 2b^2. By considering possible
remainders when dividing by 2, one comes to the conclusion that a is
itself divisible by 2, a = 2m. So 4m^2 = 2b^2. By similar reasoning, b
is divisible by 2. From this we conclude that one of our hypothes is in
error. Some of these are
the integers are consistent
sqrt(2) is rational
Which one do you reject?
Mike
Dr. Michael Albert
EXACTLY! That's EXACTLY the point!!!! That is EXACTLY the statement
which was to be proven!!!!!!!!!!!!!!
> > It doesn't demonstrate how to create a set of
> > unlistable reals: it doesn't give a single example of an unlistable
> > real.
A moment's reflection will probably bring one to the conclusion that the
concept of an "unlistable real" is not clear. Any particular real can be
put in the list. Indeed, one can take the real (which was constructed in
the proof) which wasn't in the original list and add it in to create a
new list. Now, however, you find the new list is still incomplete,
because you can construct another real (by the same recipe) which isn't
in the new list. Ok, add it in add get yet another new list. But now
one has yet *another* real not in the list. You never win. Indeed,
by showing that any list of the reals must be incomplete, one
shows that any list must be missing an infinity--indeed an uncountable
infinity--or reals.
> >It doesn't demonstrate how to create a set of reals whose
> > cardinality is provably greater than that of the naturals: nor does
> > it demonstrate that there is any such set. How then does it
> > demonstrate what it claims to?
If the integers are a subset of the reals, but there is no 1-1 pairing
of reals with integers, it seems reasonable to speak of the reals
as being the "larger" set.
Best wishes,
Mike
Jeremy Boden
>
>Erland Gadde wrote in message ...
>>Mark Adkins <adk...@cyberspace.org> wrote:
>
>(snip)
>
>You are very much concentrated in the decimal numbers.
>The decimal point is "mark" to devide two infinite long parts: before and
>after the decimal point.
>IFF Cantor愀 diagonal works after the decimal point resulting "new" numbers,
>it should work also with the integers (only) because of the symmetry for
>example.
>
>Can you create or produce any new integers? NO- you cannot. All the integers
>already exist though you cannot write them down - well, it dares so long. So
>Cantor does not work.
>
>
Cantors' diagonalisation works with real numbers ONLY because they are
uncountable - that's the whole point of the exercise.
If integers were also uncountable then Cantors' diagonalisation would
work with them too. As you rightly say, it doesn't work for the
integers. Therefore we may deduce that the integers are countable.
We knew this already.
--
Jeremy Boden
Dr D F Holt
jmcc...@sun1307.spd.dsccc.com (Mike McCarty) writes:
>In article <Pine.SUN.3.96.980929...@grex.cyberspace.org>,
>Mark Adkins <adk...@cyberspace.org> wrote:
>)Maybe I'm going about this the wrong way. Very well, instead of
>)asserting that Cantor's diagonal proof is flawed, let me ask anyone
>)reading this to please explain to me why the fact that there is no
>)list of all reals proves that the cardinality of the reals is greater
>)than the cardinality of the naturals.
>
>Definition: Two sets have the same cardinality iff there exists a
>bijection between them.
>
>Definition: The cardinality of a set A is greater than the cardinality
>of a set B iff there exist 1-1 mappings from B into A, but no 1-1
>mappings from B onto A.
I feel someone should point out at this stage that there is a theorem
(Schroeder-Bernstein) which says that, according to these definitions,
if there is a 1-1 map from A into B and also a one-one map from
B into A, then there is a one-one map from A onto B (a bijection).
In other words, if |A| <= |B| and |B| <= |A|, then |A| = |B|.
Without this result (which is not obvious), the whole theory of
cardinalities of sets would not be satisfactory.
Derek Holt.
Russell Easterly
Its the number n where n/(n+1)=1.
The nice thing about this definition
is that it tells you just how close to infinity some integer is.
Going from 0 to 1 takes you half way to infinity (1/2=50%).
100 gets you almost all of the way there (100/101=99%).
Russell
-2 many 2 count
Mark Adkins
It seems to me that there is a more direct way to determine the
cardinality of the reals than Cantor's diagonal argument. Actually,
I'd like to concentrate on the cardinality of the set of all reals
in the open unit interval (0,1) since that way the placement of the
decimal point and the sign of the diagonal number are the same as
those of every other real number in this interval and therefore
all such numbers are directly comparable. It will therefore be
assumed in what follows that the decimal point precedes all
numerical sequences. I'm also going to deal with binary expansions
since that simplifies the exposition.
There are two, single-digit binary numbers: 0 and 1. In general,
there are 2^n n-digit binary numbers where n is some natural number.
Any real number has an infinite number of digits. However, every
real number starts with some particular sequence of digits out to
any arbitrarily large but finite number of digits n. Then, if you
look at these finite binary sequences as the starting elements of
real numbers, it's clear that the sets of real numbers defined by
each are not disjoint, since for example a real number beginning
with 1 and another beginning with 10 might actually be the same
number. Then the sum of these finite sets over infinity (i.e.,
as n grows without bound) should be an upper bound to the number
of distinct infinite sequences of digits, i.e., should be an upper
bound to the cardinality of the set of distinct real numbers.
This sum is defined by an infinite series as follows:
2+4+8+16+32+...
Where the nth term equals 2^n for all natural numbers n from 1 to
infinity.
Since there are aleph_0 digits in every real number, there are are
aleph_0 terms in this series. Then this is a countable sum of
countable sets, and is countable, i.e., the sum of the series
is aleph_0.
I'd appreciate an email copy of any public reply.
Erland Gadde
Mark Adkins <adk...@cyberspace.org> wrote:
> There are two, single-digit binary numbers: 0 and 1. In general,
> there are 2^n n-digit binary numbers where n is some natural number.
> Any real number has an infinite number of digits. However, every
> real number starts with some particular sequence of digits out to
> any arbitrarily large but finite number of digits n. Then, if you
> look at these finite binary sequences as the starting elements of
> real numbers, it's clear that the sets of real numbers defined by
> each are not disjoint, since for example a real number beginning
> with 1 and another beginning with 10 might actually be the same
> number. Then the sum of these finite sets over infinity (i.e.,
> as n grows without bound) should be an upper bound to the number
> of distinct infinite sequences of digits, i.e., should be an upper
> bound to the cardinality of the set of distinct real numbers.
> This sum is defined by an infinite series as follows:
>
> 2+4+8+16+32+...
>
> Where the nth term equals 2^n for all natural numbers n from 1 to
> infinity.
>
> Since there are aleph_0 digits in every real number, there are are
> aleph_0 terms in this series. Then this is a countable sum of
> countable sets, and is countable, i.e., the sum of the series
> is aleph_0.
The set of binary expanded numbers beginning with a particular finite
sequence of digits, such as i.e. the set of all numbers of the form
0.11010001100xxxxxxxxx......, isn't countable, but uncountable.
In particular, the set of numbers of the form 0.xxxxxxxxxx.....
is uncountable, as is shown by Cantor's diagonal argument.
So, you have a countable union of uncountable sets, which is uncountable.
Regards,
Erland Gadde
Mark Adkins
>The argument [Cantor's Diagonal Proof] is not attempting to prove the
>existence of an unlistable real. This is fortunate, because there's no
>such thing as an unlistable real. If you have a favourite real, or for
>that matter a finite or countable collection of favourite reals, then we
>can easily arrange for the list to include them. But we can't include
>(anywhere near) _all_ reals in the list at the same time.
What I'm getting at is that, if the set of all reals is not listable,
then any list of reals divides the set of all reals into two disjoint
subsets: a listed set and an unlisted set. Now one can ask whether
one can add any element from the unlisted set to the list: the answer
is yes. Yet we know that if the set of all reals is unlistable, then
this subset of unlisted reals must at all times be unlistable. What
defines an unordered set? Its members. Then what makes this subset
unlistable, since no member is unlistable? You have unlistability
as a property of a set independent of the members which define it.
Meanwhile, consider this:
Let's say that first on some putative list of all reals is pi.
We know that the diagonal number will be different from pi in the
first digit, but we can ask whether it might be the same as pi in
all other digits. There are 9 numbers which are the same as pi
except in the first digit (if we use decimal expansions), and
there is no reason why these numbers cannot be the next nine
elements on the list. So, we know that the diagonal will have
to be different from pi in at least two digits. There are 9*9=81
numbers different from pi in both of the first two digits but
otherwise the same as pi. There is no a priori reason why we
cannot have a list with pi followed by these as the first 82
numbers on the list. Then it becomes clear that the diagonal
must be different than pi in every one of pi's infinite number
of digits, because there is no a priori reason why we cannot
begin a list with any arbitrarily large but finite series of
numbers each of which is different from pi in each of some
finite number of initial digits but which are otherwise the
same as pi.
Now, there are an infinite number of decimal expansions which
are different from pi in every digit -- 9^aleph_0 if you care to
make sense of that. However, if instead you use binary expansions,
then there is only one number which is different from pi in every
digit, that number being the inverse image of pi (i.e., where
the nth digit of pi is a 0 the nth digit of this inverse will be
a 1, and vice-versa). Now ask yourself if there is any a priori
reason why such a list could not have contained this single number,
the inverse image of pi, to begin with? If not, then the diagonal
is on the list. But the diagonal cannot be on the list. Is there
a mistake here, or have we found a paradox?
>It [Cantor's diagonal proof] shows that any countable set of reals
>does not contain all the reals. But there is a set which contains
>all the reals. Therefore this set of all the reals is not countable.
Strictly speaking, in order to be countable a set must be
well-orderable. So, one way that there could be no list of all
reals yet the set of all reals could have the cardinality of the
naturals, is for the set of *all* reals to be unable to be
well-ordered. I've gone into this in greater detail in the past
and tried to explain that some (most) reals are only distinguishable
on the basis of their full decimal or binary expansions, and that
therefore in practice they are undistinguishable; and that this
prevents well-ordering even if all one has to rely on is the
axiom of choice, because you still need to be able to say what
you're choosing and make sure that you've chosen every element
of the old set for membership in the well-ordered set.
However, I really do think that the problem with the diagonal
argument goes beyond practical considerations and involves some
sort of self-referential paradox. It's just that putting this
into non-constructivist terms is elusive. I've learned a lot
about it all in the meantime, just thinking about it and
thinking about what I've posted (including subsequent realizations
that some of my earlier statements were erroneous). For example,
the other day I realized that, given any infinite set which is
listable, the full set of diagonal numbers derivable from that set
is determined by the set of unique listings of that set, where a
unique listing can be distinguished from another like it by as small
as a single pair of list numbers switching position. Furthermore,
the infinite set of diagonal numbers generated this way will not
be present on any of those lists.
I'd appreciate receiving an email copy of any public replies.
Erland Gadde
> What I'm getting at is that, if the set of all reals is not listable,
> then any list of reals divides the set of all reals into two disjoint
> subsets: a listed set and an unlisted set. Now one can ask whether
> one can add any element from the unlisted set to the list: the answer
> is yes. Yet we know that if the set of all reals is unlistable, then
> this subset of unlisted reals must at all times be unlistable. What
> defines an unordered set? Its members. Then what makes this subset
> unlistable, since no member is unlistable? You have unlistability
> as a property of a set independent of the members which define it.
Suppose you have a set of 1000 hamburgers. You can eat any one of
these 1000 hamburgers. You might even eat many of them, maybe even 10,
if you are really hungry. But you can't eat all 1000 of them at once.
Now, what makes the whole set of hamburgers uneatable, when every one
of them is eatable?
Erland Gadde
Arthur L. Rubin
Actually, this is completely irrelevant to Cantor's Diagonal Proof, as
that is often restricted to the reals in the interval [0,1].
Robert Hill
> Robert Hill <ec...@sun.leeds.ac.uk> wrote:
>
> >The argument [Cantor's Diagonal Proof] is not attempting to prove the
> >existence of an unlistable real. This is fortunate, because there's no
> >such thing as an unlistable real. If you have a favourite real, or for
> >that matter a finite or countable collection of favourite reals, then we
> >can easily arrange for the list to include them. But we can't include
> >(anywhere near) _all_ reals in the list at the same time.
>
> then any list of reals divides the set of all reals into two disjoint
> subsets: a listed set and an unlisted set. Now one can ask whether
> one can add any element from the unlisted set to the list: the answer
> is yes. Yet we know that if the set of all reals is unlistable, then
> this subset of unlisted reals must at all times be unlistable. What
> defines an unordered set? Its members. Then what makes this subset
> unlistable, since no member is unlistable? You have unlistability
> as a property of a set independent of the members which define it.
If there are five people in a room and four chairs, then you
cannot seat all the people simultaneously, despite the fact that,
for each person you might choose among the five, there are ways of seating
that person (and three others). There is no magically unseatable person.
Similarly, what makes the reals unlistable is not that
any individual real is magically unlistable, but that there are
too many reals altogether.
We are not concerned with what the list might have contained,
but with what it does contain. Cantor says: "Give me a list of reals.
Any list. Choose it as fiendishly as you like. Ponder it as long
as you like. But eventually, when you've decided on it, show it to me.
Do not change it again. I will prove that it does not contain all the reals."
You are trying to change the list after showing it to Cantor.
> If not, then the diagonal
> is on the list. But the diagonal cannot be on the list. Is there
> a mistake here, or have we found a paradox?
There is no paradox. Your mistake is in trying to change the
list in the middle of the argument.
> >It [Cantor's diagonal proof] shows that any countable set of reals
> >does not contain all the reals. But there is a set which contains
> >all the reals. Therefore this set of all the reals is not countable.
>
> Strictly speaking, in order to be countable a set must be
> well-orderable.
Yes.
> So, one way that there could be no list of all
> reals yet the set of all reals could have the cardinality of the
> naturals, is for the set of *all* reals to be unable to be
> well-ordered.
Not true. If the reals had the cardinality of the naturals,
then there would be a bijection from the naturals to the reals;
that's the definition of cardinality. If we write r(n) for the
real number to which the natural number n is mapped by this bijection,
then r(0), r(1), r(2), ... is a list (and a well-ordering) of the reals.
> I've gone into this in greater detail in the past
> and tried to explain that some (most) reals are only distinguishable
> on the basis of their full decimal or binary expansions, and that
> therefore in practice they are undistinguishable; and that this
> prevents well-ordering even if all one has to rely on is the
> axiom of choice, because you still need to be able to say what
> you're choosing and make sure that you've chosen every element
> of the old set for membership in the well-ordered set.
There are two faults in this argument. Either alone is sufficient
to destroy it. One is stated in my previous paragraph. The other is that
"practical" indistinguishability is irrelevant. For any two distinct reals,
there is a finite n such that their decimal expansions differ in the nth place,
and this is all the distinguishability we need for this argument.
> However, I really do think that the problem with the diagonal
> argument goes beyond practical considerations and involves some
> sort of self-referential paradox. It's just that putting this
> into non-constructivist terms is elusive. I've learned a lot
> about it all in the meantime, just thinking about it and
> thinking about what I've posted (including subsequent realizations
> that some of my earlier statements were erroneous). For example,
> the other day I realized that, given any infinite set which is
> listable, the full set of diagonal numbers derivable from that set
> is determined by the set of unique listings of that set, where a
> unique listing can be distinguished from another like it by as small
> as a single pair of list numbers switching position. Furthermore,
> the infinite set of diagonal numbers generated this way will not
> be present on any of those lists.
Not sure I have time to try to understand the last few sentences.
Fortunately I don't need to do so.
> I'd appreciate receiving an email copy of any public replies.
Tapio Hurme
In any digit string having a digit in a place is well ordered - finite or
infinite - it does not matter.
1)The places - the place holders of a digit in the string- follow each
others. They are well-ordered
2) The possibilities to find a digit in a place holder is 1 to 10. There are
no other digits than 0,1,2,3,4,5,6,7,8,9. The content of a place holder
tells us the cardinality after analysing what we can find before
3) The infinity of string is not a problem - it causes only work to analyse.
Two infinite strings are well-ordered if the are different.
Therefore the numbers were developed. Do you see any other reason why we
have numbers?
Thus all the numbers are well ordered. It does not matter if the cardinality
of reals is greater than the cardinality of naturals. OK, there is no
bijection - so what?
So what??? Let it be!
Cantor´s diagonal or any cut, mixing or any other operation cannot develop
a string containing other digits than 01,2,3,4,5,6,7,8,9 in a ten-base
system. If we think about naturals it, can be possible to generate new
numbers that were not in the list of the naturalsA with the aid of any
diagonals. And you can - or at least should be able - to well- order that
list! You can always say the cardinality of the number. It does not matter
if it is real, natural or transcendental.
The point is that Cantor´s diagonal cannot create a new string that is not
in the list of all the strings, because any infinite string contains only
digits: 0,1,....9.
If the number is "finite" add after the finite point zeros to infinity. In
reals and trancendentals you have some other digits, but you can well order
the list, any list and complete list - too. The digits of the string -
themselves- tell us the cardinality of the string. This is the basic
property of the string.
If you cannot well-order strings there must be something wrong somewhere.
Gimme a (ten base system) string that does not contain those digits above.
Mark Adkins wrote in message ...
>Robert Hill <ec...@sun.leeds.ac.uk> wrote:
(snip)
>Strictly speaking, in order to be countable a set must be
>well-orderable. So, one way that there could be no list of all
>reals yet the set of all reals could have the cardinality of the
>naturals, is for the set of *all* reals to be unable to be
>well-ordered.
...
Jeremy Boden
<ma...@lily.csv.warwick.ac.uk> writes
>In article <6uqvm4$n7k$1...@relay1.dsccc.com>,
> jmcc...@sun1307.spd.dsccc.com (Mike McCarty) writes:
>>Mark Adkins <adk...@cyberspace.org> wrote:
>>)Maybe I'm going about this the wrong way. Very well, instead of
>>)asserting that Cantor's diagonal proof is flawed, let me ask anyone
>>)reading this to please explain to me why the fact that there is no
>>)list of all reals proves that the cardinality of the reals is greater
>>)than the cardinality of the naturals.
>>
>>Definition: Two sets have the same cardinality iff there exists a
>>bijection between them.
>>
>>Definition: The cardinality of a set A is greater than the cardinality
>>of a set B iff there exist 1-1 mappings from B into A, but no 1-1
>>mappings from B onto A.
>
>I feel someone should point out at this stage that there is a theorem
>(Schroeder-Bernstein) which says that, according to these definitions,
>if there is a 1-1 map from A into B and also a one-one map from
>B into A, then there is a one-one map from A onto B (a bijection).
>In other words, if |A| <= |B| and |B| <= |A|, then |A| = |B|.
>Without this result (which is not obvious), the whole theory of
>cardinalities of sets would not be satisfactory.
>
>Derek Holt.
The Schroeder-Bernstein theorem may not be obvious but it's really
rather intuitively reasonable. Any other result would be surprising,
especially since it's also trivially true for finite sets.
--
Jeremy Boden
Jeremy Boden
<logi...@wolfenet.com> writes
n/(n+1) = 1 => n = n + 1 => 0 = 1 (valid for all finite n)
--
Jeremy Boden
Mark Adkins
>Mark Adkins wrote:
>
>[snip]
>
>[Considering binary expansions of real numbers in (0,1):]
>
>>There are two, single-digit binary numbers: 0 and 1. In general,
>>there are 2^n n-digit binary numbers where n is some natural number.
>>Any real number has an infinite number of digits. However, every
>>real number starts with some particular sequence of digits out to
>>any arbitrarily large but finite number of digits n. Then, if you
>>look at these finite binary sequences as the starting elements of
>>real numbers, it's clear that the sets of real numbers defined by
>>each are not disjoint, since for example a real number beginning
>>with 1 and another beginning with 10 might actually be the same
>>number. Then the sum of these finite sets over infinity (i.e.,
>>as n grows without bound) should be an upper bound to the number
>>of distinct infinite sequences of digits...[this being represented
>>by the infinite series: 2 + 4 + 8 + 16 + 32 + ..., where each
>>term in the series represents 2^n finite binary sequences for all
>>natural numbers n from 1 to infinity].
>
>[snip]
>
>It isn't, and if you think about it, you should realize that it
>shouldn't be. For each n let S(n) be the number of binary sequences
>of length n. Then |S(n)| = 2^n. If S is the union of all of the
>S(n), it is indeed true that |S| = w, but S contains only the *finite*
>sequences. It's missing even so simple a sequence as <0, 1, 0, 1, 0,
>1,...>.
True, this number is not represented at any finite term in the
series, but then the series doesn't end at any nth term, just as
a non-terminating real doesn't end at any nth term. However, that
number, and all other non-terminating reals, are represented by the
series as a whole. There is no non-terminating real, including
this one, which is not represented as the limit of some infinite
sequence of ever closer finite approximations: in the completed
infinity of the series, the completed infinity of this
non-terminating real is represented exactly.
It's (sort of) analogous to the series 1/2+1/4+1/8+... which has 1
as its sum. None of the finite terms is equal to 1, yet the series
as a whole is. The series above is really quite a different sort of
beast, however, because each term represents (the cardinality of)
a set of finite binary sequences rather than any single number.
Because of this, the series as a whole can represent all binary
sequences rather than having a single sequence as the limit.
Jeremy Boden
100...@grex.cyberspace.org>, Mark Adkins <adk...@cyberspace.org> writes
[cut...]
Lengthy intro about restriction to [0,1]...
>There are two, single-digit binary numbers: 0 and 1. In general,
>there are 2^n n-digit binary numbers where n is some natural number.
>Any real number has an infinite number of digits. However, every
>real number starts with some particular sequence of digits out to
>any arbitrarily large but finite number of digits n. Then, if you
>look at these finite binary sequences as the starting elements of
>real numbers, it's clear that the sets of real numbers defined by
>each are not disjoint, since for example a real number beginning
>with 1 and another beginning with 10 might actually be the same
>number. Then the sum of these finite sets over infinity (i.e.,
>as n grows without bound) should be an upper bound to the number
>of distinct infinite sequences of digits, i.e., should be an upper
>bound to the cardinality of the set of distinct real numbers.
>This sum is defined by an infinite series as follows:
>
>2+4+8+16+32+...
>
>Where the nth term equals 2^n for all natural numbers n from 1 to
>infinity.
However, this is not the same as the number of real numbers.
[Just suppose you had used based 10; your partial sums will be:
9, 99, 999, 9999
Wow! You would be able to count things with numbers - but so what?]
>
>Since there are aleph_0 digits in every real number, there are are
>aleph_0 terms in this series. Then this is a countable sum of
>countable sets, and is countable, i.e., the sum of the series
>is aleph_0.
>
How many real numbers did you say you had got?
It's true that you need aleph_0 digits to be able to express a real
number. Unfortunately (for you) you were not able to show that there
were only aleph_0 distinct real numbers. In fact there are aleph_1.
So you have an *uncountable* sum of countable sets, which is of course
uncountable.
>
>I'd appreciate an email copy of any public reply.
>You aren't getting one.
--
Jeremy Boden
Russell Easterly
Tapio Hurme wrote in message <6utvch$1r3$1...@tron.sci.fi>...
>What is the problem?
>
>In any digit string having a digit in a place is well ordered - finite or
>infinite - it does not matter.
>
snip
>Thus all the numbers are well ordered. It does not matter if the
cardinality
>of reals is greater than the cardinality of naturals. OK, there is no
>bijection - so what?
>
snip
>If you cannot well-order strings there must be something wrong somewhere.
>Gimme a (ten base system) string that does not contain those digits above.
>
>Mark Adkins wrote in message ...
>
You are assuming that all numbers can be represented in base 10.
This is not true of all rational numbers even with infinite strings.
The rational number 1/3 can not be represented exactly in base 10.
...000.333... (base 10) is an irrational number.
It can be made to be as close to the rational number 1/3
as you want it to be, but it is not equal to 1/3.
(Actually, it is equal to 1/3 if you use Cauchy sequences to define reals.)
There are always other irrational numbers (not representable in base 10)
that will always be closer to 1/3 than ...000.333... (base 10).
Iain Davidson
>You are assuming that all numbers can be represented in base 10.
>This is not true of all rational numbers even with infinite strings.
>The rational number 1/3 can not be represented exactly in base 10.
>...000.333... (base 10) is an irrational number.
What does the preceding ... mean ?
>It can be made to be as close to the rational number 1/3
>as you want it to be, but it is not equal to 1/3.
If it is not equal to 1/3 then there must be a difference d.
But you have already said that it can be made as close as you
please.
Therefore, it can be made closer than d.
This is a contradiction.
It can be made as close as you please, so the stated inequality must
be false.
Iain Davidson Tel : +44 1228 49944
4 Carliol Close Fax : +44 1228 810183
Carlisle Email : ia...@stt.win-uk.net
England
CA1 2QP