Appendix

First-Order Logic with Fleeing Indices

A.1 INTRODUCTION

Löwenheim proved his well-known theorem for formulas of a standard first-order language with equality within a language extended with fleeing terms. He did not pay particular attention to this extended language; nor did Schröder, who, in a way, was the first to make use of fleeing indices. The aim of this appendix is to present a first-order language with fleeing terms appropriate for reconstructing, as far as is possible, the argument with which Löwenheim proved the theorem that today bears his name.

I do not intend to present all the peculiarities of the language of the logic of relatives with fleeing indices. I have slightly modified the notation and syntax in order to bring them somewhat closer to those we use today, but the changes involved are not important. In general, I have omitted everything that is not strictly necessary to an accurate reconstruction of Löwenheim's argument and to a rigorous proof of the claims I made in previous chapters. Thus, in the language I am going to present, fleeing indices are never quantified. The reasons for this are that this type of quantification considerably complicates the syntax of the language and is not essential to the reconstruction of the proof of the theorem. Nevertheless, to give a more formal presentation of the assertions I made in chapter 3, I will explain how the definition of the concept of satisfaction should be extended if the language allows quantified fleeing indices.

I will only prove the main lemmas and propositions; whenever possible, these proofs will closely follow my interpretation of those by Löwenheim.

A.2 SYNTAX

A.2.1 Terms and formulas

We introduce a first-order language L with equality and fleeing indices.

The alphabet of L contains the following symbols:

1. Logical symbols:

(a) connectives: +, ·, ‾;

(b) quantifiers: II, Σ;

(c) identity symbol: ;

(d) variables: a denumerable set of symbols. We shall use the letters i, j, h, and k (with subscripts, if necessary) to stand for variables.

2. Nonlogical symbols:

(a) constants: a countable set (possibly empty);

(b) predicate symbols: for every n ≥ 1, a countable set (possibly empty) of n-place predicate symbols.

3. Auxiliary symbols: ( , ).

The terms of L are the finite strings that can be obtained by applying the following rules:

1. the constants and variables are terms;

2. if k is a variable and r₁,...,r_n are constants or variables, then k_r1..._rn is a term.

A fleeing term (or fleeing index) is one of the form k_r1..._rn; a simple term is a variable or a constant. If k_r1..._rn is a fleeing term, r₁,...,r_n are the subindices (not the subscripts) of the term. A fleeing term depends on a variable when this variable is a subindex of that term of L.

An atomic formula of L is an expressions of one of the forms

where R is a n-place predicate symbol and t₁,...,t_n are terms.

The formulas of L are the finite strings obtained by applying the following rules:

1. the atomic formulas are formulas;

2. if is a formula, is a formula;

3. if and β are formulas, then ( + β ) and ( · β) are formulas;

4. if is a formula and i is a variable, then IIi and are formulas.

In what follows we will use the letters A, B, F, and P (with subscripts, if necessary) to stand for formulas.

Remark

I said above that neither Schröder nor Löwenheim paid much attention to syntactical aspects. As we saw, this is particularly so in the case of fleeing indices and the formulas that contain them. Since these kinds of indices are only used to change the order of the quantifiers, it is considered to be enough to know how this transformation is made, and to understand what we could call “the semantics” of the resulting formula. Supposedly, anyone who understands this process will also understand everything related to the syntax of fleeing terms (or, at least, all one needs to know).

Obviously, in this situation there is no way of knowing whether Löwenheim would have any objection to fleeing terms, such as k_k and k_iji, which cannot result from a change in the order of the quantifiers. Schröder would not accept them, because for him the subindices have to be variables of another type, but that is a different problem. We might surmise that Löwenheim would not admit them, but it would be a waste of time to consider this question. I have chosen to regard them as well formed only in order to simplify the definition.

The same type of difficulty arises in the case of formulas where fleeing indices occur. We cannot say with certainty whether Löwenheim would object to expressions which, like IIiA(i, i_j) and ), do not arise in the process of obtaining the normal form of a formula without fleeing terms.¹ These expressions present a peculiarity (it is not the subindex of the fleeing term that is quantified, but the variable that carries it) which only arises when we think in abstract of the formation rules. I have also decided to consider them all as well formed for the purpose of simplifying the definition of formula.

A.2.2 Free variables

All the variables that occur in a simple term are free. The free variables of a fleeing term are the ones on which it depends. For example, k is not free in k_i, and if r is an individual constant, k_r has no free variables.

We now define by recursion what it means for a variable i to occur free in a formula F:

1. i occurs free in an atomic formula A iff i occurs free in any term of A;

2. i occurs free in iff i occurs free in A;

3. i occurs free in A · B or in A + B iff i occurs free in A or in B;

4. i occurs free in IIjA or in iff i occurs free in A and .

A sentence is a formula without free variables. For example, if R is a binary predicate symbol, IIiRik_i is a sentence.

A.2.3 Substitution

If i is a variable, t is a term, and is a term or a formula, then the substitution of t for i in ; is defined by recursion as follows: