Some consequences of defining mathematical objects
constructively and mathematical truth effectively
A lay
perspective
Bhupinder
Singh Anand[1]
(A .pdf file of this essay before the current update is available at http://arXiv.org/abs/math.GM/0210078)
Standard expositions of classical first order
theory - rooted primarily in the works of Cantor, Gödel, Tarski, and Turing -
argue that the truth of some propositions of significant formal mathematical
languages, under any interpretation, is non-algorithmic, and essentially
unverifiable constructively. This, implicitly, admits non-constructive elements
into the domain of the interpretation. In this essay, we consider some
arguments for, and consequences of, an interpretation of classical foundational
concepts in which we define mathematical objects constructively, and
mathematical truth effectively.
Contents[2]
1. Introduction
A
formal definition of mathematical objects
An
alternative interpretation of Gödel’s Proof
The
ambiguity in Tarski’s definitions of satisfiability and truth
4. A
meta-theorem of recursive asymmetry
II. Some consequences of defining mathematical
objects constructively
1. Analysing Gödel’s
Theorem XI
Implicit
meta-theses underlying Gödel’s Theorem XI
Gödel’s Theorem XI as a conditional meta-assertion
2. Consistency
and Meta-thesis 3
3. Can
“consistency” be a formal convention?
4. Definitions
of new function and predicate letters
Instantiationally
and algorithmically computable functions
III. Some
consequences of defining mathematical truth effectively
1. Classical definitions
of “satisfiability” and “truth” are ambiguous
Classical definitions of “satisfiability” and “truth”
Expressing Church’s Thesis as an equivalence
2. Constructive definitions of classical
concepts
3. Self-terminating, converging and oscillating
Turing machines
Total
partial recursive functions
The
Arithmetical Provability Thesis and the classical Church-Turing Theses
Converging
NT-routines and Cauchy sequences
4. Turing’s computable and uncomputable numbers
6. Constructivity and classical Quantum
Mechanics
I. The
significance of defining mathematical objects constructively and mathematical
truth effectively
1. Introduction
We begin
our enquiry, by addressing the question: Are the concepts, “non-algorithmic”[3] and “non-constructive”[4], necessarily synonymous in classical[5] logic and mathematics?
We
consider, as a natural starting point, the classical interpretation of the
reasoning and conclusions in Gödel’s seminal 1931 paper [Go31a].
Gödel argues that, in a formal language[6] as basic as Peano Arithmetic[7] - which is considered as the foundation for all,
significant, formal, mathematical languages - there are undecidable[8] sentences[9] that can be recognised as intuitively true[10], under classical interpretation[11], but which are not formally provable[12] within the system.
Does
this imply that such recognition, in some cases, cannot be duplicated in any
artificially constructed and, more important, artificially controlled,
mechanism or organism whose design is based on classical logic?[13]
The
scientific, and philosophical, dimensions of an affirmative answer to the last
question have been broadly reviewed, and addressed, by
Penrose’s
argument is based on a strongly Platonist thesis that sensory perceptions simply
mirror aspects of a universe that exists, and will continue to exist,
independent of any observer ([Pe90], p123, p146)[14].
On this
view, individual consciousness would be a discovery of what there is (cf. [Pe90],
p124), and be independent of the language in which such discovery is expressed.
It follows that recognition of intuitive truth would be individually asserted -
and, implicitly, fallible - correlations between the unverifiable - and, ipso
facto, infallible - intuitive experiences of an individual consciousness, and
the formal expressions of a communicable language.
The
issue, then, is whether classical logic can adequately formalise intuitive
truth, to make it infallible, or whether such recognition is essentially
fallible[15].
Penrose
opts for the inadequacy, of classical logic, to completely capture a Platonic
mathematical reality that, he believes, manifests itself, first, in thought -
which originates in the mind consequent to sensory experience - and, second, in
its representation in a communicable language.
He
supports his view by highlighting the “ethereal” presence, and non-verifiable
properties, of various non-algorithmic ([Pe90], p168), and implicitly
non-constructive, mathematical concepts that are accepted in our formal
languages as essential to classical mathematics ([Pe90],
p123-8).
Although
Penrose’s arguments represent only one, and perhaps an arguably extreme, point
of view[16], they serve to emphasise that classical mathematics
may, yet, need to adequately legitimise the acceptance, into a theory, of
formally definable mathematical objects (cf. [Pe90], p147)[17], most obviously those that can be argued as being
essentially non-constructive.
Now, we
note that Penrose appears to base his thesis on, amongst others, a classical
consequence of Gödel’s reasoning and conclusions: we cannot express Tarskian
definitions[18] of the “satisfiability”, and “truth”, of formal
expressions under an interpretation algorithmically ([Pe90],
p159)[19].
He concludes
from this that, although we may follow a common, intuitive, process for
discovering common, mathematical, aspects of the universe, not all our
mathematically expressible discoveries are expressible by classical algorithms
([Pe90],
p533, p548).
However,
Penrose’s arguments also appear to imply further, albeit implicitly, that our
recognition of intuitive “arithmetical truth” - even when this is accepted as
being adequately formalised by the classical Tarskian definitions of the
“satisfiability” and “truth”, of formal expressions, under an interpretation -
is “absolutely” non-constructive (cf. [Pe90], p145-6).
Thus,
although Penrose does not seem to question the classical expression of Church’s
Thesis[20] ([Pe90], p64-65) as a strong identity -
which, essentially, postulates that every effectively computable function is
algorithmic - he seems to conclude from his arguments, concerning the
inadequacy of classical logic, that there may be non-algorithmic,
non-constructive, ways of acquiring mathematical insight and knowledge ([Pe90],
p538).
As is
evidenced in his discussion of Lucas’ Gödelian argument ([Pe90],
p539), Penrose does not appear to entertain the possibility, that there may be
non-algorithmic reasoning that could be intuitionistically accepted as
constructive; his arguments seem to, implicitly, treat the terms
“non-algorithmic” and “non-constructive” as synonymous[21].
1.2 A formal definition of mathematical objects
In this
essay, however, we argue that what Penrose, for instance, views as the
essentially, and absolutely non-constructive, aspects of mathematical concepts,
may simply be manifestations of a removable ambiguity in the classical
Tarskian definitions of the satisfiability, and truth, of the formulas of a
formal language under an interpretation.
We
argue that this leads to an alternative interpretation of the classical
consequences of Gödel’s seminal 1931 paper [Go31a], with implications for the
foundations of philosophy, logic, mathematics and computability.
We
start by noting that the introduction of classical, non-constructive, objects
into our mathematical ontology - particularly those introduced through
unrestricted definitions[22] - can be qualified by formally defining a set as the
range of a mathematical object that is, itself, a formal mathematical object:
Definition
1(i):
A primitive mathematical object, of a formal mathematical language, L,
is any symbol for an individual constant, predicate letter, or a function
letter (cf. [Me64],
p46; also p1,
p10), which is defined as a primitive symbol of L.
Definition
1(ii):
A formal mathematical object, of a formal mathematical language, L, is
any symbol for an individual constant, predicate letter, or a function letter
that is either a primitive mathematical object of L, or one that can be
introduced through definition (cf. [Me64], p82) into L without inviting
inconsistency[23].
Definition
1(iii):
A mathematical object, of a formal mathematical language, L, is any
symbol that is either a primitive, or a formal, mathematical object of L[24].
Definition
1(iv):
A set, in the domain of any interpretation, M, of a formal mathematical language,
L, is the interpretation of a mathematical object of L that is defined as the
range of a function in M that is, itself, an interpretation of a function
letter that is a mathematical object of L.
The
significance of these definitions is seen in Meta-theorem
1. We prove, there, the existence of an asymmetrical
recursive number-theoretic relation[25]. Such a relation is intuitively decidable constructively,
but cannot be introduced through definition as a formal mathematical object,
into any formal system of Peano Arithmetic, without inviting inconsistency;
nor, ipso facto, into any Axiomatic Set Theory in which the axioms of such
Arithmetic are theorems[26]. Hence, it would not be a formal mathematical object
of the Arithmetic, and the range, of its characteristic function[27], would also not be the interpretation of a formal
mathematical object that defines a (recursively enumerable[28]) set under interpretation!
This is
an astonishing result[29]! First, recursive number-theoretic functions, and
relations, are classically accepted as the basic building blocks for defining
constructive, and intuitionistically unobjectionable, mathematical concepts[30].
Second,
and in vivid contrast, the relative consistency, and independence, of the
Continuum Hypothesis seem to imply, prima facie, that we may also treat
Cantor’s non-constructive cardinal, aleph1, as a valid formal
mathematical object[31] of any Axiomatic Set Theory; thus, we may introduce
axiomatic definitions - and an individual constant symbol - for it into the
theory without inviting inconsistency!
1.3 An alternative interpretation of Gödel’s Proof
Now we
note that, in the proof of Theorem VI of his 1931 paper ([Go31a],
p24), Gödel argues that, in any consistent, formal, system P that formulates
Peano’s Arithmetic, we can construct a valid expression of the system, say [R(x)][32], such that [R(n)] is P-provable for any given numeral [n][33], but [(Ax)R(x)] is not
P-provable.
The
classical interpretation of this is that although [(Ax)R(x)] is not P-provable, it is true under its standard interpretation,
by Tarski’s definitions of satisfiability and truth ([Me64], p51).
We
argue, however, that, by implications that are implicit in Tarski’s
definitions, [R(n)] may be
viewed, alternatively, as an expression whose standard interpretation, R(n), can be effectively asserted as holding instantiationally[34] - and not necessarily algorithmically - for any given
natural number n, but R(x) cannot be effectively asserted as holding uniformly
- in the sense of algorithmically - for all natural numbers x collectively.
1.4 The
ambiguity in Tarski’s definitions of satisfiability and truth
Thus,
we deny the very basis for the above interpretation, of Penrose’s thesis, and
argue that classical interpretations, of Tarski’s definitions of satisfiability
and truth, contain an ambiguity: they implicitly imply the existence of an
ambiguous effective method[35], for deciding whether formal expressions, such as [R(x)], are satisfied under a given interpretation.
Specifically,
they fail to entertain the possibility that such a method may be
non-algorithmic[36]. In other words, for any given value n of its free variable, under a given interpretation,
there may always be a - possibly n-specific - non-algorithmic effective method, which can effectively
decide whether the interpretation, R(n), of a formal expression, such as [R(n)], holds instantiationally, even when there is
no n-independent
effective method that can effectively decide whether the expression [R(x)] is satisfied algorithmically, under a given
interpretation, when we substitute any numeral [n] for its free variable.
We
argue, further, that the above ambiguity is removable, by making the above
possibility explicit in the classical Tarskian
definitions of satisfiability and truth, and by weakening, and expressing, the Church and
Turing Theses as instantiational equivalences rather than as strong
identities.
Clearly,
every classically
Turing-computable number-theoretic function is effectively
computable instantiationally.
Consideration
of the converse leads naturally to the definition of self-terminating,
converging
and oscillating
neo-classical
Turing routines, and an argument that the Church and Turing Theses
may be false, when expressed as strong identities, since we can now define effectively
computable functions that are not classically Turing-computable.
We also
show that Turing’s “uncomputable” real numbers, and Cantor’s “uncountable”
real numbers, do not necessarily correspond to Cauchy sequences of rational
numbers; thus, they cannot be assumed to always define Dedekind real numbers.
In his
1931 paper [Go31a],
Gödel prefaces his Theorem V with the remark ([Go31a], p22):
“The fact which can be vaguely formulated as the
assertion that every recursive relation is definable within the system P (under
its intuitive interpretation), is rigorously expressed by the following
theorem, without reference to the intuitive meaning of the formulas of P.
Theorem V: For every recursive relation R(x1, ..., xn), there is an n-ary PREDICATE[37] r (with the
FREE VARIABLES u1 ... un) such that, for all n-tuples of numbers (x1, ..., xn), we have:
R(x1, ..., xn) => Bew[Sb(r (u1 ... un)|(Z(x1) ... Z(xn)))] (3)
~R(x1, ..., xn) => Bew[Neg Sb(r (u1 ... un)|(Z(x1) ... Z(xn)))] (4)”
In a
footnote, he adds that ([Go31a], footnote 38):
“The VARIABLES u1 ... un can be arbitrarily prescribed. There always exists,
e.g. some r with the FREE
VARIABLES 17, 19, 23, etc., for which (3) and (4) hold.”
He then
qualifies his proof with the remark ([Go31a], p23):
“We shall be content here to indicate the outline of
the proof of this theorem, since it offers no theoretical difficulties and is
fairly tedious.”
In
another footnote, he clarifies that ([Go31a], footnote 39):
“Theorem V depends of course upon the fact that, for a
recursive relation R, it is decidable on the basis of the axioms of the
system P whether or not R holds for any given n-tuple of numbers.”
Since Gödel
does not give a rigorous proof of the theorem, it is not clear whether his
remark - that the recursive relation R(x1, ..., xn) is “... definable within the system P (under its
intuitive interpretation) ...” - means that his reasoning is based on an implicit
assumption that R(x1, ..., xn) is syntactically isomorphic to the standard
interpretation of some PREDICATE r of P.
Such an
assumption would imply that a predicate letter for the n-ary relation “R”, along with suitable defining
axioms, could be introduced into P (cf. [Me64], p82) without inviting
inconsistency.
We
address this issue, and its possible direct, and indirect, consequences, in the
following sections.
In Meta-theorem
1, we consider the elementary, recursive, number-theoretic relation ~xB(Sb(y 19|Z(y))) (cf. [Go31a], p24, def. 8.1), and show that it
is not syntactically isomorphic to the standard interpretation of any[38] of its formal representations[39] in Gödel's system P[40].
In other words we argue that, if we assume the primitive recursive relation ~xB(Sb(y 19|Z(y))) to be syntactically isomorphic to an abbreviation of some formula of P, then we arrive at an inconsisten