From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Tue Mar 20 11:29:50 2007 Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2KFTorv020949 for ; Tue, 20 Mar 2007 11:29:50 -0400 (EDT) Received: from front1.acsu.buffalo.edu (upfront.acsu.buffalo.edu [128.205.4.140]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KFTesG050592 for ; Tue, 20 Mar 2007 11:29:40 -0400 (EDT) Received: (qmail 394 invoked from network); 20 Mar 2007 15:29:39 -0000 Received: from mailscan7.acsu.buffalo.edu (128.205.6.158) by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:39 -0000 Received: (qmail 868 invoked from network); 20 Mar 2007 15:29:38 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:38 -0000 Received: (qmail 20759 invoked from network); 20 Mar 2007 15:29:31 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 15:29:31 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3953941 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 11:29:31 -0400 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 10620 invoked from network); 20 Mar 2007 15:29:30 -0000 Received: from mailscan1.acsu.buffalo.edu (128.205.6.133) by listserv.buffalo.edu with SMTP; 20 Mar 2007 15:29:30 -0000 Received: (qmail 3768 invoked by uid 60001); 20 Mar 2007 15:29:25 -0000 X-Mailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11 MIME-Version: 1.0 Content-Type: text/plain; charset=Big5-HKSCS Content-Transfer-Encoding: 8bit X-Originating-IP: 72.88.52.205 X-UB-Relay: (internal) X-PM-EL-Spam-Prob: X: 18% Message-ID: <1174404565.45fffdd56ec67@mail1.buffalo.edu> Date: Tue, 20 Mar 2007 11:29:25 -0400 Reply-To: nhj@BUFFALO.EDU Sender: "Philosophy of Computer Science, Spring 2007" From: Nicolas Jackson Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (deliverance.acsu.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_00, MANY_EXCLAMATIONS,SUBJ_ALL_CAPS autolearn=no version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 3597 I used to think I understood Cantor's diagonalization proof for the uncountability of the reals, but now I'm not so sure. Specifically, I am not convinced that diagonalizing over an infinite set is valid. I know Godel, Cantor, and Turing knew what they were doing, so I'd apretiate it if anyone could tell me where I'm going wrong. It seems to me that it is possible to make a diagonalization argument with all true premises and a false conclusion (so diagonalization is invalid). Specifiacally I don't see why Cantor's diagonal argument for the uncountability of the reals can't be used to demonstate that the countable numbers are uncountable by just "flipping" the digits over the decimal point. I'll use Chaitin's phrasing of the argument to demonstrate: Suppose we have a list of all the countable numbers. Let d(i,j) be the jth digit of the ith number in the list. Let our representation of each countable number be preceeded by an infinite number of 0's so that the function is N^2->{0,1,2,3,4,5,6,7,8,9}. So if our list is 1, 2, 3, 4, 5, etc. (the most obvious ordering of the countable numbers) d(1,1)=1, d(563,2)=6, d(1,2)=0, and d(1,x)=0 for all x>1. Consider the countable number n whose kth digit is defined as 4 if d(k,k)=3 and 3 otherwise. In other words, we form n by taking all the digits on the diagonal of the list of all reals, and then changing each of these diagonal digits. (Note that the diagonal in this argument goes from the top right of the matrix to the bottom left instead of from the top left to the bottom right, though this is trivial (I think) since we could just redifine d or n to use the other diagonal. I did it this way because I think it is simpler and clearer.) The countable number n differs from the ith real in this presumably complete list of all countable numbers because their ith digits are different. Therefore this list cannot be complete, and the set of countable numbers is uncountable. Q.E.D. This is, obvoiusly, a problem. The reason why diagonalization is invalid seems to me to be that one cannot actually construct the infinitely long real r (or countable number n) in a finite amount of time. At any time t (lets say that it takes one unit of time to find one digit of r or n) we have a real r (or a countable number n) that is not in the ordering of reals (or countable numbers) numbered 1 to t, but absolutely is in the interval of reals (or countable numbers) from t off to infinity. I apologize for writing such a long email. I tried to make it as brief as possible while still making a complete thought on the issue. Anything shorter would just lead to confussion. I hope someone will take the time to read this and set me straight (or, I guess, diagonal ;). Nicolas Jackson Quoting "William J. Rapaport" : ------------------------------------------------------------------------ > | > > | > In class today, we discussed the similarities of the argument > that an > | > interaction machine can be simulated by a finite number of TMs to > the > | > argument that there are an infinite number of real numbers, hence > that > | > there are unnameable reals. > | > > | > If you're interested in following up on some of these ideas, > here's an > | > interesting and even readable(!) paper by a well-known > theoretician of > | > computation: > | > > | > Chaitin, Gregory (2006), > | > "How Real Are Real Numbers?", > | > International Journal of Bifurcation and Chaos > | > > | > PDF: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/olympia.pdf > | > html: http://tinyurl.com/2eh7tj > | > > | > > > From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Tue Mar 20 13:58:44 2007 Date: Tue, 20 Mar 2007 13:58:16 -0400 From: Albert Goldfain Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Interesting post Nick! In general, there are some very deep issues with real numbers in mathematics and it is not surprising that these come out in the diagonalization argument. Not to disregard the bulk of your email, but here's what I believe to be the crux of your complaint: > The reason why diagonalization is invalid seems to me to be that one > cannot actually construct the infinitely long real r (or countable > number n) in a finite amount of time. At any time t (lets say that it > takes one unit of time to find one digit of r or n) we have a real r (or > a countable number n) that is not in the ordering of reals (or countable > numbers) numbered 1 to t, but absolutely is in the interval of reals (or > countable numbers) from t off to infinity. And here's my two cents: The real r is constructed step-by-step by switching the diagonal digit in the (allegedly exhaustive) list of reals. I believe what it means to say that a real number is "constructable" is simply that we know at each step how to "construct" the next digit of the number even if we don't have time to finish such a construction (Do you mean something very different in your use of "construction" than "computation"?). Under this characterization r is constructable. However, there are several issues regarding the validity of arguments that refer to arbitrary reals. One of the problems is how to refer to the reals we don't have names for (or may be un-nameable). I recently read the following paper (see attached) which you may find useful: Martino, Enrico (2001), "Arbitrary Reference in Mathematical Reasoning", Topoi 20: 65-77. The reals are partitioned into the rationals and irrationals. Each rational can be expressed as an integer divided by a non-zero integer. Any integer can be "named" in a finite time and, thus, so can any rational (although this time might be quite large). *SOME* irrationals can be referred to in a finite time. For example: "pi is the ratio of the circumference of any circle to its diameter." Clearly this utterance refers to pi in a finite time, but can it "name" pi without printing out its digits? Perhaps you are willing to allow some irrationals to be named by reference? ----------------------------------------------------------------------- I think a lot of people are disregarding the Accelerating Turing Machine as a logical (yet perhaps physically impossible) way of dealing with the infinite length of numbers like pi and the diagonalized r. So here is an attempt to mutate the accelerating TM into Zeno's paradox (buckle up :)): Try to poke a hole in this argument: P1. I want to write the digits of pi and I have an algorithm for precisely computing the next digit of pi from previous digits (such algorithms *do* exist). P2. I can start in the middle of a room and write the number 3 and '.' on the floor. P3. I can walk halfway towards the wall and write the number 1 on the floor. P4. I can walk halfway towards the wall and write the number 4 on the floor. P5. I can keep walking halfway towards the wall and writing the next number of pi on the floor. P6. I will have written pi once I reach the wall. P7. I can reach the wall by walking from the center of the room to the wall (I have done this before :-)). C. Thus I can write down all of the digits of pi. There are some space problems with P5 and an even bigger issue of whether I can reach the wall if I augment my walking procedure with this stop-and-write-a-digit step. So now consider the following (better) argument: P1. I want to THINK of each digit of pi and I have MEMORIZED an algorithm for precisely computing the next digit of pi from previous digits (such algorithms *do* exist). P2. I can start in the middle of a room and think of the number 3 and a '.'. P3. I can walk halfway towards the wall and think of the number 1. P4. I can walk halfway towards the wall and think of the number 4. P5. I can keep walking halfway towards the wall and thinking of the next digit of pi. P6. I will have thought of all the digits of pi once I reach the wall. P7. I can reach the wall by walking from the center of the room to the wall (I have done this before :-)). C. Thus I can think of all of the digits of pi. Now since my motion to the wall *is* possible, this would require my thought to accelerate as I think of the digits...however, without seeing the contents of my brain, how do you know I am not thinking of all of the digits of pi each time I walk to a wall? :) [suppose also that I can forget as many previous digits as necessary to attend to the current one I am computing]. I guess I answered with a pretty long post myself...sorry...but some interesting stuff to think about. Albert From owner-cse584-sp07-list@LISTSERV.BUFFALO.EDU Tue Mar 20 16:02:53 2007 Received: from ares.cse.buffalo.edu (ares.cse.Buffalo.EDU [128.205.32.79]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2KK2rT8003307 for ; Tue, 20 Mar 2007 16:02:53 -0400 (EDT) Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KK2iMc070641 for ; Tue, 20 Mar 2007 16:02:44 -0400 (EDT) Received: (qmail 10204 invoked from network); 20 Mar 2007 20:02:44 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:44 -0000 Received: (qmail 5869 invoked from network); 20 Mar 2007 20:02:41 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:41 -0000 Received: (qmail 16977 invoked from network); 20 Mar 2007 20:02:22 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:22 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3968059 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 16:02:22 -0400 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 16598 invoked from network); 20 Mar 2007 20:02:21 -0000 Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by listserv.buffalo.edu with SMTP; 20 Mar 2007 20:02:21 -0000 Received: (qmail 821 invoked by uid 60001); 20 Mar 2007 20:02:17 -0000 References: <1174404565.45fffdd56ec67@mail1.buffalo.edu> X-Mailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11 MIME-Version: 1.0 Content-Type: text/plain; charset=Big5-HKSCS Content-Transfer-Encoding: 8bit X-Originating-IP: 72.88.52.205 X-UB-Relay: (internal) X-PM-EL-Spam-Prob: X: 18% Message-ID: <1174420937.46003dc994ed2@mail1.buffalo.edu> Date: Tue, 20 Mar 2007 16:02:17 -0400 Reply-To: nhj@BUFFALO.EDU Sender: "Philosophy of Computer Science, Spring 2007" From: Nicolas Jackson Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! Comments: To: Albert Goldfain To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU In-Reply-To: Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (deliverance.acsu.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00, MANY_EXCLAMATIONS autolearn=unavailable version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: R Content-Length: 3229 Thanks for the reply Albert. It's helping flush out exactly what my objections are. Albert said: >I believe what it means to say that a real number is >"constructable" is simply that we know at each step >how to "construct" the next digit of the number even >if we don't have time to finish such a construction That is how I understand "constructable" and "computable" to be defined in the literature and in class. My objection is that in the case of constructing the real r it is not that we don't have time to finish the number but that there is no such thing as enough time to finish it. What's more, I am not sure I believe such an r exists since at any time k r is different than all reals preceding k, but there is no compelling reason to believe that r is not in the infinite number of reals succeeding k. Another problem I have is that if you allow for constructions that take an infinite amount of time it seems that one can construct a list of all reals. Is this naming them since it is just a list of all of them and it cannot really be used (until after it is constructed, i.e. infinite time from now) to identify a particular one? The algorithm is as follows. 1.Write a decimal point 2.For(i=1;i; Tue, 20 Mar 2007 16:02:53 -0400 (EDT) Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2KK2iMc070641 for ; Tue, 20 Mar 2007 16:02:44 -0400 (EDT) Received: (qmail 10204 invoked from network); 20 Mar 2007 20:02:44 -0000 Received: from mailscan3.acsu.buffalo.edu (128.205.6.135) by front3.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:44 -0000 Received: (qmail 5869 invoked from network); 20 Mar 2007 20:02:41 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front1.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:41 -0000 Received: (qmail 16977 invoked from network); 20 Mar 2007 20:02:22 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 20 Mar 2007 20:02:22 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3968059 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 16:02:22 -0400 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 16598 invoked from network); 20 Mar 2007 20:02:21 -0000 Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by listserv.buffalo.edu with SMTP; 20 Mar 2007 20:02:21 -0000 Received: (qmail 821 invoked by uid 60001); 20 Mar 2007 20:02:17 -0000 References: <1174404565.45fffdd56ec67@mail1.buffalo.edu> X-Mailer: University at Buffalo WebMail Cyrusoft SilkyMail v1.1.11 MIME-Version: 1.0 Content-Type: text/plain; charset=Big5-HKSCS Content-Transfer-Encoding: 8bit X-Originating-IP: 72.88.52.205 X-UB-Relay: (internal) X-PM-EL-Spam-Prob: X: 18% Message-ID: <1174420937.46003dc994ed2@mail1.buffalo.edu> Date: Tue, 20 Mar 2007 16:02:17 -0400 Reply-To: nhj@BUFFALO.EDU Sender: "Philosophy of Computer Science, Spring 2007" From: Nicolas Jackson Subject: Re: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! Comments: To: Albert Goldfain To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU In-Reply-To: Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (deliverance.acsu.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-1.8 required=5.0 tests=AWL,BAYES_00, MANY_EXCLAMATIONS autolearn=unavailable version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2880/Tue Mar 20 01:04:21 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: RO Content-Length: 3229 Thanks for the reply Albert. It's helping flush out exactly what my objections are. Albert said: >I believe what it means to say that a real number is >"constructable" is simply that we know at each step >how to "construct" the next digit of the number even >if we don't have time to finish such a construction That is how I understand "constructable" and "computable" to be defined in the literature and in class. My objection is that in the case of constructing the real r it is not that we don't have time to finish the number but that there is no such thing as enough time to finish it. What's more, I am not sure I believe such an r exists since at any time k r is different than all reals preceding k, but there is no compelling reason to believe that r is not in the infinite number of reals succeeding k. Another problem I have is that if you allow for constructions that take an infinite amount of time it seems that one can construct a list of all reals. Is this naming them since it is just a list of all of them and it cannot really be used (until after it is constructed, i.e. infinite time from now) to identify a particular one? The algorithm is as follows. 1.Write a decimal point 2.For(i=1;i; Tue, 20 Mar 2007 20:03:48 -0400 (EDT) Received: from front3.acsu.buffalo.edu (coldfront.acsu.buffalo.edu [128.205.6.89]) by ares.cse.buffalo.edu (8.13.6/8.13.6) with SMTP id l2L03Gll085373 for ; Tue, 20 Mar 2007 20:03:16 -0400 (EDT) Received: (qmail 27772 invoked from network); 21 Mar 2007 00:03:16 -0000 Received: from mailscan8.acsu.buffalo.edu (128.205.7.55) by front3.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:16 -0000 Received: (qmail 11644 invoked from network); 21 Mar 2007 00:03:15 -0000 Received: from deliverance.acsu.buffalo.edu (128.205.7.57) by front2.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:15 -0000 Received: (qmail 26814 invoked from network); 21 Mar 2007 00:03:13 -0000 Received: from listserv.buffalo.edu (128.205.7.35) by deliverance.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:13 -0000 Received: by LISTSERV.BUFFALO.EDU (LISTSERV-TCP/IP release 14.5) with spool id 3975768 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 20:03:13 -0400 Delivered-To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Received: (qmail 14753 invoked from network); 21 Mar 2007 00:03:13 -0000 Received: from mailscan6.acsu.buffalo.edu (128.205.7.95) by listserv.buffalo.edu with SMTP; 21 Mar 2007 00:03:13 -0000 Received: (qmail 7716 invoked from network); 21 Mar 2007 00:03:12 -0000 Received: from castor.cse.buffalo.edu (128.205.32.14) by smtp3.acsu.buffalo.edu with SMTP; 21 Mar 2007 00:03:12 -0000 Received: from castor.cse.Buffalo.EDU (rapaport@localhost [127.0.0.1]) by castor.cse.Buffalo.EDU (8.13.6/8.12.10) with ESMTP id l2L03CXC012174 for ; Tue, 20 Mar 2007 20:03:12 -0400 (EDT) Received: (from rapaport@localhost) by castor.cse.Buffalo.EDU (8.13.6/8.12.9/Submit) id l2L03CQ9012173 for CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU; Tue, 20 Mar 2007 20:03:12 -0400 (EDT) X-UB-Relay: (castor.cse.buffalo.edu) X-PM-EL-Spam-Prob: : 7% Message-ID: <200703210003.l2L03CQ9012173@castor.cse.Buffalo.EDU> Date: Tue, 20 Mar 2007 20:03:12 -0400 Reply-To: "William J. Rapaport" Sender: "Philosophy of Computer Science, Spring 2007" From: "William J. Rapaport" Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! To: CSE584-SP07-LIST@LISTSERV.BUFFALO.EDU Precedence: list List-Help: , List-Unsubscribe: List-Subscribe: List-Owner: List-Archive: X-UB-Relay: (castor.cse.buffalo.edu) X-DCC-Buffalo.EDU-Metrics: castor.cse.Buffalo.EDU 1335; Body=0 Fuz1=0 Fuz2=0 X-Spam-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00, MANY_EXCLAMATIONS,SUBJ_ALL_CAPS autolearn=no version=3.1.7 X-Spam-Checker-Version: SpamAssassin 3.1.7 (2006-10-05) on ares.cse.buffalo.edu X-Virus-Scanned: ClamAV 0.88.6/2883/Tue Mar 20 18:49:34 2007 on ares.cse.buffalo.edu X-Virus-Status: Clean Status: RO Content-Length: 4575 Nicolas wrote: | Date: Tue, 20 Mar 2007 11:29:25 -0400 | From: Nicolas Jackson | Subject: UNCOMPUTABLE REAL NUMBERS MAY BE HAZARDOUS TO YOUR HEALTH! AND MIND! | | ... | Suppose we have a list of all the countable numbers. Here's my first problem. What do you mean by a "countable" number? >From the rest of your posting, it seems as if you mean "natural" number; is that right? (There's no such thing as a "countable" number. There are the naturals: 1, 2, 3, ... the non-negative integers: 0, 1, 2, 3, ... the integers: ... -3, -2, -1, 0, 1, 2, ... the rationals, the reals, the complex. A set of numbers is countable iff it can be put into 1-1 correspondence with the naturals, i.e, iff it can be counted. | Let d(i,j) be the | jth digit of the ith number in the list. Let our representation of each | countable number be preceeded by an infinite number of 0's so that the | function is N^2->{0,1,2,3,4,5,6,7,8,9}. So if our list is 1, 2, 3, 4, 5, | etc. (the most obvious ordering of the countable numbers) d(1,1)=1, | d(563,2)=6, d(1,2)=0, and d(1,x)=0 for all x>1. Another problem or two: You say that d(1,2)=0, i.e., that the 2nd digit of the first number on the list is 0. The first number on your list is 1; it has no second digit. So your definition of d is not clear to me. Moreover, if my interpretation is correct, then note that d(1,2)=d(10,2); I don't know if that's important or not. But you also say that you want each number to be preceeded by an infinite string of 0s. In that case, how do you manage to talk about the "first" digit? | Consider the countable number n whose kth digit is defined as 4 if | d(k,k)=3 and 3 otherwise. In other words, we form n by taking all the | digits on the diagonal of the list of all reals, and then changing each | of these diagonal digits. If we just use the natural numbers in their standard ordering: 1 2 3 ... 10 11 ... 13848759 ... and interpret your d function as I have interpreted it above, then n=33333333.... (maybe with an occasional 4 somewhere in there, but I doubt it). But note that either n is not a natural number, because it'll have an infinite number of digits, so it wouldn't be on the list anyway, or else n is finite, in which case we know that it's on the list (by the way the list was defined). | (Note that the diagonal in this argument goes | from the top right of the matrix to the bottom left instead of from the | top left to the bottom right, though this is trivial (I think) since we | could just redifine d or n to use the other diagonal. I did it this way | because I think it is simpler and clearer.) I'm afraid I don't understand this. Or are you thinking of the list as right-justified, like this: 1 2 ... 10 11 ... 398475 ... I don't see how this changes things. | The countable number n differs from the ith real in this presumably | complete list of all countable numbers because their ith digits are | different. Therefore this list cannot be complete, and the set of | countable numbers is uncountable. Q.E.D. This is, obvoiusly, a problem. No--don't forget that unlike Cantor's diagonal argument, each number on your list is finite. So when n is created, it will match some number on the list IF it's finite (and if it isn't, then we already knew it wasn't on the list, because it can't be a natural number). | The reason why diagonalization is invalid seems to me to be that one | cannot actually construct the infinitely long real r (or countable | number n) in a finite amount of time. Ah, but that's bringing into mathematics the limitations of time and space, which are not normally brought in. Real, physical systems might be subject to these limitations, but math isn't. At least, classical math isn't. There is, however, a kind of math called "intuitionistic" math that only recognizes mathematical entities that can be thought of by humans, hence that have some spatio-temporal limitations. To find out more about this kind of math (which, by the way, doesn't allow you do to calculus!), take a look at: Benacerraf, Paul; & Putnam, Hilary (yes--that Hilary Putnam, the one who thinks that anything can implement an FSA) (1964), Philosophy of Mathematics: Selected Readings (Englewood Cliffs, NJ: Prentice Hall). You're not alone in your doubts about these infinite methods, but I don't think that your argument above is clear enough to challenge them (yet).