Here is the final homework. As I emailed, sorry for not being able to get these posted sooner.
I tweaked the notes for the last week of classes (fixed some formatting and made a few small clarifications). It may be helpful to review those notes again while doing the final homework. When doing so, probably best to get the updated version.
Here are notes for Monday’s and today’s classes.
Here is the link to the department’s seminar evaluation form, which will be available until the end of the day.
Recording of today’s meeting.
Recording of today’s meeting.
Recording of last Wednesday’s meeting.
Let me know if you need access to more recordings. I will post here soon some notes covering both today’s meeting and our meeting for this coming Wednesday (the last class).
Here are solutions to Homework 9.
In a few days I’ll post the final homework assignment, which is due on Thu May 5 at 8 am.
I tweaked the notes for Monday a bit (fixed formatting, added a few clarifications).
Here are scans for today’s meeting.
Here are notes for today’s meeting.
As I just emailed the class, am feeling somewhat sick and will teach tomorrow’s class remotely.
Aiming also to post some readings here later today.
Here’s one batch of readings: over the remaining classes, read chapters 1-3 and 7 of Franzén, Gödel’s Theorem: an Incomplete Guide to its Use and Abuse. (I found it worked best to pause on p. 27 or 28, go read chapter 7 then, and then go back and resume with the rest of chapter 2.) This does have a few quirks. One is that it applies the label “Robinson arithmetic” to a formal system that’s different from what most would call by that name. (It’s the system I’ll call Shoenfield arithmetic.) But these have similar properties for the overall story, so that doesn’t matter much. A second is that it often talks about Diophantine equations and how a result established in 1970 by Matiyasevich enables us to get to results like Gödel’s via a different route. That’s interesting but not something I want us to explore. Still this book is very sensible and readable and widely recommended. It should give you a good overview of the results without getting bogged down in details.
If/when you’re interested in seeing more detail about Gödel’s famous Incompleteness Theorems (Gödel had two theorems, despite the title of Franzén’s book), a good next read is Peter Smith’s 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. 
A slower-paced introduction to these issues (and a review of many other issues we covered over the semester) is Epstein and Carnielli’s Computability (3e, 2008).
Here are solutions to Homework 8.
Here is Homework 9, which will be due by the end of next week.
Some asked for a recording of yesterday’s session. Here it is. At the very end of the session, I mentioned Compactness and wrote something on the board. Zach asked whether what I wrote was a correct formulation of Compactness and indeed it was not. We’ll discuss and clear it up on Wednesday. (There are multiple, equivalent, ways to state Compactness and in my rush I was wrongly combining pieces from the different formulations. Sorry!)
Homework 8 is posted. Try to get it in by early next week. I will post the solutions Wednesday evening Friday evening (April 8). Let me know if you need more time than that.
Reading: after sifting through a lot of texts and reviews, I’ve identified this book as having excellent and accessible coverage of the material we’re talking about in the middle “third” or so of the course:
The proof system Goldrei uses (given on pp. 87 and 221) is an axiomatic system, with the rules Modus Ponens and another rule for Universal Generalization. (As I said in class, it’s also possible to handle quantifiers entirely with axioms, but then that makes some metatheoretical results more challenging.) He also explicitly builds in a rule stating that proofs are monotonic, that is, that if Γ ⊢ φ then Γ, Δ ⊢ φ. He states this rule explicitly because otherwise there would be complications with his rule for Universal Generalization; see discussion on p. 223.
He mostly uses the same notation we’ve been using, with these exceptions: He uses ∖ for set difference, and uses → and ↔︎ where I use ⊃ and ⊂⊃. He uses ≡ to mean “is semantically/logically equivalent” (what I write as ⫤⊨). Where I say “model ℳ,” he says “structure 𝓐.” He uses 𝓐 ⊨x̅/a̅ φ to mean what I’d write as ⟦φ⟧ℳq = true, where q is an assignment that maps each of the variables in sequence x̅ to the corresponding object in sequence a̅ (see his p. 153). For term constants a, functors f, and predicate constants R, Goldrei writes a𝓐, f𝓐, and R𝓐 where I’d write ⟦a⟧ℳ, ⟦f⟧ℳ, and ⟦R⟧ℳ.
As I mentioned in a recent class, some authors restrict ⊨ to only holding between sentences (closed formulas). Others permit it to hold between open formula too. Goldrei does the latter. The way he understands Γ ⊨ φ, then, is that for every model ℳ and assignment q of free variables in Γ or φ to objects in ℳ’s domain, if every member of Γ is true on ℳ and q, then so too is φ (see his pp. 163, 188).
At this point, you should be equipped to skim most of the text up to p. 242. That’s a lot of pages, sure, but the material it covers should all be somewhat familiar to you, from your logic preparation before this course (even if you used a different proof system) and from what we’ve discussed in the past weeks. I’m not expecting that you’ll track everything he says; but it’d be good for you to skim through the text and see what is discussed where, what looks familiar, and what might look new to you. Then you’ll be equipped to use those parts of the book as reference. (Goldrei uses many examples from mathematics; when they’re talking about notions you’re not comfortable with, just skip them.)
Here’s some more specific guidance:
- Chapters 1–2: should all be accessible. Section 2.5 less important.
- Sections 3.1–3.2: you should be able to follow much of this. The part of section 3.2 discussing the “deduction theorem” (pp. 93ff) we’ll talk about next week.
- Section 3.3 on soundness and completeness for sentential logic: we’ll talk about next week.
- Section 3.4: less important
- Chapter 4: should be accessible. Section 4.4 are examples of “theories” (with additional non-logical axioms). Many of these concern structures we discussed in the first part of the course. Section 4.5 covers material we discussed to some extent when talking about algebras and morphisms.
- Sections 5.1–5.2: you should be able to follow at least the basic shape of this.
In our next 2-3 classes, we’ll be discussing the material Goldrei covers in sections 3.3 and 5.5 and chapter 6.
If you want background/side reading on other proof systems, that you may be more familiar with (or want to learn), here are some excellent options:
- Chiswell and Hodges, uses Gentzen-style natural deduction
- Peter Smith, uses Fitch-style natural deduction (an earlier edition used trees instead, and he’s posted selections from the earlier edition introducing tree-based proof systems)
- Paul Teller, uses both Fitch-style natural deduction and trees
- Nick Smith, primarily uses trees, but also has some brief surveys of other proof systems including natural deduction
All of these texts give soundness and completeness proofs for their systems. Next week we’ll be talking about completeness proofs, and I’ll try to give you an overview/reading list of more specific parts of these (or other) texts then.
As I emailed the class, tomorrow’s meeting will be remote.
Some asked for recordings of today’s Zoom session. Here is the recording. As with the other class videos I posted, you’ll need to be logged into Zoom (in your browser) to watch it. Click on “SSO” when Zoom prompts you for a password, then say you’re using unc.zoom.us, then enter your Onyen and password when you see the UNC Onyen login screen. Then you should have access.
At one point today we briefly discussed three-valued logics. I mentioned three strategies for understanding how the sentential operators worked in such systems. One view says that the new truth-value is “contagious” and any complex sentence with a component having that new truth-value also has the new truth-value. If you want to read more about this strategy, it’s also known as the “weak Kleene” or “Fregean” or “Bochvar” logic. Another strategy says that, for example, the conjunction of a false sentence and any other sentence is false, even if the second sentence has the new truth-value. This is known as the “strong Kleene” logic. I also mentioned a third logic associated with the Polish logician Łukasiewicz, which is like the second logic except that with conditionals whose antecedents and consequents both have the new truth-value, the second logic makes the conditional also have the new truth-value, whereas the Łukasiewicz logic makes the conditional true. Here are two wikipedia pages to read more. I said that on one of these systems, P will be derivable from P, but that P ⊃ P is not valid, in fact no formulas are valid. That is correct; however I misremembered and said that it was the Łukasiewicz logic that had this property. In fact it’s the second (“strong Kleene”) logic.
Here are model solutions for Homework 5, Homework 6, and Homework 7.
Here are reading notes (from the older course site) on proof systems.
Here is this week’s homework, which will be due Friday evening. Some of the questions rely on you already being comfortable with translating between English and logical notation; if you’re rusty on this hopefully some of the readings, or discussions we have in or outside of class this week can help. Other questions rely on knowing what the “semantic rules” are for how different logical operators get interpreted. These are presented in various readings, and in my web page the semantics of logical systems.
As I emailed the class, I’ll have to cancel our Monday meeting due to sickness.
We’re moving into Part II of the course, where we discuss the syntax, semantics, and proof systems for logics. Mostly logics you’re familiar with from previous coursework, though as time permits we may briefly survey some extensions or variations of those. One of the important connections between this Part of the course and what we’ve done in previous weeks will be limitations on what can be effectively decided or computed about logical truth/consequence.
What I want us to do first is (a) to get clear on the separation of issues into syntactic matters (what does a grammatical, well-formed expression in a logical system look like?), semantic matters (when is a sentence in a logical system true? when do some sentences in a logical system entail or have as a consequence another sentence? when are different sentences logically equivalent?), and issues to do with different proof systems (what does a proof of some conclusion sentence from some premise sentences look like?). The proof system issues we’ll mostly postpone until next week. Then we’ll very briefly discuss different styles of proof system for a given logical system, and these questions:
- What is the relation between proofs and the notion of entailing/consequence mentioned under the “semantic” heading?
- What is the relation between proofs and the possibility of effectively deciding if a sentence is logically valid?
For this week, though, our focus will be on syntax and semantics. Here we’ll want to (b) get comfortable with these concepts:
- terms, formulas
- atomic formulas, subformulas, main operators
- “normal form” sentences
- bound vs free occurrences of variables
- open/closed terms and formulas (closed formulas also being called “sentences”)
- properly substituting a term for free occurrences of a variable
- learning what logicians mean by talking about models or interpretations of a language
- recalling the notions of sound and valid arguments that you learned in earlier philosophy courses; learning the different, logician’s notion of a valid sentence
- learning the logician’s notion of a satisfiable sentence
- learning the notions of semantic or logical consequence, and logical equivalence
My third aim for this week is (c) to sort out different vocabulary and symbolic notation that different authors use to talk about these phenomena. There is a bit of variation in vocabulary, though thankfully only a bit. But there is a good deal of variation in notation.
I’ll give a number of readings on this material. As I said in the email, I will also pre-record one presentation for you to view at your convenience, but probably won’t be able to do this until later in the week. I expect that we’ll also be able to meet in person on Wednesday.
This reading list includes all I posted on Tue Feb 22, and adds some more.
Some of the readings are brief, easy-going surveys of this week’s material. Start with them:
- Papineau Chapter 10 — note when he talks about “syntactic consequence,” that’s what I’m calling proof (and we’ll talk about next week); when I talk about “logical consequence,” I mean what he calls “semantic consequence”
- selection from Papineau Chapter 11
- selection from Burgess’ Philosophical Logic
Here are discussion notes of mine (from the older course site):
What’s listed above is all that you have to read. What follows are some more in-depth readings, optional but recommended:
- Boolos, Burgess, and Jeffrey Chapter 9 and Chapter 10
- will be adding to this list
I started a page about A Toolbox of Strategies for Working with Algorithms. Will continue adding to it over next days. Will also try to provide more pages summarizing material about decidability/computability.
I realize some of the links under the Wednesday entry are missing. I’ll fix them later today. Fixed.
Here is some reading from Boolos, Burgess, and Jeffrey on countable and uncountable sets. This covers material we already discussed last week, and saw some other readings on; but it may help review and consolidate your understanding to see a different presentation. The text this is taken from is one of the standard textbooks covering the main issues of this class. But I think its presentation is more mathematically terse than many of you will be most comfortable with. Also I make some different pedagogical choices. So usually I won’t present material from this book as your first engagement with an idea. I will though often suggest it as secondary reading (sometimes assigned, sometimes optional) to help you in the way I described.
I also added a chapter from this text to the list of readings on syntax for logic (under Tuesday’s entry).
Here is some reading from the same text on formal models of algorithms/effective procedures:
- Chapters 3 and the start of Chapter 4, explaining how Turing Machines work and Turing’s argument that the Halting Problem is undecidable (assigned, also for review and consolidation)
- Chapters 6 and 7 (optional), explaining Kleene’s system of “Recursive functions,” and extending that to notions of “Recursive sets and/or relations” (also what they call “semirecursive” — or later in the book, “Recursively enumerable” — sets)
- Chapter 8 (optional), explaining that the functions that can be computed by Turing Machines end up being the same as those that can be defined as Recursive functions. Some places in these readings mention “abacus functions,” which is another formal system that book presents, but which I haven’t given here.
We still have a bit more to discuss about the formal models of algorithms/effective procedures; most notably Turing’s demonstration that the question whether an arbitrary Turing Machine would stop when given a specific input can not in general be decidable.
But we’re going to be shifting gears to start talking about the syntax, semantics, and proof systems for logics. I’ll post a number of readings about this. Here are some to get you started.
- See the entry under Feb 27 for an expanded reading list
- from Burgess’ Philosophical Logic
- from Papineau Chapter 10
- from Boolos, Burgess, and Jeffrey Chapter 9
Here are some discussion notes of mine (from the older course site) on the syntax of logical systems
Here is an initial version of Homeworks 5 and 6. As I say there, you have until Friday to complete the two homeworks, and can take some more time if you need it, so long as we coordinate about a reasonable extension ahead of time. Also, I may add one more question (that will take some time both for me to write up and for you to solve). I added one more question at the end and fixed one mistake. The homework should now be complete (unless I learn of more errors).
Here is some additional reading on infinite sets, from Papineau’s Philosophical Devices.
Some asked for the recordings of our Zoom sessions. Here is the one from Monday, and here is the one from today. You will (should) need your UNC logins to view.
These web notes from my phil mind class may be helpful reading for some of what we covered today. There are also links there to overviews elsewhere on the web of notions like “effective,” “computable,” “Turing machine,” and “formal automata.”
Here is a chapter from “Gamut’s” two-volume Logic, Language, and Meaning (this was a pseudonym used by a group of logicians in Amsterdam and Utrecht):
Here are readings from Partee, ter Meulen, and Wall’s Mathematical Methods in Linguistics:
- selections from Partee Ch 16 on formal grammars
- Partee Ch 17 on finite automata and regular grammars
- Partee Ch 18 on push-down automata and “context-free” grammars — least important of these
- Partee Ch 19 on grammars whose languages are only enumerable by Turing Machines
I’d rather give you something more compact to look at than these, but I haven’t found anything good yet that’s in-between the level of detail of the notes from my phil mind class and the Gamut reading, on the one hand, and the Partee readings on the other. (Whereas, if you want to go into even more detail than Partee does, I’ve got plenty of resources to point you to.) Try to skim these chapters to fill out the big-picture I was sketching in class. Try not to get overwhelmed by the details, which won’t be essential for our purposes. We’ll continue discussing these issues on Monday. I will also try to post a written overview of what’s important for us; but I don’t expect to be able to do it until Saturday earliest.
Tomorrow’s lecture will also be by Zoom.
Here are model solutions for last week’s homework.
As I emailed the class, our lecture on Monday (and probably Wednesday too) will have to be held by Zoom.
The topics I’d like us to get through this week are these. It’s a full menu, but I don’t want us to fall too far behind.
- Isomorphisms and Homomorphisms between algebra — there were already readings and notes (from the old website, translations to this site still not ready) last week
- Cardinality of Sets — will post some readings about this below, and notes later this weekend
- Formal grammars and languages — here are notes from the older website, will translate to this site as soon as I can, but you don’t need to wait for that
- Automata and Effective Decidability — here are notes from the older website, will translate to this site as soon as I can, but you don’t need to wait for that
Here are the readings on cardinality:
- Partee Chapter 4
- Papineau Chapters 2-3 — also linked this at the top of Wed Feb 16’s entry
The fourth homework is posted here, covering the material on lattices and algebras. As promised, since it was posted late, it won’t be due on Wednesday morning. We’ll extend again to the end of the day (11:59 pm) on Friday.
Here are model solutions for the third homeworks.
The lattice notes are nearly finished. Still working on translating the algebra notes from the older website.
I’ve updated some things on the more on relations page, especially at the end. May make some more small tweaks there over next few days.
I’ve got a draft of the material on lattices and so on that we discussed in class on Wednesday. Still working on this (and as I write this, haven’t even added the definition of a lattice), but depending on how you’re scheduling your time, it may be helpful to have a look at what’s already there.
The next topic we’ll discuss will be algebras and relations between algebras. Those notes are from an older version of this course, and I will be editing them in small ways to fit into the formatting, vocabulary, and continuity of our own discussion. But again, depending on your scheduling, it may be helpful to have a look at these versions, which you can regard as drafts for our course. The content won’t change in any important ways. The things labeled HOMEWORK EXERCISES in those readings aren’t assignments for you (but probably some of them will be incorporated into the homework I do give you).
Here are some additional readings from Partee’s text about algebras and relations between them. You can read these now:
This week’s homework will be on lattices and the algebra material. If I get it posted by Saturday morning, it will be due at the regular time of start-of-class-on-Wednesday. As I’ve said in class, if this makes life difficult for you, talk to me about it.
Here are model solutions to week 2’s homework. Let me know if you have any questions or see any mistakes.
In addition to the readings posted yesterday (and updated this morning), here are/will be webnotes from me:
- more webnotes from me on relations, mostly summarizing material from readings posted below
- webnotes from me on graphs and trees
- webnotes from me on lattices (to be posted later), our discussion won’t get to this until Wednesday
Here is this week’s homework (final version posted Monday morning).
Am going to be late again getting webnotes and homeworks posted. Check in again later this weekend for more. As a general rule, if I don’t have the week’s homework posted by Saturday morning, you’ll have longer to work on it.
Here is some reading material to get you started:
- review the Partee selection on relations that was posted last week, especially these notions we haven’t yet discussed: asymmetry, anti-symmetry, connectedness, equivalence relations and their relation to partitions
- read this new Partee selection on orders
- read this selection from the Open Logic Project on similar material — this selection begins by repeating a few pages from the end of last week’s reading from the same source
- read Wolf on relations and orderings
- read this selection from Steinhart. I put “?” on two passages. One is where he gives an example using “husband” in a way that ignores the existence of gay marriage. The other is about mathematical notation. He symbolizes the “transitive closure” of a relation
Ras R*. However, that notation is generally used for the transitive and reflexive closure ofR. Thusparent*would meanis a ancestor of or is identical to. To symbolize just the transitive closure ofR(as Steinhart does), usually a+is used instead of a*. (We’ll see+and*used in this way again later in the course. The general idea is that+means “1 or more times” and*means “0 or more times.”)
Here is a way you might define takeWhile2 without introducing a new function for each recursive call. (Although then the example is less instructive!)
takeWhile3 (hs, q, ks) =def dissect hs {
λ ys ^ xs if ys ≠ empty and q(ks ^ ys)! ys ^ takeWhile3 (xs, q, ks ^ ys);
λ xs. empty
}Then takeWhile2(hs, q) would be equivalent to takeWhile3(hs, q, empty). Another equivalent definition would be:
takeWhile4 (hs, q, ks) =def dissect hs {
λ ys ^ xs if ys ≠ empty and q(ks ^ ys)! takeWhile4 (xs, q, ks ^ ys);
λ xs. ks
}Here is the second homework. It covers the material on sets and functions. Since I didn’t post it until so late, it won’t be due until the end of the day (11:59 pm) on Friday.
Here are some readings for this week. Aim to get at least through the material on sets by Monday, and the rest by Wednesday. It may be that we don’t get to relations until the following week.
Prof Pryor’s notes:
Here are some other expositions of the material in 4, 5, and 6. If my exposition is too terse, or talks about too many advanced subtleties, the other expositions may be more helpful. But I hope they’ll all contribute something to your understanding of the material.
- Champollion handout
- Partee et al on sets
- Partee et al on relations and functions
- Open Logic Project on sets and relations
This may look like a lot of reading, but most of the selections are short and they’re covering the same ground. I’d be glad to know which of them you find most helpful.
I’m afraid I’ll have to post the homeworks later. Since that doesn’t leave you so much time to complete them by Wednesday, everyone will have an extension on this week’s homeworks. (At least until Friday morning; let’s seen when I get the homeworks posted.)
Here are model solutions for the homework that was due this week.
I discourage you from skipping a homework entirely, but you’re allowed to, because the worst two homeworks you submit (or fail to submit) will be ignored. If you’re not going to submit a homework on a given week, though, please email me to explicitly say so.
I will post notes on this week’s discussion, as well as readings and homeworks for next week, as soon as I can. I’m aiming to have them live by Saturday morning.
Here is a summary of Wednesday’s presentation. At the end, it points to the homework that’s due next Wednesday.
Some of the homework problems are easy, some will be more challenging. Some might be too challenging. Don’t let that make you anxious. There’s value in having you try these things, even if it’s a stretch. We’ll work out a grading standard that’s reasonable relative to what your ability is, and what’s absolutely essential for you to master.
Noel posted in the chat on Wednesday: “Hey y’all, I made a GroupMe so we can organize groups/ask questions about the homework this weekend! Here’s the link”
In the next few days, I will also post some notes about sets, to read in advance of next Wednesday’s meeting, and the homeworks that will be due after that meeting. I expect that our meeting on Wednesday (Jan 19) will largely be occupied with discussing the first week’s homework. Come prepared also to ask questions about the new notes about sets that could help you understand them better. You may want to also have a look ahead at the second homework that will be due on Jan 26, and may have some questions about that.
Proofing the notes and the homework, I see a bunch of typos. Now they’re fixed. Let me know if anything still looks wrong.
As I just emailed the class, have decided to conduct tomorrow’s meeting by Zoom. The links are at the top of this page or in that email.
I’m proceeding on the assumption we’ll be back in person for our meeting next Wednesday, and will update you if that changes.
Our first meeting was today.
I mentioned that I’d provide a page with Unicode symbols that you might use in this class. ( This site lets you draw characters on your screen and then it searches for Unicode symbols that look like that.)
As a reminder, please submit homeworks in one of these three forms (topmost are easier for me to read, but any will be accepted):
- Plain text using Unicode symbols (see link above) and/or
$math latex code like \alpha x_i etc$. If you know how to write that.
- Handwritten and scanned or (if you have to) take a photo with your phone and send that.
I’ll post the first homeworks later in the week, and they’ll be due at the start of class next Wednesday Jan 19.
We talked about the Greek alphabet and the Fraktur typeface in class today.
I also mentioned John MacFarlane’s program Pandoc, which you don’t need to know about, but if you end up writing technical documents (papers with equations in them, or html or LaTeX formatted things) may someday make your life easier.
I moved the summary of Monday’s (and the start of Wednesday’s) presentation(s) to this separate page