August 13th, 2016, 10:51 AM  #141  
Senior Member Joined: Aug 2012 Posts: 860 Thanks: 160  Quote:
Quote:
Quote:
The set of all binary strings is what we're talking about. It includes both the strings that can be described by algorithms ("Start with 1 then alternate 0's and 1's," or "The decimal part of pi in binary") plus all the strings that have no algorithmic description. Quote:
Quote:
Quote:
Quote:
Let C be the set of all bitstrings that can be described or generated by an algorithm. An algorithm is a finitelength string of symbols, like "Alternate 0's and 1's" or "Pi minus 3 in binary." That set of bitstrings is countable. It's missing all the random bitstrings. It's a tiny subset of all the bitstrings Cantor considered. I don't know where JeffJo got the idea to restrict bitstrings like this. [Why countable? If our alphabet for writing down algorithms is at most countable, there are only countably many algorithms of length 1; countably many of length 2; dot dot dot. Countable union of countable sets is countable. Hence there are only countably many algorithms]. Now since C is countable we can enumerate it and form the antidiagonal. Since the antidiagonal is not on the list, it's not in C. Therefore the antidiagonal is NOT finitely expressible. But the procedure for forming the antidiagonal ("change the nth digit of the nth string") is obviously a simple algorithm. So something went wrong earlier. Evidently (this is the murky part) the bijection itself can not be finitely describable. The bijection itself is not part of our finitelydescribable universe. So Cantor's argument doesn't apply. A constructivist will not allow us to form the bijection even though C is countable. Constructivist mathematicians (of which there are some) have to jump through hoops to get math to work. It's a tremendous limitation to demand that everything is finitely describable. But then again, in standard math we posit the existence of things we cannot possibly construct. So philosophically the constructivists have a point. Last edited by Maschke; August 13th, 2016 at 11:17 AM.  
August 13th, 2016, 11:22 AM  #142 
Senior Member Joined: May 2016 From: USA Posts: 470 Thanks: 198 
I did read the article. I do see that there are logical or at least very serious semantic difficulties using the word "constructable" in the context of Cantor's proof. The only thing that I ever said was constructable (even then not intending to imply anything about physical time and space) was the antidiagonal itself because, although the number of steps is endless, the procedure for each step can be completely and finitely specified. I don't think I shall completely reject "imaginable" because if we are talking about something we necessarily are referring to something in either our imaginations or the physical world. Since I don't believe in the physical existence of infinities, I need some word to characterize concepts that have and never have had any physical existence. But this is not a math argument; in fact it is not worth having an argument about at all. Again I appreciate your taking the time to clarify for me what your position is despite having done it before. Maybe this time I shall retain it. 
August 13th, 2016, 12:01 PM  #143  
Senior Member Joined: Aug 2012 Posts: 860 Thanks: 160  Quote:
However, this is not an algorithm. That's because it never terminates in finitely many steps. We have to carry out infinitely many steps in order to arrive at the final result. When we talk about definability or computability, we are required to get our result in finitely many steps. For example Euclid's algorithm to find the GCD of two integers terminates after finitely many steps. Quote:
With your telescoping intervals idea, we can indeed describe an infinitary procedure with finitely many symbols, but the algorithm never terminates (unless we happened to start with a finite binary expression). Your algorithm never halts to produce an answer in a finite number of steps. This is a good point. I hope I haven't confused this issue further but I do see what you are getting at. Note that to say a real number is computable means that we have an algorithm that cranks out the nth digit after a finite number of steps. Of course if we allowed infinitary procedures that took infinitely many steps we could indeed describe all the real numbers, not just the computable ones, in exactly the manner you indicate. I think I understand your point now. You are not restricting to computable numbers, you are allowing the full set of standard real numbers. Those can not all be described by (finitary) algorithms; even though there is an infinitary procedure to locate any point by halving intervals. Am I understanding you correctly now? If so, then we're all in agreement on Cantor's proof. In fact if you are reading Cantor's original papers I can see exactly where your idea came from, since Cantor's original proof of the uncountability of the reals used nested intervals exactly as you have. Conclusion: If by constructible you mean an infinitary process of telescoping intervals, we are in agreement that we're all talking about the standard set of ALL possible binary sequences, for which Cantor's proof is valid. But if you are meaning constructible in the limited sense of a (finitely terminating) algorithm, we still have trouble ... Last edited by Maschke; August 13th, 2016 at 12:19 PM.  
August 13th, 2016, 08:12 PM  #144  
Math Team Joined: Dec 2013 From: Colombia Posts: 6,394 Thanks: 2101 Math Focus: Mainly analysis and algebra  Quote:
The problem as I understand it is that although we can order all sets of instructions by length, and then lexically, we cannot know which of these sets of instructions are valid algorithms. In particular, by Turing's Halting Problem, we don't know which of these sets of instructions will end and which of them will not. We therefore have a problem in that our diagonal string is not well defined because we don't know whether the $n$th algorithm will ever produce an $n$th digit. I suspect that what we are dealing with here is the difference between a set being "countable" (i.e. that there exists an injection from it to the natural numbers) and a set being "computably enumerable" (i.e. there exists an algorithm that enumerates the members of the set). This is a pretty subtle existence problem. Mathematically, since all the possible sets of instructions are countable, any subset of them is countable. In particular, the subset containing all algorithms is countable. We know this because there exists an injection $f$ from the set of instructions to the natural numbers and we create an injection from the subset containing all algorithms simply by restricting the domain of $f$. But that does not mean that we have any practical (or even theoretical) way of actually carrying out this restriction of the domain to exhibit the injection from the subset containing the algorithms to the natural numbers. And this is the key point, because Cantor requires us to enumerate elements of $T$ and he creates his antidiagonal using this enumeration. The fact that the enumeration is not computable means that the antidiagonal is not a member of $T$ because it is not computable. Thus Cantor is unable to tell us that the computable numbers are uncountable (thankfully). References: Wikipedia: Computable Numbers  Countable but Not Computably Enumerable Stack Exchange: Is there such a thing as a countable set with an uncountable subset? Wikipedia: Recursively Enumerable Set Wikipedia: Enumeration in Computability Theory  
August 14th, 2016, 06:15 AM  #145  
Senior Member Joined: Apr 2015 From: Planet Earth Posts: 111 Thanks: 20  Quote:
Quote:
The set of natural numbers can be defined as a set that contains the number 1 and, if it contains the number n, it also contains n+1. This fails you definition of definability, yet it is the concept behind the Axiom of Infinity. Without it, we can't even show that the natural numbers N are countable, so any discussion of whether another infinite set is, or is not, countable is complete nonsense.  
August 14th, 2016, 07:19 AM  #146 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,394 Thanks: 2101 Math Focus: Mainly analysis and algebra 
The set of natural numbers shouldn't be considered to "never terminate". It's a set, an unmoving object. It has neither beginning nor end. This is distinct from the concept of a sequence which does start and may (finite) or may not (infinite) terminate. The concept of computability is set out in Wiki (see links above). The algorithm must be finite, but also needs only to approximate the required number to any given accuracy in that finite number of steps. The idea of definability is that a number can be completely and uniquely specified even if an infinite number of steps are necessary. However, the definition must contain only finitely many characters or symbols. Last edited by skipjack; August 14th, 2016 at 11:51 AM. 
August 14th, 2016, 07:50 AM  #147 
Senior Member Joined: Aug 2012 Posts: 860 Thanks: 160  Yes thanks, I should not have mentioned definability in my response to JeffJo.

August 14th, 2016, 07:40 PM  #148  
Banned Camp Joined: Jun 2014 From: Earth Posts: 945 Thanks: 191  Quote:
"Normally, the term infinite sequence refers to a sequence that is infinite in one direction, and finite in the otherâ€”the sequence has a first element, but no final element. Such a sequence is called a singly infinite sequence or a onesided infinite sequence when disambiguation is necessary. In contrast, a sequence that is infinite in both directionsâ€”i.e. that has neither a first nor a final elementâ€”is called a biinfinite sequence, twoway infinite sequence, or doubly infinite sequence. A function from the set Z of all integers into a set, such as for instance the sequence of all even integers ( â€¦, âˆ’4, âˆ’2, 0, 2, 4, 6, 8â€¦ ), is biinfinite. " Source: https://en.wikipedia.org/wiki/Sequence . Last edited by Math Message Board tutor; August 14th, 2016 at 07:44 PM.  

Tags 
argument, cantor, diagonal, infinity, number 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cantor's Diagonal Argument  zylo  Math  22  January 26th, 2016 09:05 PM 
Help! Cantor's Diagonal Argument  mjcguest  Applied Math  9  July 25th, 2013 07:22 AM 
Cantor´s diagonal argument  netzweltler  Applied Math  191  November 7th, 2010 02:39 PM 
Cantor's diagonal argument  "disproof"  Reckhard  Abstract Algebra  11  July 31st, 2010 12:05 PM 
Cantor diagonal functions  Barbarel  Number Theory  2  April 10th, 2009 02:59 PM 