(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
|-|erc
"Leonard Blackburn" <blac...@math.umn.edu> wrote in
> >- 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.
Why?
> 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.
The concept of unique number is wrong. The whole reason we *introduced digits* for
numbers was exactly to distinguish numbers.
0.xyz... is different to 0.ayz... because x =/= a
You can't come along and say, "now we will use a different digit here, here, here ,here..."
that is merely the *definition* of a unique cardinal.
We laugh at your hyperinfinities, Halt is a defined function, anti diag is an illusion.
Show me the single contradictory digit from your proof. What digit position?
Herc
Charlie-Boo
> Charlie-Boo <ch...@aol.com> wrote:
> > It begins with the innocent assertion that there is a function from N
> > to R.
>
> Actually, that's a hypothesis of the lemma. In Metamath, only axioms are
> asserted without proof.
More quibbling over terminology.
> Your questions betray several basic misunderstandings about Metamath (to
> say nothing of the distinction between a formal proof and an informal
> overview).
Unsubstantiated.
> Back in January I pointed you to the Metamath book. Have
> you read it?
I asked you first:
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)]?
C-B
Saint Cad
Thank you for all of the help. Like I said, when I learned the proof, there
were a lot of the details left out so even though I understood the proof,
the proof did not seem to be rigorous. After reading the posts, I see that
the rigor is there in the proof, just not in the professor's presentation.
For example, the fact that the list was arbitrary was left out and it seemed
that the list the prof wrote down was a specific list of reals (hence my
question about why can't we take a specific list of rationals and do the
same).
David Bernier
[...]
> The concept of unique number is wrong. The whole reason we *introduced digits* for
> numbers was exactly to distinguish numbers.
I thought some of the the ancient Romans could count from I to C and
even D or M or MM ....
David Bernier
Mike Oliver
Right. They also didn't like numbers of the form 500n+10m+6 (m<10),
or 500n+10m+4 (m<10).
Whence the rule, "I before V except after C".
|-|erc
Charlie-Boo
Frege, the debate is over his proof, not how to use his system. You
don't even know what we're talking about.
|-|erc
Shouldn't claims of formal proof include a 'context', a primer on the machine / system?
Seems like everyone here is in on something, which might be fine, or it might not.
The OP hints of using metamath. That would give us some avenue to check for flaws.
Herc
Virgil
ch...@aol.com (Charlie-Boo) wrote:
It would appear that you have no better idea than he does.
G. Frege
<ITSnetNOTcom#vir...@COMCAST.com> wrote:
> >
> > Frege, the debate is over his proof, not how to use his system.
> >
Golly, to _understand_ the formal proof you have to understand his
system first. (It's like talking to a child. *sigh*)
>
> It would appear that you have no better idea than he does.
>
Indeed.
F.
G. Frege
>
> Do you agree that both the informal proof and the formal proof must be
> valid?
>
Well, I would *prefer* that b o t h were valid. But that's exactly the
difference between these two approaches: while the formal proof can be
c h e c k e d and v e r i f i e d by computer, the informal proof cannot
(at least not presently).
On the other hand (*sigh*) ... Since the formal proof has been
c h e c k e d and v e r i f i e d there's no point in trying to
question this proof by _informal_ reasoning, man.
In the words of Norman Megill:
"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 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 thatn 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."
F.
George Greene
> Surely a more important result than the uncountability of R
> is that R has cardinality 2^aleph_0.
That is a *definition*, NOT a "result".
For all practical purposes,
2^X *means* "The powerset of X".
More to the point, 2^aleph_0 actually IS NOT
a cardinality. I mean, it HAS a cardinality,
but nobody knows what that cardinality is.
They just know that it has to be bigger than
aleph_0.
> Do you intend formalizing
> this in metamath sometime?
You can't prove a definition.
What he *needed* to be proving was the general result
that there cannot be a bijection between a set and
its powerset. R and cardinalities are not relevant
(except insofar as "has the same cardinality as"
is DEFINED to mean the same thing as "a bijection
exists between").
Robert Low
George Greene <gre...@cs.unc.edu> wrote:
>Robin Chapman <r...@ivorynospamtower.freeserve.co.uk> wrote in message
>news:<cl2g8g$dmt$3...@south.jnrs.ja.net>...
>
>> Surely a more important result than the uncountability of R
>> is that R has cardinality 2^aleph_0.
>
>That is a *definition*, NOT a "result".
Not by the definition I'm used to. If your
definition of 2^aleph_0 is "cardinality of
the power set of N", then it's a result, since
you have to prove the existence of a bijection
between R and the power set of N.
Contrariwise, if your (IMO perverse)
definition of 2^aleph_0 is "cardinality of
R", then you have to work to prove that 2^aleph_0
is the cardinality of the power set of a set
of cardinality aleph_0, which doesn't strike
me as the best way to set up the definitions.
Robin Chapman
> Charlie-Boo wrote:
>
>> jo...@bayes.joshpurinton.com (Josh Purinton) wrote in message
>>
>> 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?
In Norm's proof, if g(i) < f(i+1) < h(i) then g(i+1) and h(i+1)
satisfy f(i+1) < g(i+1) < h(i+1) < h(i). As L is the supremum of
the the g(j) then L >= g(i+i) > f(i+1). The hypothetical
case that Charlie-Poo describes "N falls between L and B",
that is L < f(i+1) < h(i), simply does not arise.
--
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_
Leonard Blackburn
> "Leonard Blackburn" <blac...@math.umn.edu> wrote in
>
> > >- 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.
>
> Why?
That's a question for you to answer. If you purported that the
diagonal proof also applied to the rationals then you would have to
prove that the diagonal number created for an arbitrary list of
rationals is itself rational. If not then there would be a gap in
your proof. So forget I said "the diagonal number produced need not
be rational" (which is true). Instead I would like to say "prove that
the diagonal number is 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.
>
>
> The concept of unique number is wrong.
Ok. Then you are objecting to something prior to the proof. So why
bother discussing Cantor's proof at all?
> The whole reason we *introduced digits* for
> numbers was exactly to distinguish numbers.
>
I thought it was to make arithmetic and notation easier.
> 0.xyz... is different to 0.ayz... because x =/= a
>
> You can't come along and say, "now we will use a different digit here, here, here ,here..."
Why not?
> that is merely the *definition* of a unique cardinal.
>
That doesn't make sense.
> We laugh at your hyperinfinities,
I don't have any hyperinfinities.
> Halt is a defined function,
What does that have to do with my post?
> anti diag is an illusion.
?
> Show me the single contradictory digit from your proof. What digit position?
>
That doesn't make sense.
-Leonard Blackburn
> Herc
Norman Megill
> Robin Chapman wrote
>
>>Surely a more important result than the uncountability of R
>>is that R has cardinality 2^aleph_0.
>
> That is a *definition*, NOT a "result".
2^aleph_0 is not defined as the cardinality of R. There is a general
definition for cardinal exponentiation, into which you plug "2" and
"aleph_0". That this specific instance of cardinal exponentiation
evaluates to the cardinality as R is a somewhat difficult proof, and
I haven't worked it out formally yet.
> For all practical purposes,
> 2^X *means* "The powerset of X".
Well, it is not a completely trivial proof. That 2^X is equinumerous to
the powerset of X is proved here:
http://us.metamath.org/mpegif/pw2en.html (warning: 400K page)
But yes, once it is proved, for practical purposes they mean the same thing.
> More to the point, 2^aleph_0 actually IS NOT
> a cardinality. I mean, it HAS a cardinality,
> but nobody knows what that cardinality is.
2^aleph_0 is a cardinal number, since cardinal exponentiation of two
cardinal numbers is a cardinal number (just like the addition of two
integers is an integer, etc.). What you mean is: you can't know
whether it equals aleph_1 in the absence of CH.
> They just know that it has to be bigger than
> aleph_0.
Yes. And also that it is at least as big as aleph_1.
http://us.metamath.org/mpegif/aleph1.html
and thus strictly bigger than aleph_0 by
http://us.metamath.org/mpegif/alephordi.html
> You can't prove a definition.
>
> What he *needed* to be proving was the general result
> that there cannot be a bijection between a set and
> its powerset.
Already done. Cantor's theorem:
http://us.metamath.org/mpegif/canth2.html
which implies no equinumerosity:
http://us.metamath.org/mpegif/sdomnen.html
which implies no bijection:
http://us.metamath.org/mpegif/bren.html
Charlie-Boo
> > >
> Golly, to _understand_ the formal proof you have to understand his
> system first. (It's like talking to a child. *sigh*)
Frege, we've been talking about the informal proof, not his system or
his claimed formal proof. His initial response to my point was, "My
feeling is that we may not get very far discussing the informal
Proof." and he kept saying, "It will be far better to critique the
formal proof."
How many times do I have to explain that? Just read the messages.
Did you actually read them?
Or do you just jump into the fray and take one side or the other
without having read what they're talking about? Or post a page from a
math book without knowing what it is (and it too wasn't what we were
talking about)? Or claim that a book or article solves a particular
problem because it is mentioned in the title?
C-B
|-|erc
> > "Leonard Blackburn" <blac...@math.umn.edu> wrote in
> >
> > > >- 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.
> >
> > Why?
>
> That's a question for you to answer. If you purported that the
> diagonal proof also applied to the rationals then you would have to
> prove that the diagonal number created for an arbitrary list of
> rationals is itself rational. If not then there would be a gap in
> your proof. So forget I said "the diagonal number produced need not
> be rational" (which is true). Instead I would like to say "prove that
> the diagonal number is rational."
so you cannot justify your statement that
If you replace "real" with "rational" in Cantor's theorem and his proof the proof would be incorrect
>
> >
> >
> > > 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.
> >
> >
> > The concept of unique number is wrong.
>
> Ok. Then you are objecting to something prior to the proof. So why
> bother discussing Cantor's proof at all?
he's the one who claims anti-diag is unique.
Here's an infnite list of reals
0.0xxxxxx..
0.1xxxxxx..
0.2xxxxxx..
0.0xxxxxxx..
0.3xxxxxx..
0.5xxxxxx..
0.8xxxxxx..
0.1xxxxxxx..
0.2xxxxxxxx..
0.0xxxxxxx..
0.1xxxxxxxx..
As you can see, 0.0xxxx.. appears repeatedly, so 0.0 is covered infinitely many times
0.1xxxxx.. appears an infinite number of times.
It doesn't matter what the digits the are, they are all present.
0.abcxxx.. is present for EVERY a, b and c.
0.abcdefghijklmnopqrstuvwxyz...... is ON THE LIST for ALL values of a, b, c, d, e, ... z
by extension every digit combination is present.
You claim there is ONE digit that is different, but that digit CANNOT appear at digit position 1.
0.1xxxx
0.2xxxx
0.3xxxx
these are all on the list of computable reals.
0.11xxxx..
0.12xxxx..
0.13xxsxx..
these are all on the list of computable reals.
The contradictory digit on your list must be after the 2nd decimal place mustn't it?
Your contradiction dissapears altogether because it cannot occur at a finite decimal.
The digits 1, 2, 3, 4, 5 .. 9, 0 are virtually identical and interchangable, they merely adjust
the region on the numberline but have *no semantic difference*, to make a formula claiming
this number (which is always only a variable) is DIFFERENT to this number is nonsense,
they are just DIGITS
Countable infinity is bigger than you can conceive or mathematically manipulate..
Herc
is mustn't a word?
Dave Seaman
> "Leonard Blackburn" <blac...@math.umn.edu> wrote in
>> "|-|erc" <sp...@fodder.abc> wrote in
>> > "Leonard Blackburn" <blac...@math.umn.edu> wrote in
>> >
>> > > >- 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.
>> >
>> > Why?
>>
>> That's a question for you to answer. If you purported that the
>> diagonal proof also applied to the rationals then you would have to
>> prove that the diagonal number created for an arbitrary list of
>> rationals is itself rational. If not then there would be a gap in
>> your proof. So forget I said "the diagonal number produced need not
>> be rational" (which is true). Instead I would like to say "prove that
>> the diagonal number is rational."
> so you cannot justify your statement that
> If you replace "real" with "rational" in Cantor's theorem and his proof the proof would be incorrect
The diagonal argument depends on the least upper bound property of the
real numbers. The diagonal argument produces a decimal digit string,
which is associated with a certain infinite series. The partial sums of
that series form a set of real numbers that is nonempty and bounded
above. The least upper bound of that set is the required number.
The same argument does not work when applied to the rationals, since the
rationals do not satisfy the LUB property.
And, by the way, there is nothing circular about the argument that if the
original list contains all of the rational numbers, then the number
produced by the diagonal argument, which is necessarily different from
any number in the list, must therefore be irrational.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
Charlie-Boo
> On 20 Oct 2004 06:13:50 -0700, ch...@aol.com (Charlie-Boo) wrote:
>
> > Do you agree that both the informal proof and the formal proof must be
> > valid?
> >
> Well, I would *prefer* that b o t h were valid. But that's exactly the
> difference between these two approaches: while the formal proof can be
> c h e c k e d and v e r i f i e d by computer, the informal proof cannot
> (at least not presently).
What difference does that make? If we use normal mathematics (not a
computer) to show that the informal proof is not valid, then still,
what is the sense of using software that tells us that "the proof" is
valid? That's just stupid, wouldn't you say?
> On the other hand (*sigh*) ... Since the formal proof has been
> c h e c k e d and v e r i f i e d there's no point in trying to
> question this proof by _informal_ reasoning, man.
It is the system that tells us that an invalid proof is valid that
needs to be checked and verified (and returned to the manufacturer.)
C-B
> F.
Josh Purinton
Charlie-Boo <ch...@aol.com> wrote:
>If we use normal mathematics (not a computer) to show that the informal
>proof is not valid, then still, what is the sense of using software
>that tells us that "the proof" is valid?
If we have verified that a formal proof is correct, then we know that
its conclusion is provable in our formal system. Our knowledge of this
fact is independent of the correctness or incorrectness of any "informal
proofs".
--
Josh Purinton
Virgil
> G. Frege <no_...@aol.com> wrote
> > On 20 Oct 2004 06:13:50 -0700, ch...@aol.com (Charlie-Boo) wrote:
> >
> > > Do you agree that both the informal proof and the formal proof must be
> > > valid?
> > >
> > Well, I would *prefer* that b o t h were valid. But that's exactly the
> > difference between these two approaches: while the formal proof can be
> > c h e c k e d and v e r i f i e d by computer, the informal proof cannot
> > (at least not presently).
>
> What difference does that make? If we use normal mathematics (not a
> computer) to show that the informal proof is not valid, then still,
> what is the sense of using software that tells us that "the proof" is
> valid? That's just stupid, wouldn't you say?
Equally stupid to say that methods that produced an invalid proof cannot
create an invalid refutation of that proof.
>
> > On the other hand (*sigh*) ... Since the formal proof has been
> > c h e c k e d and v e r i f i e d there's no point in trying to
> > question this proof by _informal_ reasoning, man.
>
> It is the system that tells us that an invalid proof is valid that
> needs to be checked and verified (and returned to the manufacturer.)
Or the system that tells us that a valid proof is invalid.
>
> C-B
>
> > F.
Charlie-Boo
> Charlie-Boo <ch...@aol.com> wrote:
> >If we use normal mathematics (not a computer) to show that the informal
> >proof is not valid, then still, what is the sense of using software
> >that tells us that "the proof" is valid?
>
> If we have verified that a formal proof is correct, then we know that
> its conclusion is provable in our formal system.
The actual theorem not having been proven, it could very well be
false, in which case your system has just proven an untrue sentence
and thus is not sound. Do you agree? And would you advocate the use
of a system that is not sound?
> Our knowledge of this
> fact is independent of the correctness or incorrectness of any "informal
> proofs".
Yes, but then what is the point of the formal proof? Does is
represent a real (conventional mathematical) proof or not? Do you
think that the formal proof demonstrates that the theorem is in fact
true?
C-B
Charlie-Boo
> In article <3df1e59f.04102...@posting.google.com>,
> ch...@aol.com (Charlie-Boo) wrote:
>
> > G. Frege <no_...@aol.com> wrote
> > > On 20 Oct 2004 06:13:50 -0700, ch...@aol.com (Charlie-Boo) wrote:
> > >
> > > > Do you agree that both the informal proof and the formal proof must be
> > > > valid?
> > > >
> > > Well, I would *prefer* that b o t h were valid. But that's exactly the
> > > difference between these two approaches: while the formal proof can be
> > > c h e c k e d and v e r i f i e d by computer, the informal proof cannot
> > > (at least not presently).
> >
> > What difference does that make? If we use normal mathematics (not a
> > computer) to show that the informal proof is not valid, then still,
> > what is the sense of using software that tells us that "the proof" is
> > valid? That's just stupid, wouldn't you say?
>
> Equally stupid to say that methods that produced an invalid proof cannot
> create an invalid refutation of that proof.
Do you mean the system that validated the faulty proof? Yes, I agree
that, as far as we know, this system might also reject that proof on
other grounds and thus be inconsistent (as well as not sound.)
We are talking about three variables:
1. Is the proof valid?
2. Does the system declare the proof to be valid?
3. Is the reasoning used by the system valid?
We seem to be in agreement that we are talking about the NO,YES,NO
case: An invalid proof that the system declares to be valid (obviously
using invalid reasoning.) You are hypothesizing the NO,NO,NO
scenario: This invalid proof is correctly rejected by the system, but
for an invalid reason!
I think that these layers of potential problems are symptomatic of the
"verification" approach to automated theorem-proving. The big secret
is that if you really do understand a particular semi-formal system
(e.g. the Theory of Computation or Cantor's theory of infinite sets)
then you really can write software to carry it out (no smoke and
mirrors) and create its theorems. Then there is no question about
your proof vs. its verification. The system simply creates the
theorems.
Now, those who (using a word processor with a Mathematical font) would
like to say that they have done this, but are unable to, are in a
dilemma. They need to:
1. Show the theorems that were generated.
2. Declare that the system generated them.
(1) is easy. It's not hard to make up a bunch of long cryptic
expressions - especially if (since) you never explain how there is any
significance to them (all 500 characters worth!) (2) is a little
trickier. You'd better be careful if you're going to claim that the
computer wrote something that in fact you personally wrote by hand.
The "solution" is to admit that you wrote the "formal proof", but
claim that the computer "verified" it. But what does that mean? It
checked the syntax of your expressions (intermediate theorems) and
verified that they were in fact equal to the result of applying some
rule to known theorems? But if it can do that, then it must know the
correct result of applying these rules, in which case it could simply
write it out instead of making it into a test against what we enter.
Then we would have a theorem-prover without the user having to enter
in the theorem.
Now wouldn't that be nice? :)
C-B
> > > On the other hand (*sigh*) ... Since the formal proof has been
> > > c h e c k e d and v e r i f i e d there's no point in trying to
> > > question this proof by _informal_ reasoning, man.
> >
> > It is the system that tells us that an invalid proof is valid that
> > needs to be checked and verified (and returned to the manufacturer.)
>
> Or the system that tells us that a valid proof is invalid.
The YES,NO,NO case!
> > > F.
Taneli Huuskonen
Hash: SHA1
En la afisho <kOCdnS7PSPz...@rcn.net> Norman Megill
<n...@nospam.see.signature.domain.invalid> skribis:
>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.
I don't know how long the Journal of Formalized Mathematics has existed
on the Web, but it has contained a formal proof of the uncountability of
the power set of the naturals for a bit more than 15 years. See
Theorem 29 in
http://www.mizar.org/JFM/Vol1/card_1.miz.html .
Regards,
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (OSF1)
iD8DBQFBe9dwX63QJgt8tpURAlXtAKCguzrhlHgsrhBeNPOHetgKEkVD5QCg8vLe
Pd7SqM3OV2ghcIVTdQ7z5uU=
=DW8e
-----END PGP SIGNATURE-----
--
All messages will be PGP signed, | Atk-yhdyshenkilöille lisätietoa
encrypted mail preferred. Keys: | intranetin hallinnollisen päätoimittajan
http://www.helsinki.fi/~huuskone/ | syöttämisestä on atk-yhdyshenkilöoppaassa.
Guantánamo macht frei! | -- Helsingin yliopiston intranet-opas
Josh Purinton
Taneli Huuskonen <huus...@cc.helsinki.fi> wrote:
> I don't know how long the Journal of Formalized Mathematics has existed
> on the Web, but it has contained a formal proof of the uncountability of
> the power set of the naturals for a bit more than 15 years. See
> Theorem 29 in
> http://www.mizar.org/JFM/Vol1/card_1.miz.html .
Theorem CARD_1:29 states: "not X,bool X are_equipotent".
I wouldn't be at all surprised to learn that someone had already
formalized a proof of the uncountability of the reals in Mizar. But
CARD_1:29 itself would be only a piece of that proof.
--
Josh Purinton
Virgil
> jo...@bayes.joshpurinton.com (Josh Purinton) wrote in message
> > In article <3df1e59f.04102...@posting.google.com>,
> > Charlie-Boo <ch...@aol.com> wrote:
> > >If we use normal mathematics (not a computer) to show that the informal
> > >proof is not valid, then still, what is the sense of using software
> > >that tells us that "the proof" is valid?
> >
> > If we have verified that a formal proof is correct, then we know that
> > its conclusion is provable in our formal system.
>
> The actual theorem not having been proven,
Who says it hasn't been?
G. Frege
<ITSnetNOTcom#vir...@COMCAST.com> wrote:
> >
> > The actual theorem not having been proven,
>
> Who says it hasn't been?
>
Charlie-Boo! Hence it m u s t be right!
BRUHAHAHAHAHAH!!!
F.
Virgil
Norman Megill
> I don't know how long the Journal of Formalized Mathematics has existed
> on the Web, but it has contained a formal proof of the uncountability of
> the power set of the naturals for a bit more than 15 years. See
> Theorem 29 in
>
> http://www.mizar.org/JFM/Vol1/card_1.miz.html .
Thank you. This is an instance of Cantor's theorem, which was added to
the Metamath database in August 1994.
http://us.metamath.org/mpegif/canth.html
The uncountability of the reals is a considerably more difficult proof
to work out formally (even though informally it appears trivial). I was
unable to find a Mizar proof of it, and if you find one let me know.
This is not to say that it couldn't be done, perhaps even without a lot
effort given Mizar's current considerable database, by someone motivated
to do it. Unfortunately it doesn't have a lot of applications beyond
appeasing the skeptics. And it doesn't even seem to do that very well,
because the skeptics won't put in the minimal effort needed to identify
where they claim the formal proof is wrong.
(As pointed out by Robin Chapman, a more important proof would be that R
has cardinality 2^aleph_0.)
Charlie-Boo
The scenario in which it has not been proven is not eliminated by your
premise. Those cases are included.
C-B
Charlie-Boo
Virgil
Non-responsive. I repeat, who says it hasn't been?
George Greene
> 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.
Well, it is time-honored; I mean, you personally would
also do this, if it were a direct proof. If a direct proof began
with "assume a list L with the following properties",
and then proceeded to show that there was an element l
not on L, then the fact that L couldn't exist in the
first place would certainly be a flaw in the reasoning
of the proof. The fact that the proof is indirect
(and, moreover, that it is a proof of a universal
generalization, that it is about ANY L with the
following properties and therefore has neither
existential import nor presuppositions -- the results
that will follow about L, from these properties, must in fact
hold WHETHER L EXISTS OR NOT -- I mean, every odd
perfect number is still odd, EVEN if there are NO
odd perfect numbers: ALL of them are STILL odd:
all zero of them) actually matters. But they
don't get that.
My point in any case is that you can't concede that
this has any elegance, not if you know some basic
propositional tautologies. An indirect proof
is going to be of the form P -> (Q & ~Q).
Since it's a conditional, it has to be equivalent
to its contrapositive, so this is the same as ~(Q & ~Q) -> ~P,
and since S -> T is ~S v T, this is (Q & ~Q) v ~P, which, by
distributivity, is Q v ~P and ~Q v ~P. Applying the
transfer theorem in the other direction to each of the conjuncts
yields ~Q -> ~P and Q -> ~P. In other words, EVERY
indirect proof (of the form P -> (Q & ~Q) ) is just the contrapositive
of a proof of (~Q -> ~P) & (Q -> ~P).
You just have to find the right Q. If you actually HAVE an
indirect proof then it reveals the right Q and it reveals
how to prove the contrapositive of each of these conjuncts.
SO YOU HAVE A PROOF OF THE EXACT SAME RESULT, USING ONLY ~P,
AND NEVER USING the "inappropriate" hypothesis P
(that something that actually cannot exist does exist anyway,
hypothetically, just for the sake of an argument that will
now be similarly contaminated by "inappropriateness").
YOU CAN ALWAYS CONTRAPOSITIVE IT AWAY. So we're NOT really
assuming that the complete list of reals (or whatever else
they might've thought we were "inappropriately" assuming)
exists.
Robert Low
George Greene <gre...@cs.unc.edu> wrote:
>mtx...@linux.services.coventry.ac.uk (Robert Low) wrote in message
>news:<cl3ksj$k9g$1...@sunbeam.coventry.ac.uk>...
>> 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.
>this has any elegance,
What, just because it's barking mad? That's
what I admire about it. I'm always impressed
by the contortions people will go through to
justify their prejudices.
(I see, however, that it remains true that Usenet
is not an appropriate medium for the use of irony.
Probably because it doesn't matter how outrageous
the statement, there's somebody out there who
already said it and meant it.)
--
Rob. http://www.mis.coventry.ac.uk/~mtx014/
Charlie-Boo
Godel
Virgil
Where did Godel say ever say anything like that?
I personally doubt very much that Godel ever said that any of Cantor's
theorems were not theorems.
|-|erc
> On Thu, 21 Oct 2004 22:26:32 GMT, |-|erc wrote:
> > "Leonard Blackburn" <blac...@math.umn.edu> wrote in
> >> "|-|erc" <sp...@fodder.abc> wrote in
> >> > "Leonard Blackburn" <blac...@math.umn.edu> wrote in
> >> >
> >> > > >- 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.
> >> >
> >> > Why?
> >>
> >> That's a question for you to answer. If you purported that the
> >> diagonal proof also applied to the rationals then you would have to
> >> prove that the diagonal number created for an arbitrary list of
> >> rationals is itself rational. If not then there would be a gap in
> >> your proof. So forget I said "the diagonal number produced need not
> >> be rational" (which is true). Instead I would like to say "prove that
> >> the diagonal number is rational."
>
> > so you cannot justify your statement that
> > If you replace "real" with "rational" in Cantor's theorem and his proof the proof would be incorrect
*a version of*
> The diagonal argument depends on the least upper bound property of the
> real numbers. The diagonal argument produces a decimal digit string,
> which is associated with a certain infinite series. The partial sums of
> that series form a set of real numbers that is nonempty and bounded
> above. The least upper bound of that set is the required number.
>
> The same argument does not work when applied to the rationals, since the
> rationals do not satisfy the LUB property.
>
> And, by the way, there is nothing circular about the argument that if the
> original list contains all of the rational numbers, then the number
> produced by the diagonal argument, which is necessarily different from
> any number in the list, must therefore be irrational.
Diagonalisation is a valid technique because diagonalisation is a valid technique.
I'm getting used to this argument!
Such a proof gives no reassurance of the diagonalisation technique, which was the whole point
of the OP. Assume diagonalisation may not work, then consider the example of rationals.
1 Start with a complete list of rationals
2 Order the list to have diagonal 0.12345678901234567890...
Every digit is present on the diag so no matter what digits your rational has it can
slide up or down the list until it fits.
3 Make an anti-diag, this has 10(n) repeating digits so it is rational but is not on the list.
Herc
Robert Low
|-|erc <sp...@fodder.abc> wrote:
>2 Order the list to have diagonal 0.12345678901234567890...
That's the tricky bit.
Dave Seaman
> "Dave Seaman" <dse...@no.such.host> wrote in
> *a version of*
>> The diagonal argument depends on the least upper bound property of the
>> real numbers. The diagonal argument produces a decimal digit string,
>> which is associated with a certain infinite series. The partial sums of
>> that series form a set of real numbers that is nonempty and bounded
>> above. The least upper bound of that set is the required number.
>>
>> The same argument does not work when applied to the rationals, since the
>> rationals do not satisfy the LUB property.
>>
>> And, by the way, there is nothing circular about the argument that if the
>> original list contains all of the rational numbers, then the number
>> produced by the diagonal argument, which is necessarily different from
>> any number in the list, must therefore be irrational.
> Diagonalisation is a valid technique because diagonalisation is a valid technique.
> I'm getting used to this argument!
The diagonal argument works because, given a mapping f: N -> R, the
argument produces a number x whose n'th digit differs from the n'th digit
of f(n) for each n. And since x is chosen to avoid dual-representation
problems, it follows that x is not in the range of f.
> Such a proof gives no reassurance of the diagonalisation technique, which was the whole point
> of the OP. Assume diagonalisation may not work, then consider the example of rationals.
> 1 Start with a complete list of rationals
> 2 Order the list to have diagonal 0.12345678901234567890...
> Every digit is present on the diag so no matter what digits your rational has it can
> slide up or down the list until it fits.
Consider the number 0.098765432109876543210987654321.... It's a rational
number. Where does it go in your list?
> 3 Make an anti-diag, this has 10(n) repeating digits so it is rational but is not on the list.
So, your method works because it works? Very clever.
Mike Oliver
> 1 Start with a complete list of rationals
>
> 2 Order the list to have diagonal 0.12345678901234567890...
> Every digit is present on the diag so no matter what digits your rational has it can
> slide up or down the list until it fits.
>
> 3 Make an anti-diag, this has 10(n) repeating digits so it is rational but is not on the list.
Oh, bravo, Herc! Seriously, this is a clever argument; it's very similar
to valid techniques we use all the time, and when I first read it (having
just stumbled out of bed moments earlier) it took me a little time to
see the error.
What we have to do is fix an actual protocol for doing the reordering,
and see what actually happens. Here's one suggestion, not the only
one certainly, but indicative:
1) start with complete list of rationals, indexed by natural numbers.
2) at stage n, we leave the first n rationals alone, and look for what
should be in position n+1 (starting with 1 as the first position; don't
like that but it makes the description easier in English).
3) If the rational already in position n+1 has the desired (n+1)st digit,
leave it where it is; otherwise move the first later rational having
the desired (n+1)st digit into position n+1, moving everything in
between along to fill the gap.
4) at the end, you have a list of rationals, indexed by the naturals, with
your desired diagonal.
The question is, have you kept all the rationals? The answer is no. Write it
out; see what happens to a number like 0.5555355555 repeating. It never gets
moved into position n+1 in step 3 of stage n, and never gets left where it is if
it's the rational already in that position. It keeps getting pushed ahead, like
sea foam ahead of the tide moving up the beach. In the final list, it isn't
even there at all.
Charlie-Boo
In 1931. If you verify a formal proof, then you have not verified
that the proof that it represents is valid. The possibility of
verifying an invalid proof came up when two readers posted messages
questioning the validity of the proof that is supposedly being
represented. I pointed out that without knowing that the system only
verifies proofs that represent valid logical arguments, it is a waste
of time to verify proofs, and the system has not succeeded in proving
the theorem.
Wffs certainly exist that nobody has proven, and Godel showed some
never will be, despite being true. A user is certainly able to type
one of these wffs into the "proof verifier". (I'll do it if nobody
else does.) But given that it erroneously "verified" an invalid
proof, who's to say it won't do so with the wff that has never been
proven?
Personally, even if the theorem turned out to be true, I see no value
in the system saying so based on an invalid proof. At that point it
is just a coincidence that it reached the right final conclusion. But
the statement that "The theorem is true because the system verified a
proof of it." is not true, and we have not proven the theorem as
claimed.
C-B
George Greene
> George Greene wrote:
>
> > Robin Chapman wrote
> >
> >>Surely a more important result than the uncountability of R
> >>is that R has cardinality 2^aleph_0.
> >
> > That is a *definition*, NOT a "result".
>
> 2^aleph_0 is not defined as the cardinality of R.
Come on. I'm on YOUR side.
The relevant point here is not so much that 2^aleph_0 "is not
defined as the cardinality of R" as it is that 2^aleph_0 IS NOT
the cardinality of R. My point was that whatever it is, it is
in virtue of DEFINITIONS and not of more complicated considerations.
Cardinality in the ZFC realm is defined in terms of bijections.
BY DEFINITION, two sets have the same cardinality if a bijection
exists between them. You can also by definition get cardinalities
being < or > on the basis of the existence of injections or surjections.
ALL OF THESE ARE DEFINITIONS AND NOT theorems. That was the point.
> There is a general definition for cardinal exponentiation,
Which is irrelevant.
The relevant operator in the sentence we were arguing about was
^,
which is NOT limited in application to cardinals.
It takes sets generally.
> into which you plug "2" and "aleph_0".
BOth of those are ORDINALS first and cardinals SECOND,
derivatively, by convention.
> That this specific instance of cardinal exponentiation
> evaluates to the cardinality as R is a somewhat difficult proof, and
> I haven't worked it out formally yet.
Neither has anyone else, nor will they ever, since it's already
been proven that ZFC does NOT impute a unique cardinality to 2^aleph_0.
There are different models of ZFC with different cardinalities for
2^aleph_0. Cardinalities and the associated alephs ascend via
LIMIT ORDINALS, NOT via powersets!
>
> > For all practical purposes,
> > 2^X *means* "The powerset of X".
>
> Well, it is not a completely trivial proof. That 2^X is equinumerous to
> the powerset of X is proved here:
> http://us.metamath.org/mpegif/pw2en.html (warning: 400K page)
> But yes, once it is proved, for practical purposes they mean the same thing.
>
> > More to the point, 2^aleph_0 actually IS NOT
> > a cardinality. I mean, it HAS a cardinality,
> > but nobody knows what that cardinality is.
>
> 2^aleph_0 is a cardinal number,
No, it isn't.
> since cardinal exponentiation of two
> cardinal numbers is a cardinal number (just like the addition of two
> integers is an integer, etc.). What you mean is: you can't know
> whether it equals aleph_1 in the absence of CH.
Or whether it equals anything else either.
More to the point, it is PROVABLE that 2^aleph_0 is NOT
any PARTICULAR cardinal number, since you can model it
with any of many DIFFERENT cardinal numbers.
More to the point, though, CARDINAL NUMBERS DON'T EXIST.
When we want to pretend that they do, we just conventionally
take initial ordinals as cardinals. Given that everybody
knows that this is what is happening, allegations like
"2^aleph_0 is a cardinal number" are just fatuous.
Ordinal arithmetic is what's relevant. Cardinals are
a VERY thin branch of what's actually going on and NOT
an important one.
>
> > They just know that it has to be bigger than
> > aleph_0.
>
> Yes. And also that it is at least as big as aleph_1.
> http://us.metamath.org/mpegif/aleph1.html
> and thus strictly bigger than aleph_0 by
> http://us.metamath.org/mpegif/alephordi.html
>
> > You can't prove a definition.
> >
> > What he *needed* to be proving was the general result
> > that there cannot be a bijection between a set and
> > its powerset.
>
> Already done.
Of course.
But my point is simply that it is not
what he was focusing on.
> Cantor's theorem:
> http://us.metamath.org/mpegif/canth2.html
> which implies no equinumerosity:
> http://us.metamath.org/mpegif/sdomnen.html
> which implies no bijection:
> http://us.metamath.org/mpegif/bren.html
Please note the PRIOR occurrence of the word
"Cantor's" in the title of the thread. OF COURSE
it's all already been proven. The point was that it
had not yet been properly FOCUSED ON by the person
initiating this inquiry!
Virgil
1931 is when, not where. I need a reference to _where_ Godel says it,
unless you have a time machine to take me back to when he said it.
A URL would be good.
Mike Oliver
> Norman Megill <n...@nospam.see.signature.domain.invalid> wrote in message news:<Fe6dnXGLUO_...@rcn.net>...
>
>>George Greene wrote:
>>
>> > Robin Chapman wrote
>> >
>> >>Surely a more important result than the uncountability of R
>> >>is that R has cardinality 2^aleph_0.
>> >
>> > That is a *definition*, NOT a "result".
>>
>>2^aleph_0 is not defined as the cardinality of R.
>
>
> Come on. I'm on YOUR side.
> The relevant point here is not so much that 2^aleph_0 "is not
> defined as the cardinality of R" as it is that 2^aleph_0 IS NOT
> the cardinality of R. My point was that whatever it is, it is
> in virtue of DEFINITIONS and not of more complicated considerations.
> Cardinality in the ZFC realm is defined in terms of bijections.
> BY DEFINITION, two sets have the same cardinality if a bijection
> exists between them. You can also by definition get cardinalities
> being < or > on the basis of the existence of injections or surjections.
> ALL OF THESE ARE DEFINITIONS AND NOT theorems. That was the point.
I don't exactly get what you're saying here (just for a change) but
it does appear that you've missed NM's point. It's not a matter
of definition that there's a bijection between R (defined, say,
by equivalence classes of Cauchy sequences) and 2^aleph_0 (defined
as the set of functions from {0,1} into the natural numbers). It's
not a *hard* theorem, but not quite as trivial as one might think,
especially if your goal is to give a complete formal proof.
Mike Oliver
> and 2^aleph_0 (defined
> as the set of functions from {0,1} into the natural numbers).
Oops! "...from the natural numbers into {0,1}", of course.
Norman Megill
>Norman Megill wrote:
> The relevant operator in the sentence we were arguing about was
> ^,
> which is NOT limited in application to cardinals.
> It takes sets generally.
Some books define a specific operation ^ : Card X. Card --> Card, which
does not take sets generally. Other books just refer to the cardinality
of the set of maps from exponent to base, with any sets as arguments.
To have a meaningful discussion we should agree on a common starting
point. What book do you prefer to use as a reference?
>> That this specific instance of cardinal exponentiation
>>evaluates to the cardinality as R is a somewhat difficult proof, and
>>I haven't worked it out formally yet.
>
> Neither has anyone else, nor will they ever, since it's already
> been proven that ZFC does NOT impute a unique cardinality to 2^aleph_0.
Textbook proofs that that R has cardinality 2^aleph_0 are given in many
places, e.g. Jech _Set Theory_ p. 31. Are you saying the result of
these proofs does not follow from the ZFC axioms?
Robert Low
Norman Megill <n...@nospam.see.signature.domain.invalid> wrote:
> > Neither has anyone else, nor will they ever, since it's already
> > been proven that ZFC does NOT impute a unique cardinality to 2^aleph_0.
>Textbook proofs that that R has cardinality 2^aleph_0 are given in many
>places, e.g. Jech _Set Theory_ p. 31. Are you saying the result of
>these proofs does not follow from the ZFC axioms?
I think he might be alluding to ZFC having a countable
model. Unless I'm getting things all jumbled up (always
a possibility) the first order axioms for the reals
have a countable model within a countable model of ZFC,
though there is no internal bijection of the reals
with the integers.
Barb Knox
"|-|erc" <sp...@fodder.abc> wrote:
Of course he can, but I expect he's decided that trying to have a
mathematical conversation with you is a lost cause.
With "real" we know (because we can prove) that every infinite sequence of
decimal digits represents a unique real. So since the diagonal is clearly
an infinite sequence of decimal digits, it too represents some real (which
by the definition of the diagonal is not in the hypothesised list).
But with "rational", not every infinite sequence of decimal digits
represents some rational (e.g., all the non-repeating sequences, which
represent non-rational reals). So the diagonal sequence need not represent
a rational, so the attempted proof fails. Happy now?
>> > > 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.
>> >
>> >
>> > The concept of unique number is wrong.
Eh? Are you saying that there isn't a unique diagonal (which is true but
irrelevant, since any diagonal will suffice -- see following), or that a
diagonal does not represent a unique real number (which is false), or what?
>> Ok. Then you are objecting to something prior to the proof. So why
>> bother discussing Cantor's proof at all?
>
>he's the one who claims anti-diag is unique.
No he isn't. There are plenty of different ways to define the diagonal.
Indeed, the general definition of making the diagonal different and non-0
and non-9 at each digit position (but not caring which of the 7 remaining
candidates are used for each digit position) allows lots of different
diagonals, ALL of which will not be in the hypothesised list.
>Here's an infnite list of reals
>
>0.0xxxxxx..
>0.1xxxxxx..
>0.2xxxxxx..
>0.0xxxxxxx..
>0.3xxxxxx..
>0.5xxxxxx..
>0.8xxxxxx..
>0.1xxxxxxx..
>0.2xxxxxxxx..
>0.0xxxxxxx..
>0.1xxxxxxxx..
>
>As you can see, 0.0xxxx.. appears repeatedly, so 0.0 is covered infinitely
>many times
>0.1xxxxx.. appears an infinite number of times.
>
>It doesn't matter what the digits the are, they are all present.
>
>0.abcxxx.. is present for EVERY a, b and c.
>
>0.abcdefghijklmnopqrstuvwxyz...... is ON THE LIST for ALL values of a, b,
>c, d, e, ... z
Correct. For any FINITE sequence of digits, that sequence can be in the
list. Note that these finite sequences all represent rationals (and not
even all the rationals at that, e.g. .3333...). No-one disagrees that the
rationals are enumerable (and even computably so); the issue is only with
the NON-rational reals.
>by extension every digit combination is present.
Bzzzzt. You can NOT just casually make such a leap from finite to infinite
sequences. As I've tried to tell you before, it is NOT the case that just
because something is true for every finite sequence then it is true for
infinite sequences too.
For an obvious example (which for some unknown reason you seem to fail to
understand), the predicate "is a finite sequence" is clearly true for all
finite sequences no matter how long, but is false for all infinite sequences.
If you can sensibly refute that example (which of course you can't) then you
might have something worth talking about.
>You claim there is ONE digit that is different, but that digit CANNOT appear
>at digit position 1.
>
>0.1xxxx
>0.2xxxx
>0.3xxxx
>
>these are all on the list of computable reals.
Not so. For example, Chaitin's omega begins with 0.0... or 0.1..., but it
is not computable.
And you still have a basic confusion about Cantor's construction. It does
NOT deal with computability in any form. The hypothesised list need not be
computable, it just needs to exist all. So Cantor's result is even stronger
than you seem to suppose.
A related result (which you also fail to accept) is that the full list of
COMPUTABLE reals (which is countably infinite) is not itself COMPUTABLE
(i.e. recursively enumerable). But that's another thread...
[snip the rest, based as it is on the above false claim about 0.1xxxx etc.]
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
Ross A. Finlayson
I apply your argument to the Equivalency Function.
For EF, f(1) = EF(0)=0, f(2)=EF(1), f(3)=EF(2), etcetera.
g(1) = 1
h(1) = 2
g(2) = 4/3
h(2) = 5/3
g(3) = 13/9
h(3) = 14/9
g(4) = 40/27
h(4) = 41/27
Etcetera.
None of those values except g(1) is an element of the range the NU/EF,
where the range is the unit interval of the reals. You can scale the
function by two thus that the range is [0,2], and the sequences g and
h would be mostly unchanged.
You construct these convergent sequences, they're meaningless.
They're arbitrary transformations to construct a convergent sequence,
where you have the alternate case to skip over values of f in the
diminishing interval. You could start at 0 and 1 instead of 1 and 2.
Then, g(2) and h(2) are undefined. If they weren't then:
g(2) = 1/3
h(2) = 2/3
g(3) = 4/9
h(3) = 5/9
and the sequences g and h converge to 1/2, with values
g(i+1) = floor(3^i/2)/3^i
h(i+1) = ceil(3^i/2)/3^i
EF takes advantage of the limit approximation of the result to show
that over the domain, N, that the upper bound of the range converges
to one. That means that at some point EF(x) is less than one half,
and at another greater than one half, and even at some value equal to
one half.
When it reaches near one half your sequences will be very near one
half. Then, for that x approximately equal to "N/2", then g(i+1) will
be _less_ than g(i), and h(i+1) _greater_ than h(i), breaking the
monotony.
Your argument is similar, in some ways, to Cantor's nested intervals
result, demanding a straight line function.
My opinion is that you can't claim that a small interval centered on
one half does not contain the same reals as those from the unit
interval, N is an infinite set.
NU/EF has a minimum value of zero and a maximum value of one, the
limit of the difference between each EF(n) and EF(n+1) is zero. EF(1)
is basically dx.
These aren't finite sets under consideration. A constructive proof is
that you can order a set thus that no element need be selected twice,
and then just iterate pairing, because they're infinite sets and there
is always one more. The pairing of values is a non-halting process
because the sets are each infinite.
Using pencil on paper, draw a straight line from zero to one. You
have just marked each of the real points from zero to one in ascending
order.
Norm, infinite sets are equivalent. The purpose of the powerset
result is to spur us to understand how that is so, and it leads to
everything in the void.
Warm regards,
Ross F.
Josh Purinton
Not in ZFC.
Sadly, Norm's prediction that "the skeptics won't put in the minimal
effort needed to identify where they claim the formal proof is wrong"
has been accurate so far.
It seems likely that computer-verified proofs will eventually be quite
common. When that day comes, the "skeptics" -- in order to avoid being
ignored -- will have to produce (or at least critique) formal proofs
that have been verified by a widely-accepted proof checking program
using standard axioms and definitions.
As Norm wrote in _ Metamath: A Language for Computer Mathematics _
<http://us.metamath.org/#book>:
Mathematicians sometimes have to put up with the annoyance of cranks
who lack a fundamental understanding of mathematics but insist that
their "proofs" of, say, Fermat's Last Theorem be taken seriously. I
think part of the problem is that these people are misled by informal
mathematical language, treating it as if they were reading ordinary
expository English and failing to appreciate the implicit underlying
rigor. [...] With easily accessible computer-based abstract
mathematics, a mathematician could say to a crank, "don't bother me
until you've demonstrated your claim on the computer!"
--
Josh Purinton
Russell Easterly
"Mike Oliver" <mike_...@verizon.net> wrote in message
news:2u7569F...@uni-berlin.de...
We can make it so only one rational is "pushed ahead" in the list.
We have to define how the diagonal number, DN, is formed.
Let's say DN(n) = . 5 if the nth digit of LIST(n) is .4 else DN(n) = .4
Assume we have a method of assigning a natural number to every rational.
(Lots of such methods exist.)
We want the DN to be a rational number like, say, .4444444.....
If the nth digit of LIST(n) is .4 then we swap it with the next number in
the list
that does not have .4 in the nth position.
There is only one chance in ten that the nth digit of LIST(n) is .4, so we
won't have to swap very many times (well maybe infinitely many times).
We can keep track of the swaps so that we can still assign a
natural number to every rational.
(The position of a rational is its original position plus or minus the
number of
positions it moves when swapped. Most positions won't be swapped.)
We know that .444... is in the original list.
Of course, we will have to push .444.. ahead forever because there
is no position in the list we can place it.
I think all of the rest of the rationals "fall out" somewhere along the way.
So, we end up with a listing of the rationals missing only the DN.
Russell
- 2 many 2 count
|-|erc
> On Tue, 26 Oct 2004 09:06:20 GMT, |-|erc wrote:
> > "Dave Seaman" <dse...@no.such.host> wrote in
>
> > *a version of*
>
> >> The diagonal argument depends on the least upper bound property of the
> >> real numbers. The diagonal argument produces a decimal digit string,
> >> which is associated with a certain infinite series. The partial sums of
> >> that series form a set of real numbers that is nonempty and bounded
> >> above. The least upper bound of that set is the required number.
> >>
> >> The same argument does not work when applied to the rationals, since the
> >> rationals do not satisfy the LUB property.
> >>
> >> And, by the way, there is nothing circular about the argument that if the
> >> original list contains all of the rational numbers, then the number
> >> produced by the diagonal argument, which is necessarily different from
> >> any number in the list, must therefore be irrational.
>
> > Diagonalisation is a valid technique because diagonalisation is a valid technique.
> > I'm getting used to this argument!
>
> The diagonal argument works because, given a mapping f: N -> R, the
> argument produces a number x whose n'th digit differs from the n'th digit
> of f(n) for each n. And since x is chosen to avoid dual-representation
> problems, it follows that x is not in the range of f.
if such an x was possible, which it isn't.
>
> > Such a proof gives no reassurance of the diagonalisation technique, which was the whole point
> > of the OP. Assume diagonalisation may not work, then consider the example of rationals.
>
> > 1 Start with a complete list of rationals
>
> > 2 Order the list to have diagonal 0.12345678901234567890...
> > Every digit is present on the diag so no matter what digits your rational has it can
> > slide up or down the list until it fits.
>
> Consider the number 0.098765432109876543210987654321.... It's a rational
> number. Where does it go in your list?
Why look for an error in this demonstration when the number
> >> produced by the diagonal argument, which is necessarily different from
> >> any number in the list, must therefore be irrational.
>
> > 3 Make an anti-diag, this has 10(n) repeating digits so it is rational but is not on the list.
>
> So, your method works because it works? Very clever.
theorems relate to other theorems in a directed acyclic graph, not a heirarchy, try some different routes.
Herc
|-|erc
>
> But with "rational", not every infinite sequence of decimal digits
> represents some rational (e.g., all the non-repeating sequences, which
> represent non-rational reals). So the diagonal sequence need not represent
> a rational, so the attempted proof fails. Happy now?
You and Dave COMPLETELY missed the point of the question.
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),
Herc
Dave Seaman
> "Dave Seaman" <dse...@no.such.host> wrote in
>> On Tue, 26 Oct 2004 09:06:20 GMT, |-|erc wrote:
>> > "Dave Seaman" <dse...@no.such.host> wrote in
>> > *a version of*
>> >> The diagonal argument depends on the least upper bound property of the
>> >> real numbers. The diagonal argument produces a decimal digit string,
>> >> which is associated with a certain infinite series. The partial sums of
>> >> that series form a set of real numbers that is nonempty and bounded
>> >> above. The least upper bound of that set is the required number.
>> >> The same argument does not work when applied to the rationals, since the
>> >> rationals do not satisfy the LUB property.
>> >> And, by the way, there is nothing circular about the argument that if the
>> >> original list contains all of the rational numbers, then the number
>> >> produced by the diagonal argument, which is necessarily different from
>> >> any number in the list, must therefore be irrational.
>> > Diagonalisation is a valid technique because diagonalisation is a valid technique.
>> > I'm getting used to this argument!
>> The diagonal argument works because, given a mapping f: N -> R, the
>> argument produces a number x whose n'th digit differs from the n'th digit
>> of f(n) for each n. And since x is chosen to avoid dual-representation
>> problems, it follows that x is not in the range of f.
> if such an x was possible, which it isn't.
Why not? Do you mean the diagonal fails to produce a decimal digit
string, or the decimal digit string produced by the diagonal process
fails to specify a real number?
Which is it? In either case, you're wrong, but I can't tell where your
error lies without further information.
>> > Such a proof gives no reassurance of the diagonalisation technique, which was the whole point
>> > of the OP. Assume diagonalisation may not work, then consider the example of rationals.
>> > 1 Start with a complete list of rationals
>> > 2 Order the list to have diagonal 0.12345678901234567890...
>> > Every digit is present on the diag so no matter what digits your rational has it can
>> > slide up or down the list until it fits.
>> Consider the number 0.098765432109876543210987654321.... It's a rational
>> number. Where does it go in your list?
> Why look for an error in this demonstration when the number
>> >> produced by the diagonal argument, which is necessarily different from
>> >> any number in the list, must therefore be irrational.
Would you have believed me if I had claimed that there must be an error
somewhere in your argument without actually pointing it out? That is
your tactic, not mine.
>> > 3 Make an anti-diag, this has 10(n) repeating digits so it is rational but is not on the list.
>> So, your method works because it works? Very clever.
> theorems relate to other theorems in a directed acyclic graph, not a heirarchy, try some different routes.
You are confused. The person who needs to try again is the person whose
argument has failed. That would be you, since your attempted list of
rationals is not complete.
Dave Seaman
You have completely missed the point of my answer. Here it is again,
from the other post:
>> The diagonal argument works because, given a mapping f: N -> R, the
>> argument produces a number x whose n'th digit differs from the n'th digit
>> of f(n) for each n. And since x is chosen to avoid dual-representation
>> problems, it follows that x is not in the range of f.
If you think this doesn't work, then you need to explain exactly where
you think the problem is. Just waving your hands and claiming no such x
exists doesn't cut it. That paragraph explains precisely why x exists
and is not in the range of f.
So the answer to your question is: the part of Cantor's proof that shows
x is not in ran(f) is the part that prevents x from being in Q if
Q \subseteq ran(f). Just apply the definition of "subset". That is not
a circular argument.