| Author |
Message |
Bob G
Guest
|
| Posted: Sun Nov 28, 2004 6:07 am
Post subject: Re: Brand new colors |
|
|
| Quote: | All fine and well, but a subset of infinity is still an infinite
number.
|
A set is not a number.
Set A is a subset of set B if every member of A is also in B.
Bob G |
|
| Back to top |
|
 |
Bob G
Guest
|
| Posted: Sun Nov 28, 2004 12:10 pm
Post subject: Re: Brand new colors |
|
|
| Quote: | How about, take any fraction of an infinite
set of integers and you still have an infinite set?
|
Actually, if I remember my Math, there are several orders of infinity,
according to a German mathematician, name of Cantor.
The first order is called "Aleph Null" and an infinite set is said to be of
that ordinality if a one-to-one mapping, or function, can be established
between its members and the set of natural numbers (1,2,3...).
For instance, the set of positive even numbers has Aleph Null ordinality
because, for every natural number, the function f(n) = 2n, that is, 1 maps into
2, 2 into 4, and so on, will yield all the even numbers.
The set of irrational numbers (those that cannot be expressed as a fraction)
has a higher order of infinity, Aleph One, but don't ask me to prove it.
It doesn't follow that any subset of the set of integers is "infinite", of
course, as has been pointed out. But it doesn't really make sense to speak of a
"fraction" of that set - you would actually have to specify which "fraction" by
means of a mapping or function and, if it maps all the natural numbers, then it
would be an Aleph Null set.
A possibly interesting exercise would be to consider the set of all subsets of
the set of integers - would that have ordinality Aleph Null or Aleph One?
Bob G |
|
| Back to top |
|
|
Don Aitken
Guest
|
| Posted: Sun Nov 28, 2004 12:13 pm
Post subject: Re: Brand new colors |
|
|
On 28 Nov 2004 06:39:20 GMT, bobjames27@aol.com (Bob G) wrote:
| Quote: | How about, take any fraction of an infinite
set of integers and you still have an infinite set?
Actually, if I remember my Math, there are several orders of infinity,
according to a German mathematician, name of Cantor.
The first order is called "Aleph Null" and an infinite set is said to be of
that ordinality if a one-to-one mapping, or function, can be established
between its members and the set of natural numbers (1,2,3...).
For instance, the set of positive even numbers has Aleph Null ordinality
because, for every natural number, the function f(n) = 2n, that is, 1 maps into
2, 2 into 4, and so on, will yield all the even numbers.
The set of irrational numbers (those that cannot be expressed as a fraction)
has a higher order of infinity, Aleph One, but don't ask me to prove it.
The wonderful thing about Cantor's proofs is that they can be |
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required. Arrange these numbers in the order which their digits
specify.
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
My amateur mathematics usually comes to grief in this group, but I
*think* I have this right.
--
Don Aitken
Mail to the addresses given in the headers is no longer being
read. To mail me, substitute "clara.co.uk" for "freeuk.com". |
|
| Back to top |
|
|
Alec McKenzie
Guest
|
| Posted: Sun Nov 28, 2004 12:14 pm
Post subject: Re: Brand new colors |
|
|
Don Aitken <don-aitken@freeuk.com> wrote:
| Quote: | The wonderful thing about Cantor's proofs is that they can be
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required. Arrange these numbers in the order which their digits
specify.
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
|
Why would that show that "the required mapping is impossible"?
All it would show is that there is a number missing from your list,
which means you had failed to "express every number in the set".
--
Alec McKenzie
mckenzie@despammed.com |
|
| Back to top |
|
|
Roland Hutchinson
Guest
|
| Posted: Sun Nov 28, 2004 6:13 pm
Post subject: Re: Brand new colors |
|
|
Alec McKenzie wrote:
| Quote: | Don Aitken <don-aitken@freeuk.com> wrote:
The wonderful thing about Cantor's proofs is that they can be
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required. Arrange these numbers in the order which their digits
specify.
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
Why would that show that "the required mapping is impossible"?
All it would show is that there is a number missing from your list,
which means you had failed to "express every number in the set".
|
Because a "missing number" can be constructed in this way for any proposed
mapping. Therefore, no proposed mapping can be the required mapping.
--
Roland Hutchinson Will play viola da gamba for food.
NB mail to my.spamtrap [at] verizon.net is heavily filtered to
remove spam. If your message looks like spam I may not see it. |
|
| Back to top |
|
|
Alec McKenzie
Guest
|
| Posted: Sun Nov 28, 2004 6:13 pm
Post subject: Re: Brand new colors |
|
|
Roland Hutchinson <my.spamtrap@verizon.net> wrote:
| Quote: | Alec McKenzie wrote:
Don Aitken <don-aitken@freeuk.com> wrote:
The wonderful thing about Cantor's proofs is that they can be
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required. Arrange these numbers in the order which their digits
specify.
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
Why would that show that "the required mapping is impossible"?
All it would show is that there is a number missing from your list,
which means you had failed to "express every number in the set".
Because a "missing number" can be constructed in this way for any proposed
mapping. Therefore, no proposed mapping can be the required mapping.
|
Which, to my mind, shows no more than an interesting paradox: that any
list of all the irrational numbers will appear to have at least one
missing.
Here's a thought: express every *rational* number in a list in the same
fashion. The same argument applied to that list would then appear to
prove that the rational numbers also are uncountable, which is untrue.
--
Alec McKenzie
mckenzie@despammed.com |
|
| Back to top |
|
|
Stan Brown
Guest
|
| Posted: Sun Nov 28, 2004 6:13 pm
Post subject: Re: Brand new colors |
|
|
"Alec McKenzie" wrote in alt.usage.english:
| Quote: | Which, to my mind, shows no more than an interesting paradox: that any
list of all the irrational numbers will appear to have at least one
missing.
Here's a thought: express every *rational* number in a list in the same
fashion. The same argument applied to that list would then appear to
prove that the rational numbers also are uncountable, which is untrue.
|
The difference (and Cantor's proof, as I remember it) is that you can
imagine an algorithm that, given infinite time, would list every
rational number. However, even that algorithm would miss the
irrationals -- that's why the count of irrationals is a higher order
of infinity than the count of rationals.
--
Stan Brown, Oak Road Systems, Tompkins County, New York, USA
http://OakRoadSystems.com
A: Maybe because some people are too annoyed by top-posting.
Q: Why do I not get an answer to my question(s)?
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing? |
|
| Back to top |
|
|
Alec McKenzie
Guest
|
| Posted: Sun Nov 28, 2004 6:14 pm
Post subject: Re: Brand new colors |
|
|
Stan Brown <the_stan_brown@fastmail.fm> wrote:
| Quote: | The difference (and Cantor's proof, as I remember it) is that you can
imagine an algorithm that, given infinite time, would list every
rational number. However, even that algorithm would miss the
irrationals -- that's why the count of irrationals is a higher order
of infinity than the count of rationals.
|
I don't think you really mean that, because you might apply the same
reasoning to odd and even numbers, with the following result:-
.... you can imagine an algorithm that, given infinite time, would list
every odd number. However, even that algorithm would miss the
even numbers -- that's why the count of even numbers is a higher order
of infinity than the count of odd numbers.
--
Alec McKenzie
mckenzie@despammed.com |
|
| Back to top |
|
|
Donna Richoux
Guest
|
| Posted: Mon Nov 29, 2004 12:10 am
Post subject: Re: Brand new colors |
|
|
Don Aitken <don-aitken@freeuk.com> wrote:
| Quote: | The wonderful thing about Cantor's proofs is that they can be
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required.
Arrange these numbers in the order which their digits
specify.
|
Well, right there is a bit of a snag. You can't *assume* that any set
can be so arranged, and in fact it can't be. (If "0.000.." is the first
element, what is the second?) You can arrange them in the same way that
all the real numbers are 'arranged" on the real number line (comparing
any two numbers; 0.215 goes between 0.212 and 0.21899 and the like) but
you can't assign them positions like "first on the list," second on the
list, etc. (What's the "first fraction" between zero and one?).
But luckily, it doesn't matter what the order is of all these strings of
infinite decimals. It's not essential for your proof. "Arranging" them
in "order" is just a mental convenience. The mechanics of generating a
new number not on the list does not depend on the order of the items
listed. They could be in random order. All there has to be, to satisfy
the supposition, is a first item on the list, a second item on the list,
and so on.
| Quote: |
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
My amateur mathematics usually comes to grief in this group, but I
*think* I have this right.
|
I'd say you got the basic idea right: if there *were* such a complete
and countable list of irationals, there would be a way to construct
another item not on the list, so such a countable list could never be
complete. Therefore the complete set is not countable.
--
Best -- Donna Richoux |
|
| Back to top |
|
|
Donna Richoux
Guest
|
| Posted: Mon Nov 29, 2004 12:10 am
Post subject: Re: Brand new colors |
|
|
Alec McKenzie <mckenzie@despammed.com> wrote:
| Quote: | Stan Brown <the_stan_brown@fastmail.fm> wrote:
The difference (and Cantor's proof, as I remember it) is that you can
imagine an algorithm that, given infinite time, would list every
rational number.
|
No big mystery there -- 0, l/2, l/3, 2/3, l/4, 3/4, l/5, 2/5, 3/5, 4/5,
l/6.... Every fraction (between 0 and l) will be named sooner or later.
There's a way to work in the "improper fractions" as well (the chart
with the zigzag diagonals).
| Quote: | However, even that algorithm would miss the
irrationals -- that's why the count of irrationals is a higher order
of infinity than the count of rationals.
I don't think you really mean that, because you might apply the same
reasoning to odd and even numbers, with the following result:-
... you can imagine an algorithm that, given infinite time, would list
every odd number. However, even that algorithm would miss the
even numbers -- that's why the count of even numbers is a higher order
of infinity than the count of odd numbers.
|
Quite right; I'm afraid that Stan's "However" does not follow. The list
of rational numbers doesn't include any irrationals simply by the way it
is defined. Listng the rationals doesn't say anything about how many
irrationals there are.
--
Best -- Donna Richoux |
|
| Back to top |
|
|
Peter Moylan
Guest
|
| Posted: Mon Nov 29, 2004 6:05 am
Post subject: Re: Brand new colors |
|
|
Bob G infrared:
| Quote: | Actually, if I remember my Math, there are several orders of infinity,
according to a German mathematician, name of Cantor.
|
They're funny things, names. Why wasn't he a singer?
| Quote: | The first order is called "Aleph Null" and an infinite set is said to be of
that ordinality if a one-to-one mapping, or function, can be established
between its members and the set of natural numbers (1,2,3...).
|
[snip]
| Quote: | The set of irrational numbers (those that cannot be expressed as a fraction)
has a higher order of infinity, Aleph One, but don't ask me to prove it.
|
The number of the irrationals is the same as the number of real numbers,
and we call it C, the cardinality of the continuum. There has for yonks
been a conjecture that C is equal to Aleph One, but the last time I
checked this had not yet been proved. To be fair, I should add that it's
a long time since I checked.
[snip again]
| Quote: | A possibly interesting exercise would be to consider the set of all subsets of
the set of integers - would that have ordinality Aleph Null or Aleph One?
|
Definitely Aleph One. As I recall it, that's precisely the definition
of Aleph One. For any N>0, Aleph N is the cardinality of the set of
all subsets of a set with cardinality Aleph (N-1). Or, less formally,
Aleph N is equal to 2 to the power of Aleph(N-1).
--
Peter Moylan peter at ee dot newcastle dot edu dot au
http://eepjm.newcastle.edu.au (OS/2 and eCS information and software) |
|
| Back to top |
|
|
Stan Brown
Guest
|
| Posted: Tue Nov 30, 2004 6:01 am
Post subject: Re: Brand new colors |
|
|
"Alec McKenzie" wrote in alt.usage.english:
| Quote: | Stan Brown <the_stan_brown@fastmail.fm> wrote:
The difference (and Cantor's proof, as I remember it) is that you can
imagine an algorithm that, given infinite time, would list every
rational number. However, even that algorithm would miss the
irrationals -- that's why the count of irrationals is a higher order
of infinity than the count of rationals.
I don't think you really mean that, because you might apply the same
reasoning to odd and even numbers, with the following result:-
... you can imagine an algorithm that, given infinite time, would list
every odd number. However, even that algorithm would miss the
even numbers -- that's why the count of even numbers is a higher order
of infinity than the count of odd numbers.
|
Dang it, you're right.
If I said "even that class of algorithms would miss" I'd probably be
closer, but that's awfully vague.
Time for me to go off and review Cantor's proof.
--
Stan Brown, Oak Road Systems, Tompkins County, New York, USA
http://OakRoadSystems.com
A: Maybe because some people are too annoyed by top-posting.
Q: Why do I not get an answer to my question(s)?
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing? |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Nov 30, 2004 6:02 pm
Post subject: Re: Brand new colors |
|
|
In article <20041128013920.06574.00001221@mb-m15.aol.com>,
Bob G <bobjames27@aol.com> wrote:
| Quote: | How about, take any fraction of an infinite
set of integers and you still have an infinite set?
Actually, if I remember my Math, there are several orders of infinity,
according to a German mathematician, name of Cantor.
The first order is called "Aleph Null" and an infinite set is said to be of
that ordinality if a one-to-one mapping, or function, can be established
between its members and the set of natural numbers (1,2,3...).
For instance, the set of positive even numbers has Aleph Null ordinality
because, for every natural number, the function f(n) = 2n, that is, 1 maps into
2, 2 into 4, and so on, will yield all the even numbers.
The set of irrational numbers (those that cannot be expressed as a fraction)
has a higher order of infinity, Aleph One, but don't ask me to prove it.
It doesn't follow that any subset of the set of integers is "infinite", of
course, as has been pointed out. But it doesn't really make sense to speak of a
"fraction" of that set - you would actually have to specify which "fraction" by
means of a mapping or function and, if it maps all the natural numbers, then it
would be an Aleph Null set.
A possibly interesting exercise would be to consider the set of all subsets of
the set of integers - would that have ordinality Aleph Null or Aleph One?
|
Definitely not Aleph Null, if I understand you right. Cantor also
proved (well, I think it was Cantor) that for any set A, A and its
"power set" (set of all subsets of A) do not have the same cardinality
("size", roughly speaking). The proof is short and similar in spirit
to the proof that the real numbers are uncountable -- you show that
any map from A to its power set "misses" something in the power set.
The details of the proof, though, are -- interesting? mind-twisting?
something. For the curious, this Wikipedia article seems pretty good:
http://en.wikipedia.org/wiki/Cantor's_theorem
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor. |
|
| Back to top |
|
|
Guest
|
| Posted: Tue Nov 30, 2004 6:02 pm
Post subject: Re: Brand new colors |
|
|
In article <mckenzie-388905.16093728112004@news.aaisp.net.uk>,
Alec McKenzie <mckenzie@despammed.com> wrote:
| Quote: | Roland Hutchinson <my.spamtrap@verizon.net> wrote:
Alec McKenzie wrote:
Don Aitken <don-aitken@freeuk.com> wrote:
The wonderful thing about Cantor's proofs is that they can be
explained quite easily. I think I can remember this one; it goes
something like this:
Express every number in the set as a decimal fraction of unlimited
length, padding out the right-hand end with zeroes or nines if
required. Arrange these numbers in the order which their digits
specify.
Now construct a number in the following way: its first digit is
different from the first digit of the first number in the list; its
second digit is different from the second digit of the second number
in the list, and so on. Where is this number in the list? Obviously,
nowhere; it is neither the first, nor the second, nor the third, etc.
So the required mapping is impossible.
Why would that show that "the required mapping is impossible"?
All it would show is that there is a number missing from your list,
which means you had failed to "express every number in the set".
Because a "missing number" can be constructed in this way for any proposed
mapping. Therefore, no proposed mapping can be the required mapping.
Which, to my mind, shows no more than an interesting paradox: that any
list of all the irrational numbers will appear to have at least one
missing.
Here's a thought: express every *rational* number in a list in the same
fashion. The same argument applied to that list would then appear to
prove that the rational numbers also are uncountable, which is untrue.
|
Well, no, because the constructed number *is* a real number, but is
by no means guaranteed to be rational (which it would need to be for
this to be a proof that the rationals are uncountable).
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor. |
|
| Back to top |
|
|
Alec McKenzie
Guest
|
| Posted: Tue Nov 30, 2004 6:03 pm
Post subject: Re: Brand new colors |
|
|
In article <31375iF33987dU7@uni-berlin.de>, blmblm@myrealbox.com wrote:
| Quote: | In article <20041128013920.06574.00001221@mb-m15.aol.com>,
Bob G <bobjames27@aol.com> wrote:
A possibly interesting exercise would be to consider the set of all
subsets of the set of integers - would that have ordinality Aleph
Null or Aleph One?
Definitely not Aleph Null, if I understand you right. Cantor also
proved (well, I think it was Cantor) that for any set A, A and its
"power set" (set of all subsets of A) do not have the same cardinality
("size", roughly speaking). The proof is short and similar in spirit
to the proof that the real numbers are uncountable -- you show that
any map from A to its power set "misses" something in the power set.
The details of the proof, though, are -- interesting? mind-twisting?
something. For the curious, this Wikipedia article seems pretty good:
http://en.wikipedia.org/wiki/Cantor's_theorem
|
To me, Cantor's proof is disturbingly reminiscent of Russell's paradox
concerning the set of all sets that do not include themselves, which is
thereby contradicted by its own definition.
I find the proof unconvincing, because the "missing something" in the
power set turns out to be precisely the subset that consists of those
integers whose mapping does not include that integer. This apparent
contradiction is then used to support the 'proof by contradiction'.
--
Alec McKenzie
mckenzie@despammed.com |
|
| Back to top |
|
|
| |
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in