Phil 455: Announcements, Readings, and Lecture Notes

The front webpage for the course is at

Here are Zoom links for course meetings and office hours.

Here is the Canvas page for course, where you’ll need to submit assignments. But most of the static information there will also be published below.

Prof Pryor’s office hours are on Mondays from 3–4:30 and Wednesdays from 1:30–3. His email is


These are in reverse-order, so the newest posts will always be at the top. The dates are when the post was first made.

Readings are in a restricted part of this site. The username and password for these were emailed to you, and will also be announced at the start of class.

Fri Apr 12

Here is Homework 10. I’ll post solutions to Homework 9 later today.

new Here are the model answers to Homework 9.

Wed Apr 10

On Monday, we’ll continue talking for a bit about the sizes of models, and about the Löwenheim-Skolem Theorems (see also Goldrei section 6.4). Then we’ll shift into talking about theories of “arithmetic,” that is, the intuitive body of mathematical truths about the natural numbers. That will mark the start of the third segment of our course, which will talk about various theories of arithmetic and their interesting properties. Including: when those theories can be decidable and/or complete, when it’s possible to “encode” or “represent” some effective operation inside an arithmetical theory (think back to Problem 84 in Homework 7), and how these phenomena are related.

Our reading for the last segment of the course will be this book by Peter Smith: Gödel without (too many) tears, which is about 140 pages. Smith also has a longer text (about 400 pages) also available online, which goes into more details.

You should start reading Smith’s shorter book at whatever pace works for you over the remaining weeks of class. I won’t try to make our lecture sessions map exactly to specific pages in that text, because that would make our class presentations more complicated, and you guys will probably be reading at different paces and on different days at any rate. Just as the written notes for the past few weeks of our course have been the Goldrei book, the written notes for the next few weeks of our course will be the Smith book.

I expect to post the model answers for Homework 9 by Friday morning. The material you’ll need to do Homework 10, which as I said in class will be short but require good mastery of the concepts we’ve been discussing, we’ve now already covered. So I will post that soon, and it will be due later next week. (Wed or Fri, as always we can be somewhat flexible as your situations merit.) The final Homework 11 will be on the last weeks of class, and will be due before the start of our “final exam session,” on Thursday May 2 at 4 pm. (We don’t have a final exam, but we will have a zoom meeting at that time for review and questions.)

Fri Apr 5

More reading to do. The first chunk of Goldrei reading (in the March 5 entry below) was on syntax and semantic issues, and the notions of logical entailment, logical truth, logical equivalence, structures/models, satisfiability, and so on. The second chunk of reading (in the March 25 entry below) was on proof systems, that we briefly discussed this past week. (What’s more important for our course narrative are the relations between proof systems and logical entailment, rather than the specifics of any particular proof system.)

You should have spent enough time with those readings to be comfortable — with at least the main threads of discussion, even if there are occasional details you’re missing.

Our last chunk of reading from Goldrei talks about the notion of compactness and related issues. These will be our discussion topics for most of this coming week. Be sure that you understand what a Soundness argument for a particular proof system would be saying; and also a Completeness argument. You can look briefly at sections 3.3, 5.3, and 5.5 of Goldrei for presentations of such arguments for the proof systems he’s working with, to see how these work. (But that’s optional, not the assigned reading. These were sections we skipped in the earlier readings.) The assigned reading is:

Thu Apr 4

Here are solutions to Homework 8.

Wed Apr 3

Here is the recording of today’s meeting. Passcode: “=1UK4c!U”.

Here is Homework 9, due next week.

Thu Mar 28

I tweaked the text of Homework 8 somewhat. It doesn’t change the substance or solutions of any of the problems. Just trying to clarify the text to avoid some possible ways you might get confused.

You may also notice some differences in the formatting of logical formulas. (If you don’t, then Force Reload one of the pages from this site. In Chrome, this means going to the View menu, holding down Shift, then selecting the Reload item.) When I have text like this, it’s just part of our mathematically-enriched metalanguage. This includes symbols like and variables for sets like Γ and metavariables for expressions in our object language, like φ and α. When I want to refer to fixed pieces of the object language, I’ll do so using either the same notation for designating strings we’ve been using all along, for example "∀" ⁀ "x" ⁀ "Fx", or I’ll leave off the quotes and format it like this: ∀xFx. If a metavariable is involved, though, it will end up looking like this: ∀xφ.

Here are the solutions for Homework 7.

Wed Mar 27

Here is today’s handout for those of you who missed class.

Mon Mar 25

Here is Homework 8. I may tweak it a bit over the next days.

I’ll try to post some brief summaries of the essentials from our discussion and the long Goldrei reading. You should be sure you’re comfortable with that earlier reading. (The stuff about conjunctive and disjunctive forms in §2.4, and prenex normal form in §4.3, isn’t crucial. Most of §2.5 on adequate sets of connectives is not crucial. He doesn’t get around to defining for predicate logic until pp. 188-89, which is just after the selection I directed you to; but you should have a look at those pages too.)

Our next Goldrei reading is on formal proof systems. He presents one for sentential/propositional logic in Chapter 3; you can read up to p. 107 and skip the rest for now. He presents one for predicate logic in Chapter 5; you can read up to p. 246 and skip the rest for now.

Mon Mar 18

Here are the model answers to Homework 6. I will post Homework 7 tonight.

new Here is Homework 7.

Sun Mar 10

Here is a writeup of material we discussed last week on SRSs and Formal Grammars.

Tue Mar 5

Things I am working on: (a) catching up with grading and giving you individual feedback on homeworks, obviously; (b) sifting through a large pile of YouTube videos about the Halting Problem to identify a few to recommend to you — if you’ve got the time and interest to watch videos about this before I’ve managed to make a recommendation, just search “halting problem undecidable” or “halting problem” on YouTube and browse around; (c) writing up some summary of our last few classes’ discussion of decidability, yessing/enumerating, string rewriting systems, and the general material on grammars. I won’t be writing up a summary of the specific material on grammars/languages for logic that we started doing at the end of last class, and will pick up again with tomorrow.

Things you should be working on — after finishing Homework 6 and catching up on any web notes already published here, or posted in the near future: (a) Start reading from this texbook. We’ll be working with this text a lot over the next weeks. We’ll be skipping some parts, and doing some things in a different order than the author does. I’ll give you specifics in a moment, and as we proceed. (b) Some of you have expressed interest in doing some review of the skills/knowledge developed in your study of introductory logic. We’ll be doing a bit of refresher/review in our own exposition, but it definitely can make sense for you to put time into this on your own, outside of class. We won’t be doing lots of proofs-within-formal-logic(s) in our course, but we will be doing some. And more importantly, it will be valuable for you to get comfortable with, not feel shaky or insecure about, your understanding of proofs-within-formal-logic(s). You are welcome to look at your original textbooks or course materials to review this; or here is one intro textbook that I will recommend. That’s about 400 pages long, but hopefully you’ll be in a position where you can skim most of it quickly, and only pause to look carefully at a few sections. So it shouldn’t be unreasonable to try to read through it in, say, two afternoon sessions of 2-3 hours. I’ll leave it to each of you to figure how much review you’d benefit from (and can fit into other pressures on your schedule). As I said, the most important concepts we need we’ll be talking about explicitly in our class, over the next few weeks. But we will be doing so at a quick pace.

With the Goldrei text, on the other hand, I do want you all to start reading. The first chunk to look at will be: Chapter 1 (this should almost all look familiar to you, and the parts that don’t you can probably skip without issue); all of Chapter 2; and the first three subsections of Chapter 4 (up to p. 185). We’ll talk about Chapter 3 later.

I’ll talk about this more tomorrow, but there are three big pieces when it comes to a logic: (i) the grammar and/or syntax of the language; (ii) the semantics (some other keywords here are models, assignments, interpretations, entailment/consequence, validity, satisfiability); and (iii) proof systems. We are right now talking about heading (i) and I hope tomorrow will begin talking about heading (ii). Heading (iii) won’t be taken up until a few classes after spring break. The first chunk of the Goldrei reading that I described covers headings (i) and (ii). It would be good if you’ve read through that whole chunk by our first meeting after spring break, or soon after that.

Mon Mar 4

Here are the model answers for Homework 5.

Thu Feb 29

updated I found a good Turing Machine simulator online and added a modified version to this site. If you click on “Advanced options” you can specify whether the tape is infinite in two directions.

Here is a Stanford Encyclopedia article on Turing Machines. I’m sure I read it before but don’t have it loaded into memory. Am looking at it now to see how accessible and suitable it is for us, but I’ve seen in recommended a few times.

I’ll try to write up the stuff we did in class this week (that’s not in the readings linked on Sunday). But I’m not sure when I’ll be able to do this. It’s natural to have questions about these issues. They are easy to only partly understand. And I want you to get as comfortable with them as you can in our course. So be sure to keep asking questions. One of you is going to Zoom with me at the office hours link tomorrow Friday at 2 pm. Others are welcome to join that session too. One of you is going to come to my office hours in Caldwell on Monday (at 3 pm). Others are welcome to join us then as well.

Wed Feb 28

Here is Homework 6. Problems 70-74 will be easy, but the ones after 70 require understanding some shorthand that we’ll not get to until the start of Monday’s class. Problems 75 and 76 are the ones that will be conceptually challenging, but they don’t require any new ideas that we haven’t already introduced.

Tue Feb 27

Here is a YouTube playlist I made with a couple of good introductory videos about Turing Machines. (I sifted through a bunch of such videos that were less useful, because of being too technical or less engaging or so on.) I’ll try to add some videos to that playlist about the Halting Problem. (There are many candidates, I should filter the list before recommending any to you.)

Sun Feb 25

I’m going to post a few readings just clarifying and spelling out what we discussed in our previous Zoom lecture. Here’s the first; the others will come later:

new Here are the other readings:

new Here is some of the new material we’ll discuss on Monday. If you have time to read it in advance, you may find that helpful. (If this is your first time learning about this material, expect it to take multiple passes through it to become comfortable with it.) But I won’t expect that everyone will be able to.

Wed Feb 21

Sent out an announcment by Canvas, but noting here also: will also have to do today’s meeting by Zoom.

Here is the recording for Monday’s class. (Passcode: 0ME%4a92).

Here is the recording for Wednesday’s class. (Passcode: +3f$Z.d$).

Mon Feb 19

Here are some Facts about Strings, that may be useful for doing some proofs.

As I announced on Canvas, today’s class will have to be held by Zoom. See the link at the top of this page.

new Here are the model answers for Homework 4.

The link to Homework 5 is in the entry below.

Wed Feb 14

Here is the reading for Monday: Strings Part 2.

And here is Homework 5, due in two weeks. It will make sense after reading the page for Monday.

Tue Feb 13

Here are the model answers for Homework 3.

Mon Feb 12

Here is the assigned reading for Wed: Strings Part 1.

Here is some optional supplementary exposition:

Wed Feb 7

Here is the link to Homework 4.

Remember we don’t meet on Monday, but instead next Wednesday Feb 14.

As I said in class, it will take me a while to put together the reading for our next unit. I’m aiming to have something short for you to read for Wednesday posted by Monday. If I don’t manage to do that, we’ll just talk through the relevant material when we meet.

Mon Feb 5

All the Homework 2s are now in, so here are the model solutions for Homework 2.

I posted a link to Homework 3 already, but there it is again. We’re saying it’s due on Friday, but as before if you need an extension until Sunday, just ask.

On Monday we’re discussing graphs and trees. For Wed of this week read these two webpages:

Here is an optional page with more details about algebras. It’s intended for reference, or to connect up this material with things you may have learned in some math classes. It’s not material we’ll be making use of in this course.

At the start of next week (Mon Feb 12 and Tuesday Feb 13) the university is closed for Wellness Days and there are no classes. We’ll meet again on Wed Feb 14. We may be continuing with the material on algebras, or will be starting to read new material about strings.

Wed Jan 31

So where we stand now is: Homework 2s are due on Friday. Looking ahead, Homework 3s are due a week later. Most of the questions on Homework 3 are ones you should now already be prepared to answer. There’s just one question (Problem 42) that depends on material we haven’t gotten to yet.

Readings for Monday Feb 5: graphs and trees (those are the notes; here is a reinforcement reading from Partee).

new I hope it will be intuitive to you that function composition is associative, that is if f, g, and h are three functions, with the domain of f being Α and its codomain being the domain of g, and the codomain of g being the domain of h, and the codomain of h being Β, then h ∘ (g ∘ f) will be the same function from Α into Β as (h ∘ g) ∘ f is. Both will map an arbitrary a ∈ Α to h(g(f(a))).

You can help yourself to the fact that is associative in any of the homework problems due this week or in later weeks.

Sun Jan 28

Am still grading the homeworks (have put off the tedious grading of proofs until the end), but so far the homeworks look not too bad. None of them are perfect, but none are worse than B+ level either. I’m going to give you some points out of a total of 63, but this result is just a loose benchmark. (You can’t translate that into a percentage and assume that 85% is a B, in the normal way.) It looks to me like all of you should be able to understand what you did wrong by looking at the model answers and then will be ready to move forward. Be sure to ask questions about anything that’s unclear. Some general comments:

On Monday, will give an opportunity to ask any questions about the model answers to Homework 1. Then will give an opportunity to ask any questions about the Homework 2, on cardinality and the material on relations we discussed last week. This will be due this Friday. Then in time that remains, will quickly summarize the notes on orders that I linked to earlier, and discuss questions you have on these. You should read and try to understand those notes before we meet.

Thu Jan 25

Here are model answers to homework 1.

Here are the second homeworks, due at the end of next week. updated I tweaked the homework slightly, and if you want to look ahead, I’ve now also posted the third homeworks.

Tue Jan 23

There’s an Assignment entry now in Canvas where you can submit your Homework 1s.

I did a little research and found that the representation of the rationals I introduced you to yesterday comes from one or the other of these two similar constructions:

The differences between these are subtle, and I haven’t had time yet to figure out which one is the basis of the construction I showed you. If any of you figure it out first, do let me know!

I don’t have my own webnotes written up for the material about cardinality we discussed. But here is some reading to reinforce/clarify that material.

As a reminder, ℵ₀ and ℶ₀ are both names for the smallest infinite cardinality, |ℕ|. ( is the first letter of the Hebrew alphabet and is pronounced “aleph”; is the second letter of the Hebrew alphabet and is pronounced “beth.”) ℵ₁ names a larger cardinality that can be shown to be the next larger cardinality after ℵ₀. ℶ₁ names the larger cardinality |𝟚|, which is the same as |ℝ|. It’s unclear/disputed whether ℵ₁ is equal to ℶ₁, or whether it’s smaller than ℶ₁.

Our next topics will be:

I expect we’ll spend one meeting on each of these topics, starting tomorrow, though we may change gears and go more slowly if feedback I get from you makes that seem better.

Fri Jan 19

Normally I have office hours on Monday afternoons from 3-4:30 (also on Wednesday afternoons at 1:30), but this coming Monday, Jan 22, I won’t be able to hold office hours. I’ll be glad to Zoom with you on Tuesday or meet on Wednesday afternoon instead.

Wed Jan 17

So for the Homework1, we’re saying they’ll be due by end of the day next Wed, Jan 24. Problems 1, 2, and 4 we did in class and you can skip. You should do problem 3, and problem 5 (though if you understood problem 4 it should be easy). You should also do all the subproblems of 6, even though we did item a in class. If you have difficulty with any of this, make sure to let me know and let’s try to talk it through. Either during my office hours (Mon and Wed afternoons, see top of this page), or we could zoom about it another time, or if it’s a quick question, can have an email exchange.

On Monday, I propose to discuss questions about the cardinality of sets. I’ll see if I can find some good textbook expositions of what we’ll be discussing. (There are many candidates, but some of them are pitched at a more advanced and maybe intimidating level than we need. Others are more basic and sloppier than I want. Have to look more thoroughly to see if I can find readings at the sweet spot.) But for the moment, I don’t yet have readings for you to look at here.

Instead, I recommend you spend any time you’ve budgeted for this course on the homework, and on reading the webotes on relations, which will be our next topic after cardinality.

Fri Jan 12

Here are the notes summarizing the main facts about sets and functions that I want us to be familiar with. For many of you, some of this will already be familiar to some degree, and these notes may be enough of a refresher. Others may welcome a fuller, slower exposition of some of this material, so I will also link to some selections from various textbooks.

Here are also some notes about relations that I want us to be familiar with. We won’t talk about relations for a few classes, but I’ll give these notes ahead of time because some of the expository selections from textbooks talk about relations first, and then define functions as relations having special properties.

Don’t get overwhelmed! I’m not expecting everyone to master all of this material immediately. But have a look at the notes on sets and functions (you can skip the exposition readings if the notes make enough sense on their own), and look ahead at the notes on relations if you have time — and see how far you can get.

Here is an initial collection of homework problems: Homework1. Have a look at these and try working out some of the initial ones in your head. We’ll try to do some (most?) of problems 1–8 when we next meet for class, on Wed Jan 17. The homework will be due sometime during the week after that (the third week of classes); we’ll talk about when specifically after our next meeting.

If you are aiming to type up some formal work, and you’re not doing it in LaTeX, here is a list of special logical/math characters you can copy and paste.

From your info sheets I can say already that Dash, Caleb, Sam, Elijah, and Sarah will need to make extra efforts to make any work they turn in to me in handwritten form clear and legible. Robert and Lillyann I don’t know yet. I can easily read the handwriting of Bean, Alex P, Audrey, Kate, and Lindsey.