[FOM] Absolute undecidability

[Arne Hole]

I now have taken a closer look at how the concept of "nontrivial" information concerning infinite bit sequences may be defined if one wants to generalize the two concrete examples considered in my PP (cf. my original posting to FOM, cited below). As I said in my reply to Timothy Chow, my initial suggestion actually does not work in the particular context of the PP; this was a mix-up of different versions on my part. Once again, sorry about that. 

Here is a new suggestion. In this definition, and the theorems following, the property Pi_1^0 can of course be replaced by other properties of formulas. For example, it may be replaced by a sharper property shared by the formulas expressing D and the negation of the MWP. As the reader may verify, they are both very short and simple formulas, so they share a lot of sharp characteristics. Translated to this setting, my absolute undecidability argument (cf. my PP) starts from  the theorems given below. I will not go into this undecidability argument here. 

DEFINITION: 
We say that a sequence {a_n} is COMPATIBLE with a property P up to bit k iff there is a sequence {b_n} with property P such that a_n = b_n for all n < k. Then we say that a property P of infinite bit sequences definable in L(PA) is NONTRIVIAL at level Pi_1^0  iff it has the following properties:

(i)  There is a Pi_1^0 sentence defining the property P for infinite bit sequences. [In other words, if we extend L(PA) by introducing a new function symbol f, then there is a Pi_1^0 sentence A in the extended language such that an arbitrary sequence {a_n} has property P iff  A is true in the standard model N when we interpret f(n) as a_n for all n.]

(ii) For all natural numbers k, the conditional probability that an infinite p = 0.5 Bernoulli sequence has the property P, given that it is compatible with P up to bit k, is less than 1.

We define an infinite bit sequence {a_n} as PURELY RANDOM at level Pi_1^0 iff it has no nontrivial property at level Pi_1^0.  

EXAMPLE:
Let  {a_n} be the base 2 decimal expansion of pi, let k be a natural number, and let P be the property that "for large enough m, there is no n>m such that there is a sequence of kn successive zeros starting with the n rang". By similar calculations as referred to in my PP, one can check that condition (ii) in the definition of nontriviality is not satisfied for this P. However, if m is a FIXED natural number, then the property P_m that "there are no sequences of kn successive zeros starting with the n rang for any n>m" is nontrivial at level Pi_1^0. Such a number m has not been found (as far as I know), so although we know that such a nontrivial property P_m of pi "exists", we have not yet "found" such a property.

THEOREM 1: 
Let {a_n} be an infinite bit sequence definable in L(PA). Let F be a family of theories in L(PA) with N as a model, such that none of the theories can prove any property of {a_n} which is nontrivial at level Pi_1^0. Then there exists a closed sentence A of L(PA) which is undecidable for 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. As explained in my PP, property (ii) in the definition of "nontrivial" holds for the property P of infinite bit sequences corresponding to D. Also, the property P may be defined by a Pi_1^0 sentence. So P is nontrivial at level Pi_1^0. Therefore, none of the theories in F can prove D, which says that P holds for {a_n}. 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 prove MWP. As explained in my PP, property (ii) in the definition of "nontrivial" holds for the property P of infinite bit sequences corresponding to the negation of MWP. Also,  the property P may be defined by a  Pi_1^0 sentence. So P is nontrivial at level Pi_1^0. Therefore, none of the theories in F can prove the negation of the MWP, which says that P holds for {a_n}. Hence we may take A  to be the negation of the MWP. QED.

THEOREM 2: 
There exists no L(PA)-definable bit sequence which is purely random at level Pi_1^0.

Proof: 
Apply the construction of the PP with r representing the sequence in question, noting that both D and the negation of MWP correspond to properties which are nontrivial at level Pi_1^0. QED.

Best, Arne.


>------------------------------
>
>>-----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.