◄
Chapter
1 ◄
Index Chapter
3 ►
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
2. Why is first order Arithmetic not omega-constructive?
Contents
2.0. Introduction
2.1. The Representation Theorem
2.2. What is the formal representation of f(x, y) in PA?
2.3.
Gödel’s Beta function
2.4. Can F(x, y, z) create a logical paradox in PA?
2.5. The ‘Liar’ paradox
2.6. The ‘Russell’ paradox
2.7. Creation through definition
2.8. When can PA+F(x1, x2, x3) be
assumed consistent?
2.9. What does PA prove constructively by (E1x3)F(k, m, x3)?
2.10. Mendelson’s proof of “PA proves: (E1x3)F(k, m, x3)”
2.11. What does (E1x3)F(x1, x2, x3) assert?
2.12. The introduction of Platonism into PA
2.13. How does PA prove the Platonistic
assertion (E1x3)F(x1, x2, x3)?
2.14. At which point does Platonism enter PA
formally?
2.15. Is PA necessarily Platonistic?
2.16. Is every model of PA necessarily
infinite, but not denumerable?
2.17. Is there a constructive PA?
In this second section we locate
specific non-constructivity
in PA and trace it to the
particular closed
Induction axiom
schema of PA,
and the strong
Generalisation rule
of inference of first order predicate calculus.
2.1. The
Representation Theorem
We start by noting that, in the
argument that a simply
consistent PA
cannot be omega-constructive,
the only overt assumptions (cf.
Gödel
1931 p190-191) were that the axioms and rules of inference of PA are recursively definable, and Podnieks
Representation Theorem (Section
3.3).
The constructive nature of the first assertion
is easily established from first principles by direct examination of the 45 functions and
relations defined recursively
by Gödel (cf.
Gödel
1931 p182-186).
We thus take a closer look at the
second assertion that every Turing-computable function
f(x, y) can be represented by a PA formula F(x, y, z) such that, for every set of natural numbers k, m, n, if f(k, m) = n then:
(ii) PA proves: (Az)(~(z=n) => ~F(k, m, z)).
2.2. What is
the formal representation of f(x, y) in PA?
Assuming that a function is Turing-computable if
and only if it is recursive,
we consider the case where f(x, y) is a recursive function,
defined by:
(i) f(x, 0) = g(x),
(ii) f(x, (y+1)) = h(x, y, f(x, y)),
(iii) where g(x1) and h(x1, x2, x3) are recursive functions
of lower rank[1] that are represented in PA by well-formed formulas G(x1, x2) and H(x1, x2, x3, x4).
Now Mendelson shows (p131 & p132)
that f(x1, x2) is represented
by the well-formed formula F(x1, x2, x3):
(Eu)(Ev)[((Ew)(Bt(u, v, 0,
w) & G(x1, w))) & Bt(u, v, x2, x3) &
(Aw)(w< x2 =>
(Ey)(Ez)(Bt(u, v, w, y) &
Bt(u, v, (w+1),
z) & H(x1, w, y, z))].
2.3. Gödel’s Beta function
Defining
Gödel’s Beta-function[2], β(x1, x2, x3) = rm(1+( x3+ 1).x2, x1), where rm(x, y) is the remainder
obtained on dividing y by x, the well-formed formula Bt(x1, x2, x3, x4) in §2.2 above
is a representation
in PA of β(x1, x2, x3), and is the well-formed formula (Mendelson p131):
(Ew)( x1 = ((1 + (x3 + 1). x2).w + x4) & (x4 < 1 + (x3 + 1). x2)).
2.4. Can F(x, y, z) create a
logical paradox in PA?
Having represented f(x, y) in PA by F(x, y, z) for every set of natural numbers k, m, n such that f(k, m) = n, the question arises: Is the well-formed formula F(x, y, z) well-defined
in PA?
In other words, can we ensure that
the recursive
predicate f(x, y) has not
been represented
by tacitly postulating a well-formed formula
F(x, y, z) of PA as well-defined, which may implicitly admit
the possibility of a formal
logical paradox
in PA?
To see the significance of this
question, we review the earlier paradox, loosely ascribed to Epimenides,
which arises obviously if we introduce by definition a ‘Liar’
expression, which reads as “The ‘Liar’ proposition is a lie”, as a valid proposition
within the language in which the expression is constructed.
Clearly the grammar of an ordinary
language, which governs the construction of words and propositions of the language for use as a
means of general unrestricted communication, does not contain the specification
necessary to prohibit the creation by definition of such vague,
or ill-defined, self-referential expressions that have the formal form of
a proposition,
but which are devoid of both communicative content and meaning.
Russell’s expression, within set
theory, for a set ‘Russell’ whose elements are all, and only, those sets
of the Theory that do not belong to themselves, is equally paradoxical.
Here also the axioms and
logical rules of
inference of the theory, which govern the construction of sets for
use in a more restricted and precise language of mathematical communication, do
not contain the specification necessary to satisfactorily prohibit the creation
by definition of vague,
ill-defined or inconsistent
entities that apparently harbour concealed concepts involving unruly infinite sets.
2.7. Creation
through definition
We note that definitions are
essentially arbitrary assignments of convenient names within a language or
theory for expressing complex reasoning in a compact, more readable, and easier
to grasp form.
The paradoxes indicate that unrestricted
definitions may admit creation of well-formed expressions within the language
or theory that lead to an inconsistency.
Clearly such expressions must be considered as ill-defined within the language
or theory.
It follows that a language or
theory that admits such well-formed expressions as well-defined cannot be reasonably assumed
to be simply consistent.
2.8.
Well-defined well-formed formulas of PA
Now the formal response towards the containment (as
distinct from the resolution) of such paradoxes in PA appears to be the implicit
thesis that if a well-formed formula is provable in PA, then it necessarily represents a function or predicate that
is well-defined
in PA.
We may, therefore, reasonably
assume that such well-formed formulas do not affect the formal consistency of
the axioms
of PA.
Thus, to ensure that F(x1, x2, x3) does
not introduce an inconsistency
in PA, Mendelson argues (p134) that F(x1, x2, x3) strongly represents
f(x1, x2) in PA, in the sense that:
PA proves:
(E1x3)F(x1, x2, x3),
where ‘E1x3’ defines
uniqueness (Mendelson
p79).
However, in the light of our
argument in the preceding paragraph, if F(x1, x2, x3) admits
construction of well-formed formulas in PA that translate, under interpretation,
as circular, ill-defined or vaguely defined predicates such as those that lead to the
logical antinomies, then the strong
representability of F(x1, x2, x3) in PA provides reasonable grounds
for arguing that PA is itself an ill-defined
system.
2.9. What does PA prove constructively by (E1x3)F(k, m, x3)?
We therefore consider in some detail
the significance of the formal
provability,
in PA, of the well-formed formula (E1x3)F(k, m, x3) for any given numerals k, m:
PA proves:
(E1x3)(Eu)(Ev)[((Ew)(Bt(u, v, 0,
w) & G(k, w))) &
Bt(u, v, m, x3) & (Aw)(w< m => (Ey)(Ez)(Bt(u, v, w, y) &
Bt(u, v, (w+1),
z) & H(k, w, y, z))].
Now “PA proves: (E1x3)F(k, m, x3)” intuitively asserts that, for any given natural numbers
k, m, we can construct
natural numbers
x3 (uniquely),
u, v that
define a Beta-function
such that β(u, v, 0) = g'(k) and, for all i<m, β(u, v, i) = h'(k, i, f'(k, i)), and β(u, v, m) = x3, where f'(x1, x2), g'(x1) and h'(x1, x2, x3) are any
recursive functions
that are formally
represented
by F(x1, x2, x3), G(x1, x2) and H(x1, x2, x3, x4)
respectively such that:
(i) f'(k, 0) = g'(k),
(ii) f'(k, (y+1)) = h'(k, y, f'(k, y)) for all y<m,
(iii) g'(x1) and h'(x1, x2, x3) are recursive functions
that are assumed to be of lower rank than f'(x1, x2).
For any arbitrarily given sequence
of natural numbers
k0, k1, ... , kn, we can clearly determine an infinity of values of up, vp,
kp such that the Beta-function β(up, vp, i) = ki for all 0 =< i =< n, and β(up, vp, (n+1)) = kp.
Hence
the PA provability of (E1x3)F(k, m, x3) is simply the intuitive assertion that, for any
given natural numbers
k and m, we can always construct some (non-unique) pair of natural numbers
u, v such that
the Beta-function
β(u, v, i) represents the
first m terms, i.e. f'(k, 0), f'(k, 1), ... , f'(k, m), which are common to every primitive recursive function such as f'(x1, x2) that is
formally represented by F(x1, x2, x3).
We can see that this is constructively provable for any given natural numbers k and m since, given F(x1, x2, x3), we can determine a suitable Turing machine to construct the sequence f'(k