FOM: true => provable [Ignore previous posting with true = provable]

V. Sazonov V.Sazonov at doc.mmu.ac.uk
Tue Nov 7 15:37:56 EST 2000


Let me try again. 

I ask everybody to ignore my previous posting with the subject: 
FOM: True = provable? Was: Goedel: truth and misinterpretations
Here follows a corrected version. 

------------
Here is one simple (metamathematical) result and corresponding 
considerations related with my attempts to give (one of) 
formalizations to ``(ontologically) true, but not provable''. 
The result looks as something opposite to this phrase. For 
definiteness, consider that all the considerations below such 
as consistency of theories or first order models or the concept 
of truth (probably assumed implicitly) are given in the 
framework of ZFC, if not explicitly stated otherwise. 

As such a subject is not my current everyday mathematical work, 
I would be especially grateful for any comments by specialists. 
The result is rather simple, but is it known, etc.? 


Let T be arbitrary sufficiently strong r.e. theory (say, PA 
or PRA) and A, B, C, etc. are any sentences (having no free 
variables) in the language of T. Consider the following axiom 
schema

(*)    (A => Pr[T](`A')

where Pr[T](x) is arithmetically definable predicate of 
provability in T of a formula with Goedel number x and 
`A' is numeral (term SSS...S0) representing Goedel number 
of A. 

Theorem 1. If T is consistent then it is consistent its 
extension T* = T + the above axiom schema (*). 

Proof. Assume that T* has a contradiction. Then 

T |- 
(A & ~Pr[T](`A')) V (B & ~Pr[T](`B')) V ... V (C & ~Pr[T](`C'))

and by distributivity and de Morgan laws we have 

T |- ~[Pr[T](`A') & Pr[T](`B') & ... &  Pr[T](`C')] & ...

It follows that  ~(`T proves a contradiction')
because otherwise the proved contradiction would yield A, B,...,C 
of which it is proved in T that them altogether are unprovable. 

That is T |- Con[T].  Therefore, due to Goedel, T |- 0=1. 

QED. 


Comment 1. Roughly speaking, Theorem 1 means that we can 
reasonably assume that 

	every true sentence is provable (true => provable). 

I omit motivation for such kind of result. Read the current 
discussion in FOM where even 

	true = provable 

was suggested as a definition of mathematical truth. 
Is it possible to have any analogous result asserting 
(roughly) this equality by extending T with the stronger 
schema 

(**)     (A <=> Pr[T](`A')?

No, this is hopeless because the negation of (**) may 
equivalently be presented as equivalence 

(***)	A <=> ~Pr[T](`A')

where A asserts its own non-provability. Goedel explicitly 
presented (by a `diagonal' construction) some such sentence 
G = G[T] for the case of any sufficiently strong T (including the 
case of T = PA). 

As Jeffrey Ketland correctly noted, (*) and (***) holding for 
Goedel's diagonal sentence G give T* |- ~G & Pr[T](`G'). 
Moreover, as T |- Con[T] <=> G we also have T* |- ~Con[T]. 
That is T* proves existence of a proof of a contradiction! 
It is well-known that in the case of T = PA, G and Con[T] are 
true in the standard model N of PA. Therefore T* does not hold 
in N. However, all this enterprise with T* was undertaken not 
for the sake of standard model. 


Informal notes. 

As I often mentioned in FOM, I have no idea what is standard 
model from a general point of view, when I think on mathematics 
outside of some its set-theoretic formalisms (specifically, 
outside of ZFC). The only (mathematical) way to approach to 
natural numbers is via formal systems of arithmetics or formal 
systems where arithmetical notions are interpretable. Thus, 
we could probably say that T* (or, say, PA*) is not so bad theory 
describing some natural imaginary world satisfying initial 
(presumably) natural axioms T plus some, also natural axioms 
(*) of metamathematical flavor. There may be some doubts on 
the naturality of the "imaginary world" of T* because it is 
somewhat unlike to what we have usually. Let us discuss this below. 

Thus, we have `truth => provability', but not vice versa (due to 
Goedel), as noted above. It looks strange, at first, that the 
converse implication does (or can) not hold. We know very well 
that what is provable is automatically considered as true in 
mathematics. If we imagine the (illusory) world of objects 
described by any given formal systems, then how it is possible 
that we cannot additionally assume that provable should be true 
(in this, even illusory world)? Mathematical theories and 
thinking are always based on this consideration! Provability is 
the only rational way to approaching to this illusory world. 
The answer which comes to my mind consists in the following. 
Any formalism intended to describe some reality or our fantasies, 
idealizations, illusions about this reality (in the case of PA 
we can think about reality of finite sets of pebbles or the like, 
embodying physically natural numbers) usually results in 
something different from initial plans. (Who predicted or wanted 
that the epsilon-delta definition of continuity would include 
also continuous, but nowhere differentiable functions; such 
"defects" of any formalization are absolutely normal and 
inevitable phenomenon.) Thus, any *traditional* formalism on 
natural numbers leads to "existence" in the imaginary world of 
these numbers some "numbers" which have no relation to the real 
sets of pebbles. We know about non-feasible numbers such as 
2^1000 or 10^{10^{10^{10^{10}}}} or much much bigger "numbers". 
Where from should it follow that any imaginary proof of 
imaginary finite length (assumed in the predicate 

Pr[T](y) \bydef \exists x Proof[T](x,y) 

under the name of the variable x under existential quantifier) 
will give a true (even in the imaginary sense of the imaginary 
world) theorem? (In our case we even have T* |- ~Con[T].) 
Therefore it seems quite reasonable that we have only one way 
implication in (*). (Recall that, newertheless, T* consistently 
extends T.) 

Imaginary provability does not guarantee truth (even illusory one)
Imaginary provability could even give an (imaginary) contradiction. 

On the other hand, it is desirable to have a "feasible" 
version of Theorem 1 with feasible proofs by using 

FPr(y) \bydef \exists feasible x Proof[T](x,y), 
FCon[T] \bydef \not\exists feasible x Proof[T](x,`0=1'), 

etc. But this requires using some appropriate formalization 
of feasibility concept (what is a separate problem). Thus, 
we could probably get a better result that 

	  true => feasible provable 

in the above sense. (Otherwise, what does it mean to be provable 
in practice?) This would be a stronger version of Theorem 1. 
Its previous version gives no guarantee for feasible (real) 
provability, only imaginary finite provability. Nevertheless, 
it demonstrates approximately the relation between ``true'' 
and ``provable'' in one of the ways discussed in FOM these days. 

Moreover, there is probably a hope that Theorem 1 could be 
further strengthened for feasible version of (**), giving 

	true = feasible provable  

which is still desirable, natural and seemingly possible. 
For feasible proofs the Goedel's diagonal trick will hardly 
work! According to one approach to feasible numbers they are 
closed only under addition operation. Multiplication is 
only a partial function there. Bur recall that Goedel's 
trick is based on syntactic substitution operation which 
corresponds to multiplication on natural numbers. 


Of course, here is no contradiction with the well known 
(and non-denial!) results on non-recursive enumerability 
of arithmetical truth in the standard model (understood in 
the framework of ZFC). Th.1 and hopefully its discussed 
above feasible versions (except informal comments) have 
precise (meta)mathematical sense.  


Anyway, this was an exercise around "true = provable". 
I myself should think more on its proper value. 


Any comments, please. 


Vladimir Sazonov




More information about the FOM mailing list