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

One-and-a-halfth-order Logic

Murdoch J. Gabbay ∗ Dept. of Computer Science Heriot-Watt University Riccarton, Edinburgh EH14 4AS UK murdoch.gabbay@gmail.com

Aad Mathijssen Dept. of Mathematics and Computer Science Eindhoven University of Technology (TU/e) P.O. Box 513, 5600 MB Eindhoven The Netherlands aad.mathijssen@gmail.com

Abstract

The practice of first-order logic is replete with meta-level concepts. Most notably there are the meta-variables themselves (ranging over predicates, variables, and terms), assumptions about freshness of variables with respect to these meta-variables, alpha-equivalence and capture-avoiding substitution. We present one-and-a-halfth-order logic, in which these concepts are made explicit. We exhibit both algebraic and sequent specifications of one-and-a-halfth-order logic derivability, show them equivalent, show that the derivations satisfy cut-elimination, and prove correctness of an interpretation of first-order logic within it.

We discuss the technicalities in a wider context as a case-study for nominal algebra, as a logic in its own right, as an algebraisation of logic, as an example of how other systems might be treated, and also as a theoretical foundation for future implementation.

Categories and Subject Descriptors F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic—Proof theory

General Terms Theory

Keywords First-order logic, α-conversion, meta-variables, nominal terms, Fraenkel-Mostowski techniques, higher-order logic.

1. Introduction

Consider the following valid assertions about first-order predicate logic with equality (FOL) [2, 4], written in standard notation also explained later in this document:

• φ ⊃ (ψ ⊃φ),

• if a ∉ fn(φ) then φ ⊃ (φ⟦a↦ →t⟧),

• if a ∉ fn(φ) then φ ⊃∀a.φ,

• if a, b ∉ fn(φ) then (∀a.φ) ⊃∀b.φ,

• if a ∉ fn(φ) then ∀a.(φ ⊃ψ) ⊃ (φ ⊃∀a.ψ),

• if a ∉ fn(φ) then ψ ⊃ (φ ⊃∀a.φ),

• ∀b.∀a.φ ⊃∀a.φ⟦b↦ →a⟧, are derivable.

These assertions cannot be proved in FOL, since FOL derivations involve FOL syntax, while the syntax of the assertions just given contains meta-variables φ, ψ, a, b and t. These are not FOL syntax, they vary over FOL syntax. Also we refer to properties of syntax when we write ‘a ∉ fn(φ)’ and ‘φ⟦a↦ →t⟧’, but FOL syntax cannot represent these explicitly.

Of course to us humans this is all obvious. One reason is that the derivations fall into a limited number of schema. For example the ‘derivation’ below on the left:

(Ax)ψ, φ ⊢φ(⊃R)φ ⊢ψ ⊃φ(⊃R)⊢φ ⊃(ψ ⊃φ)(Ax)⊥, ⊥⊢⊥(⊃R)⊥⊢⊥⊃⊥(⊃R)⊢⊥⊃(⊥⊃⊥)

is not a derivation, but it obviously represents a schema of derivations of which the (real) derivation on the right is an instance setting φ and ψ to ⊥. But is there a logic in which the beast on the left is a derivation too?

Note that it has been pointed out before that meta-variables varying over syntax are not themselves syntax, and that schematic derivations are not real derivations [20, page 7] (Hodges calls them ‘argument schema’). Many authors do leave meta-variables at the meta-level. Some suggest that this is where they belong!

We feel that as mathematical computer scientists it is reasonable, nay our duty, to pursue formalisation whenever possible. Logic teaches us that reasoning can and should be formalised, not only its conclusions. So if we use meta-variables in reasoning, we can and should ask ‘what is the mathematics of this reasoning’?

This paper presents one-and-a-halfth-order logic, a generalisation of first-order logic in which meta-variables and properties of syntax are made explicit.

We briefly mention the main technical barriers involved:

• ∀a.φ and ∀b.φ need not be α-convertible if φ mentions a and b free, so any syntactic representation which represents the meta-variable φ must sacrifice α-equivalence or some part of it. What is a suitable representation of meta-variables and how does it interact with binding?

• In the presence of meta-variables substitution becomes nontrivial, since the ∀-left intro rule (see Subsection 8.2) demands we reason about φ⟦a↦ →t⟧ where ⟦a↦ →t⟧ means ‘replace a by t’. What is a suitable and correct representation of substitution, and what are its properties?

• Once these problems are solved, what derivation rules manage the extra complexity involved so that derivations remain faithful to ‘first-order logic style’, and cut-elimination is (fairly) easily provable?

Without further ado we give derivation rules of one-and-a-halfth-order logic in Figure 1. Also, Figure 2 includes one-and-a-halfth-order logic derivations of the assertions above (in the last three examples, we left out the use of (⊃R) on the top-level implications).

Explanations and technical machinery follow in the rest of this paper. In Sections 2 to 4 we introduce the syntax and an equational axiomatisation of one-and-a-halfth-order logic in terms of nominal algebra. In Sections 5 to 7 we develop the sequent calculus of Figure 1 and establish properties including cut-elimination and equivalence with the axiomatisation. In Section 8 we show that a subset of one-and-a-halfth-order logic is equivalent to first-order logic. We discuss related and future work in the Conclusions.

2. Nominal algebra

We need a syntax in which ∀a.φ, a ∉ fn(φ), and φ⟦a↦ →t⟧ may be explicitly represented. For this we use Nominal Terms [29], which offer built-in support for meta-variables, abstraction, and freshness. In this section, we describe nominal terms and the framework of Nominal Algebra [15], which is a theory of equational equality for nominal terms.

2.1 Sorts and terms

Fix two base sorts P of predicates and T of terms; we may indicate these with δ. Fix a sort of atoms A. Define sorts τ:

τ ::= δ | A | [A]τ

The intuition of [A]τ is ‘elements of τ with an atom abstracted’. This has no intuitive functional denotation, e.g. [τ ′]τ is not a valid sort. ([A]τ behaves more like the set of α-equivalence classes of elements of τ with a distinguished bound atom.)

Fix countably infinite disjoint collections of atoms a, b, c, and unknowns X, Y, Z.

Atoms represent object-level variable symbols, for examples see a, b in the Introduction. They will have sort A. Unknowns represent meta-level variables, for examples see φ, ψ, t in the Introduction. Unknowns may have any sort and we assume that they are inherently sorted (and that there are infinitely many of each sort). We may write X : τ as shorthand for ‘X, which has sort τ’. We tend to give unknowns of sort P names P, Q, R and unknowns of sort T names T, U.

A term-former is a syntactic token f with an associated arity ρ = (τ1, . . . , τn)τ, where n ≥ 0. We may write f : ρ as shorthand for ‘f, which has arity ρ’. Fix the following term-formers:

⊥: ()P ⊃: (P, P)P ∀: ([A]P)P ≈: (T, T)Pvar : (A)T sub : ([A]τ, T)τ (τ ∈{T, [A]T, P, [A]P})

We discuss the intuitive meanings of these term-formers after we have defined terms.

We call term-formers with arities (T, . . . , T)T object-level term-formers; one example could be + : (T, T)T. We call term-formers with arities (T, . . . , T)P atomic predicate-formers; one example is ≈, others are socrates : (T)P and greek : (T)P. These too can be added and cause no difficulties for the results which follow.

We generally let f vary over all term-formers and (later in the paper) we let of vary over object-level term-formers, and op vary over atomic predicate-formers (‘o’ for ‘object-level’).

Terms t, u, v are inductively defined by:

t ::= aA | (π · Xτ)τ | ([aA]tτ)[A]τ | (f(τ1,...,τn)τ (t1 τ1, . . . , tn τn))τ

Here subscripts indicate sorting rules. We repeat the definition without them, just for clarity:

t ::= a | π · X | [a]t | f(t1, . . . , tn)

In case n = 0, we write f instead of f().

π is a permutation on atoms, we discuss π in the next subsection. We call π · X a moderated unknown; syntactically this is just a pair of a permutation and an unknown, but intuitively this represents the permutation π acting on an ‘unknown term’. This intuition is made concrete in the definition of substitution on moderated unknowns, below.

We may write t : τ as shorthand for ‘t of sort τ’. We may call terms φ : P predicates (not to be confused with atomic predicates like greek(var(a))).

We sugar the term-formers fixed earlier, and give their intuitive meaning. For any atoms a, b, terms t, u : T and predicates φ, ψ:

• ⊥ represents falsity.

• φ ⊃ψ is ⊃(φ, ψ). Intuitively, this is an implication.

• ∀[a]φ is ∀([a]φ). Intuitively, this is universal quantification (which takes an abstraction of a formula and yields a formula). Accordingly we call the syntax-fragment [a] an abstractor. It has no functional semantics; [a]t is intuitively merely t with a bound. The fact that ∀ takes an abstraction of a term and gives a term is imposed by its sort ([A]P)P.

• t ≈u is ≈(t, u). Intuitively, this is equality in the object-language.

• a is var(a). Intuitively, this term-former connects an atom a, which has sort A, and an object-level variable symbol var(a), which has sort T.

• v[a↦ →t] is sub([a]v, t) for any term v of sort T, [A]T, P or [A]P. Intuitively, this is substitution.

We use standard classical logic sugar:

¬φ is φ ⊃⊥ ⊤is ¬⊥φ ∧ψ is ¬(φ ⊃¬ψ) φ ∨ψ is ¬φ ⊃ψφ ⇔ψ is (φ ⊃ψ) ∧(ψ ⊃φ) ∃[a]φ is ¬∀[a]¬φ

To save on (unnecessary) parentheses, take [a] , [↦ →], ≈, {¬, ∀, ∃}, {∧, ∨}, ⊃, ⇔ as the descending order of precedence. Also let ∧, ∨, ⊃ and ⇔ associate to the right.

We write a ∈t (or X ∈t) for ‘a (or X) occurs in (the syntax of) t’. Occurrence is literal, e.g. a ∈ [a]a and a ∈π·X if π(a) ≠ a. We omit inductive definitions. Similarly we may write a ∉t and X ∉t for ‘does not occur in the syntax of t’.

Call t closed when t mentions no unknowns — t may still mention atoms, e.g. the term a is closed.

Write syntactic identity of terms t, u as t ≡u. This emphasises the difference from provable equality t = u, which is a logical assertion, and object-level equality t ≈u, which is a term.

2.2 Permutations and substitutions

A permutation π of atoms is a total bijection A →A with finite support, meaning that for some finite set of atoms (which may be empty) π(a) ≠ a, but for all atoms not in that set, π(a) = a. This is a mathematical notion of ‘most’: π(a) = a for most a.

As usual, we write Id for the identity permutation, π-1 for the inverse of π, and π ◦π′ for the composition of π and π′, i.e. (π ◦π′)(a) = π(π′(a)). Id is also the identity of composition, i.e. Id ◦π = π and π ◦ Id = π. We may abbreviate Id · X to X.

We write π · t for the action of a permutation on a term, defined inductively on syntax by:

π · a ≡π(a) π · (π′ · X) ≡(π ◦π′) · Xπ · [a]t ≡[π(a)](π · t) π · f(t1, . . . , tn) ≡f(π · t1, . . . , π · tn)
Lemma 2.1

(π ◦π′) · t ≡π · (π′ · t) and Id · t ≡t.

(Ax)φ, Φ ⊢∆Ψ, φ(⊥L)⊥, Φ ⊢∆ΨΦ ⊢∆Ψ, φ ψ, Φ ⊢∆Ψ(⊃L)φ ⊃ψ, Φ ⊢∆Ψφ, Φ ⊢∆Ψ, ψ(⊃R)Φ ⊢∆Ψ, φ ⊃ψφ[a↦ →t], Φ ⊢∆Ψ(∀L)∀[a]φ, Φ ⊢∆ΨΦ ⊢∆Ψ, ψ(∀R) (∆⊢a#Φ, Ψ)Φ ⊢∆Ψ, ∀[a]ψφ[a↦ →t′], Φ ⊢∆Ψ(≈L)t′ ≈t, φ[a↦ →t], Φ ⊢∆Ψ(≈R)Φ ⊢∆Ψ, t ≈tφ′, Φ ⊢∆Ψ(StructL)φ, Φ ⊢∆Ψ(∆⊢SUB φ′ = φ)Φ ⊢∆Ψ, ψ′(StructR)Φ ⊢∆Ψ, ψ(∆⊢SUB ψ′ = ψ)Φ ⊢∆,a#X1,...,a#Xn Ψ(Fr) (a ∉Φ, Ψ, ∆)Φ ⊢∆ΨΦ ⊢∆Ψ, φ φ′, Φ ⊢∆Ψ(Cut)Φ ⊢∆Ψ(∆⊢SUB φ = φ′)
Figure 1. Sequent calculus for one-and-a-halfth-order logic
(Ax)Q, P ⊢∅P(⊃R)P ⊢∅Q ⊃P(⊃R)⊢∅P ⊃(Q ⊃P)(Ax)P ⊢a#P P(StructR) (a#P ⊢SUB P = P[a↦→T])P ⊢a#P P[a↦ →T](⊃R)⊢a#P P ⊃(P[a↦ →T])(Ax)P ⊢a#P P(∀R) (a#P ⊢a#P)P ⊢a#P ∀[a]P(⊃R)⊢a#P P ⊃∀[a]P(Ax)∀[a]P ⊢a#P,b#P ∀[a]P(StructR) (a#P, b#P ⊢SUB ∀[a]P = ∀[b]P)∀[a]P ⊢a#P,b#P ∀[b]P(⊃R)⊢a#P,b#P (∀[a]P) ⊃∀[b]P(Ax)P ⊢a#P Q, P(Ax)Q, P ⊢a#P Q(⊃L)P, P ⊃Q ⊢a#P Q(StructL) (a#P ⊢SUB P ⊃Q = (P ⊃Q)[a↦ →a])P, (P ⊃Q)[a↦ →a] ⊢a#P Q(∀L)P, ∀[a](P ⊃Q) ⊢a#P Q(∀R) (a#P ⊢a#P, ∀[a](P ⊃Q))P, ∀[a](P ⊃Q) ⊢a#P ∀[a]Q (Ax)P, Q ⊢a#P,b#P,Q P(StructR) (a#P, b#P, Q ⊢SUB P = (a b) · P)P, Q ⊢a#P,b#P,Q (a b) · P(∀R) (a#P, b#P, Q ⊢b#P, Q)P, Q ⊢a#P,b#P,Q ∀[b](a b) · P(StructR) (a#P, b#P, Q ⊢SUB ∀[b](a b) · P = ∀[a]P)P, Q ⊢a#P,b#P,Q ∀[a]P(Fr) (b ∉P, Q, ∀[a]P, a#P)P, Q ⊢a#P ∀[a]P(Ax)P[b↦ →c][a↦ →c] ⊢c#P P[b↦ →c][a↦ →c](∀L)∀[a](P[b↦ →c]) ⊢c#P P[b↦ →c][a↦ →c](StructL) (c#P ⊢SUB ∀[a](P[b↦ →c]) = (∀[a]P)[b↦ →c])(∀[a]P)[b↦ →c] ⊢c#P P[b↦ →a][a↦ →c](∀L)∀[b]∀[a]P ⊢c#P P[b↦ →c][a↦ →c](∀R) (c#P ⊢c#∀[b]∀[a]P)∀[b]∀[a]P ⊢c#P ∀[c](P[b↦ →c][a↦ →c])(StructR) (c#P ⊢SUB ∀[c](P[b↦ →c][a↦ →c]) = ∀[a](P[b↦ →a]))∀[b]∀[a]P ⊢c#P ∀[a](P[b↦ →a])(Fr) (c ∉∀[b]∀[a]P, ∀[a](P[b↦ →a]))∀[b]∀[a]P ⊢∅∀[a](P[b↦ →a])
Figure 2. Example derivations in one-and-a-halfth-order logic

In this section we omit proofs of lemmas; they are all quite routine. Full proofs are available elsewhere [7, 29].

A substitution σ is a finitely supported sort-respecting function from unknowns to terms. Here, finitely supported means that for some finite set of unknowns σ(X) ≢ Id · X, but for all other unknowns σ(X) ≡ Id · X. Sort-respecting means that for each X the term σ(X) should have the same sort as X.

Write [t1/X1, . . . , tn/Xn] for the substitution σ such that σ(Xi) ≡ti and σ(Y) ≡ Id ·Y , for all Y ≢Xi, 1 ≤i ≤n. Write [] for the empty substitution, which maps each X to Id · X.

Write a ∈σ if there exists an X such that a ∈σ(X), and similarly write a ∉X if there is no such X.

A substitution σ has a natural action on terms t, inductively defined by:

aσ ≡a (π · X)σ ≡π · σ(X)([a]t)σ ≡[a](tσ) f(t1, . . . , tn)σ ≡f(t1σ, . . . , tnσ)

Give substitution and permutation actions higher precedence than abstraction and any of the sugared term-formers, and put substitution before permutation.

Note how substitution interacts with permutation in the case of an unknown, for example ((a b) · X)[b/X] ≡ (a b) · b ≡a. So π in X is ‘waiting for a substitution to arrive’, as also made formal in the following property:

Lemma 2.2

π · tσ ≡ (π · t)σ.

Another permutation action will be useful. Write tπ for the meta-level action of π on t, which is defined by:

aπ ≡π(a) (π′ · X)π ≡(π′π) · X([a]t)π ≡[π(a)](tπ) f(t1, . . . , tn)π ≡f(t1π, . . . , tnπ)

where π′π = π ◦π′ ◦π-1 (this is the conjugation action [9]).

Lemma 2.3

Fix t and π, and let σ map X ∈t to π · X, and σ′ map X ∈t to π-1 · X. Then π · t ≡tπσ and tπ ≡ (π · t)σ′.

So the two permutation actions are interdefinable in the presence of substitution σ; however, sometimes one is more natural than the other, we shall point out how, later.

2.3 Assertions, axioms and derivations

Nominal algebra has two forms of assertions:

1. A freshness (assertion) is a pair a#t of an atom and a term. If t ≡X we call the assertion primitive.

2. An equality (assertion) is a pair t = u where t and u are terms of the same sort, we discuss them below.

Write ∆ for a (possibly infinite) set of primitive freshnesses and call it a freshness context. We may drop set brackets in freshnesses, e.g. writing a#t, b#u for {a#t, b#u}. Also, we may write a#t, u for a#t, a#u.

Extend the notions of occurrence, closedness, permutation actions and substitution action pointwise to assertions and freshness contexts. Note that for a freshness context ∆, ∆σ need not be a freshness context since each unknown X in ∆ is replaced by σ(X), which is a term and need not be an unknown.

Call a pair ∆→t = u of a finite freshness context ∆ and an equality assertion t = u an axiom. If ∆= ∅, we may write the axiom just t = u.

Nominal algebra (NA) [15] is the logic of equality between nominal terms. We define the derivation rules of NA by the rules in Figure 3.

In this figure f ranges over term-formers,1 t, u, v and t1, . . . , tn range over terms, X ranges over unknowns, π over permutations, σ over substitutions, ∆ over freshness contexts, and a and b permutatively range over atoms, i.e. a and b represent any two distinct atoms. We use similar conventions henceforth. C[ ] is a context, it is introduced later.

Write ∆⊢a#t when a derivation of a freshness assertion a#t exists using the elements of ∆ as assumptions, according to the rules above. Say that ∆ entails a#t or a#t is derivable from ∆.

Call a (possibly infinite) set of axioms T a theory. We write ∆⊢T t = u when a derivation of t = u exists using the rules above, such that every assumption used is a freshnesses from ∆, and for every use of (axA) A is an axiom of T. Say that ∆ entails t = u or t = u is derivable from ∆.

For example, taking A ≡a = b and B ≡ [a]X = [b]Y as axioms, the derivations

(axA)b = c(axB)[b]b = [a]a

are valid taking π = (a b c) and any σ, and π = (a b) and σ = [b/X, a/Y], respectively. Note that it is not possible to derive a = a using (axA).

Taking C ≡a#X → [a]X = [b]X, of the derivations

(#ab)a#b(axC)[a]b = [b]ba#a(axC)[a]a = [b]a

the left one is valid, but the right one is not, because a#a is not derivable.

So now we appear to have two derivation systems; the sequent calculus for one-and-a-halfth-order logic from Figure 1 and nominal algebra from Figure 3, both using nominal terms! We shall soon show that a particular nominal algebra theory gives rise to one-and-a-halfth-order logic.

For the rest of this subsection we discuss the derivation rules of Figure 3.

Contexts C[ ] is the usual notion of context as being a ‘term with a hole’. Note that this notion may be represented directly in our syntax taking a term C with a distinguished unknown X — call it ‘the hole’ — which occurs in C only as Id · X (so not under a moderation, e.g. not as (a b) · X or somesuch). We can then define C[t] ≡C[t/X]. The restriction on the moderation is to ensure that t really does occur in C[t] and not some renamed version of it.

Note that C may contain abstractors, e.g. C ≡ [a][b]X, and that the substitution [t/X] can capture under these abstractors, e.g. C[a] = [a][b]a. See [7] for a fuller treatment of this observation.

For example, (a b)·X and g(X, X) (X is a shorthand for Id·X) are not contexts. X and h(X) are contexts. Here g and h are term-formers with arities of the form (τ, τ)τ ′ and (τ)τ ′, respectively.

The rule (fr) In (fr) square brackets denote discharge in the sense of natural deduction (as in implication introduction [20]); ∆ denotes the other assumptions of the derivation of t = u.

The rule generates ‘fresh atoms’. Clearly a ∉t, u, ∆ manifests this intuition, but also we must account for unknowns which (intuitively) represent unknown terms. Thus to generate an atom that is really fresh, also for the unknown terms we use, we insist on this explicitly with freshness conditions.

The axiom rule (axA) Where the axiom A is understood or irrelevant we may write just (ax) (and (ax′), see below).

In (ax) atoms are permuted and unknowns are instantiated. Thus atoms stand for any atoms but in a way which preserves their distinctness, whereas unknowns stand for any term at all.

(#ab)a#bπ-1(a)#X(#X)a#π · X(#[]a)a#[a]ta#t(#[]b)a#[b]ta#t1 · · · a#tn(#f)a#f(t1, . . . , tn)(refl)t = tt = u(symm)u = tt = u u = v(tran)t = vt = u(cong)C[t] = C[u]a#t b#t(perm)(a b) · t = t∆πσ(axA)tπσ = uπσA ≡∆→t = u[a#X1, . . . , a#Xn] ∆··· t = u(fr) (a ∉t, u, ∆)t = u
Figure 3. Derivation rules of nominal algebra

Recall the discussion of π · t versus tπ above. Another axiom rule is possible:

π · ∆σ(ax′ A)π · tσ = π · uσA ≡∆→t = u

however in this case, atoms in the substitution σ are renamed according to permutation π, which turns out to be rather mind-bending. For example, from the axiom [a]X = [b]X it is immediate that ⊢ [b]a = [a]a is derivable using (ax) where we choose π = (b a) and σ = [a/X]. If we use (ax′) we must choose π = (b a) and σ = [b/X].

3. Theories

Recall that a theory is a (possibly infinite) set of axioms. Write CORE for the theory which is the empty set. Other theories of interest are listed in Figures 4 and 5.

We use a shorthand in each of those figures that the theory includes the axioms listed in the figure and the axioms of previous theories:

CORE ⊂SUB ⊂FOL.

In the figures, f ranges over all term-formers of appropriate sort, a, b are particular, but arbitrary, distinct atoms, P, Q, R are unknowns of sort P, and T, U are unknowns of sort T, and X, X1, . . . , Xn are unknowns of appropriate sorts.

The theories have the following intuitive meaning:

1. CORE is a theory of α-equivalence.

2. SUB is a theory of capture-avoiding substitution.

3. FOL is first-order logic — with unknowns!

We will show how and why in the rest of this paper.

Theory SUB is discussed in detail in [14]. The rest of this section discusses theory FOL.

In Figure 5 we should think of a term of the form ‘φ = ⊤’ as meaning intuitively ‘φ is true’. Thus, it expresses a Hilbert-style axiom. The first block of rules are then standard axioms [21] of classical propositional logic, we call them propositional axioms. The second block adds quantifiers, we call them quantifier axioms; they exploit NA freshness conditions. The third block adds object-level equality, we call them equational axioms. Together, we call them the logical axioms.

Note that the quantifier axioms are not new! They appear in the literature [10, page 5 (2)], just like the propositional ones. What is new is that our axioms are not axiom-schemes but individual axioms; this, because we have meta-variables. Using nominal terms we can also represent such axiom schemes faithful to their ‘usual’ syntactic form. The next step is to show that they also admit a proof-theory.

There are interesting theories besides FOL (see the Conclusions).

4. Sequent-like admissible rules

For our first technical results we show that the rules like those of Figure 1, are valid in theory FOL.

Lemma 4.1

For all freshness contexts ∆ and predicates φ, ψ:

1. ∆⊢FOL φ ⇔ψ = ⊤ if and only if ∆⊢FOL φ = ψ;

2. ∆⊢FOL φ ⊃ψ = ⊤ if and only if ∆⊢FOL φ = φ ∧ψ.

Proof

We only prove the first part; the second is similar. For the right-to-left implication, we reduce the consequent to φ ⇔φ = ⊤ by congruence using φ = ψ; then the result follows easily.

For the left-to-right implication, suppose φ ⇔ψ = ⊤ is derivable using ∆. Then

φ = φ ∧⊤= φ ∧(φ ⇔ψ) = φ ∧ψ.

Similarly we can derive ψ = φ ∧ψ whence φ = ψ as required. □

Lemma 4.2

⊢FOL ∀[a]⊥= ⊥ is derivable.

Proof

It suffices to derive ∀[a]⊥⇔⊥= ⊤, by part 1 of Lemma 4.1. Or without sugar for ⇔:

(∀[a]⊥⊃⊥) ∧(⊥⊃∀[a]⊥) = ⊤.

By standard calculations using the propositional axioms, this follows from ∀[a]⊥⊃⊥= ⊤ and ⊥⊃∀[a]⊥= ⊤. The latter follows directly from the last propositional axiom. The former is derived as follows:

(ax)⊥[a↦→T]=⊥(symm)⊥=⊥[a↦→T](cong)∀[a]⊥⊃⊥=∀[a]⊥⊃⊥[a↦→T](ax)∀[a]⊥⊃⊥[a↦→T]=⊤(tran)∀[a]⊥⊃⊥=⊤
□

Note that by this result our intuition of FOL is that the denotation of T is a non-empty set; if T has (intuitively) an empty set as denotation then ∀[a]⊥= ⊤ would be possible for some models and ∀[a]⊥= ⊥ should not be derivable. This is due to an interaction of the first quantifier axiom with the rest of the theory, and is also present in most treatments of first-order logic [20].2

(var↦ →) a[a↦ →T] = T(#↦ →) a#X →X[a↦ →T] = X(f↦ →) f(X1, . . . , Xn)[a↦ →T] = f(X1[a↦ →T], . . . , Xn[a↦ →T])(abs↦ →) b#T →([b]X)[a↦ →T] = [b](X[a↦ →T])(ren↦ →) b#X →X[a↦ →b] = (b a) · X
Figure 4. Axioms of SUB
P ⊃Q ⊃P = ⊤ ¬¬P ⊃P = ⊤ (P ⊃Q) ⊃(Q ⊃R) ⊃(P ⊃R) = ⊤ ⊥⊃P = ⊤ (Props)∀[a]P ⊃P[a↦ →T] = ⊤ ∀[a](P ∧Q) ⇔∀[a]P ∧∀[a]Q = ⊤ a#P →∀[a](P ⊃Q) ⇔P ⊃∀[a]Q = ⊤ (Quants)T ≈T = ⊤ U ≈T ∧P[a↦ →T] ⊃P[a↦ →U] = ⊤ (Eq)
Figure 5. Axioms of FOL
Lemma 4.3

For all predicates φ, φ′, ψ, ψ′, θ, ε, atoms a, terms t, t′: T, and unknowns X1, . . . , Xn:

1. ∆⊢FOL φ ∧θ ⊃ε ∨φ = ⊤

2. ∆⊢FOL ⊥∧θ ⊃ε = ⊤

3. if ∆⊢FOL θ ⊃ε ∨φ = ⊤ and ∆⊢FOL ψ ∧θ ⊃ε = ⊤ then ∆⊢FOL (φ ⊃ψ) ∧θ ⊃ε = ⊤

4. if ∆⊢FOL φ ∧θ ⊃ε ∨ψ = ⊤

then ∆⊢FOL θ ⊃ε ∨(φ ⊃ψ) = ⊤

5. if ∆⊢FOL φ[a↦ →t] ∧θ ⊃ε = ⊤

then ∆⊢FOL ∀[a]φ ∧θ ⊃ε = ⊤

6. if ∆⊢FOL θ ⊃ε ∨ψ = ⊤ and ∆⊢a#θ, ε

then ∆⊢FOL θ ⊃ε ∨∀[a]ψ = ⊤

7. if ∆⊢FOL φ[a↦ →t′] ∧θ ⊃ε = ⊤

then ∆⊢FOL (t′ ≈t) ∧φ[a↦ →t] ∧θ ⊃ε = ⊤

8. ∆⊢FOL θ ⊃ε ∨(t ≈t) = ⊤

9. if ∆⊢FOL φ′ ∧θ ⊃ε = ⊤ and ∆⊢SUB φ′ = φ then ∆⊢FOL φ ∧θ ⊃ε = ⊤

10. if ∆⊢FOL θ ⊃ε ∨ψ′ = ⊤ and ∆⊢SUB ψ′ = ψ then ∆⊢FOL θ ⊃ε ∨ψ = ⊤

11. if ∆, a#X1, . . . , a#Xn ⊢FOL θ ⊃ε = ⊤ and a ∉θ, ε, ∆ then ∆⊢FOL θ ⊃ε = ⊤

12. if ∆⊢FOL θ ⊃ε ∨φ = ⊤, ∆⊢FOL φ′ ∧θ ⊃ε = ⊤ and ∆⊢SUB φ = φ′ then ∆⊢FOL θ ⊃ε = ⊤

Proof

The proofs of the first four items are standard and establish the equivalence of Hilbert- and sequent-style presentations of propositional logic.

For item 5 we use item 2 of Lemma 4.1. Then we need to show that ∆⊢FOL ∀[a]φ ∧θ = ∀[a]φ ∧θ ∧ε follows from the assumption ∆⊢FOL φ[a↦ →t] ∧θ = φ[a↦ →t] ∧θ ∧ε. Also, by this item and the first quantifier axiom, ∆⊢FOL ∀[a]φ = ∀[a]φ ∧φ[a↦ →t] holds.

We reason algebraically, implicitly using associativity of ∧:

∀[a]φ ∧θ= { ∆⊢FOL ∀[a]φ = ∀[a]φ ∧φ[a↦ →t] } ∀[a]φ ∧φ[a↦ →t] ∧θ= { ∆⊢FOL φ[a↦ →t] ∧θ = φ[a↦ →t] ∧θ ∧ε } ∀[a]φ ∧φ[a↦ →t] ∧θ ∧ε= { ∆⊢FOL ∀[a]φ = ∀[a]φ ∧φ[a↦ →t] } ∀[a]φ ∧θ ∧ε

The calculations for items 6 to 12 are in the same spirit, except for item 11 which is trivially deduced using (fr). □

5. Sequent presentation

We are now ready to directly confront Figure 1.

Let (predicate) contexts Φ, Ψ be finite (possibly empty) sets of predicates. A sequent is a triple Φ ⊢∆ Ψ where ∆ is a freshness context and Φ and Ψ are predicate contexts; when a context appears to the right of ⊢ we may call it a co-context.

We may write φ for {φ}, φ, Φ for {φ}∪Φ, and Φ, Φ′ for Φ∪Φ′, and we may omit empty predicate contexts, e.g. writing ⊢∆ for ∅⊢∆∅.

Extend the notions of occurrence, closedness, permutation actions and substitution action elementwise to predicate contexts.

Define the sequent calculus for one-and-a-halfth-order logic to be the set of sequents inductively specified by the derivation rules in Figure 1. We may also call this set an entailment relation (that of one-and-a-halfth-order logic, to be precise).

Call (StructL) and (StructR) structural rules. (Cut) can emulate them, but we would lose cut-elimination. To see why (Fr) is useful, consider the last two examples in Figure 2.

Our rules resemble those of Gentzen’s sequent calculus for classical first-order logic with equality [6, 17, 26], but with the following distinctive features:

• There is an explicit notion of unknown predicates given by the unknowns of sort P, which models meta-variables in the sense that, for example, ∀[a]P with [(a ≈a)/P] is ∀[a](a ≈a) (and not ∀[a′](a ≈a)).

• Freshness, α-equivalence and capture-avoiding substitution are now explicit; they are represented by derivability of freshnesses and equality in SUB as side-conditions.

As we used standard classical logic sugar like ¬P for P ⊃⊥, so we also ‘use’ the standard sequent rules for them (as sugar for ‘macros’ of sequent rules) without comment.

The sequent calculus is able to mimick the logical axioms from Figure 5:

Lemma 5.1

The following are derivable:

1. ⊢∆φ ⊃ψ ⊃φ. 2. ⊢∆¬¬φ ⊃φ.

3. ⊢∆ (φ ⊃ψ) ⊃ (ψ ⊃ρ) ⊃ (φ ⊃ρ). 4. ⊢∆⊥⊃φ.

5. ⊢∆∀[a]φ ⊃φ[a↦ →t].

6. ⊢∆∀[a](φ ∧ψ) ⇔∀[a]φ ∧∀[a]ψ.

7. If ∆⊢a#φ then ⊢∆∀[a](φ ⊃ψ) ⇔φ ⊃∀[a]ψ.

8. ⊢∆t ≈t. 9. ⊢∆u ≈t ∧φ[a↦ →t] ⊃φ[a↦ →u].

Proof

We consider just item 7. By (⇔R) and (⊃R) it suffices to derive

(a) φ, ∀[a](φ⊃ψ) ⊢∆∀[a]ψ. (b) φ⊃∀[a]ψ ⊢∆∀[a](φ⊃ψ).

We consider (a); showing (b) derivable follows similar lines:

(Ax)φ ⊢∆ψ, φ(Ax)φ, ψ ⊢∆ψ(⊃L)φ, φ ⊃ψ ⊢∆ψ(StructL)φ, (φ ⊃ψ)[a↦ →a] ⊢∆ψ(∀L)φ, ∀[a](φ ⊃ψ) ⊢∆ψ(∀R)φ, ∀[a](φ ⊃ψ) ⊢∆∀[a]ψ

The uses of (StructL) and (∀R) are valid because the following hold:

∆⊢SUB (φ ⊃ψ)[a↦ →a] = (φ ⊃ψ) ∆⊢a#φ, ∀[a](φ ⊃ψ)

The corresponding calculations are interesting but have to do with NA and SUB, not FOL. See elsewhere for details [14]. □

We conclude this section with two theorems describing how derivations and their structure (for example the ones in Figure 2) interact with atoms and unknowns. In brief: atoms can be permuted, unknowns can be instantiated.

Extending notation for permutation action, we write Ππ for the result of applying π to the terms in the syntax of Π.

Theorem 5.2

If Π is a valid derivation of Φ ⊢∆ Ψ then Ππ is a valid derivation of Φπ ⊢∆π Ψπ.

Call this property meta-level equivariance.

Proof

The statement

‘Π is a valid derivation of Φ ⊢∆ Ψ’

has four free variables and so by FM equivariance [16] is invariant under permuting atoms. The result follows. □

Write Π(σ, ∆′) for the substitution action on derivations. It is inductively defined on the structure of Π:

• If Π concludes with a rule (R) different from (Fr), it is of the form

Π1· · · Πk(R) (cond)Φ ⊢∆Ψ

where k ∈{0, 1, 2} and cond is ∆⊢SUB φ = ψ, ∆⊢a#Φ′ or empty. Then Π(σ, ∆′) is

Π1(σ, ∆′) · · · Πk(σ, ∆′)(R) (cond ′)Φσ ⊢∆′ Ψσ

where cond′ is ∆′ ⊢SUB φσ = ψσ, ∆′ ⊢a#Φ′σ or empty, respectively.

• Otherwise, the derivation concludes in

Π′(Fr) (a ∉Φ, Ψ, ∆)Φ ⊢∆Ψ

where Π′ is a derivation of Φ ⊢∆,a#X1,...,a#Xn Ψ.

Then Π(σ, ∆′) is

Π′(a′ a)(σ, ∆′′)(Fr) (a′ ∉Φσ, Ψσ, ∆′)Φσ ⊢∆′ Ψσ

where a′ is chosen fresh (i.e. a′ ∉a, Φ, Ψ, ∆, ∆′, σ) and ∆′′ = ∆′, a′#Y1, . . . , a′#Ym, in which Y1, . . . , Ym are all unknowns mentioned in σ(Xi), for 1 ≤i ≤n.

So σ is consistently applied throughout the predicate contexts occurring in Π, ∆′ replaces ∆, and (Fr) may generate slightly different freshness assumptions.

Lemma 5.3

For any ∆′, ∆, σ, if ∆′ ⊢∆σ then:

1. if ∆⊢a#t then ∆′ ⊢a#tσ;

2. if ∆⊢T t = u then ∆′ ⊢T tσ = uσ.

Theorem 5.4

If ∆′ ⊢∆σ and Π is a valid derivation of Φ ⊢∆ Ψ then Π(σ, ∆′) is a valid derivation of Φσ ⊢∆′ Ψσ.

Call this property meta-level substitution.

Proof

By induction on Π. We only treat the cases (∀R) and (Fr). The other cases are similar to the (∀R) case or simpler.

1. The case of (∀R): Suppose Φ ⊢∆ Ψ, ∀[a]ψ is derived using (∀R). Then ∆⊢a#Φ, Ψ holds and Π′ is a derivation of Φ ⊢∆ Ψ, ψ. By Lemma 5.3 ∆′ ⊢a#Φσ, Ψσ, and by inductive hypothesis Π′(σ, ∆′) is a derivation of Φσ ⊢∆′ Ψσ, ψσ. Then we conclude that Φσ ⊢∆′ Ψσ, ∀[a]ψσ is derivable, by extending Π′(σ, ∆′) with (∀R), as required.

2. The case of (Fr): Suppose Φ ⊢∆ Ψ is derived using (Fr). Then Π′ is a derivation of Φ ⊢∆,a#X1,...,a#Xn Ψ where we assume a ∉ Φ, Ψ, ∆. By meta-level equivariance (Theorem 5.2) also Π′(a′ a) is a derivation of Φ ⊢∆,a′#X1,...,a′#Xn Ψ, where a′ is chosen fresh (i.e. a′ ∉a, Φ, Ψ, ∆, ∆′, σ). By FM equivariance validity of the property

‘Π′ has the inductive hypothesis’

is itself invariant under permuting atoms. So

‘Π′(a′ a) has the inductive hypothesis’

is also valid. Take ∆′′ = ∆′, a′#Y1, . . . , a′#Ym, where Y1, . . . , Ym are all the unknowns mentioned in σ(Xi), 1 ≤i ≤n. It is easy to deduce ∆′′ ⊢(∆, a′#X1, . . . , a′#Xn)σ. By inductive hypothesis Π′(a′ a)(σ, ∆′′) is a derivation of Φσ ⊢∆′′ Ψσ. Since a′ ∉ Φσ, Ψσ, ∆′ we may deduce Φσ ⊢∆′ Ψσ using (Fr), as required.

□

This use of FM equivariance is a powerful and general technique which we do not expand on here. To our knowledge its first use to obtain theorems in an actual paper (as opposed to being the object of investigation itself [16, 11]) is in a paper on ‘Fresh Logic’ [12]. Here we shall use it repeatedly to rename atoms in the presence of unknowns.

6. Cut-elimination

This technical section establishes a cut-elimination result (Theorem 6.8) and a consistency corollary (Corollary 6.9).

We need some notation and technical lemmas. Call the depth of a derivation the greatest number of derivation steps not counting rules (Fr), (StructL) and (StructR) between its conclusion and its leaves, over all paths. We do not count NA derivations of freshnesses and equalities that occur as side-conditions. For example, the last two derivations of Figure 2 have depth 2 and 4, respectively.

Lemma 6.1

If ∆⊢a#Φ, Ψ and ∆⊢b#Φ, Ψ then

Φ, Φ′ ⊢∆ Ψ, Ψ′ if and only if Φ, (a b) · Φ′ ⊢∆ Ψ, (a b) · Ψ′.

The derivation has the same depth as the original one, and no more instances of cut.3

Call this property object-level equivariance.

Proof

By repeated use of (StructL) and (StructR). □

The following results are not normally problematic but we have internalised both α-equivalence and being fresh — so renaming and freshening must be represented in the derivation. First, a technical lemma:

Lemma 6.2

If ∆⊆∆′ then:

1. if ∆⊢a#t then ∆′ ⊢a#t;

2. if ∆⊢T t = u then ∆′ ⊢T t = u.

Lemma 6.3

If Φ ⊢∆ Ψ and ∆⊆∆′ then Φ ⊢∆′ Ψ. The derivation has the same depth as the original one, and no more instances of cut.

Call this property meta-level weakening.

Proof

We work by induction on the structure of the derivation. The conditions on preserving depth and number of cuts can easily be verified from the structure of the reasoning which follows, and we do not mention them further.

We only treat the cases (∀R) and (Fr). The other cases are trivial or similar to the (∀R) case.

1. The case of (∀R): Suppose Φ ⊢∆ Ψ, ∀[a]ψ is derived using (∀R). Then ∆⊢a#Φ, Ψ and Φ ⊢∆ Ψ, ψ are derivable. Then ∆′ ⊢a#Φ, Ψ by Lemma 6.2, and Φ ⊢∆′ Ψ, ψ is derivable by inductive hypothesis. Extending derivations of the latter with (∀R) we conclude that Φ ⊢∆′ Ψ, ∀[a]ψ is derivable, as required.

2. The case of (Fr): Suppose Φ ⊢∆,a#X1,...,a#Xn Ψ where a ∉ Φ, Ψ, ∆. Choose a′ fresh (i.e. a′ ∉ Φ, Ψ, ∆′ — note the prime on the ∆′), then Φ ⊢∆,a′#X1,...,a′#Xn Ψ is derivable by meta-level equivariance . By FM equivariance we retain the inductive hypothesis, so it follows that Φ ⊢∆′,a′#X1,...,a′#Xn Ψ. Then we may deduce Φ ⊢∆′ Ψ using (Fr), as required.

□

Write U(Stuff ) for the unknowns mentioned in the Stuff .

Lemma 6.4

If a ∉u and a#U(u) ⊆∆ then ∆⊢a#u.

Lemma 6.5

If Φ ⊢∆ Ψ and Φ ⊆ Φ′ and Ψ ⊆ Ψ′ then Φ′ ⊢∆ Ψ′. The new derivation has the same depth as the original one, and no more instances of cut.

Call this property object-level weakening.

Proof

We work by strong induction on the pair of the depth of the derivation and its structure, lexicographically ordered. We consider only nontrivial cases.

1. The case of (∀R): Suppose Φ ⊢∆ Ψ, ∀[a]ψ is derived using (∀R) and suppose the inductive hypothesis of all strictly lesser derivations. By assumption Φ ⊢∆ Ψ, ψ has a derivation of strictly lesser depth, and also ∆⊢a#Φ, Ψ holds. Choose some a′′ fresh (i.e. a′′ ∉a, ψ, Φ′, Ψ′, ∆), and take ∆′′ = ∆, a′′#U(Φ′, Ψ′, ∆, ψ). By NA weakening (Lemma 6.2) ∆′′ ⊢a#Φ, Ψ and by meta-level weakening (Lemma 6.3)4 Φ ⊢∆′′ Ψ, ψ. Then by object-level equivariance (Lemma 6.1) also Φ ⊢∆′′ Ψ, (a′′ a) · ψ, and by inductive hypothesis (the derivation still has strictly lesser depth) there exists a derivation Π of

Φ′ ⊢∆′′ Ψ′, (a′′ a) · ψ.

By Lemma 6.4 also ∆′′ ⊢a′′#Φ′, Ψ′, and by simple calculations we observe ∆′′ ⊢SUB ∀[a′′](a′′ a) · ψ = ∀[a]ψ (we use (perm), and the freshness information we have assumed of a′′). Now we can conclude Φ′ ⊢∆ Ψ′, ∀[a]ψ as follows:

Π(∀R)Φ′ ⊢∆′′ Ψ′, ∀[a′′](a′′ a) · ψ(StructR)Φ′ ⊢∆′′ Ψ′, ∀[a]ψ(Fr)Φ′ ⊢∆Ψ′, ∀[a]ψ

2. The case of (Fr): Suppose Φ ⊢∆,a#X1,...,a#Xn Ψ where a ∉ Φ, Ψ, ∆. In case a ∉ Φ′, Ψ′ then things are easy and we use (Fr). If however a ∈ Φ′, Ψ′ then we use FM equivariance to rename a to some a′ ∉ Φ′, Ψ′, ∆ in the whole derivation to obtain one of Φ ⊢∆,a′#X1,...,a#Xn Ψ. We can now apply the inductive hypothesis (which, as discussed above, is also preserved by the permutative renaming) to weaken to Φ′ and Ψ′, and finish off with (Fr).

□

Write Φ[b↦ →u] for the elementwise application of the explicit substitution to the elements of predicate context Φ.

Lemma 6.6

If Φ ⊢∆ Ψ then Φ[b↦ →u] ⊢∆ Ψ[b↦ →u]. The depth of the derivation does not increase, and neither does the number of cuts it contains.

Call this property object-level substitution.

Proof

By induction on the depth and structure of the derivation of Φ ⊢∆ Ψ, lexicographically ordered. Most cases are easy, we consider only the case of (∀R).

Suppose Φ ⊢∆ Ψ, ∀[a]ψ is derived using (∀R), and suppose the inductive hypothesis of all strictly lesser derivations.

By assumption Φ ⊢∆ Ψ, ψ is derivable and ∆⊢a#Φ, Ψ holds.

Choose some a′ fresh (i.e. a′ ∉a, b, u, ψ, Φ, Ψ, ∆) and let ∆′ = ∆, a′#U(u, ψ, Φ, Ψ, ∆). We use meta-level weakening, object-level equivariance and the inductive hypothesis to conclude that there exists a derivation Π of

Φ[b↦ →u] ⊢∆′ Ψ[b↦ →u], ((a′ a) · ψ)[b↦ →u],

which has the same depth and number of cuts.

By Lemma 6.4 also ∆′ ⊢a′#((a′ a) · ψ)[b↦ →u]. Furthermore, by simple calculations we observe

∆′ ⊢SUB ∀[a′]((a′ a) · ψ)[b↦ →u] = (∀[a]ψ)[b↦ →u].

We finish the derivation:

Π(∀R)Φ[b↦ →u] ⊢∆′ Ψ[b↦ →u], ∀[a′]((a′ a) · ψ)[b↦ →u](StructR)Φ[b↦ →u] ⊢∆′ Ψ[b↦ →u], (∀[a]ψ)[b↦ →u](Fr)Φ[b↦ →u] ⊢∆Ψ[b↦ →u], (∀[a]ψ)[b↦ →u]
□
Lemma 6.7

(Fr) may be commuted down through all other rules. The transformations involved do not increase the depth of a derivation or its number of cuts.

Proof

We consider only one case. Suppose (Fr) is followed by (≈L). It is not immediate that we may swap the derivation rules round, since perhaps t in (≈L) mentions a and t′ does not (we use notation from the rules in Figure 1). However, we may rename atoms in the derivation up to the use of (Fr) changing a to some a′ which does not occur also in t, and then proceed. That the inductive hypothesis is preserved follows by FM equivariance. □

Theorem 6.8 (Cut-elimination).

If Φ ⊢∆ Ψ has a derivation in the system above, then it has one which does not use (Cut).

Proof

The commutation cases and essential cases for the propositional part are standard [17, 26], we use Lemma 6.5 for the essential case for ⊃. The essential case for ∀ is handled by Lemma 6.6. Commutation cases are standard (except for the extra case of (Fr), which is handled by Lemma 6.7). □

Corollary 6.9

The sequent calculus of one-and-a-halfth-order logic is consistent, i.e. ⊢∆ can never be derived.

Proof

By contradiction. Suppose ⊢∆ is derivable, then by Theorem 6.8 a cut-free derivation exists. Let Π be the shortest derivation of ⊢∆ for all possible ∆. We check through all possible derivation rules and see by their syntax-directed nature that the derivation must conclude in (Fr). But then we have a shorter derivation of some ⊢∆′, which is a contradiction. □

7. Equivalence of ⊢∆ and ⊢FOL

This section shows how derivability in the sequent calculus of one-and-a-halfth-order logic relates to derivability in theory FOL (Theorem 7.5).

We need some notation.

For a context Φ = {φ1, . . . , φn}, define its conjunctive form Φ∧ to be ⊤ when n = 0, and φ1 ∧· · · ∧φn when n > 0. Analogously, define the disjunctive form Φ∨ to be ⊥ when n = 0, and φ1 ∨· · · ∨φn when n > 0. The order of the φi is irrelevant; we (promise) never (to) do anything where it matters.

Sequent derivability translates to FOL derivability in the following way:

Lemma 7.1

If Φ ⊢∆ Ψ then ∆⊢FOL Φ∧⊃ Ψ∨= ⊤.

Proof

By induction on derivations of Φ ⊢∆ Ψ. For every rule (R), the derivation has the following format:

Π1· · · Πk(R) (cond)Φ ⊢∆Ψ

Here k ∈{0, 1, 2}, Πi are derivations of Φi ⊢∆i Ψi, 1 ≤i ≤k, and cond is a (possibly empty) side-condition.

So Φi ⊢∆i Ψi are derivable, then by inductive hypothesis ∆i ⊢FOL Φi∧⊃ Ψi∨= ⊤ holds. We use this together with cond to prove ∆⊢FOL Φ∧⊃ Ψ∨= ⊤. For each inference rule (R), this is an instance of an item of Lemma 4.3.

For example, in case (R) is (Cut) ∆⊢FOL Φ∧⊃ Ψ∨= ⊤ should follow from the assumptions ∆⊢FOL Φ∧⊃ Ψ∨∨φ = ⊤, ∆⊢FOL φ′ ∧ Φ∧⊃ Ψ∨= ⊤ and ∆⊢SUB φ = φ′. This is an instance of item 12 of Lemma 4.3, using θ ≡ Φ∧ and ε ≡ Ψ∨.

In case (R) is (∀R) ∆⊢FOL Φ∧⊃ Ψ∨∨∀[a]ψ = ⊤ should follow from ∆⊢FOL Φ∧⊃ Ψ∨∨ψ = ⊤ and ∆⊢a#Φ∧, Ψ∨. This is an instance of item 6, again using θ ≡ Φ∧ and ε ≡ Ψ∨. □

For the reverse of the above, we need a number of technical lemmas.

Lemma 7.2

Bi-implication ⇔ is an equivalence relation.5 Also, ⊢∆⊤⇔φ if and only if ⊢∆φ if and only if ⊢∆φ ⇔⊤.

Lemma 7.3

For all sorts τ, terms t, u : τ, freshness contexts ∆ and contexts C[ ] : P:

if ∆⊢FOL t = u then ⊢∆C[t] ⇔C[u]
Proof

By induction on the structure of FOL derivations of t = u from ∆. (refl): ⊢∆C[t] ⇔C[t] follows by reflexivity of ⇔. (symm): ⊢∆C[u] ⇔C[t] follows from ⊢∆C[t] ⇔C[u] by symmetry of ⇔. By inductive hypothesis this follows from the assumption. The case of (tran) is similar. (cong): ⊢∆C[D[t]] ⇔C[D[v]] follows by inductive hypothesis from the assumption taking C[ ] := C[D[ ]]. (perm): we show ⊢∆C[(a b) · t] ⇔C[t] as follows:

(Ax)⊢∆C[(a b) · t] ⇔C[(a b) · t](StructR)⊢∆C[(a b) · t] ⇔C[t]

where ∆⊢SUB C[(a b) · t] ⇔C[(a b) · t] = C[(a b) · t] ⇔C[t] is the side-condition of (StructR). By (cong), this follows from the assumption ∆⊢SUB (a b) · t = t. (fr): By (Fr) derivability of ⊢∆C[t] ⇔C[u] follows from that of ⊢∆,a#X1,...,a#Xn C[t] ⇔C[u] and a ∉C[t] ⇔C[u], ∆. The former follows by inductive hypothesis, and the latter from the assumption a ∉C[t], C[u], ∆. (axA): If A is an axiom of SUB (one from Figure 4), the proof is analogous to the (perm) case. If A is a logical axiom (one from Figure 5) then, looking at the structure of the axioms, the derivation is of the form

Π(axA)φπσ = ⊤

where A is ∆′ →φ = ⊤ and Π is a derivation of ∆′πσ. We need to show ⊢∆C[φπσ] ⇔C[⊤]. By congruence and right identity of ⇔, this follows from ⊢∆φπσ. For each logical axiom A, this is an instance of an item of Lemma 5.1, using the assumption ∆⊢∆′πσ.

□
Lemma 7.4

If ⊢∆ Φ∧⊃ Ψ∨ then Φ ⊢∆ Ψ.

Proof

By (Cut) Φ ⊢∆ Ψ follows from Φ ⊢∆ Ψ, Φ∧⊃ Ψ∨ and Φ∧⊃ Ψ∨, Φ ⊢∆ Ψ. The former follows from the assumption using Lemma 6.5. The latter follows from Φ ⊢∆ Ψ, Φ∧ and Ψ∨, Φ ⊢∆ Ψ using (⊃L). We prove the former, the latter is analogous. We know Φ = {φ1, . . . , φn}, where n ≥ 0. If n = 0 then Φ∧= ⊤ and we derive ⊢∆ Ψ, ⊤ using (⊃R) and (Ax). If n > 0 then Φ∧= φ1 ∧. . . ∧φn, and it suffices to derive Φ ⊢∆ Ψ, φi for all i < n using (∧R) (n − 1 times). For each i, this follows by (Ax), since φi ∈ Φ. □

Sequent derivability is equivalent to FOL derivability:

Theorem 7.5

Φ ⊢∆ Ψ if and only if ∆⊢FOL Φ∧⊃ Ψ∨= ⊤.

Proof

The left-to-right part is handled by Lemma 7.1.

For the right-to-left part, we assume ∆⊢FOL Φ∧⊃ Ψ∨= ⊤. Then by Lemma 7.3 ⊢∆ Φ∧⊃ Ψ∨⇔⊤ is derivable. By the right identity of ⇔, also ⊢∆ Φ∧⊃ Ψ∨. By Lemma 7.4 we obtain the consequent Φ ⊢∆ Ψ. □

This theorem has some nice corollaries.

Corollary 7.6

For any ∆, φ, ψ:

∆⊢FOL φ = ψ if and only if φ ⊢∆ψ and ψ ⊢∆φ.
Proof

By Theorem 7.5 φ ⊢∆ψ and ψ ⊢∆φ are equivalent to ∆⊢FOL φ ⊃ψ = ⊤ and ∆⊢FOL ψ ⊃φ = ⊤. These can easily be shown equivalent to ∆⊢FOL φ = ψ using item 2 of Lemma 4.1. □

Corollary 7.7

FOL is consistent, i.e. ∆⊢FOL ⊤= ⊥ does not hold for any ∆.

Proof

By contradiction. Suppose ∆⊢FOL ⊤= ⊥. Using the propositional axioms and some simple equational reasoning, also ∆⊢FOL ⊤⊃⊥= ⊤. Note that ⊤≡∅∧ and ⊥≡∅∨, so by Theorem 7.5 ⊢∆ is derivable, which contradicts Corollary 6.9. □

8. First-order logic

Call a term ground if it does not mention unknowns (it is closed) and it does not mention explicit substitutions.

In this section we show formally how a syntax for a first-order logic ‘lives inside’ one-and-a-halfth-order logic, given by the ground terms of sort P (the predicates) taken up to α-equivalence of ∀-abstracted atoms, and the ground terms of sort T (the term-language). The precise term-language depends on the set of object-level term-formers and atomic predicate-formers with which we built our one-and-a-halfth-order logic in Section 2. As mentioned before, we let of and op vary over object-level term-formers and atomic predicate-formers.

8.1 Properties of ground terms

We may write the term ∀[a]φ where φ is ground just as ∀a.φ (consistent with standard notation). Recall that a in ∀[a]P may not be renamed in general, e.g. to ∀[b]P. Intuitively P represents an unknown formula which might mention a (if we know b#P we can at least rename to ∀[b](b a).P). To emphasise this we retained the notation [a] until now. In ∀a.φ where φ is ground, we know all atoms in φ and this issue does not arise.

Write fn(t) and fn(φ) for the free names of ground terms t : T and φ : P respectively, inductively defined by:

fn(a) = {a} fn(of(t1, . . . , tk)) =[1≤i≤kfn(ti)
fn(⊥) = ∅ fn(φ ⊃ψ) = fn(φ) ∪fn(ψ)fn(∀a.φ) = fn(φ) \ {a} fn(op(t1, . . . , tk)) =[1≤i≤kfn(ti)
Lemma 8.1

⊢a#φ if and only if a ∉ fn(φ), for all ground predicates φ.

Proof

By simple induction on derivations of a#φ on the one hand, and by induction on the definition of fn on the other. □

Define α-equivalence =α as syntactic identity plus

b ∉fn(φ) (a b)·φ =α ψ ∀a.φ =α ∀b.ψ.

The reader might have expected the clause for ∀ to read something like φc =α ψc∀a.φa =α ∀b.ψb where here φc is informal notation for φ with every a replaced throughout by a freshly chosen c, and similarly for ψc. The two notions of α-equivalence are identical [11]. The definition we adopt gives a closer match to how equality is defined in NA (specifically to (perm)).

Lemma 8.2

⊢CORE φ = ψ if and only if φ =α ψ, for all ground predicates φ, ψ.

Proof

By known arguments of nominal results [15, 16]. □

For each finite set of atoms make an arbitrary but canonical choice of a fresh (that is, not in the set) atom. In a given context of some finite collection of terms and predicates, which being finite mentions finitely many atoms, write ‘a fresh’ for the canonical but arbitrarily chosen a which is fresh for the atoms in that collection.

In the following definition we elide the context, which is the terms and formulae mentioned to the left of ≡.

For ground terms t, u : T and φ : P, write u⟦a↦ →t⟧ and φ⟦a↦ →t⟧ for u and φ with a replaced by t, inductively defined by:

a⟦a↦ →t⟧ ≡t b⟦a↦ →t⟧ ≡b of(t1, . . . , tk)⟦a↦ →t⟧ ≡of(t1⟦a↦ →t⟧, . . . , tk⟦a↦ →t⟧)
⊥⟦a↦ →t⟧ ≡⊥ (φ ⊃ψ)⟦a↦ →t⟧ ≡φ⟦a↦ →t⟧ ⊃ψ⟦a↦ →t⟧ (∀a.φ)⟦a↦ →t⟧ ≡∀a.φ (∀b.φ)⟦a↦ →t⟧ ≡∀b′.φ⟦b↦ →b′⟧⟦a↦ →t⟧ (b′ fresh) op(t1, . . . , tk)⟦a↦ →t⟧ ≡op(t1⟦a↦ →t⟧, . . . , tk⟦a↦ →t⟧)
Lemma 8.3

For all ground terms t, u, v : T and φ, ψ : P:

⊢SUB u[a↦ →t] = u⟦a↦ →t⟧ and ⊢SUB φ[a↦ →t] = φ⟦a↦ →t⟧

Proof

By induction on the depths of u and φ. For the case u ≡ f(t1, . . . , tn), we must prove

⊢SUB f(t1, . . . , tn)[a↦ →t] = f(t1⟦a↦ →t⟧, . . . , tn⟦a↦ →t⟧),

for which we use axiom (f ↦→) of SUB and the inductive hypothesis.

The only difficult case is φ ≡∀b.φ′ because there is no directly corresponding axiom of SUB. By calculation of (∀b.φ′)⟦a↦ →t⟧, we obtain ∀b′.φ′⟦b↦ →b′⟧⟦a↦ →t⟧, where b′ is fresh. By the inductive hypothesis we have

⊢SUB φ′[b↦ →b′] = φ′⟦b↦ →b′⟧ ⊢SUB φ′⟦b↦ →b′⟧[a↦ →t] = φ′⟦b↦ →b′⟧⟦a↦ →t⟧.

We need to prove

⊢SUB (∀b.φ′)[a↦ →t] = ∀b′.φ′⟦b↦ →b′⟧⟦a↦ →t⟧,

which follows by easy calculations using the above assumptions. □

Lemma 8.4

For all ground terms t, u, v : T and φ, ψ : P:

1. ⊢SUB u[a↦ →t] = v if and only if u⟦a↦ →t⟧ ≡v;6

2. ⊢SUB φ[a↦ →t] = ψ if and only if φ⟦a↦ →t⟧ =α ψ.

Proof

By lemmas 8.2 and 8.3, using the fact that SUB is conservative over CORE (see [14]). □

8.2 Derivability in First-Order Logic

A first-order context is a finite and possibly empty set of ground predicates Φ or Ψ. A first-order sequent is a pair Φ ⊢ Ψ. The valid judgements of Gentzen’s sequent calculus for first-order logic are inductively derived by:

(Ax)φ, Φ ⊢Ψ, φ(⊥L)⊥, Φ ⊢ΨΦ ⊢Ψ, φ ψ, Φ ⊢Ψ(⊃L)φ ⊃ψ, Φ ⊢Ψφ, Φ ⊢Ψ, ψ(⊃R)Φ ⊢Ψ, φ ⊃ψφ⟦a↦ →t⟧, Φ ⊢Ψ(∀L)∀a.φ, Φ ⊢ΨΦ ⊢Ψ, φ(∀R)Φ ⊢Ψ, ∀a.φ(a ∉fn(Φ, Ψ))φ⟦a↦ →t′⟧, Φ ⊢Ψ(≈L)t′ ≈t, φ⟦a↦ →t⟧, Φ ⊢Ψ(≈R)Φ ⊢Ψ, t ≈t

Here we take predicates up to α-equivalence, e.g. if p : (T)P is an atomic predicate term-former then ∀a.p(a) ⊢∀b.p(b) follows directly by (Ax) since ∀a.p(a) =α ∀b.p(b).

Theorem 8.5

Φ ⊢ Ψ is derivable in the system above, if and only if Φ ⊢∅ Ψ is derivable in the sequent calculus for one-and-a-halfth-order logic.

Proof

By induction on the structure of derivations, using cut-elimination (Theorem 6.8) and the results from Subsection 8.1 (Lemmas 8.1 and 8.4). □

Corollary 8.6

⊢FOL φ = ψ if and only if φ ⊢ψ and ψ ⊢φ are derivable in system above.

Proof

9. Conclusions

Explicitly representing meta-variables has a long pedigree.

Monadic second-order logic [5] enriches first-order logic explicitly with n-ary relation variables, representing ‘unknown n-ary predicates’. The stronger second-order and higher-order logics [30, 27] represent unknowns as function variables.

These approaches share two characteristic features inherited from their intended functional semantics. First, you have to choose the arity of your unknown in advance, e.g. f : nz }| { T →· · · →T →P can be interpreted as an unknown n-ary predicate — but which n? — thus these logics distribute ‘unknown predicates’ across many types. Second, and perhaps more importantly, instantiation of these variables avoids capture. Instantation of our unknowns does not, which accurately reflects our intention when we write ∀a.φ, where φ may be instantiated in a capturing manner. This lends a distinctive style to our nominal algebra theory FOL (see Figure 5), and to the sequent rules of one-and-a-halfth-order logic (see Figure 1), which accurately reflects informal practice (see [10, 20] and the examples of the Introduction) and as we have seen has allowed us to import elements of first-order proof theory quite directly into an augmented setting.

Note that second-order logic is far more expressive. One-and-a-halfth-order logic by design expresses universal quantification at top level only. For example, the following second-order theorem cannot be expressed: ∀P.(∀P.P) ⊃P. On the other hand one-and-a-halfth-order logic can express some things which second-order logic cannot, e.g. ∀[a]P ⊢a#P P is derivable. It is not presently clear what the intersection of these two logics is.

Our ambient nominal algebra framework can express certain strong ‘second-order’ principles, for instance an inductive principle on natural numbers may be expressed as a single axiom (assuming suitable term-formers 0 and succ)

P[a↦ →0] ∧∀[a](P ⊃P[a↦ →succ(a)]) ⊃∀[a]P = ⊤

rendered in second-order logic as

∀P.(P(0) ∧∀a.(P(a) ⊃P(succ(a))) ⊃∀a.P).

Our work is one (more) element in a very long line of investigations into algebraic logic [1]; for example cylindric [19], polyadic [18], and quantifier [25] algebra. There too, unknowns are syntax representing unknown elements quantified universally at top level, and abstraction [a]- (our notation) is clearly visible, e.g. as the ci of cylindric algebra. Our treatment of substitution is perhaps cleaner; cylindric and quantifier algebras axiomatise logic whose terms are in a suitable sense restricted to being atoms (our terminology), whereas we could easily extend our logic to talk about, say, λ-calculus terms just by postulating term-formers λ : ([A]T)T and app : (T, T)T plus a few nominal equalities [15, 7] (here, interesting work by Beeson is also relevant [3]). Arguably our treatment of substitution is also more systematic than polyadic algebras, at least in the sense that we define it in terms of more primitive constructs and can so study substitution in its own right [14].

Probably more important is our use of freshness contexts and permutations, by means of which we can express properties such as b#P ⊢FOL ∀[a]P = ∀[b](b a) · P, and of course the examples of the Introduction, directly. These assertions are valid in, say, cylindric algebra, but only by recourse to quantification over closed terms, thus, they cannot be stated within that framework. The extra expressivity we enjoy thanks to a slightly richer term-language and judgement-form is significant, because we can exploit it to extract a sequent presentation of derivability, namely the sequent system of Figure 1. In other words, our nominal management of binding permits us to construct an account of first-order logic which in a suitable sense is simultaneously algebraic and sequent-style.

It is possible to represent the syntax of a logic in a ‘framework’ logical system, at ‘object-level’, i.e. as an inductive datatype. Then meta-variables are easily representable as meta-variables of the framework. This path is taken by Higher-Order Abstract Syntax [24], Fraenkel-Mostowski syntax [16], and other systems ([23] is just one of very many). That is a separate enterprise from that undertaken in this paper; one-and-a-halfth-order logic is about extending the syntax of the logic itself so it contains something which behaves very much like a meta-variable ranging over unknown formulae, without losing logical properties such as cut-elimination. Perhaps one day one-and-a-halfth-order logic too will be formalised in a framework!

The technical tools used in this paper were developed based on work on Nominal Unification by the first author with Urban and Pitts [29], which introduced the theory of nominal terms up to CORE (our terminology). This was extended with Fernández [7] to Nominal Rewriting, a theory of rewriting on nominal terms, again up to CORE, and recently investigated with the second author, as a general framework of nominal algebra [15, 14].

For future work we are particularly interested in the following topics:

We can return to theory and be inspired by higher-order logic to ask whether we could permit abstraction over meta-variables, introducing an infinite hierarchy of stronger meta-variables such that at each level a meta-variable of higher level behaves to the lower level as X behaves to a (see the NEW calculus of contexts [13]). This might recover some or all of the power which one-and-a-halfth-order logic lacks compared to higher-order logic, but in a different way. In short, we envisage two- three- four- and ω-and-a-halfth-order logic. This would involve interesting extensions to the ‘nominal theme’. Another direction is to allow unknowns ranging over derivations of sequents, which may have interesting interactions with (∀R), which would abstract in such an unknown.

The semantics of one-and-a-halfth-order logic are interesting and raise the questions ‘what is an appropriate semantics for X’, and ‘what is an appropriate semantics for a’? Note that it is not possible to directly evaluate X to an element of a set underlying domain, because intuitively X ‘can mention a’. Thus we can use domains in which atoms can appear (à la Fraenkel-Mostowski sets [15, 16] or other approaches [3, 8]). The simplest solution, and perhaps the best one, is to evaluate X to terms (a ‘substitutional semantics’ [22, Section 2] faithful to its intuition as an ‘unknown term’) and then a to elements of a set underlying domain.

References

[1] H. Andréka, I. Németi, and I. Sain. Algebraic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 133–249. Kluwer, 2001.

[2] J. Barwise. An introduction to first-order logic. In J. Barwise, editor, Handbook of Mathematical Logic, pages 5–46. North Holland, 1977.

[3] M. Beeson. Lambda logic. In Second International Joint Conference on Automated Reasoning (IJCAR 2004), volume 3097 of LNCS, pages 460–474. Springer, 2004.

[4] J. Bell and M. Machover. A course in mathematical logic. North-Holland, 1977.

[5] C. Bruno. The expression of graph properties in some fragments of monadic second-order logic. DIMACS Series in Discrete Mathematics, 31, 1997.

[6] A. Degtyarev and A. Voronkov. Equality reasoning in sequent-based calculi. In J. A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, pages 611–706. Elsevier and MIT Press, 2001.

[7] M. Fernández and M. J. Gabbay. Nominal rewriting. Journal version, submitted Information and Computation, 2005.

[8] K. Fine. Reasoning with Arbitrary Objects. Blackwell, 1985.

[9] J. B. Fraleigh. A First Course in Abstract Algebra. Addison-Wesley, 7th edition, 2002.

[10] D. M. Gabbay and G. Malod. Naming worlds in modal and temporal logic. Journal of Logic, Language and Information, 11(1):29–65, 2002.

[11] M. J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.

[12] M. J. Gabbay. Fresh logic. Journal of Logic and Computation, July 2003. Accepted for publication.

[13] M. J. Gabbay. A new calculus of contexts. In Proc. 7th Int. ACM SIGPLAN Conf. on Principles and Practice of Declarative Programming (PPDP’2005). ACM, 2005.

[14] M. J. Gabbay and A. Mathijssen. Capture-avoiding substitution as a nominal algebra. Submitted ICTAC’06.

[15] M. J. Gabbay and A. Mathijssen. Nominal algebra. Submitted CSL’06.

[16] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13(3–5):341–363, 2001.

[17] G. Gentzen. Untersuchungen über das logische schließen [Investigations into logical deduction]. Mathematische Zeitschrift 39, pages 176–210,405–431, 1935. Translated in [28], pages 68–131.

[18] P. Halmos. Algebraic logic, ii. homogeneous locally finite polyadic boolean algebras of infinite degree. Fundamenta Mathematicae, 43:255–325, 1956.

[19] L. Henkin, J. D. Monk, and A. Tarski. Cylindric Algebras. North Holland. Part I (1971), Part II (1985).

[20] W. Hodges. Elementary predicate logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 1–131. Kluwer, 2001.

[21] P. T. Johnstone. Notes on logic and set theory. Cambridge University Press, 1987.

[22] H. Leblanc. Alternatives to standard first-order semantics. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 2, pages 53–132. Kluwer, 2001.

[23] M. Miculan. Developing (meta)theory of lambda-calculus in the theory of contexts. ENTCS, 1(58), 2001.

[24] F. Pfenning and C. Elliot. Higher-order abstract syntax. In SIGPLAN Conference on Programming Language Design and Implementation, pages 199–208, 1988.

[25] C. Pinter. A simple algebra of first-order logic. Notre Dame Journal of Formal Logic, 14(3):361–366, 1973.

[26] D. Prawitz. Natural Deduction: A Proof Theoretical Study. Almqvist and Wiksell, Stockholm, 1965.

[27] S. Shapiro. Systems between first-order and second-order logics. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 131–188. Kluwer, 2001.

[28] M. Szabo, editor. Collected Papers of Gerhard Gentzen. North Holland, 1969.

[29] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.

[30] J. van Benthem. Higher-order logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.

Notes

∗ Partially supported by EPSRC grant number EP/C013573/1. ↩

1 More precisely, f is a meta-variable ranging over term-formers. ↩

2 In item (4) on page 48, Hodges states that “Most authors require it to have at least one member.”, where ‘it’ denotes the domain in terms of a pure set. Also see Remark 6 on page 110 for a discussion on the implications for Hilbert-style proof calculi. ↩

3 It may mention more structural rules but by an astounding coincidence we have excluded them from our notion of depth. ↩

4 It appears convenient to prove meta-level weakening first separately; we do not want to weaken Φ and Ψ to Φ′ and Ψ′ until we have renamed a to a′′, in a moment. ↩

5 ⇔ is a reflexive symmetric transitive congruence. ↩

6 If we had binders in terms of sort T then the ≡ would become an α-equivalence. ↩