Hilbert’s interpretation of quantification

Hilbert interpreted quantification in terms of his $\varepsilon$-function as follows [1]:

“IV. The logical $\varepsilon$-axiom

13. $A(a) \rightarrow A(\varepsilon (A))$

Here $\varepsilon (A)$ stands for an object of which the proposition $A(a)$ certainly holds if it holds of any object at all; let us call $\varepsilon$ the logical $\varepsilon$-function.

1. By means of $\varepsilon$, “all” and “there exists” can be defined, namely, as follows:

(i) $(\forall a) A(a) \leftrightarrow A(\varepsilon(\neg A))$

(ii) $(\exists a) A(a) \leftrightarrow A(\varepsilon(A)) \ldots$

On the basis of this definition the $\varepsilon$-axiom IV(13) yields the logical relations that hold for the universal and the existential quantifier, such as:

$(\forall a) A(a) \rightarrow A(b)$ … (Aristotle’s dictum),

and:

$\neg((\forall a) A(a)) \rightarrow (\exists a)(\neg A(a))$ … (principle of excluded middle).”

Thus, Hilbert’s interpretation of universal quantification— defined in (i)—is that the sentence $(\forall x)F(x)$ holds (under a consistent interpretation $\mathcal{I}$) if, and only if, $F(a)$ holds whenever $\neg F(a)$ holds for any given $a$ (in $\mathcal{I}$); hence $\neg F(a)$ does not hold for any $a$ (since $I$ is consistent), and so $F(a)$ holds for any given $a$ (in $\mathcal{I}$).

Further, Hilbert’s interpretation of existential quantification—defined in (ii)—is that $(\exists x)F(x)$ holds (in $\mathcal{I}$) if, and only if, $F(a)$ holds for some $a$ (in $\mathcal{I}$).

Brouwer’s objection to such an unqualified interpretation of the existential quantifier was that, for the interpretation to be considered sound when the domain of the quantifiers under an interpretation is infinite, the decidability of the quantification under the interpretation must be constructively verifiable in some intuitively and mathematically acceptable sense of the term constructive’ [2].

Two questions arise:

(a) Is Brouwer’s objection relevant today?

(b) If so, can we interpret quantification constructively’?

The standard interpretation of PA

We consider the structure $[\mathbb{N}]$, defined as:

$\mathbb{N}$ … the set of natural numbers;

$=$ … equality;

$S$ … the successor function;

$+$ … the addition function;

$\ast$ … the product function;

$0$ … the null element,

that serves for a definition of today’s standard interpretation, say $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$, of the first-order Peano Arithmetic PA.

Now, if $[(\forall x)F(x)]$ and $[(\exists x)F(x)]$ are PA-formulas, and the relation $F(x)$ is the interpretation in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ of the PA-formula $[F(x)]$ then, in current literature:

(1a) $[(\forall x)F(x)]$ is defined true in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ if, and only if, for any given natural number $n$, the sentence $F(n)$ holds in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$;

(1b) $[(\exists x)F(x)]$ is an abbreviation of $[\neg (\forall x)\neg F(x)]$, and is defined as true in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ if, and only if, it is not the case that, for any given natural number $n$, the sentence $\neg F(n)$ holds in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$;

(1c) $F(n)$ holds in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ for some natural number $n$ if, and only if, it is not the case that, for any given natural number $n$, the sentence $\neg F(n)$ holds in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$.

Since (1a), (1b) and (1c) together interpret $[(\forall x)F(x)]$ and $[(\exists x)F(x)]$ in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ as intended by Hilbert’s $\varepsilon$-function, they attract Brouwer’s objection.

A finitary model of PA

Clearly, the specific target of Brouwer’s objection is (1c), which appeals to Platonically non-constructive, rather than intuitively constructive, plausibility.

We can thus re-phrase question (b) more specifically: Can we define an interpretation of PA over $[\mathbb{N}]$ that does not appeal to (1c)?

Now, it follows from Turing’s seminal 1936 paper on computable numbers that every quantifier-free arithmetical function (or relation, when interpreted as a Boolean function) $F$ defines a Turing-machine $TM_{F}$ [3].

We can thus define another interpretation $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ over the structure $[\mathbb{N}]$ [4] where:

(2a) $[(\forall x)F(x)]$ is defined as true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ if, and only if, the Turing-machine $TM_{F}$ evidences [5] the assertion denoted by $F(n)$ as always true (i.e., as true for any given natural number $n$) in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$;

(2b) $[(\exists x)F(x)]$ is an abbreviation of $[\neg (\forall x)\neg F(x)]$, and is defined as true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ if, and only if, it is not the case that the Turing-machine $TM_{F}$ evidences the assertion denoted by $F(n)$ as always false (i.e., as false for any given natural number $n$) in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$.

We note that $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ is a finitary model of PA since—when interpreted suitably [6]—all theorems of first-order PA are constructively true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$.

Are both interpretations of PA over the structure $[\mathbb{N}]$ sound?

The structure $[\mathbb{N}]$ can thus be used to define both the standard interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ and a finitary model $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ for PA.

However, in the finitary model, from the PA-provability of $[\neg (\forall x)F(x)]$, we may only conclude that $TM_{F}$ does not algorithmically compute $F(n)$ as always true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$.

We may not conclude further that $TM_{F}$ must algorithmically compute $F(n)$ as false in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ for some natural number $n$, since $F(x)$ may be a Halting-type of function that is not algorithmically computable [7].

In other words, we may not conclude from the PA-provability of $[\neg (\forall x)F(x)]$ that $F(n)$ does not hold in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ for some natural number $n$.

The question arises: Are both the interpretations $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ and $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ of PA over the structure $[\mathbb{N}]$ sound?

PA is $\omega$inconsistent

Now, Gödel has shown [8] how to construct an arithmetical formula $[R(x)]$ such that, if PA is assumed simply consistent, then $[R(n)]$ is PA-provable for any given numeral $[n]$, but $[(\forall x)R(x)]$ is not PA-provable.

He further showed [9] it would follow that if PA is additionally assumed to be $\omega$-consistent, then $[\neg (\forall x)R(x)]$ too is not PA-provable.

Now, Gödel also defined [10] a formal language $P$ as $\omega$-consistent if, and only if, there is no $P$-formula $[F(x)]$ for which:

(i) $[\neg (\forall x)F(x)]$ is $P$-provable,

and:

(ii) $[F(n)]$ is $P$-provable for any given numeral $[n]$ of $P$.

However, a significant consequence of the finitary proof of the consistency of PA in this paper on evidence-based interpretations of PA [11] is that the formula $[\neg (\forall x)R(x)]$ is PA-provable, and so PA is $\omega$inconsistent!

The interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ of PA over the structure $[\mathbb{N}]$ is not sound

Now, $R(n)$ holds for any given natural number $n$ since Gödel has defined $R(x)$ [12] such that $R(n)$ is instantiationally equivalent to a primitive recursive relation $Q(n)$ which is algorithmically computable as true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ for any given natural number $n$ by the Turing-machine $TM_{Q}$.

It follows that we cannot admit the standard Hilbertian interpretion of $[\neg (\forall x)R(x)]$ in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ as:

$R(n)$ is false for some natural number $n$.

In other words, the interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ of PA over the structure $[\mathbb{N}]$ is not sound.

However, we can interpret $[\neg (\forall x)R(x)]$ in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ as:

It is not the case that the Turing-machine $TM_{R}$ algorithmically computes $R(n)$ as true in $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ for any given natural number $n$.

Moreover, the $\omega$-inconsistent PA is consistent with the finitary interpretation of quantification in (2a) and (2b), since the interpretation $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ of PA over the structure $[\mathbb{N}]$ is sound [13].

Why the interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ of PA over $[\mathbb{N}]$ is not sound

The reason why the interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ of PA over the structure $[\mathbb{N}]$ is not sound lies in the fact that, whereas (1b) and (2b) preserve the logical properties of formal PA-negation under interpretation in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ and $\mathcal{I}_{PA(\mathcal{N},\ Algorithmic)}$ respectively, the further non-constructive inference in (1c) from (1b)— to the effect that $F(n)$ must hold in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ for some natural number $n$—does not, and is the one objected to by Brouwer.

Conclusion

If we assume only simple consistency for Hilbert’s system, then we cannot unconditionally define:

$[(\exists x)F(x)]$ is true in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ if, and only if, $F(n)$ holds for some natural number $n$ in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$.

This follows since, if $[(\exists x)F(x)]$ is true in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ if, and only if, $F(n)$ holds for some natural number $n$ in $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$, then PA is necessarily $\omega$-consistent — which is not the case.

Thus the interpretation $\mathcal{I}_{PA(\mathcal{N},\ Standard)}$ is not a model of PA, and Brouwer was justified in his objection to Hilbert’s unqualified interpretation of quantification.

References

Br08 L. E. J. Brouwer. 1908. The Unreliability of the Logical Principles. English translation in A. Heyting, Ed. L. E. J. Brouwer: Collected Works 1: Philosophy and Foundations of Mathematics. Amsterdam: North Holland / New York: American Elsevier (1975): pp.107-111.

Go31 Kurt Gödel. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by Elliott Mendelson. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. pp.5-38.

Hi27 David Hilbert. 1927. The Foundations of Mathematics. In The Emergence of Logical Empiricism. 1996. Garland Publishing Inc.

Hi30 David Hilbert. 1930. Die Grundlegung der elementaren Zahlenlehre. Mathematische Annalen. Vol. 104 (1930), pp.485-494.

Mu91 Chetan R. Murthy. 1991. An Evaluation Semantics for Classical Proofs. Proceedings of Sixth IEEE Symposium on Logic in Computer Science, pp. 96-109, (also Cornell TR 91-1213), 1991.

Tu36 Alan Turing. 1936. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, ser. 2. vol. 42 (1936-7), pp.230-265; corrections, Ibid, vol 43 (1937) pp.544-546. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York. pp.116-154.

An07 Bhupinder Singh Anand. 2007. Why we shouldn’t fault Lucas and Penrose for continuing to believe in the Gödelian argument against computationalism – I. The Reasoner, Vol(1)6 p3-4.

An12 Bhupinder Singh Anand. 2012. Evidence-Based Interpretations of PA. In Proceedings of the Symposium on Computational Philosophy at the AISB/IACAP World Congress 2012-Alan Turing 2012, 2-6 July 2012, University of Birmingham, Birmingham, UK.

Notes

Return to 5: We note that we can, in principle, define the classical satisfaction’ and truth’ of the formulas of a first order arithmetical language such as PA constructively under an interpretation using as evidence the computations of a simple functional language (in the sense of Mu91).