Manzano Model Theory

Manzano: Model Theory

María Manzano’s Model Theory (OUP, 1999) goes at a modest pace, is reasonably short (the main text is just 220 pages), is reasonably clearly written, and in its coverage bridges the gap nicely between the fragmentary initial treatments of model-theoretic topics that we get in some first-order logic texts and the more sophisticated complexities of e.g. Wilfrid Hodges’s Shorter Model Theory or David Marker’s Model Theory. The book is therefore an obvious candidate recommendation for someone with a background knowledge of FOL who wants to ease into studying this area of mathematical logic.

Manzano’s text is translated from a Spanish original; the translation is sadly peppered with not-quite-English sentences which shouldn’t, however, cause most readers any trouble. That aside, how well does the book work?

Ch. 1, ‘Basic notions: universal algebra’ is on structures and relations between structures (homomorphisms, embeddings, etc.). The examples are the usual ones, and will be very familiar to mathematicians (if not to philosophers, who might have appreciated a few slightly more filled-out explanations). There are some slightly odd choices of notation in the examples, and a minor presentational glitch when the first examples of types (signatures) of structures on p. 7 don’t match the official definition on the previous page (the official definition treats a type as an ordered pair of functions from labels to numbers which give the adicity of the labelled functions and relations which go to make up a structure: but examples, in an unannounced way, treat types as a pair of sequences of the values taken by these functions).

It perhaps bears comment that Manzano defines a structure at the outset starting like this:

$latex \mathfrak{A}$ is a structure iff $latex \mathfrak{A} = \langle A, \langle f_i\rangle_{i \in I}, \langle R_j\rangle_{j \in J}\rangle$ with two associated functions $latex \mu \colon I \to \mathbb{N}$ and $latex \delta \colon J \to \mathbb{N} – 0$ such that …

Now: if it passes muster to talk of a triple being associated with a pair of functions, why not adopt this way of talking more generally? So why not say: a structure consists in some objects associated with (or, as they say, equipped with) some functions and relations, etc.? Exactly what work does invoking the formal set talk which Manzano uses do here? And if it is necessary work, where does that leave the informal talk of ‘associating’ a triple with two functions?

It would be most unfair to pick out Manzano for especial criticism here, but she is glossing over something worth discussing: namely, we should distinguish (i) the mathematician’s informal notion of a structure (objects associated with/equipped with some functions and relations, etc.) and (ii) the idea of a set-theoretic model of a structure — which starts by forming the set of the relevant objects (or should that be: form a set of set-representatives of the original objects?), then models the functions and relations as themselves special sets, and then puts things into tuples, etc. You might have thought that model theorists would want to talk about this at least a little at the outset!

One other minor comment. Manzano cheerfully asserts without comment that e.g. $latex \langle\mathbb{N}, <\rangle$ is a substructure of $latex \langle\mathbb{R}, <\rangle$ — thereby assuming that natural numbers are just some of the real numbers. Readers who have already been taught to identify $latex \mathbb{N}$ and $latex \mathbb{R}$ with certain sets will balk at that. Others of her readers (better brought up?) who have come to think of the mathematical universe as strongly typed will balk for other reasons. It strikes me as odd in a book that is all about structures not at least to flag up that there are issues here that might worry those with a structuralist bent. Better, perhaps, just to keep everyone happy by saying that $latex \langle\mathbb{N}, <\rangle$ is isomorphic to a substructure of $latex \langle\mathbb{R}, <\rangle$, and the like.

Ch. 2 is on ‘First-order languages: semantics’, and introduces the usual sort of general story about syntax and one standard brand of semantics (essentially Tarski’s later model-theoretic account). Manzano then describes some specific languages, and proves a few results — e.g. that isomorphic models assign the same values to sentences. Some of the ‘book-keeping’ results get rather laboriously detailed proofs, but this is done tolerably clearly.

The obvious point to pause over is Manzano’s definitions of validity and consequence (as it happens, for formulae in general, not just for sentences — though I’m not sure she explains the point of giving the more general account). She writes, as you would expect, that a formula $latex \varphi$ is valid just if for every structure and every assignment the structure together with the assignment satisfies $latex \varphi$. But what entitles Manzano to the assumption that the quantification ‘every structure’ is well-defined? Officially, a structure is a triple whose first member is a non-empty set: but she never says outright these have to be non-empty pure sets. And indeed, she has structures whose domains contain natural numbers, symbols, truth-values, etc. and we aren’t told here that such objects are themselves all pure sets — though see §6.4.1. So, at least at this point in the book, in quantifying over all structures we seem to be quantifying over tuples built from impure sets; but what impure sets are there? That depends, presumably, what objects there are to put into impure sets. But the very idea of an object here is, to say the least murky. So it seems that talk over ‘every structure’ is going to be correspondingly indeterminate. Well, that might not matter: but it isn’t obvious at the outset that it won’t matter (if you believe in more objects than I do, you have more structures to play with than I have, so couldn’t it be that you will be able to find a structure which invalidates a sentence which looks valid to me? and if that can’t happen, shouldn’t it be explained why not?). I suspect that Manzano would want to avoid such troubles by officially going set-theoretically reductionist — again see §6.4.1: but she really ought to have addressed such questions explicitly.

Ch. 3 proves the completeness theorem. First, of course, Manzano has to give a deductive system to prove complete! She choses to adopt the sequent calculus from Ebbinghaus, Flum and Thomas. Oddly, Manzano says that an advantage of her choice is that ‘the soundness proof is much simpler’ — simpler than what?

As an aside, I have to say I don’t like her choice of calculus. A minor quibble is that, instead of writing a sequent as ‘$latex \Gamma \vdash \varphi$’, or ‘$latex \Gamma \Rightarrow \varphi$’, or even ‘$latex \Gamma \colon \varphi$’, Manzano follows EFT in just writing an unpunctuated ‘$latex \Gamma\ \varphi$’. Much more seriously, many would say that their shared system of rules runs together a classical logical rule for the connectives with a structural rule in an unprincipled way that hides e.g. the relation between classical and intuitionistic logic. [To be more specific, they introduce a classical ‘Proof by Cases’ rule that takes us from the sequents (in their notation) $latex \Gamma\ \psi\ \varphi$ and $latex \Gamma\ \neg\psi\ \varphi$ to $latex \Gamma\ \varphi$, and then show that this almost immediately yields Cut as a derived rule. This seems to me to muddy waters that usual presentations of the sequent calculus strive to keep clear.] However, but let’s not fuss about this. What matters in the present context is that we are dealing with a deductive calculus — elegant and nicely motivated or otherwise — which has certain key features which allow the completeness proof to go through. In fact, I guess a nice approach for a book concentrating on model theory would in fact be to highlight those key features to give a general theorem of the kind ‘any deductive system satisfying conditions $latex C_1, C_2, C_3, \ldots$ is semantically complete’. But Manzano, not unusually, just offers one deductive system in a take-it-or-leave-it spirit, and proves completeness for that.

And how does the Henkin-style proof go? Manzano first proves that if $latex \Gamma$ is syntactically consistent — where $latex \Gamma$ is set of formulas of a countable language, and with only a finite number of variables occurring free — then $latex \Gamma$ has a countable model. Why the uncommon initial restriction to a finite number of free variables? Because this enables her, in the usual sort of construction, to add a witness for an existential wff $latex \exists\xi\varphi(\xi)$ of the form $latex \varphi(y)$ where $latex y$ is the first variable that doesn’t yet appear free as we augment $latex \Gamma$ — assuming that only finitely many variables appear free at the outset means that we have unlimitedly many more variables remaining to play with. That rather neatly avoids the usual dodge of having to add infinitely many new names to the language by instead using the infinite supply of variables which are there already. If she cares about this neatness, it is a pity that when Manzano moves on to lift the restriction on the number of variables initially appearing free in $latex \Gamma$ she now adds an infinite number of names. What she should have done, of course, is double the indices of all the variables occurring in $latex \Gamma$ to get an equi-consistent $latex \Gamma\prime$, and then she’d have all the odd-indexed variables to play with.

Otherwise, the proof goes in pretty much the familiar way, i.e. by overkill — rather than add just enough truth-makers to $latex \Gamma$ to get a Hintikka set, we order all the wffs and go along the sequence throwing each and every wff into an augmented $latex \Gamma$ so long as it doesn’t produce an inconsistency with what’s gone before. Then a term model is produced — and Manzano (likes many authors) goes immediately for a normal model for a language with identity which adds a layer of complexity taking quotients. This isn’t how I would do things, but there is a lot of signposting (e.g. at Figure 3.3) and a real effort is made to try to ensure the proof is understandable.

With the countable case proved, Manzano then explains rather well what has to be done to extend the proof to show that a consistent set of wffs $latex \Gamma$ from an uncountable language has a model. What she doesn’t explain, however, is why we might be interested in theories framed in uncountable languages.

Apart perhaps from the rather richer diet of examples of structures, what we have so far will be broadly familiar to readers who have done a serious FOL course which goes up to the completeness proof. In Ch. 4, we start on ‘Basic notions: model theory’, concentrating first on the standard ideas of elementary equivalence, elementary substructure and elementary embeddings. The chapter then continues to discuss the notion of a theory, the ideas of a theory of a class of models and the class of models of a theory, and finishes with a first look at the notion of a diagram of a theory. All this is reasonably clearly done, though a few more examples and perhaps significantly more motivational chat would have been nice, both about why we should care and about why some of the more laborious proofs are mere ‘book-keeping’, checking results that should intuitively hold once you’ve grasped the relevant ideas. (One presentational glitch I noticed: on p. 105 where we are asked to ‘remember’ that quantifiers can be eliminated from the theory of dense orders without endpoints — when we don’t meet this result until a later chapter.)

The next two chapters are really the core of the book: Ch. 5 is on ‘The compactness theorem and its mathematical implications’ and then Ch. 6 covers ‘Löwenheim-Skolem theorems and their consequences’.

So Ch. 5 starts with some preliminaries about the notions of axiomatizable properties, classes of structures and theories. Then we get a new proof of compactness that doesn’t go via the completeness proof but still involves a Henkin-like construction on diagrams. There follows the usual catalogue of initial consequences of compactness (e.g. the notion of finiteness is not axiomatizable, if a class of structures is finitely axiomatizable iff both it and its complement are axiomatizable, arithmetic has non-standard models, an infinite grpah is 4-colourable iff all its finite subgraphs are 4-colourable). There are a few typos in the statements of definitions and theorems which shouldn’t cause any trouble. Again a little more motivational chat at various points might have been nice, and the remarks on second-order theories at the top of p. 132 are too fast to be any use (and indeed I’d quibble about the use of the idea of a ‘second-order structure’). But overall a decent treatment.

Then, half-way through §5.4, there’s something of a change in gear as the discussion turns to the ‘amalgamation’ of embeddings, and a proof that if a theory admits quantifier elimination then the class of substructures of its models is ‘amalgamable’. The discussion proceeds without any explanation of why this should be significant or other motivational pointers.

Finally in Ch. 5, the compactness theorem is proved again, this time via Loś’s theorem and ultraproducts. At the risk of getting repetitious, it has to be said that Manzano again delivers this with only a little motivational guidance as she goes along: most readers would welcome rather more help to guide intuition here. Also it would have been good to pause for some discussion comparing the different explanatory gains from the different approaches to the compactness theorem.

Ch. 6 starts with very general versions of the Downward and Upward Löwenheim-Skolem Theorems, presented as results about elementary embeddings — given a language of a certain cardinality and a structure $latex \mathfrak{A}$ of a certain cardinality there will be a smaller [larger] structure $latex \mathfrak{B}$ such that $latex \mathfrak{B}$ elementarily embeds into $latex \mathfrak{A}$ [$latex \mathfrak{A}$ elementarily embeds into $latex \mathfrak{B}$]. I think it would have helped understanding to work up to these more general versions from more familiar versions rather than derive the latter as corollaries, but that’s perhaps just a presentational preference. Manzano has a nice discussion of the very idea of non-standard models at the beginning of §6.3, before giving admirable accounts of non-standard models of arithmetic and non-standard models of the reals with infinitesimal elements.

The chapter concludes with a section on Skolem’s paradox which perhaps makes rather heavy weather of the key point. But notable here is Manzano’s §6.4.1 where she says outright that ‘concepts of natural number, function, structure, and homomorphism’ can be ‘reduced to the concept of set’, and context makes it clear she is thinking of pure sets as described by the ZF axioms. That explains, perhaps, her earlier insouciance about e.g. quantifying over all structures as if that makes determinate sense.

Finally, Ch. 7 discusses completeness, categoricity and $latex \kappa$-categoricity and proves the usual introductory results and gives Vaught’s test etc. Manzano then moves on to define the notion of a theory’s admitting quantifier elimination, gives some examples without proof, proves a general test for quantifier elimination, which is then used — at last — to show some specific theories do admit quantifier elimination. I’m not sure this approach works ideally well: by my lights, it would probably have been significantly better to work through a simple example by way of motivating the general story.

Manzano then goes on to discuss Robinson’s notion of model completeness. And the book ends with a detailed discussion of the completeness and decidable of the theory for the structure of natural numbers with successor. (There is no concluding afterword reviewing where we’ve been, or giving pointers ahead.)

So to a summary verdict:

• Standing back from the details, I do very much like the way that Manzano has structured her book. The sequencing of chapters makes for a very natural path through her material, and the coverage seems very appropriate for a book at her intended level.
• The general level of difficulty remains broadly constant through the book: students who can cope with the first half of the book will be able to press on to the very end without getting out of their depth. The presentations are in themselves mostly pretty clear if you work at them (mathematicians should have few problems, while philosophers who have happily managed a serious FOL course but lack much mathematical background might need to resort to Wikipedia occasionally but should otherwise cope too).
• I do think, however, that the discussions at quite a few points would have benefitted from quite a bit more informal commentary. It isn’t that Manzano doesn’t pause to offer general historical remarks, etc. (so far so good!): but when it comes down to explaining key formal concepts and proofs, more motivation for various choices, more ‘Look at it like this ….’ classroom-style explanations, would have helped a lot.
• In short,  key ideas are too often not sufficiently well-motivated nor are they ideally well explained. And the separation between key results and tedious ‘book-keeping’ proofs should have been better signalled. So while, by the standards of many mathematical logic books, this is quite a reader-friendly text, it could have been quite a bit more so.
• Still, though not ideal (few books are!), Manzano’s introduction to model theory at this level compares pretty well with alternatives and remains a good option for beginning work in this area of logic.