# Substitutions and Models, Part 1: Bolzano, Quine, Tarski, and Boolos

Let ‘$\Rightarrow$‘ stand for a (not-yet analyzed) relation of logical consequence. According to the substitutional analysis of quantification, $\Delta \Rightarrow P$ iff every substitution scheme $\Delta$ is true under is also one $P$ is true under. According to the model-theoretic analysis, $\Delta \Rightarrow P$ iff every model on which $\Delta$ is true is also a model on which $P$ is true. The substitutional account is generally associated with Bolzano, and the model-theoretic with Tarski. Tarski’s objections to Bolzano’s account are generally thought to tell against the substitutional account and in favor of the model-theoretic. And what goes for logical consequence goes for logical truth — especially as $P$‘s being a logical truth is generally thought equivalent to it’s being a consequence of the empty set.

Enough of background. Now for the plot: Quine, in Philosophy of Logic, has an argument that — provided the background language is rich enough for elementary arithmetic (say, Peano Arithmetic) — the two accounts of logical truth are equivalent. This is prima facie surprising, and for two reasons: First, Tarski’s objection against Bolzano’s account shows that the two aren’t equivalent in general, and so it’s surprising that they would collapse for languages of this expressive power. Second, certain objections raised by e.g. John Etchemendy (The Concept of Logical Consequence) against Tarski’s official account (or, at least, Etchemendy’s reading of it) seem easily parlayed into an argument that the two are not equivalent for any first-order language.

To thicken the plot, in “On Second-Order Logic,” George Boolos argues that, although Quine is right about the two accounts of logical truth, the result does not extend to logical consequence, even in first-order languages. This is surprising, too: given compactness results, we ought to be able to move from logical truth to logical consequence.

I want to get to the bottom of these issues in a series of four posts. Here’s my plan of attack. In this post, I’ll sketch the two theories and lay out these three prima facie puzzles in more detail. The next post focuses on Quine’s side of things, first solving some of the puzzles and then examining Quine’s argument — and the scope of the premises it requires — in more detail. The third post will be dedicated to understanding Boolos’s argument and seeing how it interacts with the central puzzle to be outlined here. A final post will look at philosophical issues kicked up in the first three.

Here’s this post’s plan of attack. In section one, I’ll lay out the substitutional account in detail and give Tarski’s argument against it. Section two explains the model-theoretic account. Section three gives an argument (derived from Etchemendy’s) that the substitutional account of logical truth predictably delivers different results for first-order languages than the model-theoretic. And in section four, I’ll outline the argument that, if the accounts of logical truth are equivalent, then so are the accounts of logical consequence.

Section 1: The Substitutional Account

Suppose L is an interpreted language. Let a substitution scheme be a function from syntactically simple terms of L to any expressions of L at all that could be substituted without turning sentences into non-sentences. (If there are bound variables, we’ll also need some restrictions to keep them from interfering with each other, but we can ignore that here.) So, for instance, a syntactically simple predicate like is tired’ (I’m pretending copula are syntactically embedded — just work with me here) could be taken to another simple one like is hungry’, or to a complex one like is about to eat every Taco in the tri-state area’. And a connective such as and’ could be taken to another simple connective, such as or’, or to a complex connective, such as ‘unless I hear by tomorrow that _______, John is going to think that _________’.

Some substitution schemes will take some simple expressions to themselves. In this case, say that it preserves those expressions.

One final bit of terminology. If P is a sentence and S a substitution scheme, let S(P) be the result of replacing all of P’s simple expressions with their values given by S. And if $\Delta$ is a set of sentences, let S($\Delta$) be the set of S(P) for P $\in \Delta$.

OK, now we’re ready for our definitions of logical consequence (and, by extension, logical truth). If $E$ is a set of expressions, then say that P is an $E$ substitutional consequence of $\Delta$, written $\Delta |\!\!\models_{E}$ P, iff for every $E$-preserving substitution scheme S, if all of S($\Delta$) are true, then S(P) is true, too.

Now, this doesn’t quite give us a definition of logical consequence; it gives us instead a definition of something like logical consequence relative to a set of preserved expressions’. The idea, though, is that if we can pick the right expressions, we’ll have our definition of logical consequence: logical consequence is substitutional consequence under substitutions that preserve those. Those are the expressions we call the logical constants’. Of course, for an arbitrary language, it’s no easy going deciding which expressions are the logical constants. But for, say, first-order languages, the idea is that the logical constants are those that are treated as logically special in our textbooks and so on (you know, quantifiers, truth-functional connectives, etc.)

That, anyway, is the idea. But in “On the Concept of Logical Consequence,” Tarski argued against the view more-or-less as follows. Suppose that L is really impoverished. Suppose, for instance, that along with logical vocabulary, it only has one predicates and two names (each of which means what they do in English):

 Names Predicates Washington was president. Lincoln

Now consider the argument:

1. Lincoln was president.
2. Therefore, Washington was president.

Intuitively, this shouldn’t count as a valid argument. But — given the extreme impoverishment of the language — it does. Any substitution scheme that preserves the logical terms won’t have any way of substituting in something for (1) that makes it true while substituting in something for (2) that makes it false. The problem, essentially, is that the only predicate the language has doesn’t divide between Lincoln and Washington, and the language doesn’t let us talk about anything else.

Consider, for instance, the scheme that sends Lincoln’ to Washington’, Washington’ to Lincoln’, and was president’ to was not president’. This makes the conclusion false — but also makes the premise false! And no other substitution scheme does the job either.

The problem is apparent: it’s simply the impoverishment of the language that’s to blame. If we had the predicate had a beard’ in the language, the argument would count as invalid: the scheme that sends was president’ to had a beard’ (and kept the names the same) would make the premise true and the conclusion false. But since our language doesn’t have such a predicate, the problem remain.

Notice the nature of the problem. The complaint isn’t that the substitutional account delivers the wrong verdict about any arguments we ever actually encounter. We speak a very rich language (English, at least for readers of this blog, and perhaps others as well). The problem is that the account delivers the wrong verdict about arguments in some possible language. So if we’re going to let this worry move us to a different account of logical consequence, notice that we must be implicitly endorsing a principle like,

UNIVERSAL: If an account of logical consequence is correct, it must deliver the right results for any possible language.

For those who accept UNIVERSAL, the natural “fix” behind the basic Bolzanian idea is to move to the model-theoretic account of logical consequence.

Section 2: The Model-Theoretic Account

The basic idea behind the model-theoretic account is that there are a range of things, models, with a certain structure, and a relation of truth in’ defined between these models and sentences of L. If the language is first-order, we can be a bit more precise: a model is an ordered pair $\langle D, I\rangle$ of a domain D and an interpretation function I. D is just any old set of things. I is a function from names of L to objects in D and predicates of L to subsets of D (or subsets of $D^{n}$, for n-placed predicates) that provides the extensions’ of those predicates on the model — provides the things in the domain that, according to the model, are the way the predicate says they are. We also need a definition for truth in’ — thanks to the necessity of dealing with quantifiers and variables, this is a fairly complex recursive one in terms of satisfaction, but I’m not going to make hay about the details here, since it’s pretty easy to see which sentences should be true on a model given that we know what terms’ denotations and predicates’ extensions are.

For instance, a model for our simple language from above would give us a set of things D, and then tell us which of those things got assigned Lincoln’, which got assigned Washington’, and which were in the extension of was president’. Then a sentence like, say, Lincoln was president’ would be true iff the thing assigned to Lincoln’ on the model was in the extension assigned to was president’ on that model, and a sentence like Something was not president’ would be true iff there were things in the domain that weren’t in the extension of was president’.

A model is called a model of a sentence iff the sentence is true on it, and a model of a set of sentences iff all the sentences in the set are true on it. If every model of $\Delta$ is also a model of P, we write $\Delta \models P$, and say that P is a model-theoretic consequence of $\Delta$.

The model-theoretic account of consequence insists that logical consequence is model-theoretic consequence. It’s fairly easy to see that the model-theoretic account won’t suffer from the problem that plagued the substitutional. Consider again the argument:

1. Lincoln was president.
2. Therefore, Washington was president.

For it to be valid, every model of 1 must be a model of 2. But there are models of 1 that aren’t models of 2. Just take a model with a domain of two things, say a and b which assigns Lincoln’ to the first, Washington’ to the second, and assigns the set $\{a\}$ to the predicate was president’.

Section 3: Inequivalence

The foregoing is enough to show that the two accounts are inequivalent; that is, it’s enough to show that the following does not hold for arbitrary languages L:

(EQ) $\Delta |\!\!\models P \textrm{ iff } \Delta \models P$

We might think that’s not a huge deal: perhaps for suitably expressive languages EQ does hold. (This, in effect, is what Quine will argue.)

But here’s a simple argument, inspired by one John Etchemendy gives against (his reading of) Tarski in The Concept of Logical Consequence. The (adapted) argument shows that for any first-order language, EQ fails.* It goes a little something like this.

Let L be a first-order language. Presumably, its quantifier ranges over more than one object. Now consider the counting sentence’

(E2) $\exists x\exists y(x \ne y)$

This sentence is true. Is it a logical truth? Or — more to the point — do we have $|\!\!\models$ (E2)? Do we have $\models$ (E2)?

Well, note first off that $\not\models$ (E2). There are always models with just one thing in the domain; on the model-theoretic conception, then, this does not count as a logical truth.

But the substitutional account disagrees. All of the terms in (E2) are logical terms, so any of the substitutions we care about for evaluating consequence will be ones that keep (E2) the same. (That is: they’re substitutions S where S(E2) = (E2)!) Since (E2) is in fact true, and the substitutions don’t turn it into any different sentence, it remains true under all substitutions — and so $|\!\!\models$ (E2).

Maybe we can fiddle with this. Here’s one way: allow that preservation’ of quantifiers can include trading in simple quantifiers for complex restricted’ ones — allow $\exists x$, to be taken, say, to $\exists x(Fx \wedge \underline{\ \ \ \ \ })$‘. (If we want to preserve duality — that is, if we want $\exists x P$ to be equivalent to $\neg\forall x \neg P$ — we’ll need to insist that substitution schemes have to mesh’ in a certain way with how they treat their existential and universal quantifiers.) Once we revise our account, we no longer have $|\!\!\models$ (E2). If `F‘ is a predicate that in fact applies to only one thing, the following counts as a false substitution instance:

(E2*) $\exists x(Fx \wedge (\exists y(Fy \wedge (x \ne y)))$

But this modification brings model-theoretic and substitutional consequence into agreement on (E2) only by making them disagree about the argument form:

1. $Fa$
2. Therefore, $\exists x Fx$

This is straightforwardly valid on the model-theoretic account. But on the (new, modified) substitutional account, the following is a fair substitution instance:

1. $Fa$
2. Therefore, $\exists x(\neg Fx \wedge Fx)$

(We get it by the substitution scheme that takes $\exists x$ to $\exists x(\neg Fx \wedge \underline{\ \ \ \ \ })$.) And this disagreement about valid arguments will turn into a disagreement about logical truth, since the model-theoretic account will, and the substitutional account will not, reckon the conditional with 1 as antecedent and 2 as consequent a logical truth.

It is possible to further modify the substitutional account to make it march in step with the model-theoretic one, at least given that L’s quantifiers in fact range over infinitely many objects. The modifications basically impose large scale constraints on the substitution instances — constraints that, for instance, if you substitute $\exists x(Fx \wedge \underline{\ \ \ \ \ })$ for $\exists x$, you have to also substitute names of things that satisfy F for names, and predicate expressions that are satisfied only by F-things for predicates. However motivated these restrictions might be (and they don’t seem very), they don’t help the prima facie puzzle. For the prima facie puzzle is that the two accounts disagree, but Quine is going to argue that they do agree, contra what’s already happened. And Quine’s argument isn’t predicated on any fancy-schmancy jazzing up of the old substitutional account; it’s predicated on the boring substitutional account of the sort described back in Section 1. So what gives?

Section 4: Consequence and Truth

The puzzle in Section 3 admits a simple solution, but I’ll wait until the next post to give it. Here, I want to present a deeper puzzle. At the end of the next post, we ought (if Quine does his work right) to be convinced that, for expressive enough languages, the following restricted version of EQ holds:

(EQ-R) $|\!\!\models P \textrm{ iff } \models P$

In the final post, Boolos is going to give us a general argument that, even for these more expressive languages (especially for them, in fact), EQ fails. All the languages in question are first-order. And there is a fairly straightforward argument that EQ holds for a given first-order language iff EQ-R holds for that language.

The argument stems from three properties of first-order logic. The first is compactness. I’ll give a generic version of it here:

(COMPACTNESS) $\Delta \Rightarrow P$ iff there is a finite subset $\Gamma \subseteq \Delta$ where $\Gamma \Rightarrow P$.

(In other words, no valid first-order arguments require infinitely many premises in order to be valid.) The second theorem is a kind of generalized deduction theorem, which I’ll write as follows:

(DEDUCTION) $Q_{1}, Q_{2}, \ldots, Q_{n} \Rightarrow P$ iff $\Rightarrow (Q_{1} \wedge Q_{2} \wedge \ldots \wedge Q_{n}) \supset P$

Finally, we have

(MONOTONICITY) If $\Delta \Rightarrow P$ and $\Delta \subseteq \Gamma$, then $\Gamma \Rightarrow P$.

That is: adding premises to an argument can’t take validity away. For all of these results, we can consider model-theoretic and substitutional versions by replacing ‘$\Rightarrow$‘ with ‘$|\!\!\models$‘ or ‘$\models$‘, respectively.

DEDUCTION and MONOTONICITY are relatively trivial, and can be seen to hold by inspecting the definitions of each kind of consequence, plus (for DEDUCTION) the truth-table for the material conditional, $\supset$. COMPACTNESS is not at all trivial, although in the model-theoretic setting it’s very well established. The substitutional variant is probably going to show itself as the cause of all the bother when all is said and done, but let’s not get ahead of ourselves. Let’s just go through the argument.

I’m actually going to just go through one half of the argument: I’ll argue that, if $\Delta |\!\!\models P$, then $\Delta \models P$. But it is trivial to reverse the argument, because all of the premises (other than EQ-R, which is a biconditional) apply equally well to both kinds of consequence. One bit of notation will help: if $\Gamma$ is any finite set, then I take the privilege of rewriting it as $\{Q_{1}, Q_{2}, \ldots, Q_{n}\}$. OK, here goes.

1. Suppose $\Delta |\!\!\models P$
2. By COMPACTNESS, for some finite $\Gamma \subseteq \Delta$, $\Gamma |\!\!\models P$
3. Rewriting, $\{Q_{1}, Q_{2}, \ldots, Q_{n}\} |\!\!\models P$
4. By DEDUCTION, $|\!\!\models (Q_{1} \wedge Q_{2} \wedge \ldots \wedge Q_{n}) \supset P$
5. By EQ-R, $\models (Q_{1} \wedge Q_{2} \wedge \ldots \wedge Q_{n}) \supset P$
6. By DEDUCTION, $\{(Q_{1} \wedge Q_{2} \wedge \ldots \wedge Q_{n}\} \models P$
7. Since $\{Q_{1}, \ldots, Q_{n}\} \subseteq \Delta$, by MONOTONICITY, $\Delta \models P$

The argument works just as well in the other direction, and EQ follows. But if both Quine and Boolos are right, EQ doesn’t follow. Something’s gone wrong. COMPACTNESS for substitutional consequence looks like the best bet. But how? What sentences follow substitutionally from an infinite set of sentences but no finite subset?

This is the central puzzle. We’ll have to wait a few more posts before hitting the bottom of this mess.

* Well, maybe just almost any — there might be some wiggle room if some first-order languages have quantifiers semantically restricted to range over just one object.