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.
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.
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.
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:
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 |.
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.
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.
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.
Readings for 8 Oct:
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:
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:
On 22 Oct, we'll discuss:
See also pp. 274--6 in the reading on Sequent proofs, below.
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.
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.
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.
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:
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:
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).
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.
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 FM where we write IM(F) --- I'm letting IM 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.
Models and Theories
Ordinals and Cardinals
Readings and homeworks for next week:
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.
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.
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.