grunwald@uiuccsb.UUCP (02/18/84)
#N:uiuccsb:9700020:000:1555 uiuccsb!grunwald Feb 17 21:33:00 1984 [ This line does not exist ] This note is intended for my further illumination and is spurred by a deep lack of intuitive understanding of the nature of infinities. The question turns to Cantors diagonalization proof for the existence of uncountably infinite numbers. In particular, the question arises "Why can I not show that the natural numbers can be demonstrated to be uncountably infinite", although I realize this runs rather counter to the definition of the naturals. Let us define a bijection from the naturals such that we reverse the digits of the index, e.g. since 6 = 110 in binary, F(6) = 011. Since we can have leading zeros in the naturals, let us represent 6 = ....000000110, and hence F(6) = 01100000000... Applying the diagonalization proof to these numbers is equivalent to the way one constructs the proof for fractional numbers in binary. The problem is that we construct a "member" of the naturals which is ....1111111xxxx (e.g. an infinite number of leading ones followed by something). Although I realize that this is not a proper member of the naturals, how can this be demonstrate outside the realm of this proof? E.g, it the property of naturals not having an infinite number of digits derived from the Cantor proof or does one have to presuppose it? Sorry if this is rather obvious, but I've not had formal set theory and thus this seemed a little more puzzling than it should be. I've been assured that naturals must be finite length can be demonstrated by other means, but I haven't seen the means. Any takers?
ags@pucc-i (Seaman) (02/18/84)
It has been asked why the Cantor Diagonalization Process cannot be applied to the natural numbers to show that there are uncountably many of them. The basic question reduces to "why can't there be a number of the form ...1111111xyz, with an infinite number of leading ones?" The natural numbers are defined by the Peano Axioms: (1) Zero is a number. (2) The successor of any number is a number. (3) No two distinct numbers have the same successor. (4) Zero is not the successor of any number. (5) Let S be a subset of the numbers which obeys the rules: (a) Zero is in S. (b) The successor of any number in S is also in S. Then S contains all of the natural numbers. Let S be the set of natural numbers whose binary representation has only a finite number of digits. By axiom (5), S is the complete set of natural numbers. Incidentally, the definition of an uncountable set is "one which cannot be placed into one-to-one correspondence with (any subset of) the natural numbers." -- Dave Seaman ..!pur-ee!pucc-i:ags "Against people who give vent to their loquacity by extraneous bombastic circumlocution."
grunwald@uiuccsb.UUCP (02/21/84)
#R:uiuccsb:9700020:uiuccsb:9700021:000:362 uiuccsb!grunwald Feb 21 00:40:00 1984 The definition of Peano numbers seems to be somewhat circular and not really conclusive. Where is the leap where it states that strings of digits must be finite length? Or perhaps by "subset," you mean "strict subset" and not "subset or the entire set?" Dirk Grunwald University of Illinois USENET : ihnp4 ! uiucdcs ! grunwald CSNET : grunwald.uiuc@Rand-Relay
bill@utastro.UUCP (William H. Jefferys) (02/22/84)
How do the Peano axioms guarantee a finite number of digits? The
axiom of induction would guarantee this once you establish the
proposition that (n has a finite number of digits) --> (successor(n)
has a finite number of digits). I don't know if the latter is really
"in" the Peano system or not since it is more a matter of representation
than existence.
--
Bill Jefferys 8-%
Astronomy Dept, University of Texas, Austin TX 78712 (USnail)
{ihnp4,kpno,ctvax}!ut-sally!utastro!bill (uucp)
utastro!bill@ut-ngp (ARPANET)ags@pucc-i (Seaman) (02/22/84)
> The definition of Peano numbers seems to be somewhat circular and not really > conclusive. Where is the leap where it states that strings of digits must be > finite length? > > Or perhaps by "subset," you mean "strict subset" and not "subset or the entire > set?" The Peano axioms are concerned with three primitive concepts: zero, number, and successor. To say that these three concepts are "primitive" means that we do not attempt to define what they mean. In fact, it is possible to interpret these concepts in more than one way. All that is required is that whatever meaning we eventually attach to the three primitive concepts must be consistent with the axioms. This is how circularity is avoided in mathematics: there are some things we simply do not define. There is nothing in the axioms about the representation of numbers in terms of digits. It is fairly easy to show that a model for the integers can be constructed by using finite digit strings to stand for "numbers", with the appropriate meanings of "zero" and "successor". In particular, "2" stands for "the successor of the successor of zero," etc. You can even build different models for the different number bases. Every time you change the underlying base, you change the meanings of "number" and "successor". In base ten, "101" is a number whose successor is "102". In base two, "101" is an entirely different number, whose successor is "110"; "102" is not a number at all. Both number systems satisfy the Peano axioms and are equally good models for the natural numbers. The "leap" which states that strings of digits must be of finite length depends only on the following assertion: "Let K be a digit string of finite length. Then the successor of K is also a digit string of finite length." This assertion is certainly true of the conventional representations of integers, using any base N. Look again at the fifth Peano axiom: (5) Let S be a subset of the numbers which obeys the rules: (a) Zero is in S. (b) The successor of any number in S is also in S. Then S contains all of the natural numbers. The finite digit strings represent a subset S which satisfies properties (a) and (b). The axiom says that there is nothing else -- S contains all of the natural numbers. Therefore no infinite digit strings can possibly represent natural numbers in a model of this type (i.e. the conventional ways of representing numbers in various bases). If you like, it is perfectly possible to model the numbers in a different way, so that infinite digit strings are possible. For example: (1) Zero is defined to be the string "000...", consisting of an infinite number of zeros. (2) A "number" is any string of the form "[111...1]000...", consisting of a finite string of ones (possibly empty), followed by an infinite string of zeros. (3) The "successor" of "[111...1]000..." is "111...1]1000...", where the number of ones has been increased by one. It is easy to see that these interpretations of "zero," "number," and "successor" are consistent with the Peano axioms, and therefore we have another model for the natural numbers. By the way, I used terms like "zero" and "one" in describing the model. This is not a circular definition. In fact, it is not a "definition" at all. I am merely using our conventional meanings of "zero" and "one" to describe a new model, then showing that the model is consistent with the Peano axioms. -- Dave Seaman ..!pur-ee!pucc-i:ags "Against people who give vent to their loquacity by extraneous bombastic circumlocution."
grunwald@uiuccsb.UUCP (02/23/84)
#R:uiuccsb:9700020:uiuccsb:9700022:000:1384
uiuccsb!grunwald Feb 22 12:33:00 1984
Here's the best answer I've recieved so far. A couple of other people sent mail
which had somewhat circular arguments. Thanks to all who responded to this
Dirk Grunwald
ihnp4 ! uiucdcs ! grunwald
--------------------------------------------------------------------------------
From: ihnp4!allegra!sdcrdcf!trwrb!pearlman
Date: Tuesday, 21 Feb 1984 18:10-PST
To: sdcrdcf!allegra!ihnp4!inuxc!pur-ee!uiucdcs!uiuccsb!grunwald
Subject: Cantor proof (net.math article)
Hi --
You asked why a version of Cantor's diagonal proof could not be
used to show that the natural numbers weren't uncountably infinite.
If M is the number "left out" of the ordering, you can prove that
M is not a natural number by contradiction:
Let n be any natural number. Then n < 2**n, by induction:
For n = 1, it's trivial:
1 < 2 = 2**1
If it's true for n, then it's true for n+1:
2**(n+1) = 2(2**n)
= 2**n + 2**n
n < 2**n, and 1 < n < 2**n, so
n+1 < 2**(n+1)
Let M be the number "left out" of your ordering. You've admitted
that M has an infinite number of leading ones, so M must be greater
than 2**n for any natural n. Thus, if M is a natural number, then
M > 2**M, which is a contradiction.
"Trust me -- I was a math major"
-- Laura
...{sdcrdcf, ucbvax, decvax}!trwrb!pearlman
--------------------------------------------------------------------------------csc@watmath.UUCP (Computer Sci Club) (02/23/84)
The replies to the net discussing the question of Cantors diagonalization
proof apllied to the whole numbers have all been adressed to the question
"Can a whole number have an infinite number of non zero digits", and have
shown that the answer is no. This invalidates the "proof" as applied to
the whole numbers, as we do not know whether or not the sequence of
zero's and ones created by the diagonalization process has a finite number
of ones. (The statement was made that M, the sequence created, would have
an infinite number of leading ones. This is only true if the usual ordering
of the whole numbers is used, but the sequence might start
100000000 ...
010000000 ...
000000000 ...
110000000 ...
100010000 ...
.
.
.
in which case M would start 00110) I here provide a proof that the number of
1's in the sequence M is infinite.
Let the ordering of the whole numbers be represented by a function f.
(i.e. f(0) is the first number in the sequence, f(1) the second etc.).
As all the whole numbers must appear f must be a bijection, i.e. if a is
a whole number then there exists b with f(b)=a. Now let us assume
the sequence M has a finite number of ones, then there exists N (N>3), such
that for all n>N the nth element of M is zero. Then (n>N) f(n) must
have a one in the nth position, ie f(n) => 2**N. Hence all numbers
c < 2**N must equal f(d) d < N. Now there are 2**N whole numbers
less than 2**(N) (don't forget zero). These cannot all fit into
N positions as N < 2**N. Therefore M must contain an infinite number
of ones.
William Hughes