# Course Information

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

*WARNING:* 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.

# Prerequisites

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

# Course Objectives

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

- Understand, construct, and formulate simple mathematical proofs in which you apply definitions, identify hypotheses, and correctly and appropriately use informal patterns of mathematical reasoning.
- 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.
- 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
- 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)
- 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.
- 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.

# Required Readings

The textbook

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

is required and will be made available electronically via D2L.

# Assessment Components

**There will be no registrar-scheduled final exam.**

## Pre-class quizzes

Open-book pre-class quizzes covering the background readings and screencasts (where applicable) for each week to be taken on D2L. There will be 10 quizzes in total. Quizzes will be available on D2L for seven days and due Mondays at 12:00 noon. There will be no quizzes due in the weeks of October 14 or December 2. Pre-class quizzes are graded either complete or not complete.

## Weekly tests

Open-book tests covering the basic concepts introduced each week, to be taken on D2L. There will be 8 tests in total. Weekly tests will be available on D2L for seven days. Tests are due Fridays at 23:30; the first test is due September 27. There will be no tests due on October 18 or November 22. Weekly tests are graded pass/no pass.

## Basic problems

Starting September 19, one short answer problem a week will be due on Thursdays, to be submitted to the PHIL 379 drop-box on the 12th floor of the Social Sciences building by 16:00. There will be no basic problem due on October 17. Basic problems are graded according to the EMRN rubric below.

## Challenge problems

Four additional short answer challenge problems will be due on October 10, October 24, November 7, and November 28. Challenge problems are graded according to the EMRN rubric below.

## In-class group work

Some of the class time will be devoted to working on sample problems rather than passively listening to lectures. Students are expected to do the readings and watch screencasts before coming to class. At least once every other week, students will be asked to submit written answers to problems they have worked on as a group. Each member of the group will receive a complete for each set of problems their name appears on.

# How your work is evaluated

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

- Pre-class quizzes and in-class group work is graded either
**complete**or**incomplete**. To count as complete, you must answer all questions. - Weekly tests are graded either
**pass**or**no pass**. To count as a pass, you must get at least 75% of answers correct. - Basic and Challenge Problems are graded using a four-level rubric called the EMRN rubric, illustrated below. An enlarged version of the rubric is available on the Blackboard site in the Syllabus and Specifications area. The grades E, M, R, and N are explained on the rubric 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 mastered 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.)

- and the work is complete and well documented, it earns an
- 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.

- there is evidence of partial understanding, it earns a

The table below shows what you have to complete in order to earn a particular letter grade in the course:

D | C | B | A | |
---|---|---|---|---|

Pre-class quizzes | 5/10 complete | 7/10 complete | 8/10 complete | 8/10 complete |

Weekly tests | Pass 4/8 | Pass 5/8 | Pass 6/8 | Pass 6/8 |

Basic problems | None | E or M on at least 5/10 | E or M on at least 7/10, with at least one E mark | E or M on at least 8/10, with at least three E marks |

Challenge problems | None | None | E or M on at least 1/4 | E or M on at least 3/4 |

In-class group work | None | Submit at least 3 | Submit at least 4 | Submit at least 5 |

**Minus grades** will be awarded to students who meet all the requirements for the letter grade except the in-class group work component. There is no D–. **Grades of D+, C+, and B+** will be awarded to students who fulfil all the requirements for the base grade and in addition complete *either* the basic problem requirement *or* the challenge problem requirement for the next grade up. **The A+ grade** will be awarded to students who complete all the requirements for the base grade and in addition *either* receive an E grade on at least 6 weekly problems *or* receive an E grade on at least 2 challenge problems.

## 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:

- You can retry weekly tests up to 5 times, until the deadline.
- 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.
- 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.

- Revising problems on which you received an N grade (see above).
- Purchase a no-questions-asked extension of 24 hours on any basic or challenge problem.
- Purchase a single attempt on a weekly test after the deadline has passed.

# Course policies

## Late policy

Assignments will not normally be accepted after the deadlines unless special permission has been given by the instructor. Failure to submit an assignment or test on time will normally result in a mark of zero. Students who cannot submit an assignment or a test due to medical reasons or other reasonable grounds should contact the instructor as soon as possible.

## 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 Grades and Non-Disciplinary Academic Appeals”). 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 (make sure to pick them up in lecture or in office hours) and your marks (check them on D2L) and compare them with the graded work returned to you.

# Peer Assisted Study Sessions

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.