Chapter Five
Preliminaries to Löwenheim's Theorem
Löwenheim uses the word “index” to refer both to variables of the formal language and to elements of the domain. Bearing in mind the fact that no distinction was made at that time between object language and metalanguage, and also that the same letters are used as variables of the formal language and as metalinguistic variables ranging over elements of the domain, a certain degree of inaccuracy is understandable. If the ambiguity amounted to this alone, there would be no need for any comment, since today we make all these distinctions and we are often not as careful as we might be. However, in “Über Möglichkeiten” Löwenheim seems to identify the domain with the set of indices; this creates a confusion which we need to clear up before going on to analyze the proof of the theorem. I will give some examples of potentially confusing statements and then make the pertinent clarifications.
The first example is found at the beginning of the paper. When he defines the concept of relative expression, Löwenheim says:
each 
and II ranging either over the indices—that is, over all individuals of the domain of the first degree, which, following
Schröder, we call 11—... (“Über Möglichkeiten,” p. 447 (232))
Remember that Löwenheim is characterizing the relative expressions. What he means is that the quantified variables range over the elements of the domain, whichever domain it is.
The second example is almost anecdotal, and we might attribute it to an oversight or a slip if we were to analyze it in isolation.
When Löwenheim expands the formula 
(i, ki) in order to explain the meaning of 
, he says: “I shall denote the indices by 1, 2, 3, ...” (“Über Möglichkeiten,” p. 452 (236)). What he actually denotes by
1, 2, 3, ... are the elements of the domain on which the formula is to be expanded, and he therefore speaks as if the domain
were the set of indices.
The third example is found in the proof that there are no fleeing equations with only unary relative coefficients and the equality symbol. At the start of the proof we read:
The left side of the equation in zero form is symmetric with respect to all indices, that is, all elements of 11, ... (“Über Möglichkeiten,” p. 460 (243))
Löwenheim is referring to a particular normal form (not the one that we have considered in the previous chapter).
The last example I will mention is more interesting and deserves a fairly detailed analysis. Löwenheim devotes the last section of “Über Möglichkeiten” to proving that the whole of relative calculus can be reduced to the calculus of binary relatives. Specifically, his objective is to present a general procedure which, given an equation f = 0, allows us to construct another equation, F = 0, whose relative coefficients are binary and such that f = 0 is satisfiable if and only if F = 0 is. After a few general considerations on the meaning and the importance of the theorem, Löwenheim begins the proof as follows:
We consider a new domain, whose elements are the elementpairs of the old 11, and which we must therefore call 12.Thus if
then
The new domain E, which we shall take as basic in what follows, now results from 12 by replacement of (i, i) by i, (i, j) by j, and so on.1
The first indication we are given of the existence of the “old 11” is the one that occurs in this quotation; this domain is not explicitly mentioned beforehand. As becomes clear a little later on, Löwenheim's argument is, generally speaking, as follows. He first supposes that the relative coefficients of a given equation f = 0 take values over any domain (“the old 11”) and, without considering whether or not these values satisfy the equation, he proposes constructing F = 0 so that it“permits exactly the transformations corresponding to those of f = 0” (“Über Möglichkeiten,” p. 466 (248)). Put in a way that Löwenheim would not like, the idea is to construct an equation whose expansion over E is essentially the same as the expansion of f = 0 over the old 11. The last step in the proof consists in showing that f = 0 is satisfiable if and only if F = 0 is.
Before going on to the indices, I should mention a coincidence (both in purpose and in style) between this proof and the proof of his famous theorem. In both cases Löwenheim sets out to give a method of construction (of an equation in this case, and of a domain in the other); in both cases also the proof begins, without saying so explicitly, with an equation that is held to be interpreted over a domain. I think this coincidence is interesting, and for this reason I have spent rather longer on this example than is really necessary for the following discussion; however, I do not aim to draw any conclusions from it to support my interpretation of the proof of Löwenheim's theorem.
Let us now discuss the problem of the indices. I will begin by analyzing the last example. Judging from the first part of the quotation, it appears that Löwenheim is proposing to illustrate his argument by taking the set of indices as the example of a domain. But if he had simply meant to present a particular example, he would have used natural numbers, as he does on other occasions. In all likelihood the indices play the role of examples, but with the first equality in the quotation Löwenheim does not mean to say that the indices are the elements of the domain; they stand for objects of any kind. There is nothing unusual in this. For example, we quite frequently use the equality
to indicate that A is any countable infinite set, and not the set whose elements are “x1”, “x2”, etc. The problem here is that Löwenheim goes slightly further.
As I said above, Löwenheim's purpose is to give a general procedure for constructing an equation that, as regards satisfiability, is equivalent to another given equation. The proof begins by assuming that the original equation is interpreted in some given domain. Therefore, what the first equality in the quotation means is: let 11 be any domain. Of course, Löwenheim could have stated it thus, but, for reasons that need not concern us here, it suits him to have at his disposal what we could consider to be a representation of the domain, not of a particular domain, but of any domain. For Löwenheim, then, the set of indicesrepresents the domain, but is not actually the domain (in the sense that we now attribute to a statement of this kind). The limitations of Löwenheim's conceptual apparatus do not allow the consideration of the set of indices as the domain of interpretation. In the following chapter I will come back to this problem, since one of the key aspects of the proof is related to it.
To an extent, the role that Löwenheim attributes to the set of indices is not a peculiarity of his own. For example, when
Peirce ([1885], p. 228, 3.393) explains the meaning of 
he does so using the equality
By this Peirce means that summation indices always range over all the elements of the domain. The first quotation from Löwenheim is simply a formulation, in words, of the previous equation. The indices serve as examples, but the above equality has a general character that a concrete example does not possess. However, when Schröder makes statements of this kind, he speaks not of indices, but of elements of the domain. The unusual aspect of this case is Löwenheim's misuse of the term “index.” To my knowledge, neither Peirce nor Schröder uses the word in the way that Löwenheim uses it in the first three examples I have quoted.
I will briefly summarize what I have said so far. In the logic of relatives, the same letters are used both as indices (i.e., variables of object language) and as metalinguistic variables ranging over the elements of the domain. However, Löwenheim goes a step further. He sometimes seems to think that, if an index can be used to denote any element, the set of indices can be used to denote any domain. If we add to this detail the lack of a distinction between language and metalanguage,we see why Löwenheim uses the word “index” as he does.
5.2.1 Löwenheim distinguishes between the different types of indices that may occur in the formula that results from eliminating the existential quantifiers from a formula in normal form. Referring to the example that he has used to describe how to obtain the normal form of an equation formula, Löwenheim says:
can contain three kinds of indices:
(1) Constant indices [[Konstante Indizes]], that is, such as must always be the same in every factor of the II (l in our example); ...
(2) Productation indices [[Produktionsindizes]] (i, j, h in our example); they run through all elements of the domain independently of one another, so that to every system of values for these indices there corresponds a factor of the II, and conversely.
(3) Fleeing indices (like ki in our example, as well as ih and lkh on page ...); their subindices (i, h, or k and h, respectively) are productation indices, and the fleeing indices are (not necessarily one to one) functions of their subindices; that is, lkh, for example, denotes one and the same element in all those factors of II in which the productation indices k and h have the same values (but lkh does not necessarily denote different elements in other factors).2
When Löwenheim classifies here the indices of IIF, what he is classifying are the terms of the formula. He does not speak of indices in the sense of elements of the domain. The constant indices are the free variables and the productation indices are the universally quantified variables. I already spoke at length of the concept of fleeing index in chapter 3. Löwenheim's explanation requires a certain clarification, but first we need to explain what factors are.
5.2.2 In the strict sense, a factor is each of the members of a product of the form A · B. Occasionally it is also said that A
is a factor of a formula when it occurs in the formula as a factor in the strict sense. For example, 
and zkii are the factors (not the productands) of
Indeed, Löwenheim uses the term with this meaning elsewhere in “Über Möglichkeiten.”
When Löwenheim speaks of factors of II in the above quotation, he is referring to the same formulas that throughout the proof of his theorem he call “factors of II in IIF” (or “factors of II in IIF = 0”). Evidently, in this context the word “factor” does not have its habitual meaning. Löwenheim cannot be referring to factors of IIF in the strict sense.
It is not hard to see what Löwenheim means, especially if we concentrate on his characterization of the productation indices, but it is worth presenting an example. Let us take the formula IIikA(i,k,j) and suppose that the domain has only the elements 1 and 2. As we know, the expansion of IIikA(i,k,j) in this domain is
The members of this product are Löwenheim's “factors of II.” Observe that the constant indices are the same in each factor, and each assignment of values to the productation indices corresponds to a factor. The systems of which Löwenheim speaks are the different assignments of values to the productation indices.3 Only when we are dealing with formulas that begin with a universal quantifier can we speak of factors in this sense.
The logical form of the expansion explains why Löwenheim uses the word “factor.” It is of no importance that the domain may be nondenumerable and then the expansion cannot be written. The reference to expansions is only required to explain why Löwenheim calls these formulas “factors.” One can say what a factor is without having to resort to expansions.
It may be that Löwenheim prefers to speak of factors of IIF and not of factors of the expansion of IIF (although in the strict sense they are factors of it) in order to avoid reference to expansions. This possibility is consistent with the interpretation discussed in chapter 3 of the warning that Löwenheim gives every time he performs an expansion. Löwenheim's purpose in the above quotation is to give a characterization of the different terms. If he thought that the expansions contravened the stipulations governing the use of the different symbols in the language, it is reasonable that he should avoid referring to them, so as not to give the impression that the characterization of the types of indices depends on them.
In the above, there is one point that needs particular emphasis. The use of the word “factor” in the context I have just analyzed
necessarily presupposes the existence of a domain. This is not simply a matter of terminology. The ideas that Löwenheim expresses,
however he formulates them, do not make sense unless a domain has been previously fixed. Today we might write R(x, y)[a, b]
to indicate that variable x takes the value a and variable y the value b, where a and b are elements of a given domain. If,
forgetting the distinction between syntax and semantics, we think of R(x, y)[a, b] as the formula that results from substituting
the variables with (canonical names of) their values, we will have a highly accurate idea of what a factor is. The different
expressions R(x, y)[a; b] that we can form for a given domain are the factors of 
. Obviously, we cannot speak of factors 
in this sense if there is no given domain.
5.2.3 In the characterization of the fleeing indices Löwenheim says that they are functions of their subindices. As I explained in section 3.4 of chapter 3, this statement is compatible with a nonfunctional interpretation of fleeing indices. All that Löwenheim means when he asserts that lkh “denotes one and the same element in all those factors of II in which the productation indices k and h have the same values” is this: if, for example, k takes the value a and h the value b, the fleeing term lkh gives rise to the term lab in all factors where k and h take these values and, obviously, this term denotes a unique element. Different values of k and h generate different terms such as l12 and l21, but of course we have no reason for presupposing that different terms denote different elements; l12 and l21 may denote the same element. Thus, all that is required in order to interpret Löwenheim's statement is that the fleeing indices generate different terms when their subindices (the productation indices) take different values (and in this sense are one to one functions of their subindices). Nothing here makes mandatory a functional interpretation of the fleeing indices in the sense I explained in chapter 3.
5.3.1 An assignment is a function from the set of individual variables of a formal language into the domain. Assignments are frequently used to fix the interpretation of the free variables (the constant indices) of a first-order formula, because they permit us to denote the element assigned to a variable in a natural way. Thus, if v is an assignmentand j a free variable of a given formula, v(j) is the element of the domain assigned to the variable j. In the cases in which we are only interested in the element assigned to a variable, we sometimes omit the reference to the assignment and say something of the sort:
In the logic of relatives there are no concepts that are totally identifiable with our syntactic concepts. The best explanation of a constant index is to say that it is a free variable, but strictly speaking the two concepts are not identifiable with each other because constant indices have semantic connotations that free variables lack. The very characterization of the constant index has a semantic nuance. Löwenheim characterizes constant indices as those that do not vary from factor to factor, and the existence of factors depends on the existence of a domain. But, leaving aside the question of how to characterize them, their semantic character resides above all in the fact that they are at the same time metalinguistic variables ranging over the elements of the domain.
As we will see in the following chapter, Löwenheim is aware that if, for example, j is a constant index of a given formula, j can take any value in the domain; but this is implicit in the semantic character of the variables. The problem, in Löwenheim's situation, is how to express that the interpretation of the constant indices has been fixed. Löwenheim possesses none of the resources that I have mentioned: he does not have the concept of assignment; he cannot assign values by means of a statement analogous to (5.1) since the same letters are used as variables of both the object language and the metalanguage. The counterpart to (5.1) in the logic of relatives is
which is extremely confusing, as the two variables are of the same type. In these cases Löwenheim says simply that j is an element of the domain, but this presents a problem: it is not clear whether or not we should understand that the value of j has been fixed.
There is a difference between formulas that have unquantified fleeing indices and formulas that have constant indices. The truth value of a formula with only constant indices is independent of what is assigned to terms that do not occur in it. In contrast, the truth value of a formula with fleeing indices depends on the elements assigned to certain terms that do not occur in it. Let us consider, for example, the formula
To determine its truth value in a domain D we need to fix, in addition to the values taken by the relative coefficients, the
elements of D which the terms generated by ki in D denote. If, for example, the domain is the set of natural numbers, the truth value of (5.3) depends on the elements
assigned to the terms k1, k2, k3, .... In general, in order to determine the truth value of (5.3) in a domain D it is necessary to know what is assigned to
the terms of the set {ka |
}. These are the terms that, as I said in chapter 3, are generated by ki in domain D. These terms are essentially treated
like non-fleeing indices. As regards 
the determination of the elements of the domain assigned to them for the purpose of interpreting a formula, the way Löwenheim
speaks of them presents the same problem as in the case of the constant indices.
5.3.2 So far the discussion has been presented in a way that obviates the need to consider assignments. In certain cases, such as (3.11) in subsection 3.2, I have used a formulation analogous to (5.1) to assign elements of the domain, but we now need to be more meticulous. In my commentary on the proof of the theorem I will use, besides the concept of solution, the concepts of assignment and interpretation. I will not give a definition of either concept here (I do so in the appendix). I merely want to make the clarifications that will enable me to use the concepts with the required precision.
As we already know, a solution in a given domain is a function that assigns truth values to the relative coefficients in the said domain. An assignment in a domain D is a function that assigns elements of D to the variables and to the fleeing indices. Remember that, if kij is a fleeing index, the terms generated by kij in D are also called “fleeing indices”; so an assignment in D also assigns elements of D to the terms generated by a fleeing index in D. If we take these indices to be functional terms, the element of D assigned to a fleeing index must depend not on its subindices, but on the elements assigned to its subindices; in this case, a function from the set of indices (fleeing or not) into the domain must fulfill this condition to be an assignment. If we do not take them to be functional terms, then any function from the set of indices in the domain will be an assignment. When an aspect of the proof of the theorem depends on whether the fleeing terms are or are not functional terms, we will consider both possibilities.
An interpretation in a domain D assigns to each formula a truth value. As we know, if D is any domain, for each solution in D and each assignment in D there is a unique interpretation in D which is defined by recursion. Leaving aside the technical details of the case, the definition is the usual one, and so there is no need to present it. We say that a formula is satisfied by (or is true under) an interpretation in D when the interpretation assigns the value true to it. A formula is satisfiable if there exist a domain D and an interpretation in D that satisfies it. In the same way, we say that an equation is satisfied by (or is true under) an interpretation in D when it assigns the same truth value to both members of the equation. The concepts of validity, validity in a domain, and so on are defined in the usual way.
When there is no possibility of confusion, I will omit the reference to the domain and will speak simply of interpretation. In particular, I will use “for every interpretation” as an abbreviation of “for every domain D and every interpretation in D.” and “there exists an interpretation” as an abbreviation of “there exists a domain D and an interpretation in D.”
On occasion, it will be necessary to make explicit the solution and the assignment that determine a given interpretation in a domain D. I will refer by (S, v) to the interpretation determined by the solution S and the assignment v (obviously, we assume that the solution and the assignment are both in D). For example, we can say that a formula is satisfiable when there exist a domain D, a solution S in D, and an assignment v in D such that (S,v) satisfies the formula in D.
5.3.3 The clarifications I have just introduced are necessary to an acceptably rigorous discussion of the following chapter, but we should recall that Löwenheim did not have recourse to them. This is to say, although his intuitions are correct, he cannot be expected to proceed as if he had all this conceptual framework at his disposal.
5.4.1 After characterizing the concepts of relative expression and relative equation, Löwenheim makes the following classification of the equations:
A relative equation can be
(a) An identical equation [[identische Gleichung]];
(b) A fleeing equation [[Fluchtgleichung]], that is, an equation that is not satisfied in every 11 but is satisfied in every finite 11 (or more explicitly, an equation that is not identically satisfied [[identisch erfüllt]] but is satisfied whenever the summation or productation indices run through a finite 11);
(c) A halting equation [[Haltgleichung]], that is, one that is not even satisfied in every finite 11 for arbitrary values of the indices. (“Über Möglichkeiten,” p. 448 (233); Löwenheim's italics)
The word “identical” is normally used to differentiate terminologically the concepts that belong to the logic of classes on the one hand from those that belong to arithmetic or to the logic of relatives on the other. Algebraic logicians speak of identical operations or equations to indicate that they are operations or equations of logic, and not of arithmetic or of the theory of relatives. However, in this case Löwenheim is using “identical” with a different meaning. Although he does not identify them, from the structure of the classification it is clear that the identical equations are the ones that are satisfied by every interpretation. All in all, then, the identical equations are the identities (that is to say, the valid ones).
In the characterization of the fleeing equations Löwenheim uses for the first time in “Über Möglichkeiten” the concept of identically satisfied equation, which will take on special importance in the proof of his famous theorem. As with other semantic concepts, Löwenheim uses it without previously clarifying its meaning. There is nothing particularly remarkable here. Saying that an equation is satisfied is the same as saying that it holds, and from the algebraic point of view, it is not necessary to clarify what it means to assert that an equation holds for a given assignment of values to its parameters. Evidently, it may be that an equation holds for any values of its parameters, that it holds only when they take values inside a particular domain, that it does not hold for any values of its parameters, and so on. These concepts are essentially the concepts of validity, validity in a specific domain, nonsatisfiability, and so on.
The various ways in which Löwenheim makes explicit the concept of an identically satisfied equation throughout “Über Möglichkeiten” show clearly what I have just said. For example, at the beginning of the proof of the last theorem in the paper, he suggests that an equation can be “identically, non-identically or never satisfied” according to whether it holds for all, for only some, or for no systems of values of their parameters (“Über Möglichkeiten,” p. 463 (246)). A little later, when he needs to use the concept in a proof, Löwenheim is more explicit and more precise:
If in fact f = 0 is not identically satisfied, then there are a domain 11 and a system of values of the relative coefficients of the relatives a, b, . . . occurring in f for which the equation is not satisfied. (“Über Möglichkeiten,” p.469 (251))
Using the terminology introduced in the previous section, we can say that an equation is identically satisfied in a domain when every interpretation in that domain satisfies it. In general, when an equation is identically satisfied in every domain Löwenheim says simply that it is identically satisfied (the above quotation is an example of this); in other words, an equation is identically satisfied when any interpretation satisfies it.
Löwenheim is on occasion a little sloppy in his use of this terminology. For example, in the proof of the last theorem in “Über Möglichkeiten” (in the paragraph following the above quotation) we find the following sentence: “For F = 0 is, after all, identically satisfied for other systems of values.” What Löwenheim means is that there are other systems of values (other interpretations) that satisfy F = 0. Löwenheim should say satisfied instead of identically satisfied. As we will immediately see, in the classification of the equations Löwenheim does the opposite: he says that an equation is satisfied when he should say that it is identically satisfied.
Returning now to the classification, identical equations are identically 
satisfied equations. In general, Löwenheim does not speak of identical equations, but of identically satisfied equations.
Fleeing equations and halting equations are non-identically satisfied equations; that is, not every interpretation satisfies them. The way Löwenheim formulates the condition that distinguishes fleeing from halting equations is slightly confusing. He should have omitted the reference to the summation and productation indices (the quantified variables) because it contributes nothing in the case of fleeing equations and can be confusing in the case of halting equations. It would have been clearer to say simply that non-identical equations can be fleeing or halting equations; fleeing equations are those identically satisfied in every finite domain and halting equations those that are not. Observe in addition that Löwenheim uses the word “satisfied” as an abbreviation of “identically satisfied.”
Put in our terms, the fleeing equations are not satisfied by every interpretation, but are satisfied by any interpretation in a finite domain. An equation is called halting if there exist a finite domain D and an interpretation in D that does not satisfy it. In other words, the identical equations are the valid ones; the fleeing equations are the nonvalid but finitely valid equations (valid in every finite domain); and the halting equations are the equations that are not finitely valid. The justification of the names of these equations is found in the proof of the theorem.
5.4.2 For the proof of the theorems, Löwenheim assumes that all the equations are of the form A = 0. This assumption permits a natural step from equations to formulas. An equation A = 0 is identically satisfied if (and only if) no interpretation satisfies A, that is, if A is not satisfiable. Consequently, A = 0 is a fleeing equation just in case A is satisfiable but not satisfiable in finite domains; and A = 0 is a halting equation if A is satisfiable in finite domains.
5.4.3 The example of fleeing equation that Löwenheim uses is
To see that (5.4) is a fleeing equation, it suffices to observe that the formula on the left of the equality symbol, and which for the sake of clarity we could write as
is not satisfiable in finite domains, but satisfiable in an infinite domain. For (5.5) to be true, the relative z should be
interpreted as a function 
from a proper subset of the domain D 
) onto D 
. It is evident that this can only be the case if D is infinite. Consequently, (5.5) will take the value 0 (and therefore
(5.4) will always be true) for every interpretation in a finite domain. In addition, (5.5) is true (it takes the value 1)
in the domain of natural numbers when we read zhi as “h is the successor of i:” In this case, (5.4) is false, which shows that it is not identical.
1“ Über Möglichkeiten,” p. 464 (246); Löwenheim's italics. Observe that Löwenheim does not use the notation of the algebra of relatives.
2“ Über Möglichkeiten,” p. 454 (238); Löwenheim's italics. There is an erratum in the English translation: in From Frege the variable k instead of the variable h is included among the productation indices in (2).
3Löwenheim uses the term “system” informally here. Elsewhere in the paper (e.g., in theorems 3 and 6) he uses it in the strict sense: a system is a relative that fulfills z = z; 1 (see subsection 2.3.3 in chapter 2).