HTML reading edition · 2 source pages · Open the source PDF

Towards a proof-theoretic approach to plurality: numbers are logical constants

I shall introduce a logic based on term sequents. This new notion of sequent extends the power of cut elimination to systems which usually require equality axioms for their formulation, e.g. systems of arithmetic. Term sequents can be used to provide an elementary logic of number which, I shall argue, allows for a purely proof theoretic (and first order) account of arithmetic truth. Term sequent logic motivates a form of logicism whereby arithmetic is a logic in its own right, rather than a theory in, or a reduct of, some stronger system (such as higher order logic). Loosely put, term sequent logic allows us to present sequent rules for the arithmetic operations that are analogous to the rules for the sentential operations of first order logic.

The moral is that not all logical constants are sentential connectives, some connect terms, and among the logical connectives are not only ,, etc. but also ,, 1, 0.

1 The proof theoretic identification of logical constants

The proof theoretic account identifies certain sentential connectives as logical constants by regarding various sequent rules as definitions of their meaning. For formal and philosophical reasons, these definitional sequent rules should satisfy some structural properties: each rule should be a left or right rule for exactly one connective; the rules together should satisfy a cut elimination theorem. Some proponents of this approach go further and argue that only connectives satisfying these properties can be referred to as ‘logical’.

But the sentential nature of the sequent calculus does not allow it to isolate a particular term former, e.g. , and provide a sequent left or right rule just for that term former. Neither does the standard sequent calculus allow for a full cut elimination theorem to be given for even elementary arithmetic. Famous applications of cut elimination to systems of arithmetic have actually proved cut elimination modulo the axioms of primitive recursive arithmetic. Since these systems require some cuts in order to derive elementary arithmetic equalities, such systems cannot ground a proof theoretic account of arithmetic.

I claim that, using the framework of term sequents, we can extend the proof theoretic account of the sentential connectives to the term formers of arithmetic.

2 Term sequents: a proof theory for arithmetic

Term sequents have the form Γ Θ :: Θ, where :: is a relation between two multisets (of multisets) of terms Θ and Θ. A term sequent therefore expresses a relation Θ :: Θ between terms as a consequence of a set Γ of sentences. Intuitively a term sequent Γ Θ :: Θ means that Θ equals Θ on the assumptions that Γ, where Θ and Θ are sums of products of terms. Examples of term sequent rules are given in Figure 1.

Combining term sequents with sentence sequents – which have the familiar form Γ ∆ (Figure 2) – we obtain a derivation system TA strong enough to derive all the atomic arithmetic facts. That is, TA is decidable for the language generated by B :: t1 t2 t1 t2B B1B2 where terms t1, t2 are closed terms (and t t2 is short for xt1x1 t2). Put another way, for any closed t1, t2, TA t1 t2 or TA t1 t2, and also TA t1 t2 or TA t2 t1.

TA satisfies cut elimination, full cut elimination, TA contains no axioms nor any essential cuts. The cut elimination theorem for TA entails the consistency and non-triviality of TA purely syntactically.

ΓΘ :: ΘAxΘ atomicΓΘ,:: Γ∆TΓtt1, Θ1 :: tt2, Θ2Γ, titjΘ1 :: Θ2Li1, j2 or i2, j1Γt1 :: t2Γtitj, ∆Ri1, j2 or i2, j1ΓΘ, t :: ΘΓΘ, 1t :: Θ1LΓΘ:: Θ, t ΓΘ:: Θ, 1t1RΓΘ :: ΘΓΘ, 0t :: Θ0LΓΘ:: Θ ΓΘ:: Θ, 0t0RΓΘ, tt1, tt2 :: ΘΓΘ, tt1t2:: ΘLΓΘ:: Θ, tt1, tt2ΓΘ:: Θ, tt1t2RΓΘ, tt1t2 :: ΘΓΘ, tt1t2:: ΘLΓΘ:: Θ, tt1t2ΓΘ:: Θ, tt1t2R
Figure 1: Term sequent rules of TA
Γ, Ai∆ Γ, A1A2∆L1i2ΓA1, ∆ ΓA2, ∆ ΓA1A2, ∆RΓC, ∆ Γ, C∆ Γ∆CutΓ, Axt∆ Γ,xA∆LΓA, ∆ ΓxA, ∆Rx not free in Γ, ∆Γ, A∆ ΓA, ∆RΓA, ∆ Γ,A∆L
Figure 2: Sentence sequent rules of TA

3 Numbers, arithmetic meaning and truth

I argue that TA provides a proof theoretic characterisation of the meanings of the basic arithmetic terms and operations 0, 1,,. TA itself is not strong enough to prove all arithmetic facts. I argue that this is a virtue, for it does not tie the meanings of the basic arithmetical terms to any particular arithmetic structure. Indeed, it is not hard to extend TA so that it becomes a theory of rational numbers as well as positive integers. Still further extensions are also possible.

To account for arithmetic truths I suggest that we treat quantifiers over natural numbers substitutionally. That is, I propose that when we appear to quantify objectually over numbers, we are in fact quantifying substitutionally over numerals. Since a complete logic of the behaviour of numerals is given by TA, this legitimates the substitutional interpretation of the quantifiers. Furthermore, on this approach, we can regard the relation numerals have to numbers as akin to the relation sentential connectives have to truth functions and variable assignments. Thus we can regard numbers as semantic devices that help explain the contribution numerals make to the truth conditions of sentences containing them. Beyond this, I claim, we need no metaphysics of number.

4 Further applications

Term sequents make for a flexible framework. By choosing the right term sequent structure and imposing derivation rules, we can build logics for different algebras of terms. I shall describe one further application of particular relevance: we can use term sequents to provide a logic for the basic mereological connectives and operations ,c, (i.e. the language of set theory without set membership). This provides a first order logic for plural terms and predication.