- This text is required: Sider, Logic for Philosophy. I ordered some copies for the NYU Bookstore, also you can click on the link to find it at Amazon.
- We assume you already know how to do proofs in a formal system, for at least first-order predicate logic with identity. This class will do very little of that; it will be more concerned with proving things in an informal (but mathematically rigorous) way about such systems. (But not only that.)
- A good review of the material we'll suppose you've been exposed to is Paul Teller's Modern Formal Logic Primer. That text is available for free online. Teller uses two proof systems, one called "Natural Deduction" and the other called the "Tree" or "Tableau" system. We'll be using two
*different*proof systems, but one of ours will be fundamentally similar to Natural Deduction. - We also assume some general mathematical knowledge, which we will review (and extend) in the first meetings. One book covering some of this background is Steinhart, More Precisely: The Math You Need To Do Philosophy.
- Some texts covering ground that often parallels Sider (and sometimes goes into things he doesn't) are: Gamut, Logic Language and Meaning vol 1; Partee et al, Mathematical Methods in Linguistics; Boolos et al, Computability and Logic 5th ed. These are listed in order of increasing difficulty --- but they have different virtues, so the later members don't dominate the earlier ones. If you're serious about mastering the technical tools this course introduces, I strongly recommend reading through one or more of these alongside Sider. It's very helpful to see how different authors present the same issues in somewhat different ways.
- As the course progresses, I've often been including reading selections from, or referring to, Bostock, Intermediate Logic.
- For discussion of formal grammars, automata, and computability theory, I've been including reading selections from, or referring to, Sipser, Introduction to the Theory of Computation.
- Peter Smith has an excellent guide to what to read to learn more logic. His Introduction to Goedel's Theorems looks like it might be more approachable and thorough than Boolos, Burgess, and Jeffrey, and so should be worth looking at. (I haven't yet read it.)
- Graham Priest's Introduction to Non-Classical Logic 2nd ed looks like an excellent resource for learning more about modal logic, intuitionistic logic, many-valued logics, and other "heresies".
- Finally, there are many good resources on specific topics at the Stanford Encyclopedia of Philosophy and at Wikipedia. (Wikipedia seems to be pretty reliable and useful for math topics; though not always so reader-friendly.) Another online resource is math.stackexchange.com.

I don't care how much you collaborate on the homeworks, or how much help you get from other people or texts. The point is for you to master --- or at least work up to a comfortable level with --- the material. If that involves reading more broadly than the texts I suggested (presumably on the web), or talking to more people for help, great: I'm sorry that things aren't going easier but I'm delighted by your effort to overcome your imperfect understanding. All I ask is that what you do turn in to me, comes with your promise that you at least believe yourself to now understand what you're submitting.

Those of you who want to audit the course are free to do so, and to attend sporadically if that works best for you. You're also free to just follow along on the website if you're not able to make it to class. I do strongly encourage you also to at least think through the homeworks. Of course you don't need to submit them to me for review, but if you'd like me to review them I'm willing to.

On webpage so-and-so, you write that "...". I think I would have understood this more clearly if you had said instead "..."or:

Based on such-and-such, I think this is a mistake, and what you should have written (meant to write?) is instead "..."or:

In other contexts, I've seen/heard people talk about this differently. Since others might also find themselves in those contexts, it might be less confusing for them if you explain that "..."or so on. You get the idea.

If you can't give me the best kind of feedback, with proposed specific improvements, but want instead to just ask questions or express your bewilderment at some part of the discussion, that may potentially also be helpful.

- Notes on collections, with and without order (pandoc) (pretty)
When I remove the "--- in progress" tag from a link, as I have here, then I believe the web page to be complete. There may be formatting glitches or typos or substantive mistakes; please let me know if you find any. I may continue to tweak the page to fix such things and refine the exposition. Please also let me know if parts of this are too compressed for your comfort, and it would be useful to have things spelled out in more detail or with more examples.

- Some more vocabulary about sets (pandoc) (pretty)
- Partee on sets (Ch 1, pp. 3--26)
- Partee on relations and functions (Ch 2--3, pp. 27--bot 47)
- Partee on strings (Ch 8.5.6, pp. mid 213--bot 215)
- Notes on functions and relations (pandoc) (pretty)
- Some elementary but potentially useful remarks from Heim and Kratzer on sets, relations, and functions --- unfortunately the scans are hard to read

Try to read and get comfortable with as much of the preceding as you can for our meeting on 10 Sept. I trust that some of it will be familiar to all of you, but for most of you, at least some of it will be new. Also start on the exercises included throughout my notes. The Partee readings (and in later weeks, the Sider readings) have exercises in them; but you don't have to work on those exercises unless I copy some of them over into my notes and explicitly designate them as homework. (As I have done, in a few cases.)

For the moment, I'll be relaxed about when the homework is due. Get as far as you can as soon as you can. Soon we will find a rhythm, and the material for you to read and the homework for you to work on will be available for each coming week immediately after our class meetings. Then I will expect you to (try to) complete each week's homework by that Sunday evening. Some of the time you will get stuck; that's okay.

When we meet on 10 Sept, we'll see how far you've all gotten. As I said during the first meeting, I am not going to try to orally present everything. I will assume you've tried to master it already on your own, and we'll be using our group meetings to clarify and explain what isn't as clear as it should be.

Once we're on board about sets, relations, and functions, then we will begin to discuss algebraic structures, which are certain packages of sets and functions. Below are some readings and notes for that. We will discuss these when we meet on 17 Sept.

- Notes on algebraic structures (pandoc) (pretty)
- Relations between algebras (pandoc) (pretty)
- More advanced notes on algebra --- optional (pandoc) (pretty)
- Partee on algebras (Ch 9, pp. 249--55), isomorphisms (Ch 8.5.3, pp. mid 203--mid 205), and groups (Ch 10, pp. 257--76)

- Pinter, Introductory chapter --- provides some mathematical and interesting historical context about modern algebra
- Wolf, Appendix on groups, rings, and fields --- a short exposition of these structures

Hmm, was a lot of math. Now you may go on and never explicitly encounter the terms "codomain" or "monoid" or "ring" again in your philosophical career. However, I do think that getting some familiarity with these elementary notions is extremely useful for the more familiar semantic and logical issues we're going to focus on in most of the course. It also helps give you context, so that you can be better placed to see the formal tools that philosophers make most use of in their broader mathematical homes.

And we're not finished: there's some more math (about relations and orders) it will be good to get acquainted with too. But I'll hold off on that for a bit.

There are 42 exercises by the end of the previous chunk of readings. If you're just getting started on the homework, that's a lot of problems to do by Sunday 15 Sept --- even though, I hope, once you get the hang of it only a few of the problems will require much head-scratching. Anyway, I'm aware of this and am not yet tightening up expectations for when things are due. That said, do *try* to get as far as you can by 15 Sept, so that you'll be able to get caught up with the rhythm of a new set of readings and homework for each week, to be discussed in the next week's meeting.

As announced in class on Sept 15, I expect you to turn in the exercises up to #42 by Sunday 22 Sept. You should also try to turn in the exercises for the next batch of readings (to be discussed on 24 Sept) by the same date, but at latest by Sunday 29 Sept.

Feel free to email if you're ever unclear on what a problem is asking, or get stuck and aren't clear on how to proceed. Also feel free to consult with each other.

Generally, there will be fewer exercises each week, but the individual exercises will become more challenging.

Our topics for 24 Sept will be as follows:

- Read Sider, pp. 5--6
- Bostock, Introduction and remarks on notation, pp 3-top 24
- More about strings (pandoc) (pretty)
- In the preceding notes, I discussed a difference between how Sider and Bostock on the one hand and I on the other hand understand sentence constants in our formalisms. I came across an interesting discussion by Peter Smith, where we learn that (i) Goldfarb, Quine, and Mendelson had something like Sider and Bostock's view, but
*most*logic authors over the past 50 years have had one of two other views, which Smith associates with (ii) Shoenfield and (iii) Kleene and Enderton. I was recommending view (ii). (Though Smith doesn't mention him here, Hodges in the longish summary of sentential and predicate logic that I link to below takes the same line as the group (i)-ers. Hodges discusses this in his section 12.) - Formal grammars and languages (pandoc) (pretty)
- [See the notes and Partee reading on trees, listed further down this page.]
- Automata (pandoc) (pretty)
- Gamut on formal languages and automata
- Epp on formal languages and automata --- don't worry about understanding the
*proof*of Kleene's Theorem on pp. 801--803, but you should try to understand what the theorem*says* - Read Sider, pp. 25--28, 90--91, 133--137 (these are sections 2.1, 4.1, 6.1--6.2)

**Optional additional reading.**
If you feel that you have a good grasp on the material presented in my notes, and can follow the main threads of the Epp and Gamut selections, then you should have enough to get by with for the rest of this course. If however, you'd like to read a more unpacked, thorough, yet still accessible presentation, then I recommend reading some of the following material, especially some parts of the (long) Chapter 1. Also, if you'd like to dig deeper and understand more, in that case too I recommend reading some of the following material. This will be especially helpful if you'd also like to work through Boolos et al.

These chapters are taken from Sipser, Introduction to the Theory of Computation. You can read them at your own pace. We are not going to discuss material from Ch 1--2 except insofar as it's addressed in the notes or readings above. Issues discussed in the other chapters are introduced a bit in this week's notes, but we will be coming back to them later.

A few divergences between Sipser's terminology and ours are worth noting: generally, his ℕs start with 1 not 0 (but in one chapter, he temporarily switches to the other usage); he uses the symbol ⚪ for string concatenation; and he uses the symbol ∪ in regexes where I've used the symbol |.

- Chapter 1, Regular Languages
- Chapter 2, Context-Free Languages (only part of the chapter is provided)
- Chapter 3, The Church-Turing Thesis
- Chapter 4, Decidability
- Chapter 6.1, How a Turing machine can describe itself
- Chapter 6.2, Decidability of Logical Theories

Here are also some chapters from Partee covering some of the same ground. The first two correspond roughly to the first two chapters of the Sipser book. The Partee discussion is quicker (which has both pluses and minuses) and sometimes the difference between things being explained by linguists (Partee and co-authors) rather than by a computer scientist (Sipser) shows through.

The last chapter corresponds roughly to the rest of the Sipser material; all of this is stuff we will be returning to and focusing on later.

- Chapter 17, Finite automata and regular grammars/languages
- Chapter 18, Pushdown automata and context-free grammars/languages
- Chapter 19, Turing machines and recursively enumerable languages

These items belong conceptually with the preceding batch of topics, but you should read or review them for the 1 Oct meeting --- as well as the other materials posted below.

- A fuller explanation of conventions for mentioning expressions (Sider's S1 and S2 example that we discussed in seminar on 24 Sept; on 2 Oct, updated comments comparing my explanation to Sider's in Appendix A of his book)
- Some other comments and unfinished business from the 24 Sept meeting, including one of the new homework exercises due Sunday 29 Sept
- Graphs and trees (pandoc) (pretty)
- Partee on strings, grammars and trees

We will only discuss material from the above list that you have questions about. Our main topics for discussion on 1 Oct will be the following readings. All homework exercises below are due the first Sunday after they are posted. (So this batch will be due by Sunday 29 Sept.) But if you get stuck, don't get too stressed about it. For the moment, I just want you to try to complete them.

- Notes on syntax (pandoc) (pretty)
- Semantics for the language of sentential logic --- re-read Sider, pp. 25--28 (section 2.1); read pp. mid 29--bot 33 (beginning of section 2.3)
- Semantics for the language of predicate logic --- re-read Sider, pp. 90--91 (section 4.1); read pp. 91--mid 95 (beginning of section 4.2)
- Identity and functors --- read Sider, pp. 107--113 (sections 5.1 and 5.2)
- Selections from Bostock's Ch 2--3, pp. 24--top 30, 70--top 89, bot 90--96
- Notes on logic and semantics (pandoc) (pretty)
- Homework exercises due Sunday 29 Sept (pandoc) (pretty) --- clarificatory notes added Friday afternoon and Sunday morning

Readings for 8 Oct:

- Logical truth and logical consequence --- read Sider, pp. 1--11, 28--29, 33--37, 95--98 (Ch 1 until end of section 1.6, section 2.2, end of sections 2.3 and 4.2, section 4.3)
- Selections from Gamut Ch 2--3:
- Syntax for sentential and predicate logic (pp. 35--40, 70--83)
- Semantics for sentential and predicate logic (pp. 44--54, mid 87--top 103)
- Identity and functors (pp. 103--109, 112--113)
- Logical properties of arguments (pp. 114--top 122)

All of the preceding should mainly be review and solidifying your understanding of what we discussed on 1 October. The terminology and some theoretical choices of these authors vary, but I hope you'll be able to track the unifying ideas. Learning how to do that is part of the skillset I'm aiming for you to acquire from this course.

The next bits (also assigned for 8 Oct) extend what we've done previously:

- Readings from Bostock on substitution (pp. 32--top 33, bot 35--36, mid 100--107)
- Readings from Gamut on substitution principles (pp. 122--top 128)
- More notes on logic and semantics (pandoc) (pretty) --- sorry, I emailed you about this page on Oct 8 but forgot to make the link here "live"
- Homework exercises due Sunday 6 Oct (pandoc) (pretty) --- whoops! caught a typo that made problem 63 even easier than it should be, fixed on Monday 7 Oct
- Semantics for the language of
*modal*sentential logic --- re-read Sider, pp. 133--137 (sections 6.1--6.2); read pp. 137--mid 140 (beginning of section 6.3), skim pp. 140--top 143 (to end of section 6.3.1)In the last readings, don't worry at this point about the "requirements" placed on the accessibility relation (that is, whether we have system K or S5 or what); we'll discuss that later.

As we discussed in class on 8 Oct, we will meet on 15 Oct despite the university's being closed. Also, we will delay the discussion of proof theories for a bit, and instead discuss some more complex issues while remaining at the semantic level. Our next set of topics is very broad, so we'll content ourselves with just a brief survey. We can think of these topics as naturally beginning with the notion of a definite description, and angling off in several directions from that starting point.

Before the readings on descriptions and subsequent matters, though, here are some selections from Bostock on issues you've already considered:

- Readings from Bostock on induction on formula complexity (pp. 48--55)
- Teller Vol 2, Ch 11 on induction
- Enderton goes into more detail about inductive and recursive defintions (Enderton proves a "recursion theorem" which is different from the theorem Sipser applies the same name to in his Ch 6.1)
- Partee on recursive definitions (pp. bot 181--mid 185)
- Readings from Bostock on identity (pp. 323--mid 324, bot 327--top 329, mid 332)
- Readings from Bostock on functors (pp. mid 333--bot 336, top 338--mid 341)

- Read Sider on descriptions, pp. bot 113--bot 119 (section 5.3), including his discussion of how to eliminate functors and descriptions
- Bostock on descriptions (pp. bot 341--bot 348)
- Gamut on descriptions (pp. mid 158--164)
- Gamut on multisorted logics and restricted quantification (pp. 165--mid 168)
- Read Sider on further quantifiers, pp. bot 119--mid 123 (section 5.4, excluding 5.4.3 on second-order logic)
- Read Sider on multivalued logic, pp. mid 73--top 79 (section 3.4 up to and including 3.4.2)
- Gamut on multivalued logics and presuppositions (pp. mid 173--bot 185, bot 188--mid 190)
- Read Sider on free logic, pp. top 129--mid 132 (section 5.6, excluding 5.6.2 on proof theory)
- Bostock on free logic (pp. bot 348--365, 375--377)

- Homework exercises (pandoc) (pretty) --- I won't be able to read these until Tuesday, so you can turn them in when we meet instead of on Sunday
- Here are scans of some exemplary solutions for some of the recent homeworks, including some solutions that are less-than-ideal, with some comments from me about why. I trust this won't make any of you uncomfortable. You all seem to me to be doing rather well so far, with just some ragged edges here and there that should be expected as a natural part of learning. I hope that posting annotated solutions to some homeworks will help improve the ragged parts. In any case, I don't explicitly indicate who the authors of the different solutions I choose are.
- Notes on quantifiers, descriptions, multivalued and free logic (discussed in class, will post soon)

On 22 Oct, we'll discuss:

- Derivations in sentential logic --- read Sider, pp. 37--50 (sections 2.5--2.6), and pp. 56--62 (section 2.8)
- Derivations in predicate logic --- read Sider, pp. 99--104 (section 4.4)
- Soundness of proof systems --- read Sider, pp. 50--55 (section 2.7), and skim pp. 104--106 (section 4.5)
- Bostock on "structural rules" (assumption, thinning, cut) --- pp. top 30--top 32, bot 96--mid 97
See also pp. 274--6 in the reading on Sequent proofs, below.

- Bostock on Axiomatic proofs --- pp. 190--216, bot 220--mid 236, 237--238
This reading supplements and extends the Sider reading on axiomatic proofs in sentential and predicate logic. It also goes into more detail about the deduction thorem, which it's important for you to acquire a good understanding of. It's

*not*important for you to keep track of all the details Bostock reports about which axioms are independent from which others, and what different packages of basic axioms we might choose. - Bostock introduction to Natural Deduction and Sequent proofs --- pp. 239--top 242, 273--top 283
This reading has a few pages from the start of Bostock's chapter on "Natural Deduction" proof systems, which many of you learned in previous logic classes. I haven't included here any exposition of the specifics of those systems, just Bostock's comments about how these systems relate to axiomatic systems; and then in a later chapter, his discussion of how they relate to "Sequent" proof systems, like the one Sider presents in his section 2.5.

- Notes on proof systems (pandoc) (pretty)
- Homework for 20 Oct (pandoc) (pretty)
- Optional reading: Bostock on Sequent proofs with multiple formulas on the rhs --- pp. top 291--top 299
- Optional reading: Partee comparing axiom systems and grammars (pp. bot 185--mid 188)

To solidify your understanding of derivations, you could review Teller's elementary exposition of Natural Deductions for sentential and predicate logic. Natural Deduction systems are only superficially different from the single-conclusion Sequent system that Sider uses.

- Teller Vol 1, Ch 5, Ch 6, Ch 7 on sentential proofs
- Teller Vol 2, Ch 5, Ch 6 on predicate proofs
- Teller Vol 2, Ch 9 on identity, functors, and descriptions (ignore the discussion of tree proofs, on pp. 144--top 145, mid 151--mid 152)
Some details: Teller uses what I call [disjunctive syllogism] as the ∨-elimination rule, whereas Sider uses what I call [dilemma]. Teller uses boldface capital letters for schematic formulas, where Sider and I use lowercase Greek letters. Teller calls models "interpretations," and for most of his books, he adopts the simplifying assumption that every object in his models' domain is designated by some term constant. (I don't think these last points come up in the readings presented above, but I thought I'd mention them just in case.)

Also useful, and strongly recommended:

- Teller Vol 2, Ch 10 on schemas, use vs mention, syntax vs semantics, soundness, completeness, and consistency. Teller uses
**Mod(I,**to mean that every sentence (closed formula) in set*Z*)(he italicizes his set variables, though it's hard to notice) is true on model*Z***I**. - Partee on informal proofs (Ch 7.6--7.7, pp. bot 170--bot 175)
- Hodges' summary of sentential and predicate logic --- 129 pages long and detailed, much of it at about the same level of difficulty we've been working. So far we've covered the material that Hodges discusses through the end of his section 15, and sections 18 and 21 (to the bottom of p. 55, then pp. bot 63--top 67, mid 73--bot 77).
Some details: The proof system for sentential logic he discusses on pp. mid 19--mid 22 is the Tree/Tableau system, which some of you have seen before but we're not studying in this class. On pp. mid 22--mid 23 he discusses Sequent proofs with multiple formulas on the rhs; we've mentioned these but aren't studying them here either. He calls models "structures," and at the top of p. 38, he uses M ⊨ φ[g] as notation for what we're writing as ⟦φ⟧

_{M g}= true; this is a common variant. (See also his pp. 12--14 for further clarification about the double turnstile.) Hodges adopts the Sider/Bostock/Quinean conception of sentence constants as schematic (see his section 12 and p. 52, and the discussion by Peter Smith that I added to the Sept 24 links, above). Hodges calls signatures "similarity types" (see his section 13). On p. 54, he calls formulas which are either atomic or negations of atomic "basic"; another common name for these is "literals." (Yet another term is to call the set of these the "diagram" of the language.)

I've accumulated a lot of tiny fixes and tweaks to earlier web pages, so you should expect previous notes I've posted to often have small updates. You don't *have* to go back and re-read things, if you just want the big picture. But it may sometimes help to review the material, so I will push the updates I think are useful. In these cases, I generally won't put any tag on this index page, but each page's timestamp should reflect the last time it was updated. (There's no way for you to see exactly what was changed, unfortunately.)

You could profitably spend time reviewing material we've already covered in the course. I have been (and will continue to) post some additional readings into earlier weeks' reading lists. I'll mark these with a tag. It's OK if you don't manage to read all of these, but I'm posting them because I think they'll be helpful, so I encourage you to try to look at them when you have a chance.

There isn't any homework for this week. Spend your time reviewing old material, especially by reading some of the Teller (easier) and/or Hodges (harder) linked above. On 29 Oct, we will discuss soundness and (especially) completeness of proof systems, and Compactness. The target readings are:

- Re-read Sider, pp. bot 53--55 (section 2.7) on the soundness of his axiomatic system for sentential logic
- Read Teller Vol 2, Ch 13, pp. 191--top 199 (that is, only sections 13-1 and 13-2) on the soundness of a Natural Deduction system for sentential logic. Such systems are fundamentally similar to Sider's Sequent system.
- Read Sider pp. 62--66 (section 2.9); this gives a "Henkin-style" proof of the completeness of his axiomatic system for sentential logic. Henkin-style proofs can also be given for predicate logic proof systems, along similar lines, but are a bit more complex.
- Partee discusses the general strategy of Henkin-style completeness proofs (Ch 8.6.4, pp. mid 227--top 229)
- Hodges (linked just above) discusses completeness in his section 16, and surveys some Henkin-style proofs for Natural Deduction systems for predicate logic (pp. 56--mid 61). Section 17 (pp. mid 61--bot 63) discusses some consequences/corollaries of these proofs, including Compactness and the Loewenheim-Skolem theorem(s). I expect that some of the details of section 17 will elude you for the time being, but you might try to give this an initial read now.
- Re-read Sider's two paragraphs on p. 105 (in section 4.5) on Compactness

For our meeting, be sure you've at least (re-)read the Sider and Teller on soundness, and read Sider and Partee on completeness, and try to get through and understand Hodges Section 16. (Best if you read all of Hodges from Section 1--16.)

**Note:** "completeness" gets used in a variety of ways in logic and math. Among the variety of uses, two to attend to are (i) when we ask whether a proof system is complete; and (ii) when a set of sentences contains (or proves) every formula or its negation. This week's focus is completeness in sense (i), sometimes called "semantic completeness." Confusingly, completeness in sense (ii) is often *appealed to* in proofs of semantic completeness (sense i). Notion (ii) is sometimes called "negation completeness" or "deductive completeness"; it's what Sider is getting at with his notion of "maximal consistency."
Goedel famously gave some of the first proofs for the semantic completeness of predicate logic (sense i); and then even more famously proved some "incompleteness" results about arithmetic. The latter results differ not only in concerning arithmetic (rather than *all* theories expressible in predicate logic) but also in concerning "completeness" in sense (ii).

- Bostock gives one completeness proof for his axiomatic system for sentential logic (Ch 5.5, pp. 217--mid 220). This is a "Kalmár-style" proof, suited only for sentential systems.
- You could read the rest of Teller's Vol 2, Ch 13 (from p. 199), which develops a Tree/Tableau-
*like*proof of completeness for his Natural Deduction system. Teller recommends reading section 12-1 as background, but there's nothing there that won't already be obvious to you when reading Ch 13. Note that Teller says "(semantically) inconsistent" where we say "unsatisfiable," and says "syntactically inconsistent" where some other authors just say "inconsistent." (I've resolved to say*inconsistent*_{⊢}for the latter notion, and avoid saying bare "inconsistent" as much as possible.) Of all the optional reading, I recommend this most hesitantly, because we've so far been avoiding thinking about Tree/Tableau proofs.If you do read it, then continue with Ch 14 on Compactness for sentential proof systems, and Ch 15 for soundness and completeness for Natural Deduction system for predicate logic. (Skip section 15-2, pp. 230--mid 234 on trees/tableaux.) At the end, Teller extends his results to proof systems including

**=**.As I mentioned above, Teller in the early part of his books adopts the simplifying assumption that every object in the domain is named. In Ch 15, he lifts that restriction, but goes with the substitutional semantics we saw Bostock using, rather than the assignment-based semantics that Sider and most other contemporary authors use.

- Boolos, Burgess, and Jeffrey, selections from Ch 12--13 (pp. top 139--bot 142, bot 146--mid 148, 153--mid 162) discusses Compactness and the Loewenheim-Skolem theorem(s), and gives a direct proof for them, which doesn't depend on what proof system one may be using.
As Burgess explains (in a passage I omitted from this selection), soundness for any finite proof system implies that if some finite subset of a set of sentences Γ can prove a contradiction, then Γ is unsatisfiable (has no model). Completeness implies the converse: that if Γ is unsatisfiable, then from some finite subset one can prove a contradiction. Taken together, we get the result that Γ is unsatisfiable iff from some finite subset one can prove a contradiction, which means that Γ is satisfiable iff from every finite subset one can't prove a contradiction; and satisfiable subsets must be ones that can't prove a contradiction. This gives us Compactness: if every finite subset of Γ is satisfiable, Γ is also satisfiable. (The "only if" direction also holds, trivially.) So from soundness and completeness for any finite proof system we can derive Compactness as a corollary. As I said, though, the above Burgess selection instead argues for Compactness directly.

Some notational details: Similar to Hodges, Burgess uses M ⊨ φ[d] as notation for what we're writing as ⟦φ⟧

_{M g}= true. (But Burgess puts in his square brackets [ ] not an assignment function but rather the object d from the domain that is being assigned to the first free variable in φ.) Also, Burgess writes*F*^{M}where we write I_{M}(*F*) --- I'm letting I_{M}be the atomic interpretation function for model M.

Readings for November 5. (No homework.)

I'm going to post a large collection of pieces. Some parts of these may be beyond you; just try to get out of them what you can.
I also highly recommend reading all the pieces on the "Also useful, and strongly recommended" list before last week's readings. (Teller Ch 10, Partee, a bunch of Hodges sections --- include section 16, posted in the main reading list for last week.)
I recommend *not* trying to read the optional readings below right at the beginning, but try to get more of the big picture by reading through all the non-optional ones. I do realize there's too much here for you all to thoroughly digest.

- Here's a scan of the Gamut section on soundness and completeness that I distributed a photocopy of in class last week(pp. bot 148--155)
- Partee on consistency, completeness, and independence (pp. 202--mid 203)
**Models and Theories**- Partee on theories and models Section 8.5.1, pp. mid 200--201; short, but not sure if this will be helpful
- Enderton on relations between models and algebraic structures pp. 90--104
- Wolf on theories (pp. bot 28--38)
- Optional, more advanced: Chapter from Wolf on model theory --- this is long and some parts will certainly be beyond you, but you will also find some discussion of a few topics I introduced quickly in class. Ch. 5, pp. 165--223
**Orders**- Wolf on relations and orderings Appendix B, pp. 349--354
- Partee on orderings (pp. bot 47--53)
- Partee on orderings, part 2 (pp. bot 207--mid 213)
- Optional: more advanced Partee discussion of orders, lattices, boolean algebras from Ch 11, pp. 277--mid 303
**Ordinals and Cardinals**- Cardinality --- read Sider, bottom p. 16--24 (end of section 1.8)
- Partee on infinities Ch 4, pp. 55--73
- Enderton on cardinals pp. 8--10
Lots of optional reading to pursue this further if you like.
- Partee on ZFC (pp. bot 217--bot 219)
- Hodges section 23 on set theory, pp. bot 79--top 83 (whole Hodges article was linked before)
- Hodges appendix C on set theory, pp. mid 113--mid 119 (whole Hodges article was linked before)
- Wolf chapter on set theory, ordinals, and cardinals Ch. 2, pp. 59--94; Appendix C, pp. 355--359
- Wikipedia on Ordinal arithmetic

**Arithmetic**- Notes on Peano arithmetic and non-standard models (pandoc) (pretty)
- Partee on Peano arithmetic (pp. top 194--top 200)
- Partee on more about Peano arithmetic (pp. bot 215--bot 217)
- Partee on sets-as-numbers.pdf (pp. 75--83)
- Hodges section 20 on intended models (pp. 70--top 73)
- Hodges appendix B on arithmetic, pp. 108--mid 113

Readings and homeworks for next week:

Notes for 12 Nov (these are updated from what we looked at in class):- Up to Goedel's First Incompleteness Theorem, and Beyond (pandoc) (pretty)
- Additional reading for those who want to explore further: Peter Smith's Goedel without (too many) tears. This is an 88-page informal summary of the core parts of his longer book, Introduction to Goedel's Theorems.
- Further reading on Goedel (may reinforce or help you better understand Smith): most of the first 2/3 of Boolos Burgess and Jeffrey's book; also Smorynski and Enderton

- For 19 Nov: Sider Chapter 6 on Modal Sentential Logic
Homework: Sider gives 20 exercises in Chapter 6. Try to do half of them, you can choose which ones. It's ok to give me these on Tuesday instead of Sunday, and remember it's ok to give me handwritten assignments if you find that substantially easier. If you're not able to do half the problems, then get as close to that as you can.

- For 26 Nov: Sider Chapter 7 on Uses/Extensions of Modal Sentential Logic (you can skip section 7.4 on semantics for intuitionistic logic); and Chapter 9 on Quantified Modal Logic (in honor of Ben, you can skip section 9.7).
Homework: From Chapter 7, do Exercises 7.1, 7.2, and 7.4. Sider gives answers to the first two, but as always when you submit any homework solutions you are promising that you at least believe yourself to understand what you're submitting. From Chapter 9, do Exercises 9.1b, 9.1d, 9.2, 9.4, and 9.5.

- For 3 Dec: Sider Chapter 8 on Counterfactuals
Homework: Due all of the exercises from Chapter 8. Due in class on Tuesday 3 December.

**Note:**For question 8.3c, there is a material conditional on the right-hand side of the double turnstile (in my printed copy), but this should be a counterfactual instead.Here is my solution to Sider's problem 8.6.