University of Calgary

# Logic II (Phil 379)

Logic II is an introduction to computability and the basic metatheory of first-order logic (undecidability and incompleteness). Official, printable outlines can be found at the end of this page.

# Course Description

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. The latter will allow us to study the sizes of infinite sets. In particular, we will prove Cantor’s celebrated results that there are different levels of infinity. We will assume (almost) no background. Here, we will first apply proof methods from elementary logic to a new, abstract domain, and become familiar with a central proof method of metalogic: induction.

In the second part of the course, we will begin to investigate first-order logic more closely. We will see how the formulas of first-order logic are precisely defined, what structures for first-order languages are and how truth in structures and entailment is related. We will discuss how properties of structures can be expressed, and how theories are related to their models. We will study how first-order logic can formalize facts and reasoning about some domains of interest to philosophers, computer scientists, and logicians. We will introduce a proof system for first-order logic, Gentzen’s natural deduction. We will then turn to the metatheory of first-order logic, where we will concentrate on a few central results: the soundness and completeness theorems, which relate 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.

Some of the material we will be covering is discussed in your 279/377 text—if you used The Logic Book, review chapters 8 and 11; in Chellas’ Elementary Formal Logic, review chapters 7 and 9 and the appendices; in Language, Proof and Logic, review chapters 15, 16, 18.1–18.3; in Formal Logic: Its Scope and Limits, sections 2.7–2.10, 3.13–3.15, 4.13–4.15.

# Prerequisites and Preparation

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

# Required Text

The Open Logic Project, Sets, Logic, Computation.

The electronic version is also provided on the course website. A limited number of printed copies will be available in the campus bookstore.

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

# Evaluation

Six problem sets (60%, 10% each), three in-class quizzes (30%, 10% each), and participation (10%). The first two quizzes are 30 minutes each; the last one is 75 minutes. Quizzes are cumulative and closed-book. There will not be a registrar-scheduled final exam.

You must submit all six problem sets, and complete all three quizzes to pass the course.

For each answer to a question in a problem set or test you will receive a letter grade (possibly with +’s or ’s) reflecting the level of mastery of the material shown by the work you submit. The grading rubric is given below:

A

Excellent—superior performance, showing comprehensive understanding of subject matter. (Your solution to an assigned problem shows that you understand the problem and how to solve it; the solution is complete and rigorously correct, it is reasonably direct and elegant, and you have presented it clearly with all necessary information given.)

B

Good—clearly above average performance with knowledge of subject matter generally complete. (Your solution shows that you understand the problem, but your solution is not perfect. There may be minor gaps in your proof, the solution is correct but circuitous, your presentation of the solution is less than perfectly clear, or you left out pertinent information.)

C

Satisfactory—basic understanding of the subject matter. (Your answer shows that you understand what the question is asking, but your solution is incomplete or incorrect.)

D

F

Fail—Unsatisfactory performance. (It is not clear that you understand what the question is asking, your proposed solution is fundamentally mistaken, or you’ve only reformulated the question without giving an answer.)

In computing your final grade, your marks will be converted to grade points (A = 4, B = 3, C = 2, D = 1, F = 0, with +/ adding/subtracting 0.3), and averaged according to the weights given above. The final mark is the letter grade corresponding to this average plus a margin of 0.1 (i.e., an average of 3.9 earns an A, an average of 3.6 an A, etc.).

Participation will be evaluated based on your contribution to discussions, in-class group work, and passing online reading assessments. You get credit for each substantive post in the discussion forums, or substantive answer to a post; for each online reading assessment passed; for each in-class group exercise participated in. Consistent in-class participation counts for three credits. Completing the introduction survey earns you one credit as well. Reading assessments are time restricted, so be sure to complete them while they are available. To earn an A, you need 12 credits; otherwise your grade point value for the participation part of your course grade will be 1/3 of your number of credits.

# Assignments and Policies

## Submitting assignments

You may submit problem sets electronically in D2L, in class, or in the Phil 379 dropbox in the corridor outside SS 1253 in the Philosophy Department.

## Late work

Late submissions of problem sets will be penalized by the equivalent of one grade point per calendar day or part thereof.

There will be no extensions and no make-up quizzes under normal circumstances (i.e., unless you can document an illness or other emergency which prevented you from taking the quiz or submitting the assignment).

## Collaboration

Collaboration on problem sets is encouraged. However, you must write up your own solutions, and obviously you must not simply copy someone else’s solutions. You are also required to list the names of the students with whom you’ve collaborated on the problem set. If you collaborate without following these instructions, it constitutes cheating.

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

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 (homework assignments, midterms) will only be reappraised within 15 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.

# Course Website

A course website on the university’s D2L server has been set up. You will be automatically registered if you’re registered in the class. To access the D2L, you can either go directly to d2l.ucalgary.ca and log in with your UCIT account name and password, or you can access it through the myUofC portal at my.ucalgary.ca.

# Schedule of Topics, Readings, and Due Dates

Week 1

(Sept 13, 15). Introduction. Sets and Relations. (Chapters 1, 2)

Week 2

(Sept 20, 22). Induction. Functions. (Appendix A, Chapter 3)

Week 3

(Sept 27, 29). Enumerability. Sizes of sets. Cantor’s theorem. (Chapter 4)

Problem set #1 due Sept 27.

Week 4

(Oct 4, 6). Syntax of first-order logic. Structural induction. (Chapter 5)

Week 5

(Oct 11, 13). Semantics of first-order logic. Structures. (Chapters 5)

Problem set #2 due Oct 13.

Week 6

(Oct 18, 20). Structures and Theories. Natural deduction. (Chapters 6, 7)

Quiz #1 on Oct 18.

Week 7

(Oct 25, 27). Derivations. The soundness theorem. (Chapter 7)

Problem set #3 due Oct 27.

Week 8

(Nov 1, 3). The completeness theorem. (Chapter 8)

Week 9

(Nov 8). Compactness and Löwenheim-Skolem theorems. (Chapter 8)

Problem set #4 due Nov 8.

Week 10

(Nov 15, 17). Turing machines. Computable functions.

Quiz #2 on Nov 17.

Week 11

(Nov 22, 24). The halting problem. The decision problem.

Problem set #5 due Nov 24.

Week 12

(Nov 29, Dec 1). The decision problem. Applications.

Week 13

(Dec 6, 8). Review. Further topics.

Problem set #6 due Dec 6. Quiz #3 on Dec 8.

## Official Outlines

File attachments: