Problem with Cantor's diagonal argument
Henry
diagonal argument which he used to 'prove' that the decimals between 0
and 1 are uncountable. What's even worse, he used that to say that the
infinity of the decimals is larger than the infinity of the integers
(but that's another matter). What I would like to know is how could he
establish the diagonal argument on a list that I'm not sure can be
created at all. How can someone create a list like:
1 <--> .2332245.....
2 <--> .4898495.....
The basic question here is how can you assign the number 1 to a
number that has an infinite number of digits. In the example above,
what is the number that 1 'points' to? Since you can keep adding an
infinite number of digits after the decimal point how can you say that
1 is pointing to a specific number? A possible list would be something
like:
1 <--> .25
2 <--> .50
Here the number 1 is assigned to the specific number .25, not to an
arbitrary number that has an infinite number of digits after the
decimal point.
Given these questions, how can the proof itself hold true. I don't
see that its initial premise makes logical sense. What's also
confusing is saying that if you can't use the integers to count the
decimals that kind of assumes that you'll run out of integers (you'll
reach the largest integer ever) which makes no sense. Comments
please!!
In an alternate but related topic, I think it is absurd to talk
about an infinite being larger than another. That just does not make
sense at all. Infinity doesn't have an end so:
Inf + Inf = Inf
Inf * Inf = Inf and so on.
Any comments are welcome
Andy Berget
>
> In an alternate but related topic, I think it is absurd to talk
> about an infinite being larger than another. That just does not make
> sense at all. Infinity doesn't have an end so:
>
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
certainly e^x tends to infinity much faster than x does. this is the
idea behind l'hopital's rule and the reason one thinks that lim
n^4/(n^5+1) goes to zero instead of inf/inf. you appear to be thinking
of infinity more as a quantity opposed to a notion. things get
arbitrarily large, the notion of infinity is something like, you give me
any number M and I'll give you an M' larger than M.
Mike Oliver
> Any comments are welcome
Don't worry; you'll get plenty. Though one is never sure
quite why.
Keith Keller
avil...@email.msn.com (Henry) writes:
> While reading Paul Erdos' story in "My brain is open" I found Cantor's
> diagonal argument which he used to 'prove' that the decimals between 0
> and 1 are uncountable. What's even worse, he used that to say that the
> infinity of the decimals is larger than the infinity of the integers
> (but that's another matter). What I would like to know is how could he
> establish the diagonal argument on a list that I'm not sure can be
> created at all.
Isn't that the point? ;-)
> How can someone create a list like:
>
> 1 <--> .2332245.....
> 2 <--> .4898495.....
>
> The basic question here is how can you assign the number 1 to a
> number that has an infinite number of digits.
Why do the digits matter? The number exists, regardless of the digits.
Consider sqrt(2): its decimal representation does not terminate in 0s,
but it still exists. Even the representation of 1/3 doesn't terminate,
but surely it exists.
> In the example above,
> what is the number that 1 'points' to? Since you can keep adding an
> infinite number of digits after the decimal point how can you say that
> 1 is pointing to a specific number? A possible list would be something
> like:
>
> 1 <--> .25
> 2 <--> .50
>
> Here the number 1 is assigned to the specific number .25, not to an
> arbitrary number that has an infinite number of digits after the
> decimal point.
Actually, 1 is mapped to the number .250000000000... in this case.
So does 1/4 now not exist, too?
> Given these questions, how can the proof itself hold true. I don't
> see that its initial premise makes logical sense. What's also
> confusing is saying that if you can't use the integers to count the
> decimals that kind of assumes that you'll run out of integers (you'll
> reach the largest integer ever) which makes no sense. Comments
> please!!
You're not *counting* them, you're mapping them. The theorem is that
you can never map every integer uniquely to every real number. It
has nothing to do with counting numbers at all.
The main confusion of the above is that numbers exist independent of
how we choose to represent them.
> In an alternate but related topic, I think it is absurd to talk
> about an infinite being larger than another. That just does not make
> sense at all. Infinity doesn't have an end so:
>
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
If the above makes sense, then the notion of one ''infinity'' being
larger than another should also make sense. Also, remember that
infinity isn't a number, and doesn't really exist at all, so infinity
+ infinity doesn't exist, either. Aggregating sets is a different
matter, which isn't relevant to this thread yet.
Good luck grasping infinity--it's weird stuff.
--keith
--
kke...@speakeasy.net
public key: http://wombat.san-francisco.ca.us/kkeller/public_key
alt.os.linux.slackware FAQ: http://wombat.san-francisco.ca.us/perl/fom
Dudley Brooks
>
> The basic question here is how can you assign the number 1 to a
> number that has an infinite number of digits. In the example above,
> what is the number that 1 'points' to? Since you can keep adding an
> infinite number of digits after the decimal point how can you say that
> 1 is pointing to a specific number?
This is somewhat irrelevant because of the comment later on, but an
infinite decimal is considered to be clearly specified if there is a
rule for generating it, so that you always "know" what the next decimal
is going to be, whether you take the time to write it or not. There are
several ways to do this. For example, (1) the decimal is a repeating
decimal, equivalent to a rational number: 0.3333333... = 1/3,
0.714285714285714285... = 5/7, etc. However, another proof by Cantor
shows that if *all* the decimals were of this form, the pairing *would*
be possible, because the set of rationals has the same cardinality as
the set of natural numbers. You can also get irrational numbers by
rules. For example, it can be shown that
0.11010010001000010000010000001..., a clearly specified number (rule:
"no 0, one 0, two 0's, etc."), is irrational. Or you could put 1 <-->
all the decimals digits of pi, 2 <--> every 2nd decimal digit of pi, 3
<--> every 3rd decimal digit of pi, etc. And there are rules for
calculating the decimals of pi, so pi (and the above-described numbers
derived from it) are considered to be precisely defined. Of course, in
the latter case there would clearly still be a one-to-one
correspondence, and in fact a similar theorem in the Theory of
Computation says that there are only a countable number of possible
rules.)
(By the way, some or even all of the decimals in the correspondence
could be of the type you prefer -- that doesn't affect Cantor's proof at
all, since the proof doesn't care what the decimals in any real table
actually look like. Any decimal of the type you prefer can be trivially
made infinite by putting all 0's after it.)
Skipping ahead to your third point:
> What's also
> confusing is saying that if you can't use the integers to count the
> decimals that kind of assumes that you'll run out of integers (you'll
> reach the largest integer ever) which makes no sense.
When you count up to a *finite* number, you count (in theory) until you
run out. By I say "in theory" because even if the number is not
infinite, but just merely "big" you don't really count until you run out
-- you wouldn't have time. What Cantor did (and actually Galileo did it
before him, and probably even Archimedes -- some historian of
mathematics correct me if I am mistaken) was to generalize and say that
what you are really doing when you count (or compare two sets) is making
a one-to-one correspondence between them, and (as in the first
paragraph) if there is a convincing *rule* for making that comparison,
you consider that the comparison has been made, whether you take the
time to keep going or not. So for example when Galileo, long before
Cantor, showed that the number of even integers is *not* half the number
of all integers, as people naively thought, but in fact the *same* as
the number of all integers, he did so by giving the rule "pair each
integer to its double". If you really had to *keep* counting, that
would be like saying "OK, you've counted up to 10, which corresponds to
20, but how do I know there's a number which corresponds to 11?"
"That's easy, 2*11 = 22 corresponds to 11." "OK, but how do I know
there's a number that corresponds, say, to 197?" "That's easy, 2*197
corresponds to 197." "OK, but how do I know ..." "It doesn't matter
what number you say, the number that corresponds to n is 2n." So
therefore we *know* that the number of even integers is the same as the
number of all integers. Galileo did this for various other sets and
concluded, as you do, that any two infinite sets have the same
cardinality. However, he was incorrect, because he failed to analyze
(or didn't know how to analyze) the cases in which this is *not* true.
Now the crucial point. Here's what Cantor is actually saying (or,
rather, *how* he is actually saying it):
He's *not* saying that you'll run out of integers before you run out of
real numbers (infinite decimals) -- obviously you never run out of
either. Rather, he's saying, What would it mean if the set of reals
*did* have the same cardinality as the set of integers? It would mean
that we *could* (i.e. hypothetically) give an (infinitely long) table
showing the correspondence between the two. But in fact, no matter
*what* table someone presents me *claiming* that it shows a
correspondence between the integers and *all* (emphasis on "all") the
reals, I can always come up with a real number which I can *prove* is
not on the table! (And again, that real number is specified by a
precise *rule*, so even though I don't have the time to write out all
its decimals, it's considered to be clearly defined -- I can keep
writing its decimals as long as I want to.) So in other words, any time
you claim to have counted all the real numbers, I can always come up
with one you missed.
A further point (without any details)
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
To show that, you first have to define what it means to add or to
multiply two infinite numbers. Cantor showed that there was a logical
way to extend arithmetic to transfinite numbers, then showed (where I'm
using a0 as shorthand for "aleph_nought", the *first* transfinite
number, the number of all integers):
a0 + finite = a0
a0 + a0 = a0
a0 * finite = a0
a0 * a0 = a0
finite ^ a0 = a0
a0 ^ finite = a0
just as you've suggested.
But he then showed
a0 ^ a0 > a0
He did this by showing how to define a set which clearly and
meaninfgully had the size a0 ^ a0, and then showing that, again, that
set could not be put into one-to-one correspondence with a0 -- again, no
matter how you tried to do it, you would always wind up leaving out some
element of the larger set.
Hope this clarified it for you. (And I just realized that this is
probably all in a FAQ anyway. Sorry. Too many years of being a tutor;
I *had* to try explaining it!)
Seth Dutter
Now suppose that you have 2 collections of objects and you want to have
some way to tell whether there are equal amounts in each collection. The
most obvious way to do so is to create pairings, take one object from
each collection and pair it with another, if there is some way to pair
them up then both collections are of the same size.
Therefore two sets are defined to be the same size or rather they have
the same cardinality if there is some way to pair them off, where one
from one set corresponds to exactly one in another. For finite sets this
completely obvious, and extending it to infinite sets is a very natural
thing to do. Cantor's argument then proceeds that if they are of the
same size there must be some way to pair each element of the integers
with all the numbers between 0 and 1 then this list exists and it seems
as though you are familiar with the rest of the proof. And you are
absolutely right there is no way to make such a list which includes all
the numbers and that is why they are of different sizes.
Examining the other issue you say that infinite+infinite=infinite so it
doesn't make sense for there to be different sizes of infinity. Lets
apply this same logic elsewhere. finite+finite=finite, by your logic it
wouldn't make sense for there to be different sizes of finite things, so
3 is just as big as 500 which is just as big as a million. Hopefully you
see that logic doesn't quite work. Hope this helps.
-Seth
Mike Oliver
> To show that, you first have to define what it means to add or to
> multiply two infinite numbers. Cantor showed that there was a logical
> way to extend arithmetic to transfinite numbers, then showed (where I'm
> using a0 as shorthand for "aleph_nought", the *first* transfinite
> number, the number of all integers):
>
> a0 + finite = a0
> a0 + a0 = a0
> a0 * finite = a0
> a0 * a0 = a0
> finite ^ a0 = a0
> a0 ^ finite = a0
Not quite right. 2^Aleph_0 > Aleph_0. In fact 2^Aleph_0 is the
cardinality of the continuum.
Doug Norris
>What I would like to know is how could he
>establish the diagonal argument on a list that I'm not sure can be
>created at all.
He gives an algorithm for constructing it; therefore, you, I, or anyone
else that's interested can construct it. Therefore, it can be created.
Doug
ma...@mimosa.csv.warwick.ac.uk
>about an infinite being larger than another. That just does not make
>sense at all. Infinity doesn't have an end so:
>
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
>
>
> Any comments are welcome
I think it is absurd (and also arrogant) to take one brief look at something
which you know nothing about, and then to call it absurd. But you are by
no means alone in doing that!
Derek Holt.
Nico Benschop
> inf * inf = inf [2]
> and so on. ..[3]
>
> Any comments are welcome
Indeed, counting the continuum sounds somehow contradictory,
and by Cantor 2^N ('the continuum') is 'uncountable' indeed...
Re[1][2]: True,
But [3]: inf ^ inf > inf, by Cantor's diagonal argument.
First notice the reason why [1] and [2] hold: what you call 'inf' is
the 'linear' infinity of the integers, or Peano's set of naturals N,
generated by one generator, the number 1, under addition, so:
^^^^^^^^^^^^^ ^^^^^^^^^^^^^^
N(+)={+1}* where the star means repetition (iteration) ad infinitum.
Now [2], which you can imagine in the XY plane, with inf along the
two orthogonal axes X and Y, counting only the (discrete) pos.integer
positions along them, and all the grid points in the positive quarter
(quadrant) of the plane, of which there are inf x inf = (inf)^2.
That should be essentially more than Inf, you'd say...
But no, the clue is that all grid points have a simple 'quasi-linear'
ordering, starting at the origin, zig-zagging along increasingly
(linear growing) longer diagonals:
|
9 .
|
3 8 .
|
2 4 7 .
|
0--1--5--6--+--+--
So you see, this quadratic infinity is mappable 1-1 to a linear one.
This holds by extension also for higher dimensions D>2: (inf)^D = inf,
that is, for any *finite* D, as you can hopefully imagine.
Notice that this still has little to do with arithmetic, but with
a way of 'linear' arrangemnt or process of 'generating' all objects.
Now [3]: Cantors 2 ^ inf, to start with. This you can imagine as all
infinitely long sequences over an alphabet A of 2 symbols, say A={0,1}
They can represent all reals on interval [0,1) by 0/1 strings right
of the binary point. But this arithmetic interpretation is NOT
necessary, it is just a matter of 'counting' strings, and in fact
trying to find a 'linear' arrangement for them to be all counted.
Now Cantors argument is that, unlike the XY plane for inf^2, or
hypercube inf^D for D>2, this is essentially not possible: viz. a
single generator, so |A|=1, can NOT model the generation process
for all countably long (infinite length) strings A* over A if |A|>1.
His diagonal argument to show this is very simple, and again has
little to do with reals on [0,1) - just being a special interpretation,
but everything with strings over some alphabet A of at least 2 symbols.
In fact he shows that whatever list of (binary) strings of lentgh k
you take (for finite k there are 2^k): any square k x k table of
such strings has a diagonal that is a string (length k) which is
not in that listing if you 'swap bitwise' all bits in the diagonal.
For k=6 there are 2^6= 64 binary strings, and take any selection of 6:
0 1 1 1 0 0 diagonal: 0 1 0 0 0 1 (left top to right bottom)
1 1 0 1 0 1 swapped: 1 0 1 1 1 0 is not a row in this 6 x 6 table,
0 1 0 1 0 1 because it differs in each position
1 0 1 0 1 0 from each row, at that position!
0 0 0 0 0 0
1 1 1 0 1 1
This holds for finite k, no matter how large, and in fact:
-------- _independent_ of length k ------
hence (by some axiom) also for infinite k,
called omega w, the countable ('linear') infinite of Peano's naturals,
or the integers, including the negative, which also are countable.
So for any infinite w x w binary table the Cantor-diagonal is not in
that table. This 'leap-of-faith', about talking of an inf x inf square
table "existing" is really about the impossibility of a linear ordering
of all |2^w| w_long binary strings. That's all: a string counting
story, not an arithmetic problem at all... the 'reals' came later.
So notice: Cantors table is _square_ (w x w) to have a diagonal
at all, and his argument also holds for any finite table: k < 2^k,
and essentially by the 'missing diagonal' (anti-closure: not ALL)
argument then also for length k = linear (countable) infinite.
And,ever since Cantor, infinite stringset |A*| is called 'uncountable'
for |A|>1, so an aphabet of at least 2 symbols. I hope this helps...
So exponentiation (^) is _really_ something else, compared with (*)(+)
In fact, while arithmetic (+) and (*) are both associative and
commutative operations, and although (^) is repeated (*), which itself
is repeated (+), note that (^) is neither associative nor commutative!
-- NB - http://home.iae.nl/users/benschop/cantor.htm
http://home.iae.nl/users/benschop/sgrp-flt.htm
Dudley Brooks
>
> Dudley Brooks wrote:
>
> > finite ^ a0 = a0
> > a0 ^ finite = a0
>
> Not quite right. 2^Aleph_0 > Aleph_0. In fact 2^Aleph_0 is the
> cardinality of the continuum.
Right you are. Moral: Don't do math late at night.
Nico Benschop
Should Henry be punished for his trying to understand ?
He seems to me a motivated student, don't cut him down for
his 'I think it is absurd' remark on comparing infinities.
Have you not wondered, some time long ago?
"It is remarkable that curiosity has survived formal education."
(roughly quoted, from A.Einstein)
-- NB
ma...@mimosa.csv.warwick.ac.uk
I am sorry but my opinion remains unchanged. I honestly cannot understand
how anyone can spend an hour or so reading about a topic that has been
thought about and studied in detail for more than a hundred a years by some
of the keenest minds on the planet, and then assert that it is all rubbish.
That applies not just to mathematics, but to any serious object of study,
whether it is relativity, evolution, philosophy, art, music.
The appropriate response is to say "I do not understand this", or (in the
case of art or music), "I am able to appreciating this", not "This is all
junk". If you were really trying to understand something, you would hardly
say "This is absurd".
Derek Holt.
Dave Seaman
Dudley Brooks <voi...@best.com> wrote:
>
>This is somewhat irrelevant because of the comment later on, but an
>infinite decimal is considered to be clearly specified if there is a
>rule for generating it, so that you always "know" what the next decimal
>is going to be, whether you take the time to write it or not. There are
>several ways to do this. For example, (1) the decimal is a repeating
>decimal, equivalent to a rational number: 0.3333333... = 1/3,
That can't be right, because there are only countably many "rules" that
can be formulated using finite strings of characters from a finite
alphabet. Yet, there are uncountably many real numbers. Therefore, it
follows that almost all of the real numbers have no rules associated with
them whatsoever.
--
Dave Seaman dse...@purdue.edu
Amnesty International says Mumia Abu-Jamal decision falls short of justice.
<http://www.amnestyusa.org/news/2001/usa12192001.html>
Dave Seaman
Henry <avil...@email.msn.com> wrote:
>While reading Paul Erdos' story in "My brain is open" I found Cantor's
>diagonal argument which he used to 'prove' that the decimals between 0
>and 1 are uncountable. What's even worse, he used that to say that the
>infinity of the decimals is larger than the infinity of the integers
>(but that's another matter).
Why is that "even worse"? Both statements mean precisely the same thing.
"Uncountable" means "larger than the infinity of the integers", in the
sense that there is no mapping from the integers *onto* the given set.
>What I would like to know is how could he
>establish the diagonal argument on a list that I'm not sure can be
>created at all. How can someone create a list like:
We don't have to create the list. The list is given to us in the
hypothesis of the theorem. In geometry, we accept that infinitely long
lines exist, even though we can never finish drawing them. In analysis,
we accept that real numbers exist, even though we can never finish
writing them down.
The proof shows that if we have any list of reals, whether describable in
finite terms or not, there are real numbers that are not in the list.
> Given these questions, how can the proof itself hold true. I don't
>see that its initial premise makes logical sense. What's also
>confusing is saying that if you can't use the integers to count the
>decimals that kind of assumes that you'll run out of integers (you'll
>reach the largest integer ever) which makes no sense. Comments
>please!!
No, there is no assumption that you will run out of integers. Quite the
opposite, in fact. The theorem says that if f: N -> R is a mapping from
the natural numbers to the reals, then there are real numbers that are
not in the range of f. That's what a "list" really is: a mapping
defined on the natural numbers. That means *all* of the natural numbers,
with none left out. The proof shows that no matter how you arrange
things, there will still be some real numbers left unaccounted for.
That's what it means to say that the reals are uncountable.
> In an alternate but related topic, I think it is absurd to talk
>about an infinite being larger than another. That just does not make
>sense at all. Infinity doesn't have an end so:
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
If X and Y are any sets at all (either finite or infinite), then we say X
is larger than Y (actually X has a larger cardinality than Y, or |X| >
|Y|), if there is a way to pair off each member of Y with some member of
X, but there is no way to do this without having members of X left
unaccounted for. Thus, the statement "the reals are uncountable" is
identical to "the reals have a larger cardinality than the integers."
Dale Hurliman
Henry wrote:
> While reading Paul Erdos' story in "My brain is open" I found Cantor's
> diagonal argument which he used to 'prove' that the decimals between 0
> and 1 are uncountable. What's even worse, he used that to say that the
> infinity of the decimals is larger than the infinity of the integers
> (but that's another matter). What I would like to know is how could he
> establish the diagonal argument on a list that I'm not sure can be
> created at all. How can someone create a list like:
>
> 1 <--> .2332245.....
> 2 <--> .4898495.....
>
> The basic question here is how can you assign the number 1 to a
> number that has an infinite number of digits. In the example above,
> what is the number that 1 'points' to? Since you can keep adding an
> infinite number of digits after the decimal point how can you say that
> 1 is pointing to a specific number?
>
<snip>
Cantor's arguement is a kind of _reductio ad absurdum_ arguement. He
says, in essence, "Let us assume one could make a one to one list of the
integers and the corresponding real numbers between 0 and 1. If that
could be done, even then, I can still show that there are more reals in
the range 0-1 than there are integers." And you must grant that that
initial assumption is certainly a liberal assumption. So even granted
such a liberal assumtion there are still more reals than integers.
Therefore our initial liberal assumption must be false. Such a list can
not be made. Therefore, based on the definition of set size (The size
of a set is defined by a one to one correspondence between integers and
set members) there must be more real numbers between 0 and 1 than there
are integers. Q.E.D.
Dale
Henry
> I am sorry but my opinion remains unchanged. I honestly cannot understand
> how anyone can spend an hour or so reading about a topic that has been
> thought about and studied in detail for more than a hundred a years by some
> of the keenest minds on the planet, and then assert that it is all rubbish.
> That applies not just to mathematics, but to any serious object of study,
> whether it is relativity, evolution, philosophy, art, music.
>
Derek, if everyone would think like you do, then there would be no
progress.
For how many years people thought the earth was flat???!!! Is it a sin
to question what's been "studied in detail"? I'm not saying that *I*
will find any new theorems or fix any flaws in Cantor's views. If
people become afraid to ask, question or criticize anything beacuse
it's been accepted by most people then new ideas will never surface
and progress will stall. Sorry if I hurt anyone's feelings by using
the word "absurd".
Arturo Magidin
> Derek, if everyone would think like you do, then there would be no
>progress.
>For how many years people thought the earth was flat???!!!
Bad example. Aristarchus of Samos had already shown the Earth wasn't
flat.
>Is it a sin
>to question what's been "studied in detail"?
You missed Derek Holt's point. Questioning what has been studied in
detail is not a sin. Claiming that, after one hour of thought,
anything you haven't understood is "pure junk" ->is<- one. It's called
arrogance.
Had somebody come along and said "I've thought about the 'flat earth'
thing for five minutes; I think you are all a bunch of idiots! It's
wrong!" ->then<- he is worthy of being laughed at.
>I'm not saying that *I*
>will find any new theorems or fix any flaws in Cantor's views. If
>people become afraid to ask,
The other post didn't ->ask<-. It ->proclaimed<- it all to be junk.
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Randy Poe
>
> While reading Paul Erdos' story in "My brain is open" I found Cantor's
> diagonal argument which he used to 'prove' that the decimals between 0
> and 1 are uncountable. What's even worse, he used that to say that the
> infinity of the decimals is larger than the infinity of the integers
> (but that's another matter). What I would like to know is how could he
> establish the diagonal argument on a list that I'm not sure can be
> created at all. How can someone create a list like:
>
> 1 <--> .2332245.....
> 2 <--> .4898495.....
>
> The basic question here is how can you assign the number 1 to a
> number that has an infinite number of digits.
Why not? Are you saying that a number without a simple
pattern doesn't exist?
The argument starts with a statement like this: Suppose
you have a list of reals, numbered r_1, r_2, r_3, ...
one for every natural number.
You are presumably not talking about rationals, which
have an infinite but repeating sequence of digits. There
are also irrationals that can be constructed with simple
patterns, like
0.12345678910111213141516...
(I'm just writing down 1, 2, 3, ..., 10, 11, 12, ...)
Are you saying this number doesn't exist?
> In the example above,
> what is the number that 1 'points' to? Since you can keep adding an
> infinite number of digits after the decimal point how can you say that
> 1 is pointing to a specific number?
It's "pointing" to whatever particular infinite sequence
you meant. I think you're taking the view that "infinite
means it keeps changing". That's wrong. Pick any real number
and put it in position 1. After you've picked it, you
don't get an infinite number of choices for what's in
position 1. That number has a fixed n-th digit for every
n.
- Randy
ma...@mimosa.csv.warwick.ac.uk
>> I am sorry but my opinion remains unchanged. I honestly cannot understand
>> how anyone can spend an hour or so reading about a topic that has been
>> thought about and studied in detail for more than a hundred a years by some
>> of the keenest minds on the planet, and then assert that it is all rubbish.
>> That applies not just to mathematics, but to any serious object of study,
>> whether it is relativity, evolution, philosophy, art, music.
>>
>
> Derek, if everyone would think like you do, then there would be no
>progress.
>For how many years people thought the earth was flat???!!! Is it a sin
>to question what's been "studied in detail"? I'm not saying that *I*
>will find any new theorems or fix any flaws in Cantor's views. If
>people become afraid to ask, question or criticize anything beacuse
>it's been accepted by most people then new ideas will never surface
>and progress will stall. Sorry if I hurt anyone's feelings by using
>the word "absurd".
OK, I may have over-reacted to your use of "absurd", which I interpreted
as meaning "This stuff is all nonsense". If so I apologise.
But if you did mean to say "This is all nonsense" then I stand by what I
said! You need to really understand something properly before you can
sensibly start to question it.
Derek Holt.
Phil Carmody
>
> While reading Paul Erdos' story in "My brain is open" I found Cantor's
> diagonal argument which he used to 'prove' that the decimals between 0
> and 1 are uncountable. What's even worse, he used that to say that the
> infinity of the decimals is larger than the infinity of the integers
> (but that's another matter). What I would like to know is how could he
> establish the diagonal argument on a list that I'm not sure can be
> created at all.
In that case you've not just misunderstood the proof, but misunderstood
the _method_ of proof being used. Reread, I suggest.
Phil
Dudley Brooks
>
> That can't be right, because there are only countably many "rules" that
> can be formulated using finite strings of characters from a finite
> alphabet. Yet, there are uncountably many real numbers. Therefore, it
> follows that almost all of the real numbers have no rules associated with
> them whatsoever.
Yep. Surprising and unintuitive. This is virtually identical to the
theorem that there are uncountably many (2^aleph_0) functions on the
integers and only countably many algorithms.
I think the unintuitiveness must be because of the discrepancy between
the every-day meaning of "rule" (and what we think a rule ought to be
able to do) and the precisely defined mathematical meaning. I imagine
you could even "specify" one of the real numbers which has no rule by
giving some clever decimal representation of one of the impossible
problems in Theory of Computation, such as the Halting Problem. But
that wouldn't be a rule, because a rule must, as you say, be finite and
definite -- an algorithm, in short, and there's no algorithm for the
Halting Problem.
Or did you mean that it can't be right that you could make your integers
<--> reals table using just rule-defined reals? There's no
contradiction there, because any proposed table (waiting to be
demolished by Cantor's argument) would only have countably many entries
anyway.
> Amnesty International says Mumia Abu-Jamal decision falls short of justice.
Always glad to see a supporter of Amnesty International.
Dudley Brooks
>
> Sorry if I hurt anyone's feelings by using
> the word "absurd".
One obvious question at this point is, Has anyone's posted explanation
been clear enough to anawer your objections? Several people have given
basically the same explanation (the only one there is!), but in very
different words and presupposing very different levels of familiarity
with the subject.
Bob Kolker
Dave Seaman wrote:
> Dave Seaman dse...@purdue.edu
> Amnesty International says Mumia Abu-Jamal decision falls short of justice.
> <http://www.amnestyusa.org/news/2001/usa12192001.html>
We should give that murdering son of a bitch a fair trial before we hang
him.
Bob Kolker
Henry
> Henry wrote:
> >
> > While reading Paul Erdos' story in "My brain is open" I found Cantor's
> > diagonal argument which he used to 'prove' that the decimals between 0
> > and 1 are uncountable. What's even worse, he used that to say that the
> > infinity of the decimals is larger than the infinity of the integers
> > (but that's another matter). What I would like to know is how could he
> > establish the diagonal argument on a list that I'm not sure can be
> > created at all. How can someone create a list like:
> >
> > 1 <--> .2332245.....
> > 2 <--> .4898495.....
> >
> > The basic question here is how can you assign the number 1 to a
> > number that has an infinite number of digits.
>
> Why not? Are you saying that a number without a simple
> pattern doesn't exist?
No. That's not what I'm saying.
>
> The argument starts with a statement like this: Suppose
> you have a list of reals, numbered r_1, r_2, r_3, ...
> one for every natural number.
>
> You are presumably not talking about rationals, which
> have an infinite but repeating sequence of digits. There
> are also irrationals that can be constructed with simple
> patterns, like
> 0.12345678910111213141516...
> (I'm just writing down 1, 2, 3, ..., 10, 11, 12, ...)
>
> Are you saying this number doesn't exist?
No. I acknowledge that the number that you've given does exist.
>
> > In the example above,
> > what is the number that 1 'points' to? Since you can keep adding an
> > infinite number of digits after the decimal point how can you say that
> > 1 is pointing to a specific number?
>
> It's "pointing" to whatever particular infinite sequence
> you meant. I think you're taking the view that "infinite
> means it keeps changing". That's wrong. Pick any real number
> and put it in position 1. After you've picked it, you
> don't get an infinite number of choices for what's in
> position 1. That number has a fixed n-th digit for every
> n.
OK. Here's what I mean when I ask to what number is the number 1
pointing to:
If you say that 1 <--> .3984038..... then 1 is actually pointing to
many different numbers with different values, not to one specific
number with one specific value. Here's why, the number that I used
above .3984038 becomes a new number (new value) as soon as you add one
digit after the last one. The number .3984038 is different from
.39840387 and this one is different from .398403872 and so on so I
don't see how can you say that the number 1 is pointing to a specific
number with a specific value when you say that the digits after the
decimal point continue ad infinitum. Now one exception would be if you
talk about 0.25000000.... with an infinite number of zeros. No matter
how many zeros you add the actual value of 0.25 remains unchanged. As
soon as you add a non zero value, you end up with a new number.
Some people say that the fact that you cannot create Cantor's list
proves that the reals can't be counted. I see it differently. If the
list cannot be created, how can the theorem hold true? If you assume
that there is a list that contains an integer for every real, and
later you say that you'll find a real number that's not on the list
then your initial premise was false!
People please don't take this as arrogance or think that I'm calling
this whole thing nonsense. I'm just voicing my opinion.
Thanks.
Herman Jurjus
"Dave Seaman" <dse...@seaman.cc.purdue.edu> wrote in message
news:a4gf7t$2...@seaman.cc.purdue.edu...
> In article <cca46c2a.02021...@posting.google.com>,
> Henry <avil...@email.msn.com> wrote:
>
> >While reading Paul Erdos' story in "My brain is open" I found Cantor's
> >diagonal argument which he used to 'prove' that the decimals between 0
> >and 1 are uncountable. What's even worse, he used that to say that the
> >infinity of the decimals is larger than the infinity of the integers
> >(but that's another matter).
>
> Why is that "even worse"? Both statements mean precisely the same thing.
> "Uncountable" means "larger than the infinity of the integers", in the
> sense that there is no mapping from the integers *onto* the given set.
>
> >What I would like to know is how could he
> >establish the diagonal argument on a list that I'm not sure can be
> >created at all. How can someone create a list like:
>
> We don't have to create the list. The list is given to us in the
> hypothesis of the theorem. In geometry, we accept that infinitely long
> lines exist, even though we can never finish drawing them. In analysis,
> we accept that real numbers exist, even though we can never finish
> writing them down.
OK. But aren't there people outthere who can imagine 'potentially' infinite
sets, but not 'actual' infinite sets?
To those people, would Cantor's argument make sense?
Cheers,
Herman Jurjus
Dave Seaman
Bob Kolker <bobk...@mediaone.net> wrote:
>Bob Kolker
I try not to get into flame-fests over this in newsgroups where it would
be off-topic, so I'll just post two URL's, one for the pro-Mumia side and
one for the anti-Mumia side:
<http://www.refuseandresist.org/mumia/>
<http://www.danielfaulkner.com/>
Yes, I am familiar with the arguments at the danielfaulkner site, but I
find them unconvincing. Others may decide for themselves.
--
Dave Seaman
>> That can't be right, because there are only countably many "rules" that
>> can be formulated using finite strings of characters from a finite
>> alphabet. Yet, there are uncountably many real numbers. Therefore, it
>> follows that almost all of the real numbers have no rules associated with
>> them whatsoever.
>Yep. Surprising and unintuitive. This is virtually identical to the
>theorem that there are uncountably many (2^aleph_0) functions on the
>integers and only countably many algorithms.
[ . . . ]
>Or did you mean that it can't be right that you could make your integers
><--> reals table using just rule-defined reals? There's no
>contradiction there, because any proposed table (waiting to be
>demolished by Cantor's argument) would only have countably many entries
>anyway.
No, that's not what I meant. The proof applies to all countable lists,
whether rule-specified or not.
>> Amnesty International says Mumia Abu-Jamal decision falls short of justice.
>Always glad to see a supporter of Amnesty International.
Likewise.
--
Dave Seaman dse...@purdue.edu
Amnesty International says Mumia Abu-Jamal decision falls short of justice.
Dave Seaman
Herman Jurjus <h.ju...@hetnet.nl> wrote:
>"Dave Seaman" <dse...@seaman.cc.purdue.edu> wrote in message
>news:a4gf7t$2...@seaman.cc.purdue.edu...
>> We don't have to create the list. The list is given to us in the
>> hypothesis of the theorem. In geometry, we accept that infinitely long
>> lines exist, even though we can never finish drawing them. In analysis,
>> we accept that real numbers exist, even though we can never finish
>> writing them down.
>OK. But aren't there people outthere who can imagine 'potentially' infinite
>sets, but not 'actual' infinite sets?
>To those people, would Cantor's argument make sense?
There is more than one Cantor argument. The one that seems most
appropriate here is the power set version. Given any set X, the power
set of X, P(X), is the set of all subsets of X. A version of Cantor's
theorem says that if X is any set at all (finite or infinite), then |X| <
|P(X)|.
Proof: There is an obvious injection f: X -> P(X) given by x |-> {x}.
This establishes that |X| <= |P(X)|. In order to show that the
cardinalities are not equal, we need to show that no mapping f: X -> P(X)
is a surjection. That is, given f: X -> P(X), we need to find a member S
of P(X) (depending on f) such that S is not in the range of f.
Let S = { x in X : not(x in f(x)) }. It follows from this definition
that for every x in X, x belongs to S <==> x does not belong to f(x).
Therefore, S differs from f(x) for every x in X, which is what it means
to say S is not in the range of f.
Corollary. The powerset of the natural numbers, P(N), is uncountable.
Now, you can deny that infinite sets exist if you like, but you can't
deny that Cantor's proof applies to all sets that exist. You can deny
that there is a set N if you like, but you can't deny that *if* there is
a set N, then the set P(N) is larger than N.
Randy Poe
> If you say that 1 <--> .3984038..... then 1 is actually pointing to
> many different numbers with different values, not to one specific
> number with one specific value.
That's a problem with your specification, not the list.
You're right, that if I say "element 1 is some number which
begins 0.3984038" then I have not specified element 1. However,
the Cantor proof says assign any fixed constant real number to
list position 1, another to 2, etc.
If I say pi = 3.14159... does that mean there are infinitely
many possible values for pi?
> If the list cannot be created, how can the theorem hold true?
What does this mean? What does it mean, "the list cannot
be created"? Lots of lists can be created. The theorem proves,
rigorously, that any list with a countable number of elements
is incomplete.
>If you assume that there is a list that contains an integer
>for every real, and later you say that you'll find a real
>number that's not on the list then your initial premise was false!
That would be the contradiction version of the proof. Before
you go objecting to that, learn about proof by contradiction.
For instance, that hoary old chestnut, the proof that sqrt(2)
is irrational.
It starts out, "suppose sqrt(2) is rational, that is it
can be written in the form m/n..."
It then goes on to a contradiction. So "the initial premise
was false!". Yes. That's the point in a proof of that
form: If you make an assumption that leads to a self-contradiction,
then that assumption can't be true.
But it's not necessary to do this proof as a proof by
contradiction. You can simply say, "suppose I have a list"
without specifying anything else about that list. Then
you can show that there's a real not on the list. Therefore
all lists are incomplete.
Now what's wrong with that? What is wrong with "suppose I
have a list, and I don't care how you built it"? What
cases have been left out?
- Randy
Harlan Messinger
"Henry" <avil...@email.msn.com> wrote in message
news:cca46c2a.02021...@posting.google.com...
> While reading Paul Erdos' story in "My brain is open" I found Cantor's
> diagonal argument which he used to 'prove' that the decimals between 0
> and 1 are uncountable. What's even worse, he used that to say that the
> infinity of the decimals is larger than the infinity of the integers
> establish the diagonal argument on a list that I'm not sure can be
> created at all. How can someone create a list like:
>
> 2 <--> .4898495.....
>
> The basic question here is how can you assign the number 1 to a
> what is the number that 1 'points' to? Since you can keep adding an
> infinite number of digits after the decimal point how can you say that
> like:
>
> 1 <--> .25
> 2 <--> .50
>
> Here the number 1 is assigned to the specific number .25, not to an
> arbitrary number that has an infinite number of digits after the
> decimal point.
If you start,as you are doing, with the supposition that you can't create
such a list, then you've already proved his conclusion, which was that you
can't make such a list. (By definition a countable set is one that *can* be
sequenced like this. So if a set can't be sequenced like this, in a
one-to-one correspondence with the integers, then the set, by definition,
ain't countable.) So what's the problem?
Putting that aside, *if* you were to try to assign a specific
non-terminating, non-repeating number between 0 and 1 to an integer, the way
you would identify that number is by defining a way to know, for any
position p, what digit is at that position.
I think this is very funny anyway. The last time I stopped in at sci.math,
there was a thread on this subject. Today there's another one. Is a thread
on this subject always going on at any given time? It's like the perennial
question in comp.lang.java.programmer about why 3. * (1. / 3.) is
0.9999999999999.
Wade Ramey
avil...@email.msn.com (Henry) wrote:
> If you say that 1 <--> .3984038..... then 1 is actually pointing to
> many different numbers with different values, not to one specific
> number with one specific value.
Nonsense. The arrows are simply heuristic aids, and you've taken the idea
of "pointing" very strangely indeed.
If we can't agree that the square roots of the natural numbers can be
counted, we're not going to get very far.
1 <--> sqrt(1)
2 <--> sqrt(2)
3 <--> sqrt(3)
.
.
.
You OK with this? Now consider
1 <--> sqrt(1) = 1.000000
2 <--> sqrt(2) = 1.14213...
3 <--> sqrt(3) = 1.73205...
.
.
.
Whatever "pointing" problem you're having, you also have it here. Do you
really think there is a problem here?
--W.
nos...@auerbachatunity.ncsu.edu
>If you assume
>that there is a list that contains an integer for every real, and later you
>say that you'll find a real number that's not on the list then your initial
>premise was false!
And the initial premise was that the reals were listable. So now you have
Cantor's conclusion: the reals aren't listable. (Where listable has the
precise meaning: being able to be put into 1-1 correspondence with the
(positive) integers.)
--
Regards,
David
"Always carry a large flagon of whisky in case of snakebite and furthermore
always carry a small snake"
WC Fields
"What would life be without arithmetic, but a scene of horrors?"
-Rev. Sydney Smith, letter to young lady, 22 July 1835
-----------------------------------------------------------
David Auerbach nos...@auerbachatunity.ncsu.edu
Department of Philosophy & Religion
NCSU
Box 8103
Raleigh, 27695-8103
-----------------------------------------------------------
George Greene
: While reading Paul Erdos' story in "My brain is open" I found Cantor's
: diagonal argument which he used to 'prove' that the decimals between 0
: and 1 are uncountable. What's even worse, he used that to say that the
: infinity of the decimals is larger than the infinity of the integers
: (but that's another matter). What I would like to know is how could he
: establish the diagonal argument on a list that I'm not sure can be
: created at all.
Well, that's the whole point. The list CAN'T be created at all.
: How can someone create a list like:
:
: 1 <--> .2332245.....
: 2 <--> .4898495.....
:
: The basic question here is how can you assign the number 1 to a
: number that has an infinite number of digits. In the example above,
: what is the number that 1 'points' to? Since you can keep adding an
: infinite number of digits after the decimal point how can you say that
: 1 is pointing to a specific number?
Do you think real numbers exist or not?
Consider the real number pi. If you choose to represent it
in decimal, that representation of pi has an infinite number of
digits. Are you therefore saying that if I wanted to list the
real numbers, I could not list pi first?
That was rhetorical; the answer is, YES, you ARE saying that, but
the question then becomes, why are you saying something so stupid?
Dudley Brooks
*specifying* or *writing* of particular irrational numbers. It's an
interesting question in itself -- which several other posters have
answered correctly, but maybe not clearly ;^) -- but it's irrelevant to
(the beginning of) the proof of Cantor's Theorem, which in a nutshell
says "Any time you *claim* to have come up with a list of all the real
numbers, I can always show you a real number which is not on your
list." He doesn't really care how you *write* the list, so it's
irrelevant how real numhers are specified. In other words, you're
worried about what such a list would actually (physically) look like,
but in fact that doesn't matter.
But your question about the naming of real numbers *is* relevant to the
*end* of the argument, because -- what does Cantor mean when he says "I
can *show* you a real number which ..."? How can he show it to you
without writing it? Well, what he means is, "I can show you the method
to go about writing that real number, so that however far you may have
already written it, you can always know precisely how to continue
writing it. And that method is clear enough that you can easily see
that none of the numbers on your list matches it."
> Some people say that the fact that you cannot create Cantor's list
> proves that the reals can't be counted.
The only people that say that, don't understand the proof. That's *not*
the argument. [Well, depending on what you mean. If they're saying
that the fact that you can never finish writing an infinite decimal, and
never finish writing an infinite list, proves that the reals are
uncountable, then they don't understand the argument. But if they're
saying that you can't make a list which contains *all* the reals, then
they're merely stating *what* Cantor proved, not *how* he proved it.]
> I see it differently. If the
> list cannot be created, how can the theorem hold true?
One source of confusion here is that we have to keep very clear about
which direction we're going. We can easily create a list where every
integer is paired with a real. As I and many other responders have
explained, there are many, many ways to make every real number on such a
list clearly defined and clearly understood, so that any two people
looking at the list are in perfect agreement about what any given real
number is, in the sense that, given 0.3984038......, they both agree
what the next digit should be, and the next, and the next, and so on. I
won't go into the details of that any further, because, as I say, it's
irrelevant.
What Cantor's Theorem says is that we can't go in the other direction --
we can't create a list where all reals (emphasis on *all*) are paired
with integers. (And since "list" means lines labelled "1", "2", "3",
etc., we can more simply just say that Cantor proved that we can't make
a list of all the reals.)
> If you assume
> that there is a list that contains an integer for every real, and
> later you say that you'll find a real number that's not on the list
> then your initial premise was false!
Yes, that's exactly what we want to happen! It's called Reductio ad
Absurdum or Proof by Contradiction. We *want* to prove that you "can't*
make a list of *all* real numbers. So we assume just the *opposite*,
namely that you *can* make such a list, and then demolish the assumption
by finding a real number not on the list. So the assumption that you
*can* create the list is false, so therefore we conclude that you
*can't* create the list.
But it's also possible to do it more directly, without proof by
contradiction. In this method there is no initial premise, because we
don't *assume* we have such a list -- we actually *present* such a list
(so to speak -- we present some way of describing or creating the
list). Rather, what we do is (mistakenly) *claim* that our list
contains *all* real numbers. Then, when Cantor comes up with a real
number which is not on the list, he has merely proved that our claim was
mistaken -- the list does *not* contain all real numbers. And he does
it in such a way that it is clear that no matter what list we present,
he can *always* find a number which is not on it.
Dudley Brooks
>
> In article <3C6BF6AF...@best.com>,
> Dudley Brooks <voi...@best.com> wrote:
> >Dave Seaman wrote:
>
> >Or did you mean that it can't be right that you could make your integers
> ><--> reals table using just rule-defined reals?
> No, that's not what I meant.
I didn't really think it was.
Jim Heckman
On 14-Feb-2002, "Harlan Messinger" <hmess...@erols.com> wrote:
[...]
> I think this is very funny anyway. The last time I stopped in at sci.math,
Hi, Harlan! Please feel free to visit as often as you like! :-)
> there was a thread on this subject. Today there's another one. Is a thread
> on this subject always going on at any given time?
Pretty much. It's not unlikely the single most broached and rebroached
fallacy on the group, if you discount the voluminous threads lauched by
one particular insane person on Fermat's Last Theorem.
> It's like the perennial
> question in comp.lang.java.programmer about why 3. * (1. / 3.) is
> 0.9999999999999.
"How can 0.999... really be equal to 1 ?" is another 'popular favorite' on
sci.math.
--
Jim Heckman
Nico Benschop
>
> Henry wrote:
> >
> > While reading Paul Erdos' story in "My brain is open" I found
> > Cantor's diagonal argument which he used to 'prove' that the
>
> [...]
> His diagonal argument to show this is very simple, and has little
> to do with reals on [0,1) which is special interpretation, but
> everything with strings over some alphabet A of at least 2 symbols.
> In fact he shows that whatever list of (binary) strings of lentgh k
> you take (for finite k there are 2^k): any square k x k table of
> such strings has a diagonal that is a string (length k) which is
> not in that listing if you 'swap bitwise' all bits in the diagonal.
> For k=6 there are 2^6= 64 binary strings, and take any selection of 6:
>
> 0 1 1 1 0 0 diagonal: 0 1 0 0 0 1 (left top to right bottom)
> 1 1 0 1 0 1 swapped: 1 0 1 1 1 0 is not a row in this 6 x 6 table,
> 0 1 0 1 0 1 because it differs in each position
> 1 0 1 0 1 0 from each row, at that position!
> 0 0 0 0 0 0
> 1 1 1 0 1 1
>
> This holds for finite k, no matter how large, and in fact:
> -------- _independent_ of length k ------
> hence (by some axiom) also for infinite k,
> called omega w, the countable ('linear') infinite of Peano's naturals,
> or the integers, including the negative, which also are countable.
Re: finite Cantor Diagonals (CD) as generative principle:
Rather than just *one* extra diagonal, I just wondered for the
finite case of order k: is there a minimum number (maybe < k ?) of
such k x k binary tables which, by permuting rows of each table,
generate as CD's *all* 2^k binary strings of length k ?
There are k! > 2^k (k>3) permutations, but not all generate different
diagonals. A table like the next (k=6) seems to be very 'prolific':
0 0 0 0 0 1 Note: a diagonal entry is not changed if its row
0 0 0 0 1 1 is replaced by a row with the same entry
0 0 0 1 1 1 in that column. E.g: pair swapping involes
0 0 1 1 1 1 4 entries: in rows i,j and cols i,j -
0 1 1 1 1 1 producing a new CD only if the row distance
1 1 1 1 1 1 (symm.difference) \neq 0 there.
> [...]
> So exponentiation (^) is really something else, compared with (+) (*).
> In fact, while arithmetic (+) and (*) are both associative and
> commutative operations, while (^) is repeated (*), which itself is
> repeated (+), notice that (^) is neither associative nor commutative!
>
> -- NB - http://home.iae.nl/users/benschop/cantor.htm
> http://home.iae.nl/users/benschop/sgrp-flt.htm
Nico Benschop
>
> Henry wrote:
> >
> > While reading Paul Erdos' story in "My brain is open" I found
> > Cantor's diagonal argument which he used to 'prove' that the
> > decimals between 0 and 1 are uncountable. [...]
>
> [...]
> His diagonal argument to show this is very simple, and has little
> to do with reals on [0,1) which is special interpretation, but
> everything with strings over some alphabet A of at least 2 symbols.
> In fact he shows that whatever list of (binary) strings of lentgh k
> you take (for finite k there are 2^k): any square k x k table of
> such strings has a diagonal that is a string (length k) which is
> not in that listing if you 'swap bitwise' all bits in the diagonal.
> For k=6 there are 2^6= 64 binary strings, and take any selection of 6:
>
> 1 1 0 1 0 1 swapped: 1 0 1 1 1 0 is not a row in this 6 x 6 table,
> 0 1 0 1 0 1 because it differs in each position
> 1 0 1 0 1 0 from each row, at that position!
> 0 0 0 0 0 0
> 1 1 1 0 1 1
>
> This holds for finite k, no matter how large, and in fact:
> -------- _independent_ of length k ------
> hence (by some axiom) also for infinite k,
> called omega w, the countable ('linear') infinite of Peano's naturals,
> or the integers, including the negative, which also are countable.
Re: finite Cantor Diagonals (CD) as generative principle:
Rather than just *one* extra diagonal, I just wondered for the
finite case of order k: is there a minimum number (maybe < k ?) of
such k x k binary tables which, by permuting rows of each table,
generate as CD's *all* 2^k binary strings of length k ?
There are k! > 2^k (k>3) permutations, but not all generate different
diagonals. A table like the next (k=6) seems to be very 'prolific':
\
0 0 0 0 0 1 Note: a diagonal entry is not changed if its row
0 0 0 0 1 1 is replaced by a row with the same entry
0 0 0 1 1 1 in that column. E.g: pair swapping involes
0 0 1 1 1 1 4 entries: in rows i,j and cols i,j -
0 1 1 1 1 1 producing a new CD only if the row distance
1 1 1 1 1 1 (symm.difference) \neq 0 there.
\
Or equivalently: its symmetric image (while also columns may be used):
\
1. 1 0 0 0 0 0 If 'weight' w(i) is the number of 1's in row i,
2. 1 1 0 0 0 0 and R(w) the set of all k_strings of weight w,
3. 1 1 1 0 0 0 then symmetric analysis would require to
4. 1 1 1 1 0 0 generate all Ranks R(w) for w=0..k
5. 1 1 1 1 1 0 E.g. swap rows (2,3): CD= 0 0 1 0 0 0
6. 1 1 1 1 1 1 or if i<j swap (i,j): CD= 1 in place j, rest 0
\ So swaps yield ranks R(1), and also R(k-1) by
taking -CD (bitwise inverse CD).
Q: Does an m_cycle permution yield CD \in R(m-1) ?
\
Like (1,2,3) --> 1 1 1 0 ... CD= 0 1 1 0 0 0
1 0 0 0 ...
1 1 0 0 ...
1 1 1 1 0 .
\ ...etc
Randy Poe
>
> On 14-Feb-2002, "Harlan Messinger" <hmess...@erols.com> wrote:
>
> [...]
>
> > I think this is very funny anyway. The last time I stopped in at sci.math,
>
> Hi, Harlan! Please feel free to visit as often as you like! :-)
>
> > there was a thread on this subject. Today there's another one. Is a thread
> > on this subject always going on at any given time?
>
> Pretty much. It's not unlikely the single most broached and rebroached
> fallacy on the group, if you discount the voluminous threads lauched by
> one particular insane person on Fermat's Last Theorem.
Along with some variation of "how can all the integers be finite
if there are infinitely many of them?"
- Randy
LarryLard
When I used to frequent sci.math under a different name, must have been a
couple of years back, there always used to be threads about 0.999
(recurring), and the relationship of that number to 1. There don't seem to
be as many of that sort of thread any more.
--
Larry Lard
Replies to group please.
Doug Magnoli
Arturo Magidin wrote:
> In article <cca46c2a.02021...@posting.google.com>,
> Henry <avil...@email.msn.com> wrote:
>
> > Derek, if everyone would think like you do, then there would be no
> >progress.
> >For how many years people thought the earth was flat???!!!
>
> Bad example. Aristarchus of Samos had already shown the Earth wasn't
> flat.
>
OK, so before him. Also phlogiston comes to mind.
Perhaps the OP isn't the only person missing the point.
-Doug Magnoli
[Delete the two and the three for email.]
Jon Miller
> OK. But aren't there people outthere who can imagine 'potentially' infinite
> sets, but not 'actual' infinite sets?
> To those people, would Cantor's argument make sense?
Kronecker had a hard time with it. His attacks were not so much that Cantor
was wrong as that he was doing "bad mathematics".
There are even (intelligent) people who (claim that they) are unable to believe
in infinite sets at all. To them, Cantor's argument makes no sense.
There are people who deny the law of the excluded middle. To them, proving
that not-A is false does not prove that A is true. (Example, quoted from
memory: "While not disgruntled, his manner indicated that he was far from
gruntled." [Wodehouse] Clearly, in real life, not-not-A isn't always A.) In
particular, proof by contradiction doesn't exist for these people. Brouwer (of
fixed-point fame) was a powerful example.
Jon Miller
Torkel Franzen
> There are even (intelligent) people who (claim that they) are unable
> to believe in infinite sets at all. To them, Cantor's argument
> makes no sense.
Why is that? Cantor's argument does not presuppose the existence
of any infinite set.
> There are people who deny the law of the excluded middle. To them, proving
> that not-A is false does not prove that A is true.
But Cantor's argument is perfectly constructively valid, and does
not rely on the law of excluded middle.
Chris Menzel
> The question you are asking is basically about the *naming* or
> *specifying* or *writing* of particular irrational numbers. It's an
> interesting question in itself -- which several other posters have
> answered correctly, but maybe not clearly ;^) -- but it's irrelevant to
> (the beginning of) the proof of Cantor's Theorem, which in a nutshell
> says "Any time you *claim* to have come up with a list of all the real
> numbers, I can always show you a real number which is not on your
> list."
Right, so long as we understand this in a way that doesn't suggest that
this is just a problem with the lists that *we* are capable of coming up
with. The point (your point, I'm sure) is that every list of reals
(understood simply as a 1-1 mapping from the positive integers into the
reals) is incomplete, regardless of whether or not we are capable of
coming up with it.
Chris Menzel
Duran Castore
"Henry" <avil...@email.msn.com> escreveu na mensagem
news:cca46c2a.02021...@posting.google.com...
> While reading Paul Erdos' story in "My brain is open" I found
Cantor's
> diagonal argument which he used to 'prove' that the decimals
between 0
that the
> infinity of the decimals is larger than the infinity of the
integers
> (but that's another matter). What I would like to know is how
could he
> establish the diagonal argument on a list that I'm not sure can
be
>
> 1 <--> .2332245.....
> 2 <--> .4898495.....
>
> The basic question here is how can you assign the number 1 to
a
> number that has an infinite number of digits. In the example
above,
> what is the number that 1 'points' to? Since you can keep
adding an
> infinite number of digits after the decimal point how can you
say that
> 1 is pointing to a specific number?
Since the number is fixed, all digits of it are already there. No
one is "adding digits" to any number in the list; just choose
distinct real numbers (between 0 and 1) and assign each one to a
natural number. Okay, this will take infinite time, so we assume
it's already done; the specific real numbers assigned don't
influence the proof.
>A possible list would be something like:
>
> 1 <--> .25
> 2 <--> .50
>
> Here the number 1 is assigned to the specific number .25, not
to an
> arbitrary number that has an infinite number of digits after
the
> decimal point.
This way, you are listing only terminating rational numbers. The
point is, you can choose _any_ real number, regardless of which
it is rational or not.
> Given these questions, how can the proof itself hold true. I
don't
> see that its initial premise makes logical sense. What's also
> confusing is saying that if you can't use the integers to count
the
> decimals that kind of assumes that you'll run out of integers
(you'll
> reach the largest integer ever) which makes no sense. Comments
> please!!
No one "runs out" of integers. The idea, in the diagonal
argument, is to compare two sets of numbers, both infinite, and
show that one is "bigger" than the other, in the sense that,
whatever the way we compare them, one of the sets always have
elements remaining to be compared. Other posters already talked
about it, way better than I can.
Duran Castore.
Virgil
> There are even (intelligent) people who (claim that they) are unable
> to believe in infinite sets at all. To them, Cantor's argument
> makes no sense.
Why is that? Cantor's argument does not presuppose the existence
of any infinite set.
> There are people who deny the law of the excluded middle. To them, proving
> that not-A is false does not prove that A is true.
There are people who will deny that (P or (not P)) is necessarily
true, but those same people will insist that (P and (not P)) is
necessarily false. It is the second form which is relevant to
Cantor's proof, not the first.
Harlan Messinger
"Virgil" <vmh...@attbi.com> wrote in message
news:vmhjr2-35D8AB....@netnews.attbi.com...
I don't get it. In symbolic logic, isn't "not" *defined* such that (P or
(not P)) is necessarily true and (P and (not P)) is necessarily false?
Dudley Brooks
>
> > "Any time you *claim* to have come up with a list of all the real
> > numbers, I can always show you a real number which is not on your
> > list."
>
> Right, so long as we understand this in a way that doesn't suggest that
> this is just a problem with the lists that *we* are capable of coming up
> with. The point (your point, I'm sure) is that every list of reals
> (understood simply as a 1-1 mapping from the positive integers into the
> reals) is incomplete, regardless of whether or not we are capable of
> coming up with it.
Right, that's what I meant by "any time". Clearer would have been, "For
*any* list which you claim ...". (And naturally it's not important what
anyone *claims" about the list -- the list *is* incomplete, whether
anyone claims it's complete or not. As someone else pointed out, it's
not really a proof by contradiction. I was just trying to give it the
flavor of a Socratic dialogue because when I used to tutor I discovered
that an adversarial give-and-take presentation helped people understand
proofs that they didn't understand when the proofs were just set out
before them.)
As far as whether we are "capable of coming up with it" ... Hmm, that
leads to all kinds of interesting questions -- interesting to a total
amateur like me, anyway. For instance, since there are more reals than
there are rules (or algorithms) for specifying reals, would it be
possible to clearly specify a list of countably many reals,*none* of
which was specifiable by a rule? Sounds obvious that we couldn't, since
I said "specify" a list, and "specify" seems to mean "specify by a
rule", and yet I can't help thinking that maybe there's some really
clever, tricky way to do it. For one thing, "specify" is an English
word, not a mathematical one, so is there a useful sense of
"non-algorithmically specifying"? (Useful meaning that it lets us talk
about some precise properties of what we have specifed, even though what
we have specified isn't precise.) Is this just "round triangle" misuse
of words, or does this relate to anything real mathematicians have
done? And similarly (or by extension), is there something which is more
specified than an existence proof but less specified than a constructive
proof?
Virgil
"Harlan Messinger" <hmess...@erols.com> wrote:
For most people, yes, but there are those that insist that the
falseness of P is insufficient to guarantee the truth of not P and
vice versa. They deny what is generally known as the law of the
excluded middle, and say that there may be something in the middle,
"between" P and not P.
Harlan Messinger
I still don't understand. A system is defined by its axioms. In discussing
reasoning that takes place within the system as defined, how can one
disagree with one of the axioms?
I mean, if they want to go play with a system where propositions are
trivalent, fine, let them. It may even be productive. But that doesn't alter
how traditional bivalent symbolic logic works.
Virgil
"Harlan Messinger" <hmess...@erols.com> wrote:
It is quite possible to do large amounts of mathematics in systems
whose axioms do not include or allow a law of the excluded middle.
And there is a school of thought that rejects anything that cannot
be done in such systems. I think that one such school of thought is
called intuitionism, and its foremost supporter was Brouwer.
Chip Eastham
> "Virgil" <vmh...@attbi.com> wrote in message
> news:vmhjr2-35D8AB....@netnews.attbi.com...
> > Jon Miller <jonatha...@home.com> writes:
> >
> >
> > > There are people who deny the law of the excluded middle. To them,
> proving
> > > that not-A is false does not prove that A is true.
> >
> > There are people who will deny that (P or (not P)) is necessarily
> > true, but those same people will insist that (P and (not P)) is
> > necessarily false. It is the second form which is relevant to
> > Cantor's proof, not the first.
>
> I don't get it. In symbolic logic, isn't "not" *defined* such that (P or
> (not P)) is necessarily true and (P and (not P)) is necessarily false?
The propositional calculus can be "fragmented" by taking out certain axioms
like (P or (not P)), the "law of the excluded middle" mentioned above. One
obtains weaker (but therefore consistent) systems of logic this way.
In particular proponents of "constructive" mathematics and specifically
"intuitionist" logic eschew the law of the excluded middle.
Regards,
Chip
Harlan Messinger
In other words, are these people who refuse to see the difference that most
people implicitly understand to exist between "short" and "not tall"?
Harlan Messinger
"Jim Heckman" <jamesr...@abcyahoo.xyzcom> wrote in message
news:u6orlm6...@news.supernews.com...
>
> On 14-Feb-2002, "Harlan Messinger" <hmess...@erols.com> wrote:
>
> [...]
>
> > I think this is very funny anyway. The last time I stopped in at
sci.math,
>
> Hi, Harlan! Please feel free to visit as often as you like! :-)
Jim! You speak English!
>
> > there was a thread on this subject. Today there's another one. Is a
thread
> > on this subject always going on at any given time?
>
> Pretty much. It's not unlikely the single most broached and rebroached
> fallacy on the group, if you discount the voluminous threads lauched by
> one particular insane person on Fermat's Last Theorem.
>
> > It's like the perennial
> > question in comp.lang.java.programmer about why 3. * (1. / 3.) is
> > 0.9999999999999.
>
> "How can 0.999... really be equal to 1 ?" is another 'popular favorite' on
> sci.math.
Ah, yes, I'd forgotten. Conversely, regarding ones-complement integer data
type cyber-notation, "How can there be both positive zero and negative 0"?
Virgil
"Harlan Messinger" <hmess...@erols.com> wrote:
More accurately, they refuse to accept that everyone is either tall
or not tall without some sort of constructive proof.
Jonathan Hoyle
> number that has an infinite number of digits.
Every number has an infinite number of digits, whether it is an
irrational number like 3.14159... or an integer like 1.000...
> In the example above, what is the number that 1 'points' to? Since you
> you keep adding an infinite number of digits after the decimal point how
> can you say that 1 is pointing to a specific number? A possible list would
> be something like:
>
> 1 <--> .25
> 2 <--> .50
>
> Here the number 1 is assigned to the specific number .25, not to an
> arbitrary number that has an infinite number of digits after the
> decimal point.
How is 1/4 written as .25000... anymore arbitrary than 1/3 written as
.333...? If you just change bases to Base 3 say, 1/4 is now the
"arbitrary" number .0202... and 1/3 is the "specific" number .1. It
is mere notation, they are both non-moving constant values, not
something that "gets added on" to. Just because they are represented
with an infinite number of digits does not keep them from being
precise constants.
> Given these questions, how can the proof itself hold true. I don't
> see that its initial premise makes logical sense. What's also
> confusing is saying that if you can't use the integers to count the
> decimals that kind of assumes that you'll run out of integers (you'll
> reach the largest integer ever) which makes no sense. Comments
> please!!
Yes, you will "run out" of integers before you completely map the
reals, if you wish to think of it that way. Just because it is hard
for you to understand does not mean it doesn't make sense. It was
hard for me to understand when I first encountered it, but the problem
was my understanding, not the logic itself. I may be bounded by my
limitations, but Mathematics is not.
> In an alternate but related topic, I think it is absurd to talk
> about an infinite being larger than another. That just does not make
> sense at all. Infinity doesn't have an end so:
>
> Inf + Inf = Inf
> Inf * Inf = Inf and so on.
Be careful that you do not confusing the difference between an
infinite number and an infinite representation of a number. For
example, 0.333... is an infinite representation of a finite number,
and N_0 (Aleph-0) is a finite representation of aan infinite number.
As for your transfinite arithmetic, saying "Inf * Inf = Inf" may be
true, but it is as vague as me saying "Finiteness * Finiteness =
Finiteness". My statement is true, but there is more than one finite
quantity. Likewise, there is more than one infinite quantity.
Moreover, there are more than one class of infinities. What we happen
to be discussing here are called "cardinal numbers", but there are
ordinals, non-standard reals, and a few other types of infinity. But
that is probably more than you need to know for now. Suffice it to
say, your error is assuming that there is one universal infinity that
fits all mathematical models, and such an assumption has been proven
to be logically inconsistent.
Harlan Messinger
Why does it not suffice for them to say that that's how "not" is *defined*?
Virgil
"Harlan Messinger" <hmess...@erols.com> wrote:
> "Virgil" <vmh...@attbi.com> wrote in message
> news:vmhjr2-9E34CB....@netnews.attbi.com...
> > In article <a4revv$2cs7s$1...@ID-114100.news.dfncis.de>,
> > "Harlan Messinger" <hmess...@erols.com> wrote:
> >
> > > > It is quite possible to do large amounts of mathematics in systems
> > > > whose axioms do not include or allow a law of the excluded middle.
> > > >
> > > > And there is a school of thought that rejects anything that cannot
> > > > be done in such systems.
> > >
> > > In other words, are these people who refuse to see the difference that
> most
> > > people implicitly understand to exist between "short" and "not tall"?
> >
> > More accurately, they refuse to accept that everyone is either tall
> > or not tall without some sort of constructive proof.
>
> Why does it not suffice for them to say that that's how "not" is *defined*?
>
>
As I am not an apologist for the intuitionists' position, you will
have to ask someone who is.
Dudley Brooks
subject, but I have read that in Category Theory there are categories
called topoi (plural of topos), which are mathematical structures which
have many of the properties of Set Theory (enough properties to "do all
of mathematics" on); that each topos has a different logic "naturally"
associated with it; that the logic associated with the category (or
topos) called "SET" is standard two-valued logic; and that various other
topoi correspond to various other logics, including various Intuitionist
logics.
But please don't ask me for any further clarification. I introduce this
only to possibly solicit clarification or comment from those more
knowledgeable.
Alexey Dejneka
Intuitionism treats such systems in a way similar to the way in which
classically reasoning logician treats contradictory axioms: thay may
be studied, but it has no practical sense and does not serve the
primary purpose of logic--to describe reasonings of a `real'
mathematics.
Regards,
Alexey Dejneka
Torkel Franzen
> Intuitionism treats such systems in a way similar to the way in which
> classically reasoning logician treats contradictory axioms: thay may
> be studied, but it has no practical sense and does not serve the
> primary purpose of logic--to describe reasonings of a `real'
> mathematics.
I don't know if this is a good analogy. After all,
intuitionistically, we have double negation interpretations of
classical theorems, so that from a classical point of view
intuitionistic logic is just as strong as classical logic.
What would be the equivalent for contradictory theories
wrt classical logic?
Alan Stern
Because that *isn't* how "not" is defined in intuitionistic logic.
The notions of truth, falsity, negation, ... all have intuitionistic
definitions that are somewhat different from the classical definitions
you may be accustomed to.
Under intuitionism, saying that A is true means something like this:
There is a constructive procedure for determining whether A holds or
not, and it gives a positive result. Saying that A is false means
that there is such a constructive procedure and it gives a negative
result.
Now you can see that from this point of view, A could be neither true
nor false. In particular, if there is no constructive procedure for
determining whether A holds or not, then an intuitionist would say
that neither A nor not-A is true.
Alan Stern