Theorem of the Week: the Łos-Tarski preservation theorem

(This may or may not become a regular feature; at the moment, the “theorem of the week” title is more aspirational than anything else…)

So, this week I came across a nice theorem, that I imagine is well known to model theory people, but which seems to me to have a some potentially cool philosophy of science implications. The theorem in question is the Łos-Tarski preservation theorem (not to be confused with what’s usually called “Łos’s theorem”, which is the Łos ultraproduct theorem – although that’s certainly a contender to be a future Theorem of the Week). Informally, the theorem says that a set of first-order formulas is preserved under the taking of substructures (over the models of a fixed theory T) if and only if all the formulas in it are universal (modulo T). So first, let’s spell out both halves of this – starting with the right-hand-side, which turns out to be the simpler one.

So, on the one hand, a formula is universal if it’s constructed purely out of quantifier-free formulas using conjunction, disjunction, and universal quantification. To say that \Phi is equivalent modulo T to a set of universal formulas means that there’s a set \Psi of universal formulas such that for any model A of T, a sequence (a_1, a_2, \dots) satisfies all the formulas in \Phi iff it satisfies all the formulas in \Psi.

On the other hand, a substructure of a first-order structure A is a structure whose domain is a subset of A‘s, and whose extensions are obtained by restricting the extensions on A to that subset. More formally, B is a substructure of A iff \textrm{dom}(B) \subseteq \textrm{dom}(A) and for any predicate P in the signature, P^{B} = P^A|_{\textrm{dom}(B)}. Then, to say that a set of formulas \Phi is preserved under substructures over the models of T means the following: given any models A, B of T such that B is a substructure of A, for any (possibly infinite) sequence (b_1,  b_2, \dotsc,) of elements of B, if (b_1, b_2 \dotsc) satisfies all the formulas in \Phi in A, then it satisfies all the formulas in \Phi in B.

In other words, preservation under substructures means that any time a bunch of formulas are all true of some individuals in a given model of T, then they will also all be true of those individuals in any submodel of that model (provided that the individuals are included in the submodel). The simplest case is where \Phi only contains sentences, as then it just boils down to the condition that if they’re all true of a given model, they’re also all true of any submodel. In sum, then, there’s a sense in which this property means that the set of formulas \Phi exhibits a kind of mereological harmony: it’s true of the whole only if it’s true of the parts.

To see how this condition could fail to hold, think of an existentially quantified statement: “there be dragons”, say (\exists x Dx). Just because there are dragons somewhere in a model, it doesn’t follow that any submodel has to contain dragons. So naively, we can anticipate that having existential quantifiers around might problematise preservation under substructures. On the other hand, it seems pretty natural to think that universal quantifiers aren’t a problem. If something’s true of everything in a model, then we’d expect it to still be true of everything in every substructure (since the everything in a substructure is just a part of the everything in the whole structure). More precisely, we’d expect that if a set \Phi of formulas is equivalent modulo T to a set of universal formulas, then the set \Phi will be preserved under taking substructures on models of T—which is, of course, the right-to-left half of the Łos-Tarski theorem. And, indeed, this turns out to be reasonably easy to prove.

What’s interesting, though, is the other direction. This tells us that if our set of formulas is preserved under taking substructures, then it has to be equivalent to a set of universal formulas. Hence, an apparently purely semantic property of a set of formulas—staying true of individuals, even when you chuck away other stuff—turns out to strongly pin down the syntactic character of that set. This makes the situation rather reminiscent of Beth’s theorem, which also states that a semantic property (implicit definability) and a syntactic property (explicit definability) turn out to coincide, even though at first glance the syntactic property looks stronger. And in fact, the parallels to Beth’s theorem seem to go deeper than this, although I admit that here we’re getting to the technical details I haven’t properly looked into yet: but Hodges’s proof of Beth’s theorem merely notes that it follows “from Theorem 6.6.1 as [the Łos-Tarski theorem] followed from Theorem 6.5.1”. This would also suggest that the Łos-Tarski theorem, like Beth’s theorem, will fail to hold in higher-order contexts, which might temper some of the philosophical lessons that can be drawn from this; still, let’s put that to one side.

Alright. So we’ve learned that being a set of universal formulas is, more or less, the same thing as being preserved in substructures. The reason why this seems interesting to me is how it bears on the question of what characterises a law of nature. There is a long-standing tradition in philosophy of science of taking laws of nature to paradigmatically be universally quantified statements. More specifically, in fact, there’s a tradition of thinking that laws of nature have to be of the form \forall x (Fx \rightarrow Gx), but let’s just go with the weaker claim.

What other properties do laws of nature have to have? Again, there’s a traditional answer: the laws have to be necessary, in some appropriate sense of that word. The problem with this, of course, is that it’s not at all clear how the requirement that laws be necessary could ever be empirically checked, at least insofar as “necessity” is understood as a matter of holding at all possible worlds: we cannot, after all, pop across to some nearby possible worlds to check whether or not the laws hold there. Of course, one could derive necessity from the laws instead, by taking it that necessity (at least, the relevant kind of necessity—presumably, nomological necessity) is defined by the laws. Unfortunately, although it will now be analytic (and so empirically verifiable, if only vacuously) that the laws are necessary, this is at the price of making necessity into no kind of constraint on the laws at all.

A better answer, I think, is that the laws are required to be—in effect—preserved under the taking of substructures. Of course, in the context of scientific theories we don’t tend to talk about substructures; instead, we talk about subsystems. But the point stands: by and large, we expect that when the laws hold of a system, they will also hold of the subsystems which make it up. This is a point that a few people have made recently. For instance, Mike Hicks has a paper on an “epistemic role account” of Humeanism which argues that Humeans should require best systems to exhibit virtues connected to the possibility of experimentally testing theories; he then goes on to observe that

The requirement that the lawbook be supportable by observation or experiments, then, constrains our lawbook as follows: to perform experiments, we need laws which can be observed in isolated subsystems of the universe…[this] requires the laws to apply to subsystems of the universe as well as the universe as a whole.

Hicks, “Dynamics Humeanism”

I also take this to be an idea that David Wallace has been arguing for: I’m not sure if there’s a neat quote like this one, but it’s pretty clearly there in the papers on Fundamental and Emergent Geometry in Newtonian Physics and observability and symmetry. No doubt there are others too – this seems like the kind of thing that pops up in different places, rather than being discussed in a single debate.

(Incidentally, there are some subtleties about whether we should think of the laws as holding of arbitrary subsystems, or only of those subsystems which are reasonably isolated. I tend toward the former, since most laws will let you stick in background structure to represent whatever the subsystem’s environment is up to (this is an observation due to David Wallace) – but others, including Hicks and Schaffer, and (I think, though I’ve not read the paper yet!) Hicks and Demarest, seem to disagree.)

At any rate, the philosophy-of-science relevance of the Łos-Tarski theorem is then to point us toward a potentially profound connection between these two conditions. At least insofar as the theorem holds, the only way for a law to be preserved under substructures is for it to be universal in form. This suggests a way to push back, then, against the lawlikeness of anything which doesn’t have such a universal form: e.g. the Past Hypothesis, or the assertion that there exists a quantum wavefunction with such-and-such properties (as some Bohmians, eg Goldstein Zanghi and Dürr, have proposed). Note that this wouldn’t mean arguing that existential claims are never a legitimate part of scientific theories—just that we shouldn’t characterise such claims as falling under the laws. Going back to the Łos-Tarski theorem, bear in mind that there are no constraints on the “background” theory T, which can have existential quantification in it up to the nines.

So the picture that emerges is of a two-tiered kind of scientific laws: a background theory which postulates existence claims (say, “there exists such-and-such spacetime structures, and particles with such-and-such properties”), overlaid with a set of universal claims (“all particles must move and interact, relative to one another and the spacetime structure, in such-and-such a way”). This mirrors Tim Maudlin’s picture of theories as giving first an “ontology” and then a “nomology”; what is neat, though, is that (if you’ll grant that nomology has to be preserved under substructures), the Łos-Tarski theorem means that these two aspects of scientific theories will be intimately bound up with the difference between the existential and the universal modes of quantification.