Phil 455: Announcements, Readings, and Lecture Notes

Links

The front webpage for the course is at phil455.jimpryor.net.

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 jimpryor@unc.edu.

Posts

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.

Mon Apr 29

Here is a link to the final homework.

Here is a link to the seminar evaluation, due by end of day tomorrow.

Wed Apr 24

Here is a link to today’s handout, which we’ll continue to discuss on Monday. See entries below for what reading to do.

Here is the recording of today’s meeting. Passcode “iU*C$%^2” (without the quotes!)

Here are the model answers to Homework 10.

Mon Apr 22

Here is a link to today’s handout.

Be sure you’re caught up with the reading assigned for today, especially Chapter 9 which is about the system/algebra/calculus of primitively rekursive functions. Here is the next batch of reading, that you should do for Wednesday. It mostly steps through and reinforces what we talked about in class today:

• Chapter 17 on the not-necessarily-primitive rekursive functions (bringing in the “minimization” or “first_zero” operation)

• Sections 5.1-5.3: the first two sections were assigned earlier, be sure you’re comfortable with them, then read Section 5.3 which talks about the notion of “expressing a relation or function in a formal language”

• Chapter 10, which introduces the notions of “capturing” a relation or function in a formal theory of arithmetic, and then explains why our middling arithmetics can do this for all the primitively rekursive functions (in fact they can do it for the non-primitive ones too, but we don’t need the extra complexities that introduces)

For next Monday, the reading will be:

• Chapter 3

• the rest of Smith’s Chapter 4 (4.3-4.8), probably good to read the whole of this chapter starting again

• the rest of Smith’s Chapter 5 (5.4-5.6), probably good to read the whole of this chapter starting again

• Chapter 11 — this should remind you of what you did in Homework 7, Problem 84

• Chapters 12 through 15 13 (Chapters 14 and 15 are optional)

Thu Apr 18

Here’s a handout with some spelled-out details and examples about the calculus/system of primitively rekursive functions. We’ll talk through it on Monday, but it’d be good if you familiarized yourself with the handout beforehand.

You should also aim to have read (and understood as best you can — ask questions or for help when you don’t) Chapter 2, Sections 4.1 and 4.2, Sections 5.1 and 5.2, and Chapters 6, 7, and 9 in Smith’s book Gödel without (too many) tears. (The intervening Chapters and Sections will play a role in the later action, so it’s not like they won’t matter. You may find it less distracting to read up through Chapter 9 in sequence, rather than skipping parts and having to process Smith’s references back to things he said in Chapters you skipped. But we haven’t yet taken up the issues of those skipped parts yet in class. I’m trying to point to the parts of his text that cover material we’ve introduced and tried to explain so far in class.)

Chapter 2 in particular of Smith’s text, our previous work in the class should have prepared you to follow. Notice that the notion I’ve been calling “a theory being deductively complete,” Smith is calling “negation completeness.” The meaning is the same: namely, that for every sentence ψ in the language, the theory either contains ψ or contains ¬ψ.

Smith talks about “the intended semantics” of a language — this is the one model we’re aiming to pin down, and he calls the language together with that model an “interpreted language.” Also when he talks about “theories,” he doesn’t just mean a (deductively closed) set of sentences, but that together with a specific proof system. These are just minor terminological and book-keeping differences from how we’ve been talking. (Other authors talk more the way we do in these ways, but diverge in other ways.)

In Chapter 3, which you’ll be reading at some point in the near future (maybe already now) Smith introduces another use of the label “sound.” (Sigh, why do people have to keep giving new meanings to words that already have a use!?) He says a theory is “sound” when all of its theorems (the sentences it contains) are true, when interpreted in the intended way. Also the proof system has to be such that it preserves truth on that model. — This is weaker than the proof system being sound in the more familiar sense we’ve been discussing in past weeks, since this only states a requirement about how the proof system is related to the one intended model, not all models. But the only proof systems we’ll be considering will be sound in the stronger (more familiar) sense of preserving truth on all models.

At various points in the discussion, theorists bring in the notion of “truth.” This can happen in at least three different ways. (Maybe there are more, these are the ones I can think of.)

• Some theories include a predicate that is supposed to represent within the language that some string (or number that encodes a string) is true. This comes up later in the discussion, and I expect we won’t get that far in our class. In Smith’s book this idea is introduced in Chapter 16.

• A second way in which truth can be invoked is we sometimes talk about which model is the right or correct or intended one, and which sentences in the language does that model make true. Those will be called for example “the truths (or true sentences) of arithmetic.” This goes hand-in-hand with the notion of a theory being “sound” in the sense we talked about Smith using in the previous paragraph.

• A third way is connected to the second. If we have one special model which is the one we intend for the language to be describing, and we have the notion of which sentences in the language that model makes true — never mind if we can figure out, using an effective method or in any other way, which sentences those are, mathematically for any single model there will be the set of sentences that it makes true — then one kind of “theory” we can talk about is the theory that includes exactly those sentences. The ones that are true on the intended model. When the language in question is meant to describe facts about the natural numbers, addition, multiplication, and so on, then this “theory” of all the sentences in that language that are really true about the natural numbers is sometimes called true arithmetic. It is a sound theory in Smith’s sense (all its theorems are true) and it is also deductively/negation complete. But it may well be (yes, sadly it will definitely be) that the theory is not effectively axiomatizable. I found it weird to be talking about a “theory” that wasn’t axiomatizable, when I first learned this material. Maybe you will too. But some of the discussion does do this. Remember the special technical usage of “theory” we’re working with, where it can be any deductively closed set of sentences. Doesn’t need to be axiomatizable, nor does it even need to be consistent.

Our topics for Monday will be continuing to discuss the primitively recursive functions (see Smith Chapter 9), briefly discussing how that system can be strengthened (see Smith Chapter 17), and hopefully at least introducing the ideas of Smith Chapter 10. (The sections I asked you to read from Chapters 4 and 5 are needed background.)

Some correlations: (a) the notions of “effectively enumerable” and “effectively decidable” sets we’ve been talking about for a while are introduced in Smith’s Chapter 5. (b) Smith’s Theorem 7 in that Chapter is Problem 108 in the current Homework 10.

Note that the “Baby Arithmetic” Smith discusses in his Chapter 6 is different from the one we discussed in class. (There are multiple theories reasonably called “Baby Arithmetics.”) The one we discussed in class is called Presburger Arithmetic, and Smith mentions it on p. 46, near the end of his Chapter 7.

Wed Apr 17

I read some more on the possibility of elementary equivalence and models that fail to be isomorphic despite having (domains with) the same cardinality. There is in fact a simple way of seeing this is possible.

Let the language have = as its only predicate, no functors, and countably many constants c0, c1, c2, and so on. Our first model has a countable domain, and maps constants to all but finitely many of the objects in its domain. To keep things simple, let’s suppose it doesn’t leave any objects unnamed. The second model’s domain will be another countable set, let’s say it’s a proper superset of the first model’s. The second model maps constants to all the same objects that the first model does. But it has more unnamed objects. Because of the way these models map constants, and the only atomic sentences in the language are things like c0 ≠ c1, c0 = c2, and so on, they are going to make all the same sentences in the language true. But there will be no way to make a bijection between their domains that respects the fact that 0 objects have no constants mapped to them by the first model, but 1 object has no constant mapped to it by the second model. (You can then make a third model which again makes all the same sentences true, but has two objects in its domain that no constants are mapped to. And so on.)

Here is the link I found most helpful (my example is based on one from there), and nother helpful link that Alex found:

• Simple examples of non-isomorphic but elementarily equivalent structures

• Understanding the meaning of and difference between elementary equivalence and isomorphism of logical models by way of an example

Fri Apr 12

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

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:

• pp. 106-8, stating the thesis of Completeness for his sentential proof system, and discussing the thesis of Compactness as a corollary.

• the last paragraph of p. 263

• Chapter 6. I expect you will find this challenging. Try to isolate the parts you don’t understand (for example, lot of the math details like on pp. 268-270 aren’t essential for our purposes), and follow the main discussion thread as best you can. You’ll definitely need to read this material several times. I hope that looking at it in advance, then discussing it in class, then reading it again will be a good strategy for you to get the most comprehension.

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.

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

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:

• Dissecting, Stinkiness, Winkiness

Here are the other readings:

• Encoding Trees

• Other Encodings to/from Strings and Numbers

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.

• Turing Machines

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.

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:

• from Partee Chapter 8

• from Partee Chapter 16

• from Partee on inductive definitions

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:

• Algebras — optional supplementary exposition from Partee

• Relations between Algebras — optional supplementary exposition from Partee

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

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:

• For problems 7b and 7c, I counted the simple answer as being “no” and worth one point, but gave you a bonus point for each case if you noted that in the special cases where the relevant domains had fewer than two elements, the function could then be injective.

• Some of you need to pay a bit more attention to when some variable, or the input to some function, is a set, versus a function, versus a number, versus some other kind of object, versus a pair (or larger tuple) of some of these. Also be more careful about when you’re talking about some arbitrary argument to a function, versus when you’re talking about the whole domain of possible such arguments. In typeset text, sometimes you’ll see these referred to like this: f is a function whose domain is Α, let a be some arbitrary argument to f. Or g is a function whose domain is Φ, let φ be some arbitrary argument to g. It’s easy here to tell the difference between Α and a, and between Φ and φ. But when you’re giving me handwriting, this is much harder to see the difference between. In some cases I think you even confused yourselves.

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. 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 Calkin-Wilf tree

• the Stern-Brocot tree

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 ℶ₁.

• Exposition of Cardinality from Partee

  I will just call the author of this text “Partee,” though in fact it’s a group of three linguists (Barbara Partee, Alice ter Meulen, and Robert Wall). Some notes on this reading:

  1. Partee calls sets “equivalent” meaning what we mean by calling them “equinumerous.” She uses “denumerable” to mean “countably infinite.”
  2. The proof we did in class that |ℕ| < |𝟚^ℕ| appears on pp. 66 of this reading.
  3. Cantor’s more general proof that for any set Δ, |Δ| < |𝟚^Δ| appears on pp. 62-3.
  4. The “Continuum Hypothesis,” which says that there are no infinities “in between” |ℕ| and |𝟚^ℕ| (and thus that ℵ₁ = ℶ₁) is mentioned on pp. 65-6. As I said in class, it’s now known (since the 1960s) that standard set theory does not prove the Continuum Hypothesis to be true, but neither does it prove it to be false.
  5. At several places (pp. 58, 66-69), Partee discusses “strings” and “languages.” We will discuss these in our class later. To orient you quickly, a string is just a sequence of zero or more letters from a fixed set of choices (the set of letters is called the alphabet). A language is just a set of strings: usually only some of the possible ways of combining letters count as belonging to the language.
  6. I recommend Partee’s discussion clarifying the difference between “infinite” and “unbounded” on pp. 69-70. As an example, finite sets of natural numbers have an unbounded cardinality. For any cardinality such a set may have, there’s another finite set of natural numbers that’s larger. But all of these sets have finite sizes. (There are infinitely many of them, but none of them has an infinite size.) So “having an unbounded size” doesn’t mean “having an infinite size.”

• Exposition of Cardinality from Suber

  You may find this old web page helpful. Some of the math theorems it states (and proves) go beyond what you need to master for this course, but you may find them interesting. Or you can just skim over them.

Our next topics will be:

• relations (those are the notes; for reinforcement readings see the expositions posted in the Jan 12 entry below)

  Note that all three of those readings talk about a relation being “connected” or “connex” to mean it has the property I’m calling “weakly connected.”

• orders (those are the notes; here is a reinforcement reading from Partee)

• lattices (those are the notes; here is a reinforcement reading from Partee)

• graphs and trees (those are the notes; here is a reinforcement reading from Partee)

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.

• Notes on sets and tuples

• Notes on functions

• Exposition of Sets, Relations, Functions from Partee et al

• Exposition of Sets, Relations, Functions from Nick Smith

• Exposition of Sets, Relations, Functions from Boxes and Diamonds

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.

• Notes on relations

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.