◄
Contents ◄
Index Chapter
2 ►
Beyond
Gödel
Simply consistent
constructive systems of first order Peano’s Arithmetic that do not yield
undecidable propositions by Gödel’s reasoning
(A compiled copy of Chapters 1 to 6 can be downloaded as a .pdf file from http://arxiv.org/abs/math/0201059.)
Chapter 1. First order Arithmetic is not omega-constructive
Contents
1.0. Introduction
1.1. Introducing omega-constructivity : omega-PA
1.2. The significance of omega-constructivity
1.3. Constructive PA should be intuitive
1.4. Differentiating between omega-constructivity
and omega-completeness
1.5. The relevance of omega-constructivity
1.6. prf'(x, y) is a
Turing decidable predicate
1.7. The Representation Theorem
1.8. Can PA be both simply consistent and omega-constructive?
1.9. Consequences of the omega-constructivity
of omega-PA
1.10. The meta-mathematical inconsistency in omega-PA
1.11. A
simply consistent PA is neither omega-constructive, nor omega-complete
1.12. What
is the significance of the omega-incompleteness of PA?
1.13. The
Gödelian
argument
1.14. omega-provable
propositions and PA
1.15. What
kind of propositions are omega-provable?
1.16. The
Platonistic axiom of reducibility and PA
1.17. What
is the significance of: (Ax)F(x) is omega-provable?
1.18. Why
is first order Arithmetic
not omega-constructive?
We take as our primary reference Mendelson’s first order
exposition of the essentially second
order formal
system and various revolutionary concepts introduced by Gödel in his
original paper “On
formally undecidable propositions of Principia Mathematica and related systems
I”.
We also borrow some content,
and style of presentation, from Karlis Podnieks’ proof of Goedel’s incompleteness
theorem in his e-textbook “Around Goedel’s Theorem”.[1]
We take as our starting point the
systems of first order
predicate calculus
and first order
Arithmetic
defined by Mendelson
(p57 & p102).
We introduce the concept of omega-constructivity,
and show that standard
first order Arithmetic PA is not omega-constructive.
1.1.
Introducing omega-constructivity : omega-PA
We say
that a simply
consistent formal
system of standard
first order Arithmetic PA is omega-constructive if and only if it is not the case that,
for any well-formed formula F(x1, x2, x3, ... , xn) of PA, we can have both:
(i) ~(PA
proves: F(x1, x2, x3, ... , xn)), and
(ii) (Ax1, Ax2, Ax3, ..., Axn)(PA proves:
F(x1, x2, x3, ... , xn)), where the domain of xi is the set of natural numbers.
In other words, we cannot have a
situation where a well-formed formula such as F(x) is unprovable
in PA,
but F(1), F(2), F(3),
... are all provable,
if PA is both simply consistent
and omega-constructive, where n denotes the numeral representing[2] the natural
number n in the formal system PA.
We name such an omega-constructive PA system ‘first order omega-Arithmetic’, and
refer to it as omega-PA.
1.2. The
significance of omega-constructivity
This definition implicitly
reflects the thesis that an infinite,
compound, meta-assertion
such as "F(1) is provable in PA & F(2)
is provable
in PA
& F(3) is provable in PA & ..." is simply a
convenient way of expressing and visualising the meta-assertion “F(n) is provable
in PA
for all n”, where n is intuitively taken to range over the natural numbers.
1.3.
Constructive PA should be intuitive
We argue that, in a constructive
formal system
of PA that is intended to formalise the natural numbers
- where the intended domain of x under interpretation contains, and preferably
consists only of, elements that correspond to the numerals that
represent
the natural numbers
in the formal system
- the meta-assertion
“F(x) is provable in PA” should
intuitively translate as equivalent
to “F(n) is provable in PA for all
n”, where n is intuitively taken to range over the natural numbers.
So a formal system that is not omega-constructive is counter-intuitive.
1.4.
Differentiating between omega-constructivity and omega-completeness
We note the difference between omega-constructivity and omega-completeness.
PA is said to be omega-complete if and only
if there is a no well-formed formula F(x) with one free variable such that:
(i) ~( PA proves:
(Ax)F(x)), and
(ii) (An)( PA proves: F(n)), where the domain of n is the set of natural numbers.
Now, in our intended formal system PA of the natural numbers,
an infinite,
compound, meta-assertion
such as "F(1) is provable in PA & F(2)
is provable
in PA
& F(3) is provable in PA & ... " can also be intuitively asserted
as a consequence
of a meta-proof of the generalization
"(Ax)(F(x) is provable
in PA)".
However, we need to consider the
possibility that, under interpretation,
such a PA may admit an infinite domain
for x that is not denumerable, or
that the generalisation
"(Ax)(F(x)" may be a well-formed formula, but an ill-defined proposition
under interpretation
(which could be the case if F(x) either represents, or translates under interpretation
as, a vague
predicate).
It follows that, under our
intended formalisation,
the denumerable
meta-assertion
"F(1) is provable in PA & F(2)
is provable
in PA
& F(3) is provable in PA & ..." cannot be assumed
to conversely
yield a proof
of '(Ax)F(x)’ in PA.
So a system that is not omega-complete is not necessarily counter-intuitive.
1.5. The
relevance of omega-constructivity
To see the relevance of omega-constructivity to PA, we consider in §1.5
to §1.7 the primitive
recursive (Mendelson p120)
predicate prf'(u, y), which we define[3] as true if and only if u is the Gödel-number (Podnieks 2001 Section 5.2) of a well-formed formula F(x1, x2, x3, ... , xn) of PA, containing the free variables x1, x2, x3, ... , xn, and y is the Gödel-number
of a proof
in PA of F(u, x2, x3, ... , xn).
1.6. prf'(x, y) is a Turing decidable predicate
Now we can construct a Turing machine
that, given any u and v, will decode (Podnieks 2001 Excercise 5.3) u into F(x1, x2, x3, ... , xn), check whether x1 occurs
in it, construct F(u, x2, x3, ... , xn) by replacing x1 wherever
it occurs by u, decode
v, check if v is a proof
sequence, and finally check to see if F(u, x2, x3, ... , xn) is the last well-formed formula in the proof sequence
coded by v.
Thus prf'(x, y) is a Turing-decidable predicate.
1.7. The
Representation Theorem
By Podnieks
Representation Theorem (Section 3.3) we can therefore construct
a PA-formula PRF'(x, y) expressing the predicate prf'(x, y) such that, for any given k1, k2:
(i) prf'(k1, k2) is true
=> PA proves: PRF'(k1, k2), and
(ii) ~prf'(k1, k2) is true
=> PA proves: ~PRF'(k1, k2).
We let r be the Gödel-number of ~PRF'(x1, x2).
We consider the well-formed formula ~PRF'(r, x2).
Now, from the definition of prf'(u, y), it follows that[4]:
(iii) prf'(r, y) is true
<=> y is the Gödel-number of a proof in PA of ~PRF'(r, x2).
1.8. Is PA
both simply consistent and omega-constructive?
In §1.8
to §1.11, we next address the question : Can PA be both simply consistent
and omega-constructive?
Let us
assume that it is, and that omega-PA proves ~PRF'(r, x2), so that some natural number k is the Gödel-number of this proof.
Then, by §1.7(iii), prf'(r, k) is true and hence,
However, by our premise, we have
that,
omega-PA proves: ~PRF'(r, x2), and so
Therefore, since omega-PA is assumed simply consistent, it follows that ~PRF'(r, x2) cannot be proved in omega-PA.
1.9.
Consequences of the omega-constructivity of omega-PA
We thus have from the omega-constructivity of omega-PA that it is not the case that:
(An)(omega-PA proves: ~PRF'(r, n)).
Now, since prf'(x, y) is primitive recursive, if ~prf'(r, y) is true for all y, it follows meta-mathematically from §1.7(ii)
that:
(An)(omega-PA proves: ~PRF'(r, n)).
So, if it is not the case
that,
(An)(omega-PA proves: ~PRF'(r, n)),
then it is not the case that,
~prf'(r, y) is true for all y.
Hence we have, meta-mathematically,
that:
~prf'(r, k) is false for some k,
prf'(r, k) is true,
omega-PA proves: ~PRF'(r, x2).
1.10. The
meta-mathematical inconsistency in omega-PA
We have thus demonstrated that if PA is assumed both simply consistent
and omega-constructive, then
we have the meta-mathematical
inconsistency:
(i) omega-PA proves: ~PRF'(r, x2)
=> ~(omega-PA proves: ~PRF'(r, x2)), and
(ii) ~(omega-PA proves: ~PRF'(r, x2))
=> omega-PA proves: ~PRF'(r, x2).
1.11. A simply consistent PA is neither omega-constructive,
nor omega-complete
So, if standard first order
Arithmetic PA is assumed simply consistent, then it cannot be omega-constructive in the
sense defined above in §1.1.
Since, in standard first order Arithmetic PA,
we have that:
PA proves:
F(x) <=>
PA
proves: (Ax)F(x),
it follows that standard first order
Arithmetic PA is, additionally, not omega-complete.
1.12. What is the significance of the omega-incompleteness
of PA?
Now, if standard first order
Arithmetic PA is assumed simply consistent, then there is the well-formed formula ~PRF'(r, x2) with one free variable such that:
(i) ~(PA
proves: (Ax2)~PRF'(r, x2)), and
(ii) (An)(PA proves:
~PRF'(r, n)).
The question
arises: What is the significance of such omega-incompleteness of PA?
To get some
indirect perspective on this question, let us for a moment consider the Gödelian
argument.
1.13. The Gödelian
argument
One
interpretation, of the Gödelian
argument as offered by J.R.Lucas,
is the thesis that there is some non-mechanistic element - knowledge of
which is Platonistically
available to human intelligence but cannot be reflected in any machine intelligence
- that is involved in establishing that a well-formed formula such as (x)F(x) is formally
unprovable in
PA, yet translates into a true proposition
under interpretation
in the standard model.
However, if the foregoing
arguments are simply non-constructive
and intuitionistically
objectionable, but not non-mechanistic,
then the Platonistic
elements of the reasoning are built into the formal logic itself, and can be built
equally rigorously, independent of any model, into machine intelligence.
1.14. omega-provable propositions in
PA
Thus if we introduce:
~(PA
proves: (Ax)F(x)) & (An)(PA
proves: F(n))
as the meta-definition of:
‘(Ax)F(x)’ is omega-provable in PA,
we can reasonably argue that PA establishes the meta-assertions: