June 20th, 2017, 08:23 PM  #21  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
Proving that $s$ is computable is to prove that $x$ is computable also, but if $x$ is computable then $x$ is in the list so Cantor's diagonal argument must be faulty. We can't say Cantor's diagonal argument is faulty, so we must accept that $s$ is not computable.  
June 20th, 2017, 08:30 PM  #22 
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Given an enumeration $t_i$ of all the computable numbers, then we can work backwords ($f^{1}$, or antizigzag to try use your terminology) to create the number $s$. There are uncountably many such numbers $s$, which is what I noted with my set A, because there uncountably many ways to rearrange the listing $t_i$.

June 20th, 2017, 08:34 PM  #23  
Senior Member Joined: Aug 2012 Posts: 1,527 Thanks: 364  Quote:
Which part of everything else that I'm writing are you not reading or not understanding or regarding as not coherent enough to merit a response? Given an enumeration of the computable reals, we antizigzag it to work back to a computation of the enumeration. Why doesn't this argument work? We KNOW it's wrong, we agree with that. But where exactly is the flaw? I believe there is some understanding to be had in answering this question. I can not quite visualize or grasp the corresponding situation in the inverse case. Given a settheoretic enumeration, why can't I antizigzag to compute the enumeration? You keep saying, "Because we know we can't." Right. Now ask yourself WHY the antizigzag argument fails. Also I think there is confusion between: * Why the antidiag of an enumeration of ALL computables can't be computable; and * Why my antizigzag argument fails. These two are related, essentially the same question, but we have not grokked exactly why they are the same question. Last edited by Maschke; June 20th, 2017 at 08:38 PM.  
June 20th, 2017, 08:36 PM  #24  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
Added bonus: Cantor provided only one antidiagonal in his classic proof, but there are uncountably many ways to create antidiagonals (where all that is needed to create an antidiagonal in this sense is to ensure that at least one, but possibly more, bits of the antidiagonal differ from some bits of each element of a listing). Demonstrating that there are uncountably many computable antidiagonals should be impossible too. This is ultimately what I've been pondering since the start of this thread.  
June 20th, 2017, 08:39 PM  #25  
Senior Member Joined: Aug 2012 Posts: 1,527 Thanks: 364  Quote:
This snapping back and forth isn't helping. I'm going to stop for a while. I'd like you to respond to the points I'm making if you are so inclined.  
June 20th, 2017, 08:41 PM  #26  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
"The diagonalization argument is actually the "standard" way to prove there is no f(i,n) with those properties." If the diagonalization argument is merely the "standard" way then this implies there are other "known" ways.  
June 20th, 2017, 08:49 PM  #27  
Senior Member Joined: Aug 2012 Posts: 1,527 Thanks: 364  Quote:
In fact I pretty much understand it completely in my head, but my formal writeup is just stuck somewhere. I'm trying to get some understanding. At this point it's glib to invoke diagonalization. That's a proof that imparts no understanding. And it doesn't explain the seeming paradox of reverse zigzagging. Here's something that bothers me. * You claim that given an enumeration of the computables there's an s such that rows(zigzag(s)) outputs exactly that enumeration; and * I have expressed doubt that there is in general such an s, and challenged you to argue that there is such an s; and * So far you have not engaged this point. This may or not be the central point, but it's one of the points that's bothering me and I'd like to draw your attention to it. Last edited by Maschke; June 20th, 2017 at 08:52 PM.  
June 20th, 2017, 08:51 PM  #28 
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21 
PS  You keep saying "given" an enumeration of the computable reals. Once we are given that, we can of course antizigzag to compute $s$. We can't just be given that enumeration because your question rests on why we can't compute that enumeration (to which I cited your relation to the halting problem issue). We know the enumeration exists in a settheoretic sense based on axioms. Distinguishing between that which exists via set theoretic axioms and that which is computable is the heart of the issue. Agreed?

June 20th, 2017, 08:59 PM  #29  
Senior Member Joined: Aug 2012 Posts: 1,527 Thanks: 364  Quote:
THIS IS THE POINT! We ARE given an enumeration of the reals. Why doesn't antizigzagging work???? Why not? We can enumerate any countable set. That's basic set theory. We can enumerate the computable reals as $c_1, c_2, \dots$. Nobody should look twice at that statement. Normally nobody would. Quote:
Quote:
We DO have an enumeration, which is a mapping from the naturals to the computables, along with the inverse map from the computables to the naturals. Simply via the induced order of the naturals. So now we have some enumeration. Maybe we think we have no way to compute it. But we seemingly CAN compute it via inverse zigzagging. What is wrong with that argument?????? Specifically I'm not saying this is particularly obvious. I believe that by the time I can answer this question to my own satisfaction I'll have learned something more about computablity theory. I think there's some insight to be had here. By the way I think your zigzagging idea is very insightful. It sparks a lot of really good questions. Last edited by Maschke; June 20th, 2017 at 09:07 PM.  
June 21st, 2017, 06:14 AM  #30  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
1) Let B be an enumeration of the wellformed formulas of a formal language capable of expressing the computable reals. 2) ‘Compute’ a listing C of those formulas for computable reals. In set theory, we rely on the axiom schema of specification generally, where we are guaranteed an axiom saying “this subset of B exists” for each formula in the language of, for example, ZFC. While such a formula $f$ exists in ZFC by reason of an axiom (simply, where the formula $f$ is equivalent to saying “let C = { x in B : x is a formula for a computable real }”), it may not, or in fact cannot, exist in the formal language used to compute the computable reals. Namely, computing the formula for determining which elements of B are formulas for computable reals is different than simply asserting a set containing only those formulas exists by relying on the axiom schema of specification. 3) Inverse zigzag to compute $s$, meaning $f^{1}( \,C) \, = s$. The problem obviously arises in step 2. I still don’t think I’ve fully answered your question, but hopefully it’s extremely apparent why computing the formula is different than simply saying “let this subset exist” based on the axiom schema. Last edited by AplanisTophet; June 21st, 2017 at 06:33 AM.  

Tags 
noncomputable, reals 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Reals  Lalitha183  Abstract Algebra  3  June 2nd, 2017 10:02 PM 
Power Set of the Reals is Countable  zylo  Topology  2  July 2nd, 2016 05:05 PM 
Independence of Reals  mathbalarka  Number Theory  1  May 9th, 2013 05:51 AM 
Computable completion  iclestu  Applied Math  2  October 26th, 2011 11:40 AM 
Integration over the reals? finding R(dx)  cernlife  Real Analysis  5  May 30th, 2011 08:37 PM 