What is this course about?

Formal logic has many applications both within philosophy and outside (especially in mathematics, computer science, and linguistics). This second course will introduce you to the concepts, results, and methods of formal logic necessary to understand and appreciate these applications as well as the limitations of formal logic. It will be mathematical in that you will be required to master abstract formal concepts and to prove theorems about logic (not just in logic the way you did in Phil 279); but it does not presuppose any (advanced) knowledge of mathematics. We will start from the basics.

We will begin by studying some basic formal concepts: sets, relations, and functions, and the sizes of infinite sets. We will then consider the language, semantics, and proof theory of first-order logic (FOL), and ways in which we can use first-order logic to formalize facts and reasoning about some domains of interest to philosophers, computer scientists, and logicians.

In the second part of the course, we will begin to investigate the meta-theory of first-order logic. We will concentrate on a few central results: the completeness theorem, which relates the proof theory and semantics of first-order logic, and the compactness theorem and Löwenheim-Skolem theorems, which concern the existence and size of first-order structures.

In the third part of the course, we will discuss a particular way of making precise what it means for a function to be computable. To this end, we will discuss a “model of computation”: Turing machines. We will show that there are problems which are undecidable in the sense that there is no Turing machine which, in a finite amount of time, provides a definite yes-or-no answer. The first example of an undecidable problem is the halting problem, i.e., the problem of deciding, given the description of a Turing machine, whether it halts on a given input. We will also show that the decision problem—i.e., the problem of deciding, given a sentence of first-order logic, whether it is valid—is undecidable.

If there is time, we will cover some advanced topics at the end of the semester, such as second-order logic or solvable cases of the decision problem.

This is a course in metalogic. It builds upon the material in Logic I (Phil 279/377), but is very different in character. Doing well in Phil 279 is no guarantee that this will come easy to you.

How will the course be run?

The course will be delivered in a hybrid synchronous/asynchronous model. There will be readings, prerecorded lecture videos, discussion boards, and quizzes on the course website (D2L). You can read, watch, and participate in discussions more or less when you choose, so that part of the course will not happen at the same time for everyone (i.e., it is asynchronous). There will also be weekly Zoom sessions at specific times where everyone will participate at the same time (i.e., those are synchronous):

In lecture, we will go through exercises, review material, ask and answer questions, sometimes in small groups (breakout rooms).

What prerequisites do I need for this course?

Logic I (Phil 279) or Elementary Formal Logic (Phil 377) is a prerequisite for this course.

What will I learn in this course?

By the end of the course, you should be able to …

1. Understand, construct, and formulate simple mathematical proofs in which you apply definitions, identify hypotheses, and correctly and appropriately use informal patterns of mathematical reasoning.
2. Understand and apply the methods of definition by induction and proof by induction, both for the natural numbers and for inductively defined sets such as the set of formulas of first-order logic.
3. Understand and use the vernacular of set theory (sets, relations, functions) to describe and explain the metalogical properties of the model and proof theory of first-order logic as well as of Turing machines and computable functions, and to prove intermediate facts about infinite sets and their sizes using, e.g., the diagonal method of Cantor’s theorem.
4. Understand the formal syntax, model theory, and proof theory of first-order logic, to explain the definitions, the properties, and the relationships between logical notions (free and bound variables, sentences, satisfaction, consequence and satisfiability, inference rule, derivation, provability and consistency), and to prove intermediate facts about them (such as the soundness of the proof system).
5. Understand the completeness theorem of first-order logic, to explain the overall structure as well as the individual steps of the proof, to explain and prove from it corollaries such as the compactness and Löwenheim-Skolem theorems, and to apply these to properties of theories and the size of models thereof.
6. Understand the concept of Turing machines, how they can be used to define computable functions, to construct simple Turing machines, to formulate and prove the undecidability of the halting problem, and to formulate and explain the decision problem.

What will I have to do in this course?

Visit the D2L/Brightspace site

The course has a D2L/Brightspace site. You will find (information on) course readings, videos, scheduled Zoom meetings, assignments, quizzes, tests, and grades there. Any updates, including revisions to the course schedule, PASS sessions, course schedule, will be posted there. To make sure you don’t miss a deadline or an important update, please review your notification settings.

Read the textbook

The textbook is:

Sets, Logic, Computation: An Open Introduction to Metalogic (Fall 2021 edition)

It is free and available on D2L in PDF. You may also purchase a paper copy if you like.

You should read along as we cover the topics in the course. Each unit in the Content section on D2L will tell you which chapters of the books to read. We won’t cover, and you won’t be tested on, everything in the book.

Watch some lecture videos

Each week, there will be a few lecture videos. You should watch these videos in preparation for the synchronous class meetings, i.e., before Wednesday. The videos are posted on D2L, as are the slide decks that go with them.

Attend Zoom sessions

We’ll have Zoom sessions every week on Wednesdays, 14:00–15:15. During these meetings, we will work on problems related to the week’s material, often in small groups. I’ll assume that you’re prepared (i.e., have watched the lecture videos and done the reading). There will also be opportunity for Q&A and discussion. Recordings will be available.

Ask and answer questions on the discussion board

There will be a discussion board for the course set up on CampusWire. You might want clarification on something in lecture or the textbook, or you’re stuck on an exercise and need a hint or have someone to tell you what the problem with your proposed solution is. Your instructor and TAs will help. One of the course outcomes, however, is to make you a better, more collaborative learner and teacher yourself. So feel free to attempt to explain things others ask questions about, and provide hints for those who get stuck yourself.

Pre-class quizzes

There will be 10 open-book pre-class quizzes covering the background readings, to be taken online on D2L. Quizzes will be due at 14:00 of the first day the relevant topic is discussed in class, but will be available on D2L for seven days prior. Pre-class quizzes are graded either complete or not complete.

Weekly tests

There will be 10 open-book tests covering the topics in class, to be taken on D2L. They will usually be due Mondays at 23:59; the first test is due September 13. Tests are graded pass/no pass.

Basic problems

There will be 8 short-answer basic problems. They will usually be due on Mondays at 23:59, to be submitted on D2L or Carnap. The first problem will be due September 13. Basic problems are graded according to the EMRN rubric below.

Challenge problems

There will also be 3 additional challenge problems. Challenge problems are graded according to the EMRN rubric below.

Group work

Some of the class time will be devoted to working on sample problems. You are expected to do the assigned readings before coming to class. At irregular intervals we will solve problems in lectures in small groups. Every week there will also be problems posted on CampusWire, which you will be asked to solve together. A contribution to a solution might be an idea for how to do it, adding a step of a proof, or pointing out a mistake. Every week in which you contribute to the solution of these problems in Zoom breakout rooms or on CampusWire earns you a complete for group work for that week.

What do I need for all that?

This course will be delivered online. One lecture meeting per week will take place via Zoom at the set lecture times, but most content will be delivered asynchronously (that means: not at a specific time). To access the material and complete the assignments you will need a computer and access to the internet (for some things a smartphone or tablet are enough, but a desktop or laptop with a keyboard, mouse, and large-ish screen will be much more comfortable).

You will need an account with the UCalgary IT service, without which you cannot access D2L.

To participate in synchronous groupwork sessions, and to communicate with your instructor, TAs, and fellow students, you need a Zoom account. To participate with audio and video, you need a microphone and webcam, ideally on a computer with keyboard and mouse. However, attending the synchronous Zoom sessions is not required to pass the course.

Instructions for getting IT and Zoom accounts, accessing D2L, and additional tips for how to best learn online are available at:

taylorinstitute.ucalgary.ca/learning-continuity

How will my grade be determined?

There will be no registrar-scheduled final exam.

Your work is evaluated on one of three scales, depending on what it is:

1. Pre-class quizzes and in-class group work are graded either credit (CR) or no credit. To get credit, you must score at least 50% on a quiz, or participate in the group work exercise in a given week.
2. Weekly tests are graded either pass (P) or no pass. To count as a pass, you must get a point score of at least 70%.
3. Basic and Challenge Problems are graded using the four-level EMRN rubric, illustrated below. Marks of E (exemplary) and M (meets expectations) are “passing”. Marks of R (needs revision) and N (not assessable) are not passing.

Please note that with the exception of the weekly tests, none of the work in the class is assessed using points. Your progress toward a grade in the course is determined simply by the quantity of passing marks you earn on various assignments and how many E marks you receive on basic and challenge problems. This is a “competency based” approach to grading that gives you full control over how you earn your grade and provides transparency as to what you have shown competence and what you still need to work on.

EMRN rubric

• If your work demonstrates thorough understanding of the concepts and meets the expectations outlined in the assignment…
  • and the work is complete and well documented, it earns an Exemplary (E) mark.(The work meets or exceeds the expectations of the assignment. Communication is clear and complete. Mastery of concepts is evident. There are no nontrivial errors. This work could be used as a classroom example.)
  • otherwise, it earns a Meets Expectations (M) mark.(Understanding of the concepts is evident through correct work and clear explanations. Some revision or expansion is needed, but no significant gaps or errors are present. No additional instruction on the concepts is needed.)
• if not, but …
  • there is evidence of partial understanding, it earns a Revisions Needed (R) mark.(Partial understanding of the concepts is evident, but significant gaps remain. Needs further work, more review, and/or improved explanations.)
  • otherwise, it earns a Not Assessable (N) mark.(Not enough evidence is present in the work to determine whether there is understanding of the concepts. The work is fragmentary, contains significant errors or omissions, or there are too many issues to justify correcting each one.)

Course grade

The table below shows the minimum requirements in order to earn a particular letter grade in the course.

For instance, to receive a B+ in the course, you must get credit on at least 8 quizzes and 6 group work exercises, pass 10 tests, receive an M or better, of which 3 must be an E, on at least 7 basic problems, and an M or better on at least one challenge problem.

Revision

You have the opportunity to revise almost any item of work in the class if you want to raise your grade on it. Specifically:

1. You can retry weekly tests up to 3 times, until the deadline.
2. You can resubmit any basic or challenge problem on which you received a grade of at least R once, up to seven calendar days after the graded problem was returned.
3. You can use a token (see below) to revise any basic or challenge problem on which you received a grade of N.

Tokens

Tokens are a kind of currency for this class. Each student has three (3) tokens to spend to bend the rules of the class in various ways. You can use a token to do the following.

1. Revising a problem on which you received an N grade (see above).
2. Submitting a problem by the deadline for revisions if you did not turn it in.
3. Purchase a no-questions-asked extension of 48 hours on any basic or challenge problem.
4. Purchase a single attempt on a weekly test after the deadline has passed.

Are there PASS sessions for this course?

Yes, this course is supported by the PASS (Peer Assisted Study Sessions) program. PASS provides students with free, organized study groups facilitated by a student who has been successful in the course before. Attending PASS can help you build your understanding of course content as well as learn valuable study skills which will help you to succeed in the course. You will meet your PASS leader and receive more information in the first weeks of classes. PASS sessions will be held on Zoom as well.

What course policies should I be aware of?

Recording Zoom sessions

In order to allow students to review synchronous sessions, these Zoom sessions will be recorded and the recordings made available to students in the course. Recorded sessions will not be used for any other purpose. Nevertheless, if you object to your image or voice being recorded, you should make sure to turn your video off and set your microphone to mute. (You can use the Zoom chat function to ask questions.) Breakout rooms (small groups) will not be recorded, and as a courtesy to your fellow students, you are encouraged to use video and audio while in a breakout rooms.

Conduct

Learning can only happen well if everyone feels like they belong and are free to ask questions and participate in discussions. It is partly on you to make sure our course is such a space. So please be respectful, positive, and constructive in your participation in the course. It should go without saying, but do not post (links to) anything racist, mysogynist, or homophobic, or NSFW, and don’t stalk or harrass your fellow students or instructors. Also, do not share links or passwords to live or recorded Zoom sessions outside the course.

Late policy

If you do not complete an assignment by its deadline, it counts as not completed and will not be assigned a mark. However (see above) you can spend tokens to extend a deadline by 48 hours, or to complete an assignment after the deadline.

If there are factors beyond your control, and which you could not reasonably have planned for, which prevent you from completing activities (illness, family emergency, etc.) please contact the instructor so we can make arrangements. Please do so as soon as possible. You will not have the opportunity to make up work you missed early in the term if you don’t tell me until the last week of term.

Plagiarism

You might think that it’s only plagiarism if you copy a term paper off the internet. However, you can also plagiarize in a logic course, e.g., by copying a proof verbatim from the textbook or the internet (and only making the necessary changes to apply it to the assigned problem.) The point of logic problems which are similar to the proofs in the text is to make you work through those proofs, understand them, and then prove a similar result on the problem sets. Hence, all solutions must be in your own words; copying or paraphrasing closely from the text or elsewhere constitues plagiarism, which must be reported to the Dean’s office by university policy. It may result in a failing grade or worse penalties.

Checking your grades and reappraisals of work

University policies for reappraisal of term work and final grades apply (see the Calendar section “Reappraisal of Graded Term Work”). In particular, term work will only be reappraised within 10 calendar days of the date you are advised of your marks. Please keep track of your assignments and your marks (check them on D2L).

When is it all going down?

Due dates are tentative and subject to revision. Quizzes are due Wednesdays at 14:00 each week and are on the material covered that week. Tests, basic, and challenge problems are due Mondays at 23:59 and typically are on the material covered the preceding week or two.