Logic: A Study Guide — Basic Model Theory

I’m continuing work on the update for Teach Yourself Logic: A Study Guide. So there are now five chapters in the new Logic: A Study Guide.

There are three preliminary chapters, giving an introduction for philosophers, an introduction for mathematicians, and a guide-to-the-Guide. Then there is a long chapter on FOL. I’ve previously posted versions of these.

The fifth chapter is on entry-level model theory. There’s an overview introducing a few elementary results, intended to give a flavour of the enterprise. There follows the usual sort of reading guide.

Here then is the Guide including this new  chapter. Need I add? — all comments very gratefully received.

In particular I’m sure I can do better at the end of the displayed box on p. 34. I say earlier in the chapter that — although the focus is of course on standard first-order model theory — it is worth at this stage knowing just a bit about second-order logic/theories (so you get e.g. a glimmer of why first-order arithmetic isn’t categorical which a second-order arithmetic can be). But what short and accessible reading on second-order logic would you recommend at this stage? Later in the Guide we’ll be taking a serious look at the topic: but what brisk (perhaps arm-waving but still helpful) intro could be offered at this point?

13 thoughts on “Logic: A Study Guide — Basic Model Theory”

1. Ted Sider has a set of class notes titled “Crash course on higher-order logic” that he’s hosting on his website http://tedsider.org/teaching/higher_order_20/higher_order_crash_course.pdf which I think are rather accessible at this level. At 68 pages I am not sure if it qualifies totally as short, although the main points on second order logic are covered in just the first 25 pages, which is relatively short, and of course it has the added bonus of being free and online. I also really, really enjoy the fact that it covers handling higher-order logics using lambdas and types. In topics and conversations about the consistency strength/interpretability hierarchy, people often say that higher-order arithmetic is equivalent to type theory, but don’t explain anything beyond that statement. Contrary to those discussions, I think this is a good explanation of what that actually means.

2. Regarding second-order logic: what about selected sections of Shapiro’s “Foundations without Foundationalism? Or maybe selected sections of Button & Walsh?

3. ZFC, on its intended interpretation, makes all kinds of strongly infinitary claims about the existence of sets much bigger than the set of natural numbers.

Does it? Why then the use of large cardinal axioms?

1. I didn’t mean “strongly” as a technical term. Sure, the powerset of the powerset of the powerset … of the powerset of omega is tame (compared with a “large cardinal”), but much bigger than the set of natural numbers. But I’ll drop the “strongly” in case it misleads.

1. I see there is potentially an issue about “strongly”; it was more “all kinds” I was wondering about, though. Is there a nice way — better than “all kinds” or “many” — to characterise the infinitary claims it makes, as opposed to the ones it doesn’t? If not, how about just saying “makes infinitary claims about the existence of sets much bigger than the set of natural numbers”? Or just “makes claims about the existence of sets much bigger than the set of natural numbers”?

1. Oh heavens, I see the point now! The “all kinds of” was unthinkingly casual!

A quirk I’d not consciously registered before. I (most English speakers?) use “all kinds of” just to mean “a good variety of kinds” or something like that (not really all). So I might say “The CUP bookshop only sells books from the University Press, but Waterstones stocks all kinds of books” — where of course I don’t really mean all.

1. I wasn’t trying to make quite that sort of point either. A better Waterstones comparison might be saying “Waterstones stocks all kinds of books” if they didn’t stock fiction.

4. Is point (v) correct? I can’t find any flaw in the argument but there is a sentence that expresses for an arbitrary relation that it yields a successor for every object, it is anti-reflexive, and it is transitive which only has infinite models.

Edit, after a few minutes of thought: I found my answer but it would be great if you could clarify the point in the text. It may cause some confusion.

1. I thought (v) was an elegant, surprising and simple example to use here and it helps with understanding the proof of non-standard models for arithmetic that follows. I hadn’t seen it before, or if I had, I’d forgotten it.

I also had to pause and think about it for a while to understand how it is consistent with the fact that there are first-order sentences which are true only in infinite domains. If I’ve understood this rightly, the limitation is with the ‘if’ part: the proof shows there cannot be a formula which is true in every infinite domain. Hence a fortiori there cannot be one which is true in all and only infinite domains.

So for example, the sentence Navid mentions would be false in a model in which there are infinitely many distinct objects none of which bears the relation to anything (ie the relation is empty). You need the ‘if’ direction in the proof because that’s what implies that the negation of $latex \exists_\infty$ is true only in finite domains, which is what would make the infinite set of sentences unsatisfiable.

I agree with Navid that it might be worth adding a footnote or comment on this, perhaps explaining how you can have a sentence that is true only in infinite domains. On the other hand, I feel like I learned something by having the moment of cognitive dissonance and having to think about it for a while. The worry might be that some students who do not already know that you can write down a formula true only in infinite domains might come away with the impression that this cannot be done. So perhaps a footnote saying something like ‘There are many first order formulas which are true only in infinite domains, for example …. How is this consistent with (v)?’ That way you leave a kind of nice puzzle for the student to think about.

Two typos:
page 28, item (iii) “Structures can similarly expanded or reduced” should be “structures can be similarly expanded or reduced” or “structures can similarly be expanded or reduced”.

p. 31, paragraph after item (viii) ‘iare’ should be ‘are’.

Scroll to Top