Course Description

This course aims to equip philosophy graduate students with solid foundations to deal with logic in papers they read and write, and discussions they participate in. We will discuss some difficult metalogical results, but will tend more towards equipping you with a broad understanding of the field than towards refining your proof skills. We will loosely follow Sider's Logic for Philosophy and will cover a smorgasbord of issues in logic, metalogic, math, and formal semantics.

This is designated as a Small Discussion Seminar, which means attendance is limited to NYU Philosophy PhD and MA students, except by permission of the instructor. Email me to discuss the possibility of registering or auditing if you don't fit that description.

Homework, Credit for the Course, Auditing the Course

There will be homework every week, and doing this homework will be how you get credit for the course. There will be no final exam or paper. You should get each week's homework to me by Sunday evening at latest. That way, if you have problems with it, we'll have some opportunity to address them before our next class meeting --- by email if necessary but more comfortably in person. I will be in the department on Mondays, and always around my office from 11--1. When we don't have department meetings, I'll be free even longer, up until teatime.

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.

Feedback welcome

Anyone following this website, either taking the class or auditing it, or even just reading from home, is welcome to give me feedback on the material I post here. The best kind of feedback will be:
On webpage so-and-so, you write that "...". I think I would have understood this more clearly if you had said instead "..."
Based on such-and-such, I think this is a mistake, and what you should have written (meant to write?) is instead "..."
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.


How to format homework and questions you send me

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.

Optional additional reading.

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:

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:

Now, here are more readings for 15 Oct beginning with descriptions: (I will supply the Gamut readings sometime on Thursday.) Other stuff for 15 Oct:

On 22 Oct, we'll discuss:

new 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.

new Also useful, and strongly recommended:

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 updated 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 new 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).

Optional additional reading.

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.

Surely that's enough for next week! :-) Read around through the list and focus on what you find most accessible and helpful.

Readings and homeworks for next week:

Notes for 12 Nov (these are updated from what we looked at in class): Here's the schedule for our remaining meetings.