(Not quite) Cantor's diagonal proof
Norman Megill
my Metamath site; see
http://us.metamath.org/mpegif/mmcomplex.html#uncountable . As far as I
can tell, this appears to be the first complete formalization of this
fact available on the web, although if someone can point me to another
one I will be happy to correct this statement.
The proof is not Cantor's original diagonal proof using decimal
expansions. Instead I used a variation that was easier to formalize.
However, I believe it is in the same spirit as Cantor's diagonal proof,
in the sense that it constructs a real number different from all the
numbers in a purported list of all real numbers.
I have seen discussions on sci.math and sci.logic from time to time in
which doubts have been expressed that the real numbers are uncountable.
If nothing else my proof may provide such discussions with something
concrete to point to, in the form of an absolutely rigorous and
irrefutable proof, in which every miniscule detail is exposed for
inspection and can (in principle) be followed by anyone with sufficient
patience, mathematician or not. Whether or not the proof will have any
effect on disbelievers is uncertain. But in any case it was an
interesting project and no one can say I didn't try:)
-- Norm Megill nm at alum dot mit dot edu
Norman Megill
> I have placed a complete formal proof that the reals are uncountable on
> my Metamath site; see
> http://us.metamath.org/mpegif/mmcomplex.html#uncountable .
It looks like the 'us' server is down. The proof is also available here:
http://us2.metamath.org:8888/mpegif/mmcomplex#uncountable
Jon Haugsand
> Norman Megill wrote:
>
> > I have placed a complete formal proof that the reals are uncountable on
> > my Metamath site; see
> > http://us.metamath.org/mpegif/mmcomplex.html#uncountable .
>
> It looks like the 'us' server is down. The proof is also available here:
> http://us2.metamath.org:8888/mpegif/mmcomplex#uncountable
Nice one. One point: you claim:
"It is a set of real numbers that do not match any f(i) on the
original list! It it tempting to think that the interval shrinks
down to exactly nothing, but in fact it will not be empty, and
the formal proof shows this. In particular, it will contain at
least one real number, which is the supremum (meaning "least
upper bound") of all values g(i)."
Actually, if this interval, call it [g_sup,h_inf] is greater than a
single point, then you will also have rationals in your interval,
effectively proving that the rationals are uncountable.
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92
Norman Megill
> Nice one. One point: you claim:
>
> "It is a set of real numbers that do not match any f(i) on the
> original list! It it tempting to think that the interval shrinks
> down to exactly nothing, but in fact it will not be empty, and
> the formal proof shows this. In particular, it will contain at
> least one real number, which is the supremum (meaning "least
> upper bound") of all values g(i)."
>
> Actually, if this interval, call it [g_sup,h_inf] is greater than a
> single point, then you will also have rationals in your interval,
> effectively proving that the rationals are uncountable.
Thank you for pointing this out. You are, of course, correct, and I
have corrected the web page.
|-|erc
a formal proof but with errors then?
Herc
Norman Megill
LOL! However, the mistake was carelessness in my informal description
on the web page. The formal proof was not touched; it was and is
correct, and was verified by a computer program. My informal
description was not verified by a computer program.
Virgil
Norman Megill <n...@nospam.see.signature.domain.invalid> wrote:
> I have placed a complete formal proof that the reals are uncountable on
> my Metamath site; see
> http://us.metamath.org/mpegif/mmcomplex.html#uncountable . As far as I
> can tell, this appears to be the first complete formalization of this
> fact available on the web, although if someone can point me to another
> one I will be happy to correct this statement.
Have a look at Cantor's first proof of the uncountability of the reals,
which also mkes direct use of the LUB, GLB properties of the reals. The
"diagona;l" proof was Cantor's second proof.
Norman Megill
Yes, I was considering formalizing Cantor's first proof:
http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof
before I came across the one in Truss.
The one I used is Theorem 5.18 of Truss, _Foundations of Mathematical
Analysis_ (1997) p. 114. He doesn't say where it came from, but it is a
very straightforward, easy to understand proof. My only change was to
compute explicit values for the auxiliary functions, whereas he lets
them have any values meeting the necessary conditions. I couldn't
figure out how to formalize the word "any" inside of a recursive
construction (and certainly I don't want to invoke the Axiom of Choice),
but perhaps he had in mind a simpler proof with no arithmetic at all
that I am not seeing.
Saint Cad
"Norman Megill" <n...@nospam.see.signature.domain.invalid> wrote in message
news:kOCdnS7PSPz...@rcn.net...
<snip>
> I have seen discussions on sci.math and sci.logic from time to time in
> which doubts have been expressed that the real numbers are uncountable.
I don't think any serious mathematician doubts that the reals are
uncountable, but can raise questions as to the validity of Cantor's Diagonal
Proof. For example, we construct a real number not on the list. OK, simply
add it to the bottom of the list. The list should still be of countable
cardnality. You retort that you can now construct another real not in the
list. Add that to the bottom. We continue back and forth, so at which
point does the list become uncountable? I'm sure that someone can come up
with a valid reason why this approach does not invalidate the Diagonal
Proof, but I think it does demonstrate that Cantor's proof by itself does
leave a bit to be desired.
Here's another question. Suppose I list all of the repeating and
terminating decimals (i.e. rationals). What in Cantor's proof prevents me
from finding some sort of order for them so that I can use the diagonal
method to create a repeating decimal not in the list, thereby "proving" that
the rationals are uncountable? I know that I can't actually do this (the
rationals are countable), but it would take someone else to explain why in
order to dismiss this "counter" to his method. Again, Cantor's method may
be shown to not be invalid, but it take more than just his method by itself.
Virgil
"Saint Cad" <sain...@emailblackhole.com> wrote:
> "Norman Megill" <n...@nospam.see.signature.domain.invalid> wrote in message
> news:kOCdnS7PSPz...@rcn.net...
>
> <snip>
>
> > I have seen discussions on sci.math and sci.logic from time to time in
> > which doubts have been expressed that the real numbers are uncountable.
>
> I don't think any serious mathematician doubts that the reals are
> uncountable, but can raise questions as to the validity of Cantor's Diagonal
> Proof. For example, we construct a real number not on the list. OK, simply
> add it to the bottom of the list. The list should still be of countable
> cardnality. You retort that you can now construct another real not in the
> list. Add that to the bottom. We continue back and forth, so at which
> point does the list become uncountable? I'm sure that someone can come up
> with a valid reason why this approach does not invalidate the Diagonal
> Proof, but I think it does demonstrate that Cantor's proof by itself does
> leave a bit to be desired.
The point of Cantor's diagonal construction is not that it applies to
one list, but that it applies simultaeously to all lists. Thus the
creation of a list creates the non-member along with it.
Also, with slight modifications, it can be shown to create "as many"
non-members as members for every list.
>
> Here's another question. Suppose I list all of the repeating and
> terminating decimals (i.e. rationals). What in Cantor's proof prevents me
> from finding some sort of order for them so that I can use the diagonal
> method to create a repeating decimal not in the list, thereby "proving" that
> the rationals are uncountable? I know that I can't actually do this (the
> rationals are countable), but it would take someone else to explain why in
> order to dismiss this "counter" to his method. Again, Cantor's method may
> be shown to not be invalid, but it take more than just his method by itself.
Since that are several well published surjective functions from the
naturals to the rationals, a proof that the rationals are uncountable
would, one hopes, be impossible, and would devastate mathematics if one
were ever found.
Saint Cad
"Virgil" <ITSnetNOTcom#vir...@COMCAST.com> wrote in message
news:ITSnetNOTcom%23virgil-3E1A92...@comcast.dca.giganews.com...
> In article <sR0dd.2643$EP4.1417@trnddc06>,
> "Saint Cad" <sain...@emailblackhole.com> wrote:
>
>> "Norman Megill" <n...@nospam.see.signature.domain.invalid> wrote in message
>> news:kOCdnS7PSPz...@rcn.net...
>>
>> <snip>
>>
>>
>> Here's another question. Suppose I list all of the repeating and
>> terminating decimals (i.e. rationals). What in Cantor's proof prevents
>> me
>> from finding some sort of order for them so that I can use the diagonal
>> method to create a repeating decimal not in the list, thereby "proving"
>> that
>> the rationals are uncountable? I know that I can't actually do this (the
>> rationals are countable), but it would take someone else to explain why
>> in
>> order to dismiss this "counter" to his method. Again, Cantor's method
>> may
>> be shown to not be invalid, but it take more than just his method by
>> itself.
>
> Since that are several well published surjective functions from the
> naturals to the rationals, a proof that the rationals are uncountable
> would, one hopes, be impossible, and would devastate mathematics if one
> were ever found.
Exactly! But my question is can Cantor's proof by itself be shown to not
suffer this flaw?
|-|erc
>
> >>
> >> Here's another question. Suppose I list all of the repeating and
> >> terminating decimals (i.e. rationals). What in Cantor's proof prevents
> >> me
> >> from finding some sort of order for them so that I can use the diagonal
> >> method to create a repeating decimal not in the list, thereby "proving"
> >> that
> >> the rationals are uncountable? I know that I can't actually do this (the
> >> rationals are countable), but it would take someone else to explain why
> >> in
> >> order to dismiss this "counter" to his method. Again, Cantor's method
> >> may
> >> be shown to not be invalid, but it take more than just his method by
> >> itself.
> >
> > Since that are several well published surjective functions from the
> > naturals to the rationals, a proof that the rationals are uncountable
> > would, one hopes, be impossible, and would devastate mathematics if one
> > were ever found.
>
> Exactly! But my question is can Cantor's proof by itself be shown to not
> suffer this flaw?
>
The diagonal would have to repeat.
0.1.....
0.x2....
0.xx3...
0.xxx4...
0.xxxx1...
0.xxxxx2..
0.xxxxxx3...
0.xxxxxxx4...
0.xxxxxxxx1...
All you have to do is find the numerator and denominator for an anti-diag number.
it has the same number of repeating digits as the diag but every digit is offset.
Hence that countable construction actually missed some numbers, since you have
a given finite index for a counter example.
So its not a counter-argument to using diag proof.
Herc
|-|erc
Corollary : Every complete list of rationals has an irrational diagonal.
Herc
Tim Peters
> I don't think any serious mathematician doubts that the reals are
> uncountable, but can raise questions as to the validity of Cantor's
> Diagonal Proof.
Na, serious mathematicians don't question it. Serious philosophers, on the
other hand, don't have sanity as part of their job requirement <wink>.
> For example, we construct a real number not on the list.
You're done. Stop! The proof ends there. There's nothing more to do. At
this point, you get it or you don't. Thinking about taking another step
shows that you don't yet understand the proof, or, perhaps, don't understand
what it is that's *been* proved.
At the start, you were allowed to present any list whatsoever. If the reals
are in fact countable, then there is a such a list containing all the reals.
But the proof shows that it doesn't matter which list you start with: it
shows that *any* list doesn't contain all the reals. To accomplish that, it
only needs to demonstrate that a single real is missing from the list. And
that it did. There's nothing more to do.
> OK, simply add it to the bottom of the list.
The proof already ended. You're just pissing in the wind now <wink>. BTW,
if you *have* to confuse yourself with this line of argument, put it at the
top of the list instead. Since any *interesting* list here is unbounded,
there is no "bottom" to the list.
> The list should still be of countable cardnality.
Yes. This new list is irrelevant, but you could indeed add new reals to it,
for eternity if you want to remain confused that long.
> You retort that you can now construct another real not in the list. Add
> that to the bottom. We continue back and forth, so at which point does
> the list become uncountable?
It never becomes uncountable. If it did, the natural numbers would be
uncountable too. But there is a list containing all the natural numbers --
the point of the proof is precisely that there is no way to pair the
naturals with the reals. It's not trying to prove that there are "lots and
lots and lots" more reals than naturals, it's just trying to prove that
there's no pairing. It succeeded at that the first time.
> I'm sure that someone can come up with a valid reason why this approach
> does not invalidate the Diagonal Proof,
In what conceivable sense could this invalidate it? The rules of the game
at the start were that you got *one chance* to give a list with all the
reals. The proof shows that you're doomed to fail: the list you claimed to
be a pairing is proven not to be a pairing. Game over.
Now a sore loser might insist on playing again, but nothing can change that
they *already lost*. The game ended when the proof produced a real not on
the list. If you go on anyway, you could continue to play it over again,
and do so an unbounded number of times, and continue to lose every time.
> but I think it does demonstrate that Cantor's proof by itself does leave a
> bit to be desired.
Not in the sense of proving what it intended to prove. To the contrary,
it's an elegant and simple proof. You may be getting off track in imagining
it's more complicated than it really is.
> Here's another question. Suppose I list all of the repeating and
> terminating decimals (i.e. rationals). What in Cantor's proof prevents
> me from finding some sort of order for them so that I can use the
> diagonal method to create a repeating decimal not in the list, thereby
> "proving" that the rationals are uncountable? I know that I can't
> actually do this (the rationals are countable), but it would take
> someone else to explain why in order to dismiss this "counter" to his
> method. Again, Cantor's method may be shown to not be invalid, but it
> take more than just his method by itself.
Cantor's proof applies to a purported list of all reals. It succeeds at
what it intended to prove. It's not required to prove anything other than
that, and insisting that it's a flaw if it doesn't prove anything other than
that would be silly.
So this isn't a start at a "counter" until you describe a method for
creating a repeating decimal not on a list of rationals. Try to! It will
be instructive <wink>. It's not Cantor's proof of the uncountability of the
reals that will stop you, it's ultimately Cantor's distinct proof of the
countability of the rationals that will account for the failures. It's
possible that you'll really have to try (and fail) some number of times
before this will sink in.
Dave Seaman
> "Norman Megill" <n...@nospam.see.signature.domain.invalid> wrote in message
> news:kOCdnS7PSPz...@rcn.net...
><snip>
>> I have seen discussions on sci.math and sci.logic from time to time in
>> which doubts have been expressed that the real numbers are uncountable.
> I don't think any serious mathematician doubts that the reals are
> uncountable, but can raise questions as to the validity of Cantor's Diagonal
> Proof. For example, we construct a real number not on the list. OK, simply
> add it to the bottom of the list. The list should still be of countable
> cardnality. You retort that you can now construct another real not in the
> list. Add that to the bottom. We continue back and forth, so at which
> point does the list become uncountable? I'm sure that someone can come up
> with a valid reason why this approach does not invalidate the Diagonal
> Proof, but I think it does demonstrate that Cantor's proof by itself does
> leave a bit to be desired.
No, it doesn't demonstrate that. The form of Cantor's proof is to show
that for every mapping f: N -> R there is a real number x (depending on
f) such that x is not in the range of f. Notice that this statement is
precisely the logical negation of the statement "there is a surjection
from N onto R".
Perhaps you are familiar with epsilon-delta proofs in analysis. The
proof that a real function f is continuous at a point in its domain takes
the form "for every epsilon > 0 there exists delta > 0 (depending on
epsilon) such that blah blah blah". Why is it that no one ever attempts
to demonstrate a flaw in such proofs by picking a different epsilon after
the proof is done? It's exactly the same idea as picking a different f
after the proof in the previous paragraph is done.
In the former case we say "Let f: N->R be given. Let x = _________.
Then x is not in the range of f because ____________, Q.E.D."
In the latter case we say "Let epsilon > 0 be given. Let delta =
________. Then blah blah blah holds because ____________, Q.E.D."
The structure of the two proofs is exactly the same. There is no point
in trying to introduce a different f (or a different epsilon) because
every possible f (or epsilon) was already considered in the proof, and
none is left over.
> Here's another question. Suppose I list all of the repeating and
> terminating decimals (i.e. rationals). What in Cantor's proof prevents me
> from finding some sort of order for them so that I can use the diagonal
> method to create a repeating decimal not in the list, thereby "proving" that
> the rationals are uncountable?
First of all, the problem is with rationals that have dual
representations, such as 0.999... = 1.000.... Not every repeating
decimal has a dual representation. In fact, the only numbers that have
dual representations are those that end in all 9's or all 0's. The
diagonal construction can be arranged so that all the digits generated on
the diagonal are 1's and 2's (say), thus avoiding any possibility that
the new digit string will be an alternate representation of something
already on the list.
>I know that I can't actually do this (the
> rationals are countable), but it would take someone else to explain why in
> order to dismiss this "counter" to his method. Again, Cantor's method may
> be shown to not be invalid, but it take more than just his method by itself.
The number produced by the diagonal argument (correctly constructed)
necessarily differs from each number in the original list. It follows
that if the original list contains all the rationals (which is possible)
then the generated number must be irrational.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
David Bernier
The only reason for introducing the "anti-diag" is in order
to prove that the reals are uncountable.
In computer science, there is the notion of
local/global variables.
Similarly, in mathematics some definitions are (implicitly)
limited to one proof or one area of mathematics.
Other definitions are "global", for example the definition
of a group.
In the (attempts) to formalize mathematics, the
ZFC formal set theory is notable. In
ZFC set theory, integers, functions, groups,...
are are all sets; yet, the word "set" is
never defined.
To ZFC skeptics, one possible reassurance is
"so far, so good". In other words, as a formal theory,
ZFC has been extensively studied and undergone a lot
of scrutiny. In the past several decades, no
contradiction has been found in the formal
theory ZFC (but perhaps NSA has found a
contradiction?? ...)
David Bernier
Daniel W. Johnson
> Here's another question. Suppose I list all of the repeating and
> terminating decimals (i.e. rationals). What in Cantor's proof prevents me
> from finding some sort of order for them so that I can use the diagonal
> method to create a repeating decimal not in the list, thereby "proving" that
> the rationals are uncountable? I know that I can't actually do this (the
> rationals are countable), but it would take someone else to explain why in
> order to dismiss this "counter" to his method. Again, Cantor's method may
> be shown to not be invalid, but it take more than just his method by itself.
Nothing in Cantor's proof *allows* you to coerce the resulting diagonal
number to be rational.
If you apply the diagonal method to a (not necessarily complete) list of
rationals, this will generate a number not on the list. This new number
will either be a rational not on the list or an irrational not on the
list. You'd have to rule out the possibility of it being irrational
before you can work with "rational not on the list" as a conclusion.
If you apply the diagonal method to a (not necessarily complete) list of
reals, this will generate a number not on the list. This new number
will either be a real not on the list or .... There is no other
possibility, so we are done.
Speculating about finding a complete rational list with a rational
diagonal is as pointless as speculating about finding two even numbers
whose sum is odd.
--
Daniel W. Johnson
pano...@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W
Robin Chapman
<snip>
Surely a more important result than the uncountability of R
is that R has cardinality 2^aleph_0. Do you intend formalizing
this in metamath sometime?
--
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"Lacan, Jacques, 79, 91-92; mistakes his penis for a square root, 88-9"
Francis Wheen, _How Mumbo-Jumbo Conquered the World_
|-|erc
Well no, diagonalisation is a generic proof technique, unless you literally mean introduce here.
The question was can the technique prove a bogus result? Can you use anti-diag
on the countable set of rationals and find another rational?
Say you start with a conventional countable list of rationals. Then you reorder them so that
each diag digit falls on the repeating diag sequence. This seems possible if the repeating
diag sequence contains all 10 digits.
Original rationals list
1 0.1
2 0.2222222222222222
3 0.343434343434343434
4 0.50000000000000000
5 0.750000000000000000000
6 0.6666666666666666666
7 0.444444444444444444
We need to rearrange this to form a repeating diagonal, then we can find a 'new' rational.
0.1..
0.x2..
0.xx3..
0.xxx4..
0.xxxx5
0.xxxxx6
0.xxxxxx7
0.xxxxxxx8
0.xxxxxxxx9
0.xxxxxxxxx0
0.xxxxxxxxxx1
0.xxxxxxxxxxx2
0.12345678901234567890...
this is the simplest diagonal you could find, because such a diagonal must match
0.111111
0.2222222
0.3333333
so it must have every digit somewhere.
it could repeat after 1000 digit long sequence but it must have some finite repeating sequence.
Can we just reorder any list of rationals to match the repeating diagonal?
1 0.1
2 0.2222222222222222
3 0.343434343434343434
4 0.50000000000000000
5 0.750000000000000000000
6 0.6666666666666666666
7 0.444444444444444444
New list
0.1 so far so good
0.22222222 yep
0.343434 yep
0.5000000000 doesn't fit!
That would make 0.1230 on the diagonal, we need it be 0.1234567890
So we put numbers 4, 5, 6 into a queue.
0.1
0.22222
0.343434
0.4444444 now we have reordered the rationals into having the diagonal that we want!
The question is, will there be numbers left over in the queue? is this the same list of numbers we started with?
No its not, because given any repeating diagonal
0.1234567890
we can find a repeating anti diagonal
0.2111111111211111111121111111..
This number is just .... well you're good at working out factors..
but it has a numerator and denominator that are fairly small so it should appear early in the original list of countables
(depending on the counting technique).
So the reordering operation is not possible, hence a repeating diagonal is not possible on a list of rationals,
hence diag technique does NOT make a new rational from the list of rationals, as it should.
Herc
Robert Low
Saint Cad <sain...@emailblackhole.com> wrote:
>I don't think any serious mathematician doubts that the reals are
>uncountable, but can raise questions as to the validity of Cantor's Diagonal
>Proof. For example, we construct a real number not on the list. OK, simply
No, this is not an argument against the validity of the proof
It's a straight proof by contradiction. Assume that the reals
are countable: if they are, then there's a bijection between
them and the integers. But then you can construct a real that is not
associated with any integer. This is a contradiction, therefore
the reals are not countable. It isn't just showing that something
was missed of the list, since the assumption was that the
list was complete.
This 'counter-argument' is really just a proof that the person
making it doesn't understand the structure of the proof.
bri...@encompasserve.org
>
> Saint Cad <sain...@emailblackhole.com> wrote:
>>I don't think any serious mathematician doubts that the reals are
>>uncountable, but can raise questions as to the validity of Cantor's Diagonal
>>Proof. For example, we construct a real number not on the list. OK, simply
>
> No, this is not an argument against the validity of the proof
> It's a straight proof by contradiction. Assume that the reals
> are countable: if they are, then there's a bijection between
> them and the integers.
As it is usually cast in this group, Cantor's Diagonal proof is
not a proof by contradiction that "no complete [countable] list of reals
exists". It is a direct proof that "all [countable] lists of reals
are incomplete".
Direct:
Let L be an arbitrary list. Show that L must be incomplete.
Since L was arbitrary, all lists are incomplete.
Contradiction:
Let L be a complete list. Show that L must be incomplete.
Contradiction. So there exists no complete list.
> This 'counter-argument' is really just a proof that the person
> making it doesn't understand the structure of the proof.
Agreed. Either form of the proof proceeds by exhibiting a number not
on a particular list. Finding a different list that contains that
number misses the point.
John Briggs
Robert Low
<bri...@encompasserve.org> wrote:
>mtx...@linux.services.coventry.ac.uk (Robert Low) writes:
>>>uncountable, but can raise questions as to the validity of Cantor's Diagonal
>>>Proof. For example, we construct a real number not on the list. OK, simply
>> No, this is not an argument against the validity of the proof
>> It's a straight proof by contradiction. Assume that the reals
>not a proof by contradiction that "no complete [countable] list of reals
>exists". It is a direct proof that "all [countable] lists of reals
>are incomplete".
Oh. I admit, I haven't bothered polling past articles to see
how it's presented in either of the groups you might mean by
"here": I've always used the proof by contradiction
version, and assumed that most other people did too. Live and
learn.
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
David Bernier
Let's say we look at some list of all the positive integers, for example
1, 2, 3, 4, 5, ....
Next, we reorder the numbers on the list (I would think of a deck
of cards numbered 1, 2, 3, ... placed on a table of
infinite length and we shuffle the deck and
replace the shuffled deck back on the table
in an orderly way as before.)
Could there be some positive integer that disappeared from
the deck after the shuffle? No.
Could a card with -5 have made its way into the
deck? No.
Just as one can think of a deck of cards with exactly one card having
a given number, such as 24, and every positive integer being on
some card, one could think of a deck of cards bearing the rational
numbers.
David Bernier
Dave Seaman
It's not that there is anything wrong with indirect proofs. It's just
that the Cantor-deniers are often those who don't understand indirect
proofs in general, and the indirect form of the diagonal argument
provides yet another target for their attacks.
Charlie-Boo
> |-|erc wrote:
> >>Jon Haugsand wrote:
> >> > Actually, if this interval, call it [g_sup,h_inf] is greater than a
> >> > single point, then you will also have rationals in your interval,
> >> > effectively proving that the rationals are uncountable.
> >>
> >>Thank you for pointing this out. You are, of course, correct, and I
> >>have corrected the web page.
> >
> > a formal proof but with errors then?
>
> LOL! However, the mistake was carelessness in my informal description
> on the web page. The formal proof was not touched; it was and is
> correct, and was verified by a computer program.
Then something must be wrong with your computer or program.
You are taking a series of intervals [g(i),h(i)] that (1) contains no
f(i) = the list, (2) keeps shrinking with a size approaching zero, and
(3) always contains a real number. So you claim that it approaches a
single number that is a real number that is not any f(i). Jon
Haugsand pointed out that this argument applies to rational numbers,
and your web site responds that the limit of rational numbers is not
always a rational number (e.g. the partial expansions of the digits of
pi) and it is the limit that is the counterexample to the purported
enumeration.
However, Cantor constructed a series of numbers that converges (who
would like to supply a proof of convergence?) You are constructing a
series of intervals, which does not define a single number. For,
suppose that there were a number L that this series of intervals
contains as a limit. But when f(j) is a number between L and the
upper bound of the interval, you reset the lower bound to a number >
f(j) and thus > L, so L is not in the new interval and is not a
"limit" after all.
Your argument applies to any set of real numbers that intersects every
nonempty interval of real numbers, e.g. the rational numbers (Jon
Haugsand's example.) (What other sets of real numbers meet this
condition? How about changing "real" to "rational" or
"transcendental" etc.?)
C-B
PS I address the question of formalizing Cantor's proof in a recent
thread, "Question on the Equivalence of Cantor & Turing". My premises
were that (1) It is easy to formalize self referential results such as
those of Godel and (especially) Turing. (2) Cantor's proof is very
similar to these results. I really do think that you should
contribute to that effort and that a system that represented both self
reference and the power set would be powerful indeed.
I am glad that your "mechanical proof" isn't completely phony - in
contrast to such frauds as Boyer & Moore's _A Mechanical Proof Of The
Unsolvability Of The Halting Problem_ (1982)
http://citeseer.ist.psu.edu/boyer82mechanical.html
You are addressing # 1 in my list that Boyer & Moore do not:
"What do we need to show to demonstrate a mechanical means of creating
and proving a mathematical theorem? How about:
1. A convincing self-contained logical argument that the theorem is
true.
2. A formal representation of that logical argument.
3. An explanation of how the formalism (a) represents arguments in
general, and (b) represents the given argument.
4. A method by which the formal representation was mechanically
generated, including,
5. A transcript of the interaction with the mechanical system during
which the formal representation was generated."
Norman Megill
> Then something must be wrong with your computer or program.
<snip>
My feeling is that we may not get very far discussing the informal
proof, whose purpose is only to give you a rough guideline. It will be
far better to to critique the formal proof, whose conclusion I gather
you do not agree with. That is the reason I posted a link to it.
For example: pick the very last step of the very last piece of the
formal proof at http://us.metamath.org/mpegif/ruc.html . It claims that
step 14 can be inferred from steps 12 and 13. Do you agree with this
claim? If so, then you must disagree with either step 12 or 13. From
your comments I would guess step 12 is the one that might trouble you.
So look at what step 12 is inferred from. And so on, until you arrive
at a point that you have a question about, which I can try to help
explain to you.
Robert Low
Dave Seaman <dse...@no.such.host> wrote:
>It's not that there is anything wrong with indirect proofs. It's just
>that the Cantor-deniers are often those who don't understand indirect
>proofs in general, and the indirect form of the diagonal argument
>provides yet another target for their attacks.
Does using a direct proof actually work any better? (At
convincing the deniers, that is: I find the proof by
contradiction more satisfying, but that's just a matter
of taste.)
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
Dave Seaman
A surprising number of people attempt to attack the indirect proof at the
very first step by claiming (from finite considerations) that no complete
list can exist, and therefore the diagonal argument can't even be
applied. People who use that argument tend to be impervious to logic.
Robert Low
Dave Seaman <dse...@no.such.host> wrote:
>A surprising number of people attempt to attack the indirect proof at the
>very first step by claiming (from finite considerations) that no complete
>list can exist, and therefore the diagonal argument can't even be
>applied. People who use that argument tend to be impervious to logic.
So, since a complete list can't exist, the proof that no
complete list can exist is flawed, and therefore we can
reject the conclusion that no complete list can exist.
It has a certain elegance, I have to admit.
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
Leonard Blackburn
Please read the replies to you made by Tim Peters, Dave Seaman, Daniel
W. Johnson, and Robert Low (all of which were made after you wrote
this).
Especially Tim Peters has pointed out your flaws in not understanding
Cantor's Diagonal Argument with the clarity of a thousand suns.
-Leonard Blackburn
|-|erc
But its an infinite deck you have to be sure. There is a *constraint* on the shuffle.
Each card must end with a 5.
Start with 1,2,3,4,5,6,7,8...
Becomes 5,15,55,25,35,...
We just repeatedly pushed some cards towards the end and moved some cards forward.
This is the format the 'shuffle' must result in. Is it the same list? No. Infinite lists are not
necessarily well behaved when shuffled.
Everyone here is assuming-a-complete-rationals-list-has-an-irrational-diagonal, by
working backwards from "rationals are countable". We can prove it.
Numerator
1 2 3 4 5 6
1 1 2 4 7
2 3 5 8
3 6 9
4 10
Denominator
We start counting the rationals in a way that covers all numerator/denominator pairs.
I n/d
1 1/1
2 2/1
3 1/2
4 3/1
5 2/2
6 1/3
Say n = 3, d = 2
I = (n + d)^2 / 2 +d (fudged algorithm)
I = 8
so 3/2 is the 8th rational.
1 1.0
2 2.0
3 0.5
4 3.0
5 1.0
6 0.33333333
CAN THIS LIST (rearranged) CONTAIN A REPEATING DIAGONAL?
If it can, then diagonalisation is proven to be a flawed technique.
Assume it does contain a repeating diagonal.
By definition, the repeating diagonal has some fixed number of repeating digits.
0.123451234512345
Given any diagonal, we can form an anti-diagonal
0.211112111121111
21111/100000
But that's just numerator 21111 and denominator 100000
Given any numerator and denominator value, we can calculate its
position in the list.
numerator 21111
--------------------------->
| / / / / /
| / / / /
| / / /
| / /
| /
|
| 10,000 *
v
denominator
I = (n + d) ^2 / 2 + d
I = 100,332,345
So given the diagonal is 0.1234512345...
the 100,332345th rational will not fit into this list. It could be ANY repeating diagonal,
we can always calculate the Ith rational that won't fit.
Therefore the assumption that the diagonal repeats is contradicted.
-----------------------------------------------------------------
Therefore, a full set of rationals cannot contain a repeating diagonal, as we can count to any anti-diag.
Herc
|-|erc
"|-|erc" <sp...@fodder.abc> wrote in
>
>
> 0.211112111121111
>
> 21111/100000
>
> But that's just numerator 21111 and denominator 100000
you get the gist of it!
Herc
Saint Cad
"Leonard Blackburn" <blac...@math.umn.edu> wrote in message
news:aa503d8.04101...@posting.google.com...
Let me start by saying that I don't believe Cantor's Method is in fact
invalid. I know from when I got my BA in math that the proof as presented
in class left a lot to be desired. I guess the issue I was trying to raise
is: are there arguments against Cantor's Method that need results other that
the method by itself to dismiss?
The first "disproof" of Cantor was one presented by another student (not
me!) at the time. I never liked that argument either. It struck me as
similar to the argument to "the number of naturals is finite since listing 1
to N is a finite cardnality and adding one more (i.e. 1 to N+1) is finite.
QED." I do have to admit though that the idea a couple of posters presented
(including Tim) that the original list of reals is arbitrary is a good
point, one the professor didn't make when I originally learned it.
The second "disproof" was in honor of James Harris. I was thinking of his
idea of a counterexample to Wiles proof to see where it broke down. I had
tried it myself and I kept running into the same problem - I could never
show that the number created by the diagonal was repeating. I posted it in
hopes that someone could show me why I kept running into the same problem
over and over without the circular argument of "It fails because the
rational are countable" and could instead point out where exactly Cantor's
Method fails on rational numbers.
|-|erc
I've shown this... 3 times now. Yes it fails because the rationals are countable, so what does
'they are countable' mean?
1 Given a countable list containing all rationals
2 Given any *new number* that has a repeating decimal
3 Given any number with repeating decimal, we can calculate the integer numerator and denominator.
4 Given any numerator and denominator pair, we can calculate its position in the list.
numerator 21111
--------------------------->
| / / / / /
| / / / /
| / / /
| / /
| /
|
| 10,000 *
v
denominator
5 Given it has a fixed position in the countable list, it cannot be new. Contradiction to 1&2.
6 Corollary : Every complete list of rationals has an irrational diagonal
HTH
Herc
Mike Oliver
> Let me start by saying that I don't believe Cantor's Method is in fact
> invalid. I know from when I got my BA in math that the proof as presented
> in class left a lot to be desired.
None of us can really speak to that; we weren't in your
class. So it's probably better if you stick to discussing
some version of the proof that's publicly and conveniently
available.
> The second "disproof" was in honor of James Harris. I was thinking of his
> idea of a counterexample to Wiles proof to see where it broke down. I had
> tried it myself and I kept running into the same problem - I could never
> show that the number created by the diagonal was repeating. I posted it in
> hopes that someone could show me why I kept running into the same problem
> over and over without the circular argument of "It fails because the
> rational are countable" and could instead point out where exactly Cantor's
> Method fails on rational numbers.
It doesn't "fail"; it produces an irrational number. What's
left to say? If you could use the method to diagonalize out
of the rationals, producing a number that's nevertheless rational
(but yet can't be rational), then we'd have a problem. But
you haven't done that, so I don't see the problem.
Josh Purinton
No. The error was in the informal English description, not in the formal
(machine-checked) proof or proof checker.
--
Josh Purinton
Charlie-Boo
The error is not in how the proof was described. The proof itself is
not mathematically valid. Would you want a proof checker that
reported that an invalid proof is valid?
Do you agree with my argument that there is no "supremum"? The series
has no limit. No point stays within the shrinking interval.
Here is a simple graphic representation of the proof. Let the current
interval (g(i) to h(i)) be A to B on the number line:
< - - - A - - - - - - - - - - B - - - >
If the next number listed, N, is within the interval:
< - - - A - - - - N - - - - - - B - - - >
we avoid N be letting the next interval A' to B' be between N and B:
< - - - A - - - - N - - A' - - B' - - B - - - >
However, this zig-zag to avoid the numbers N listed also avoids any
particular number L, preventing it from remaining in the interval
indefinitely. For, suppose that the limit (supremum) is L:
< - - - A - - - L - - - - - - - - B - - - >
and N falls between L and B:
< - - - A - - - L - - N - - - - - - B - - - >
Then the new interval A' to B' is between N and B:
< - - - A - - - L - - N - - A' - - B' - - B - - - >
and the new interval does not contain L.
Agree?
C-B
Charlie-Boo
> Charlie-Boo wrote:
>
> > Then something must be wrong with your computer or program.
> <snip>
>
> My feeling is that we may not get very far discussing the informal
> proof, whose purpose is only to give you a rough guideline. It will be
Do you agree that both the informal proof and the formal proof must be
valid?
Do you agree with my conclusion that that there is no limit L that is
contained in all of your intervals [g(i),h(i)]?
As far as the formal proof goes, I would say that wherever it first
uses your argument to conclude that N is of less cardinality than R is
where the error occurs. Where does that occur? I see that RUCLEM38
concludes that there is no function from N onto R. It begins with the
innocent assertion that there is a function from N to R. Then it
presents 4 long expressions and references to theorem CLEQID that A=A.
How are these expressions justified? How is the conclusion that there
is no function from N onto R justified? In particular, where does it
first use the "supremum"? By my reasoning this limit does not exist.
C-B
Unknown
> to R.
Actually, that's a hypothesis of the lemma. In Metamath, only axioms are
asserted without proof.
Your questions betray several basic misunderstandings about Metamath (to
say nothing of the distinction between a formal proof and an informal
overview). Back in January I pointed you to the Metamath book. Have
you read it?
--
Josh Purinton
Norman Megill
> Norman Megill <n...@nospam.see.signature.domain.invalid> wrote
>
>>Charlie-Boo wrote:
>>
>> > Then something must be wrong with your computer or program.
>><snip>
>>
>>My feeling is that we may not get very far discussing the informal
>>proof, whose purpose is only to give you a rough guideline. It will be
>>far better to to critique the formal proof.
>
> Do you agree that both the informal proof and the formal proof must be
> valid?
No. Only the formal proof must be valid. It is certainly desirable
that the informal proof be valid, as it helps better communicate the
formal proof to humans, but it is irrevelant to the validity of the
conclusion of the formal proof.
> Do you agree with my conclusion that that there is no limit L that is
> contained in all of your intervals [g(i),h(i)]?
No. Your conclusion is wrong. Each interval [g(i+1),h(i+1)] is nested
inside of [g(i),h(i)]. As i grows, they nest tighter and tighter around
a single point, which is the supremum.
Please, convince yourself by writing a simple computer program to
print out the first few values of the interval [g(i),h(i)] as i grows.
For f you could use a random number generator, for example. Watch as
the interval converges to a single point. Given any f, you can compute
the value of the supremum to as many decimal places as you like.
That the limit L -- which I call S in the formal proof -- is contained
in all of the intervals [g(i),h(i)] is proved in
http://us.metamath.org/mpegif/ruclem35.html . The notation is
(G`A) < S < (H`A), where (G`A) means g(i).
> As far as the formal proof goes, I would say that wherever it first
> uses your argument to conclude that N is of less cardinality than R is
> where the error occurs. Where does that occur?
http://us.metamath.org/mpegif/ruclem37.html is the first place that
shows F cannot map onto R. In that proof, it is step 24, which combines
steps 19 and 23 with modus tollens. Step 23 says: if F maps onto the
reals, its range must contain the supremum S (which we previously proved
is a real). Step 19 says: the supremum S is not in the range of F.
The conclusion (step 24) says: F cannot map onto the reals.
> I see that RUCLEM38
> concludes that there is no function from N onto R. It begins with the
> innocent assertion that there is a function from N to R. Then it
> presents 4 long expressions and references to theorem CLEQID that A=A.
http://us.metamath.org/mpegif/ruclem38.html is merely a technical lemma
to get rid of hypotheses ruclem.1-ruclem.5 in
http://us.metamath.org/mpegif/ruclem37.html . In order to prevent the
bulk of the proof from being even more awkward than it is, these five
hypotheses use variables C, D, G, H, and S to abbreviate certain
expressions, so that these expressions won't have to be repeated over
and over throughout the proof. For example, S abbreviates the supremum
sup(ran G, R, <) so that we can simply mention S when we want to mean
sup(ran G, R, <). When we no longer need to refer to these
abbrevations, we substitute the right-hand side of each hypothesis into
the left-hand side. Then both sides become equal, and we can eliminate
them with cleqid, which states simply A=A.
The expression in, for example, step 6 of ruclem38 is very long because
of nested abbreviations that are being eliminated. The abbreviation S
expands to include a reference to G, which in turn expands to include
references to C and D, which finally are very long expressions
themselves.
> How are these expressions justified?
By the theorem A=A, where A is any class expression, even a very long
one.
> How is the conclusion that there is no function from N onto R justified?
By the modus tollens in step 24 of
http://us.metamath.org/mpegif/ruclem37.html .
> In particular, where does it first use the "supremum"?
http://us.metamath.org/mpegif/ruclem34.html step 7.
> By my reasoning this limit does not exist.
Your reasoning is wrong. That the limit S exists (i.e. is a real number)
is shown in the last step of http://us.metamath.org/mpegif/ruclem34.html .
You cannot refute that.
G. Frege
<n...@nospam.see.signature.domain.invalid> wrote:
As usual.
F.
G. Frege
(google-no...@xoxy.net) wrote:
> In article <3df1e59f.0410...@posting.google.com>,
> Charlie-Boo <ch...@aol.com> wrote <bla bla>
>
> Back in January I pointed you to the Metamath book.
> Have you read it?
>
This is a joke, isn't it? (Charly just likes to babble...)
F.
Leonard Blackburn
> > Please read the replies to you made by Tim Peters, Dave Seaman, Daniel
> > W. Johnson, and Robert Low (all of which were made after you wrote
> > this).
> > Especially Tim Peters has pointed out your flaws in not understanding
> > Cantor's Diagonal Argument with the clarity of a thousand suns.
> >
> > -Leonard Blackburn
>
> Let me start by saying that I don't believe Cantor's Method is in fact
> invalid. I know from when I got my BA in math that the proof as presented
First, let's not call it a "method." Let's call it a "proof". If you
believe his proof is correct, then you would not be asking how to
dismiss the kinds of objections raised to it. The objections you
mentioned don't address the proof at all. Tim Peters already said,
once the proof is done it's done. One can't object by saying "but
what if we append this diagonal number..." because the proof is over.
That "objection" doesn't even address the proof.
> in class left a lot to be desired. I guess the issue I was trying to raise
> is: are there arguments against Cantor's Method that need results other that
> the method by itself to dismiss?
If you think that's possible, then you aren't sure that the proof is
correct, which means you really don't understand the proof. Proofs
cannot both be correct and not be able to withstand objections on
their own.
>
> The first "disproof" of Cantor was one presented by another student (not
> me!) at the time. I never liked that argument either. It struck me as
> similar to the argument to "the number of naturals is finite since listing 1
> to N is a finite cardnality and adding one more (i.e. 1 to N+1) is finite.
> QED."
That's ridiculous. That doesn't even make me think twice about the
cardinality of the naturals.
> I do have to admit though that the idea a couple of posters presented
> (including Tim) that the original list of reals is arbitrary is a good
> point, one the professor didn't make when I originally learned it.
>
Unfortunate. Well, now that you see that the original list of reals
is arbitrary than the possible objections are over, right?
> The second "disproof" was in honor of James Harris. I was thinking of his
> idea of a counterexample to Wiles proof to see where it broke down. I had
> tried it myself and I kept running into the same problem - I could never
> show that the number created by the diagonal was repeating. I posted it in
> hopes that someone could show me why I kept running into the same problem
> over and over without the circular argument of "It fails because the
> rational are countable" and could instead point out where exactly Cantor's
> Method fails on rational numbers.
I don't understand your last point. If you replace "real" with
"rational" in Cantor's theorem and his proof. The proof would be
incorrect because the diagonal number produced need not be rational.
So, you wouldn't have a proof that the set of rationals is
uncountable. There is nothing surprising there.
I just don't see the point in raising objections to a proof without
pointing out what the error is. Which line of the proof is wrong?
That's what I would ask an objector.
-Leonard
Norman Megill
No. You've chosen the wrong L. Each function f will have its own
L, and you must pick the correct L for that function.
In this program I purposely pick the next value of f inside the
current interval, to try to fool it the way you describe above.
The intervals converge to the supremum 1.8038... in this case.
This supremum stays within the shrinking interval until the
computer's floating point precision is exhausted.
But pick whatever function for f(i) that you like, and put it at
the line with "f_iplus1 =". No matter what you function you pick,
it will always converge to a supremum.
#include <stdlib.h>
#include <stdio.h>
int main() {
long i;
double f_i, g_i, h_i, g_iplus1, h_iplus1, f_iplus1;
/* See algorithm at
http://us.metamath.org/mpegif/mmcomplex.html#uncountable */
/* Initialize */
f_i = 0; g_i = f_i + 1.0; h_i = f_i + 2.0;
for (i = 1; i < 10; i++) {
printf("i = %ld, f(i) = %f, g(i) = %f, h(i) = %f\n", i, f_i, g_i, h_i);
/* Pick next f(i+1) inside current interval to try to fool it
according to C.B.'s argument */
f_iplus1 = g_i + (h_i - g_i) * (double)(rand())/(double)(RAND_MAX);
if (g_i < f_iplus1 && f_iplus1 < h_i) {
g_iplus1 = (2.0 * f_iplus1 + h_i) / 3.0;
h_iplus1 = (f_iplus1 + 2.0 * h_i) / 3.0;
} else {
g_iplus1 = (2.0 * g_i + h_i) / 3.0;
h_iplus1 = (g_i + 2.0 * h_i) / 3.0;
}
/* Prepare for next iteration */
f_i = f_iplus1; g_i = g_iplus1; h_i = h_iplus1;
}
return 0;
}
i = 1, f(i) = 0.000000, g(i) = 1.000000, h(i) = 2.000000
i = 2, f(i) = 1.505418, g(i) = 1.670279, h(i) = 1.835139
i = 3, f(i) = 1.761741, g(i) = 1.786207, h(i) = 1.810673
i = 4, f(i) = 1.792513, g(i) = 1.798566, h(i) = 1.804620
i = 5, f(i) = 1.802357, g(i) = 1.803112, h(i) = 1.803866
i = 6, f(i) = 1.803748, g(i) = 1.803787, h(i) = 1.803826
i = 7, f(i) = 1.803803, g(i) = 1.803811, h(i) = 1.803819
i = 8, f(i) = 1.803813, g(i) = 1.803815, h(i) = 1.803817
i = 9, f(i) = 1.803815, g(i) = 1.803816, h(i) = 1.803816