[FOM] Absolute undecidability

[Arne Hole]

Many thanks for the responses I got on this posting. I have collected them below, and I will reply to them one by one. My original email is cited at the bottom. First, I would like to point out two things:

(i) My results are not about undecidability in concrete theories, no matter how strong they are.  I am discussing the existence of statements which are absolutely undecidable in principle, independent of any theory.

(ii) While I use the choice r = Omega as the target in my PP example, my results of course do not depend on any assumption that Omega is "extremely undecidable" (whatever that would be taken to mean) or similar things. The relevance of Omega in my context is that it gives an example of an infinite bit sequence whose concrete undecidability properties to me seem sufficient for my purposes.

Now for the responses, you will find my reply following each of them.

------------------------------

>Date: Tue, 08 Sep 2015 12:00:09 +0300
>From: Panu Raatikainen <panu.raatikainen at helsinki.fi>
>To: Foundations of Mathematics <fom at cs.nyu.edu>
>Subject: Re: [FOM] Absolute undecidability
>Message-ID:
>	<20150908120009.Horde.pL0WcJytVDm0bEoYLHdcDQ1 at webmail.helsi
>nki.fi>
>Content-Type: text/plain; charset=UTF-8; format=flowed; DelSp=Yes
>
>My old critical discussion of the talk (by Chaitin and others) about the
>"extreme uncomputability" of Omega might be relevant:
>
>http://www.mv.helsinki.fi/home/praatika/AIT.pdf
>
>Best, Panu
>
>
>
>
>
>--
>Panu Raatikainen
>
>Ph.D., Adjunct Professor in Theoretical Philosophy
>
>Theoretical Philosophy
>Department of Philosophy, History, Culture and Art Studies P.O. Box 24
>(Unioninkatu 38 A)
>FIN-00014 University of Helsinki
>Finland
>
>E-mail: panu.raatikainen at helsinki.fi
>
>http://www.mv.helsinki.fi/home/praatika/

------------------------------

My reply: 
I think your paper is a good example of the open  discussions one should have concerning these things. However, I find the relevance for this particular discussion limited. As remarked above, I do not assume that Omega has any particularly  "extreme" undecidability properties. The undecidability properties that it do have, are sufficient for it to work as an ingredient in my PP example.  Other choices are possible, as mentioned in the PP.

Another, perhaps more peripheral,  comment: I am sure you will agree that statements unprovable in theories with, say, the set of true \Pi_n^0 sentences as axioms, represent something entirely different from what I am discussing. Of course one can find theories of that kind where both the negation of my MWP and the statement D (which exists if the MWP is true) can be proved, provided they are known in advance to be "true". But this does not tell us anything. You can achieve the same effect simply by adding D or the 
negation of MWP as a non-logical axiom to PA. (If the MWP is true, then we add D. If the MW is false, then we add the negation of MWP. In both cases we have theories where all the axioms are "true", and the statement  in question is provable.)  The point is, of course, that we do not know by direct reference that the formulas in question are true.  

------------------------------

>Date: Mon, 7 Sep 2015 14:38:11 -0400
>From: Joe Shipman <joeshipman at aol.com>
>To: Foundations of Mathematics <fom at cs.nyu.edu>
>Subject: Re: [FOM] Absolute undecidability
>Message-ID: <27E6BC45-0410-4E49-8E47-14819815EADB at aol.com>
>Content-Type: text/plain;	charset=us-ascii
>
>I don't think your "nontrivial information about an infinite number of bits of
>Omega" is a clear enough concept.
>
>In the case where MWP is true, then there is an absolutely undecidable true
>statement of the form "D is the maximal winner" which gives very concrete
>implications about specific bits of Omega (infinitely many specific finite
>consecutive subsequences which are not all 1's, one for each length greater
>than D)..
>
>However, in the case where MWP is false, there is only a finite amount of
>information that that tells us, and there is no specifiable finite set of bits about
>which any meaningful information may be learned.
>
>-- JS
>
>Sent from my iPhone

------------------------------

My reply: 
In the theorem of my PP presentation, there is a an explanation of what the concept "nontrivial information about an infinite number of bits of Omega" is taken to mean in that particular context; formally it is simply information of one of the two kinds described on the previous slides. However, I agree that finding a useful general definition is interesting. Here is a suggestion I have tried (not mentioned in the PP), roughly described: 

We say that an infinite bit sequence {b_n} is a TAIL of the infinite bit sequence {a_n} if there a natural number k such that b_n=a_(n+k)  for all natural numbers n. Then we may say that a property P of infinite bit sequences definable in L(PA) is NONTRIVIAL  (wrt to an infinite number of bits) iff it has the following properties:

(i) If {a_n} has the property P , then all tails of {a_n} also have the property P

(ii) The probability that an infinite p = 0.5 Bernoulli sequence has the property P, is less than 1.

 [On the basis of this, we may define an infinite bit sequence {a_n} as "purely random" iff it has no nontrivial property.  This way of defining randomness for infinite bit sequences is different from the incompressibility based definitions.]

According to the definition above, the negation of the MWP is nontrivial. The MWP itself is not, but it implies that another nontrivial  property holds for the sequence in question. This property P is of the form  "The number m is a maximal winner" , where m is referred to directly. It is expressed by the sentence D. Thus  (i) the MWP implies a nontrivial property , and (ii) the negation of the MWP is nontrivial. (Try finding another L(PA)-definable property satisfying these two requirements.  My tip is that it will be quite similar to the MWP.:-))

We may prove theorems of the following kind (this can obviously be generalized):

Theorem: Let {a_n} be an infinite bit sequence definable in L(PA), and let F be a family of theories in L(PA) with N as a model and with the property that none of them can prove any nontrivial property of {a_n}. Then there exists a closed sentence A of L(PA) which is undecidable in all the theories in F.

Proof: Since {a_n} is definable in L(PA), the formula MWP (with respect to {a_n})  exists as a formula in L(PA). Suppose the MWP  is true in N. Then the formula D also exists, and is true in N. Since the theories in F have N as a model, they cannot refute D. And since D is nontrivial, they cannot prove D. Hence we may take  A = D. Now suppose the MWP is false in N. Then since they have N as a model, none of the theories in F proves MWP. And since the negation of the MWP is nontrivial, they cannot refute the MWP. Hence we may take A = MWP. QED.

Interesting examples of {a_n} include sequences where the complexity involved in obtaining information about initial segments of {a_n} increases rapidly with the
length of the segment. For such sequences it may be "reasonable" to assume that the premise in the theorem above holds with F chosen to include all "reasonable" axiom sets expressible in the given language  (to use Harvey Friedman's  term from the posting cited below).  Then the sentence A in the theorem comes through as absolutely undecidable. In the PP presentation, I considered Omega as a candidate for such a sequence.

Concerning your last paragraph, I think I understand your point. But in line with the above, I would say that if any of the two situations arising from us proving D or the negation of the MWP is the "more absurd", I would choose the last one. The probability that a p = 0.5 Bernoulli sequence has the property we would have established for Omega in the first situation, is less than 1, but still nonzero. The corresponding probability for the second property is zero. So, if anything, I find the second property "more nontrivial" than the first.  The information involved is either way "finite", the way I look at it. After all, it is given to us by a single closed statement of L(PA). 

------------------------------

>Date: Mon, 7 Sep 2015 13:57:45 -0400
>From: Harvey Friedman <hmflogic at gmail.com>
>To: Foundations of Mathematics <fom at cs.nyu.edu>
>Subject: Re: [FOM] Absolute undecidability
>Message-ID:
>	<CACWi-
>GUTKq58JrHv7WFN_GABmhNCE6S9g_iJ17fzhmVduyqNLA at mail.gmail.com>
>Content-Type: text/plain; charset=UTF-8
>
>On Mon, Sep 7, 2015 at 7:26 AM, Arne Hole <arne.hole at ils.uio.no> wrote:
>> Earlier this summer I posted a link to a draft paper on the subject of
>> absolute undecidability (underdetermination of truth). I have received
>> some useful comments, but I still feel that the main point, which I
>> think is quite significant,  has not come across. Therefore, in an
>> attempt to make things as transparent as possible, I have now made a
>> short PP presentation giving a simple example based on my results. You
>> may find it at
>>
>> http://folk.uio.no/arnehole/AbsUndec.pdf
>>
>> This should take only some minutes to scan through. It is shown that if all
>closed formulas in the language L of PA are either true or false in the standard
>model N, then for each real number r whose base 2 decimals are definable in L,
>there is a closed formula A_r in L such that if we are able to decide the truth
>value of A_r in N, then we will have nontrivial information concerning an
>infinite number of decimal bits in r. As an example, I take r to be the halting
>probability known as Chaitin's Omega. Other interesting examples include pi,
>the Euler number e etc.
>>
>My own take on absolute undecidability, or absolute unprovability goes like
>this.
>
>1. It would be nice to have a robust definition of what a reasonable axiom of
>set theory is, even if reasonable ones may conflict. Then it becomes possible
>to prove that none such reasonable extension settles a question. I am not
>aware of such a thing. A good target for this approach would be to prove that
>any reasonable axiom of set theory does not settle the continuum hypothesis.
>This approach must be measured by how compelling the notion of
>"reasonable axiom" really is.
>
>2. One feature of all reasonable axioms that we know are that they are
>reasonably short. Even if they are schemes, they are reasonably short.
>thus ZFC is reasonably short. But here, the prospects of finding a single
>sentence that cannot be settled by any short system of axioms will still require
>some handle on "reasonable axioms" beyond being short, because otherwise
>we can just add the target sentence or its negation to ZFC and still have
>something short. So we are still confronted with the difficulties in 1.
>
>3. What I succeeded in doing is to identify a real constant c of nature, that
>everybody - or everybody I like to talk to (smile) - likes. And prove that any
>reasonably short axiom system is not going to determine what c is. This is the c
>of the posting
>
>579: Impossible Counting  5/26/15  8:58PM
>
>http://www.cs.nyu.edu/pipermail/fom/2015-May/018742.html
>
>https://u.osu.edu/friedman.8/foundational-adventures/downloadable-
>manuscripts/
>#88. Impossible Counting, May 26, 2015, 9 pages, draft.
>
>c = THE NUMBER OF BINARY OPERATIONS *:A x A into A, UP TO 12-SIMILARITY
>- i.e., have the same restrictions to 12 element sets up to isomorphism. Here
>A can range over absolutely all sets, or instead range over countable sets, or
>instead be fixed at N. The same result holds.
>
>Harvey Friedman

------------------------------

My reply:

This project certainly seems interesting. I guess that if you want to obtain a meaningful notion of what a "reasonable" axiom is, then you will also have to develop a notion of "unreasonable" axioms. And, as you write, size cannot be the only thing that matters. So then one has to look for some other reason why we cannot possibly use a given
sentence as an axiom. I would suspect that you would then end up discussing arguments tied to intrinsic properties of the formulas that are to be "disqualified", that is, properties dependent only on the language in which the formulas are expressed and the intended interpretation of that language. In other words, my tip is that you would wind up discussing absolute undecidability in the sense I am doing, that is, in a theory-independent sense. But then again, this is just speculations on my part.





------------------------------

>-----Original Message-----
>From: Arne Hole
>Sent: Monday, September 07, 2015 1:26 PM
>To: 'fom at cs.nyu.edu'
>Subject: Absolute undecidability
>
>Earlier this summer I posted a link to a draft paper on the subject of absolute
>undecidability (underdetermination of truth). I have received some useful
>comments, but I still feel that the main point, which I think is quite significant,
>has not come across. Therefore, in an attempt to make things as transparent
>as possible, I have now made a short PP presentation giving a simple example
>based on my results. You may find it at
>
>http://folk.uio.no/arnehole/AbsUndec.pdf
>
>This should take only some minutes to scan through. It is shown that if all
>closed formulas in the language L of PA are either true or false in the standard
>model N, then for each real number r whose base 2 decimals are definable in L,
>there is a closed formula A_r in L such that if we are able to decide the truth
>value of A_r in N, then we will have nontrivial information concerning an
>infinite number of decimal bits in r. As an example, I take r to be the halting
>probability known as Chaitin's Omega. Other interesting examples include pi,
>the Euler number e etc.
>
>Best, Arne H.