# Logic

This is the webpage for the PH101 classes taught at LSE in 2014-2015. The convener of this course is John Worrall. John devised all the course materials except the quizzes, which were devised by Georgios Zouros, based on John's materials. Everything is hosted on LSE's teaching platform, Moodle. Therefore they are only accessible to registered students. During term time these pages will be updated weekly so please check back regularly. If you find any typos in the lecture notes, exercise sheets, or on these pages please let Alex know.

## Weekly assignments

WeekClassExercise SheetSolutionsQuiz NumberLecture Notes Exam Section
MT31Exercise Sheet 2Solutions 2Quiz Number 2Part 1, pp. 1-43 Section A
MT42Exercise Sheet 3Solutions 3Quiz Number 3Part 1, pp. 44-48 Section A
MT53Exercise Sheet 4Solutions 4Quiz Number 4Part 1, pp. 49-55Section A
MT64Exercise Sheet 5Solutions 5Quiz Number 5Part 1, pp. 55-67Section A
MT75Exercise Sheet 6Solutions 6No Quiz: ASSIGNMENT Part 1, pp. 68-76Section A
MT86Exercise Sheet 7Solutions 7No Quiz: ASSIGNMENTPart 1, pp. 76-80Section A
MT97Exercise Sheet 8Solutions 8Quiz Number 8Part 2Sections A & D
MT108Exercise Sheet 9Quiz Number 9Part 3Section B
LT19Exercise Sheet 10Solutions 10 No QuizPart 4, pp. 1-24Section C & D & E
LT210Exercise Sheet 11Solutions 11Quiz Number 11Part 4, pp. 24-30Section C & D & E
LT311Exercise Sheet 12Solutions 12Quiz Number 12Parts 5 & 6Section C & D & E
LT412Exercise Sheet 13Solutions 13Quiz Number 13Part 6, pp. 1-10Section C & D & E
LT513Exercise Sheet 14Solutions 14Quiz Number 14Part 6, pp. 10-17Section C & D & E
LT614Exercise Sheet 15Solutions 15Quiz Number 15Part 6, pp. 17-28Section C & E
LT715Exercise Sheet 16Solutions 16Quiz Number 16Part 7Section C & E
LT816Exercise Sheet 17Solutions 17Quiz Number 17Part 8, pp. 1-4Section C & E
LT917Exercise Sheet 18Solutions 18Quiz Number 18Part 8, pp. 4-12Sections C & D & F
LT1018Exercise Sheet 19Solutions 19No Quiz: Assignment Parts 9 & 10, pp. 1-7Sections D & F
ST119Exercise Sheet 20Solutions 20No QuizPart 10, pp. 8-18Section F
ST220RevisionN/ANo Quiz: AssignmentParts 1-10Sections A-F

If you are not sure when your class is you should consult the official LSE Timetable.

## Lecture Notes

The lecture notes for the course can be found on Moodle and are divided into 10 parts. You can access all of them below:

## Lecture Slides

Although Slides are important, especially when you miss a lecture, they are not a substitute for the Lecture Notes! Nevertheless, you can access the slides for all lectures that have already been delivered below.

## Past Exam Papers

The course has not changed much in the last years so the exercises contained in most of the past exam papers are indicative to what you should expect from this year's exam. However, you should be careful that the structure of the final exam has changed in 2012 (the Mock Exam below follows the new format). Some past exams have solutions. The majority do not and will not be provided; however, we encourage you to come to us with any questions you may have.

## Practice Exercise Sets

In addition to the exercises in the Lecture Notes, the weekly assignments and the past exam papers, there are four extra sets of exercises available to you.

## Office Hours

All class teachers hold weekly office hours during term time in LAK 1.02. Appointments can be booked via LSE4U by clicking on the button above. (NB: Georgios's office hours are walk-in only)

Camilla ColomboTuesday 15:00-16:00 LAK.1.02C.F.Colombo-at-lse.ac.uk
Goreti FariaTue 11:00-12:00 LAK.1.02M.G.Faria-Da-Costa-at-lse.ac.uk
Alex MarcociFriday 14:00-15:00
Friday 17:00-18:00
LAK.1.02A.Marcoci-at-lse.ac.uk
James NguyenFriday 11:00-12:00
Friday 16:00-17:00
LAK.1.02J.Nguyen1-at-lse.ac.uk
Georgios ZourosThursday 11:30-13:30 LAK.1.02G.Zouros-at-lse.ac.uk

## Prerequisites

There are no prerequisites for this course. Students are not assumed to have any background in Logic, Mathematics or in Critical Thinking/Thinking Skills.

## How to study for the course

Preparing for Lectures
##### Before a Lecture:
• have a first look at the Lecture Notes pertaining to the new lecture.
##### During a Lecture:
• concentrate on understanding the lecture and take notes directly on the slides.
• attendance will not be taken during lectures, but it is expected you will attend all lectures.
##### After a Lecture:
• you can watch a recording of the lecture via Echo, but be mindful that recording equipment frequently breaks down!
• carefully read the relevant section of the Lecture Notes and make sure you now understand all the claims.
• prepare questions for the classes.
Preparing for Classes
##### Before a Class:
• read again the relevant section of the Lecture Notes.
• submit the Moodle Quiz (before midnight on the previous Sunday).
##### During a Class:
• ask any questions that came up during the lecture.
• compare your solutions to those presented and in case they differ then make sure you understand why. Not all differences are mistakes! Also you may have reached the correct answer for the wrong reason. Justification matters!
##### After a Class:
• contact your class teacher with any unanswered questions you may have.
• after a few days re-attempt all exercises and compare your answers to the solution sheet. If there are any problems contact your class teacher.

## How to prepare for the exam

1. Read the Lecture Notes Sections 1 to 10.
2. Solve all the exercises discussed in the Lecture Notes.
3. Redo all the exercises from the weekly exercise sheets.
4. Solve all the self-study exercises (Exercise Sets A to D).
5. Solve the mock exam.
6. Solve all the past exam papers: 2004, 2005 and 2007-2014.
7. Attend all revision sessions if you have questions.
8. Finally go to your class teacher with any questions that remain.

## What to do should you be in trouble

If you do find that you are struggling to understand something, it is important to sort it out quickly. Here are the steps you should take:

1. Raise the issue in class and ask for clarification.
2. If you are still unclear then do any of the below: contact your class teacher:
3. Of course, you are always welcome in John's office hours.

## Glossary of terms

This Glossary has been put together by Seamus Bradley. You can download the .pdf version directly from Seamus's website, together with his recommendations for further reading (note, however, that Seamus is using a slightly different notation).

We are using p, q, r for sentences, P, Q, R for predicates and Γ, Δ, Θ for sets. I also use wedge (∧) to denote conjunction instead of ampersand (&).

 Also known as the Sheffer stroke. “One or other of the sentences is False.” p|q or p ↑ q. Equivalent to ¬(p ∧ q). All other connectives can be written using only alternative denial. First half of a conditional. The “p” in p → q "p, q, r…” The smallest units of meaning in propositional logic. The building blocks of logic. Also called “propositional variables” or “elementary sentences” “If and only if”, sometimes shortened to “Iff”. p ↔ q Γ or Γc. The set of things not in Γ Sentence composed of several atomic sentences connected by logical connectives (p → q) ∧ (¬r ∨ q) This sentence is in fact a conjunction. One of its conjuncts is a disjunction and the other is a conditional. The final sentence of an inference. The end point of an argument compound sentence of the form “If …then …” e.g. p → q A useful proof rule. We assume “for the sake of argument” that p. If, from this, we can prove q, then we can conclude p → q without the assumption, p. Either half of a conjunction An “and” sentence. p ∧ q Second half of a conditional The “q” in p → q A sentence or set of sentences is consistent if they can all be True together. In propositional logic this means that there is a Truth value assignment that makes all the sentences True. In predicate logic this means there is a model of the sentences A placeholder standing for some unspecified but determinate individual A sentence whose truth-value can be both True or False depending on the truth values of the atoms is contingent. It is a sentence that is neither a tautology nor a contradiction. A sentence that is always false; regardless of the truth-values assigned to the atomic sentences. Its negation is a tautology. A counterexample to an inference is something that shows that the inference is invalid. In propositional logic a counterexample is a Truth value assignment that makes the premises True but the conclusion False. In predicate logic, a counterexample to the inference from premises Δ to conclusion σ is a model of Δ ∪ {¬σ} Either half of a disjunction An “or” sentence. p ∨ q A special case of tautological implication: gets us from ¬p, p ∨ q to q The Domain of an interpretation tells you what things the interpretation is about. If the domain were “Animals” then the quantifier “∀x” would be interpreted as meaning “for all animals” a ∈ q: “a is an element of q”, “a is a member of q” A proof rule that allows us to deduce ∃xPx from Px or from Pa. The rule allows us to introduce an existential quantifier “There exists” ∃ A proof rule that allows us to conclude Pα from premise ∃xPx. This rule allows us to eliminate an existential quantifier A sentence σ is independent of a set of sentences Δ when the inference from Δ to σ is invalid and so is the inference from Δ to ¬σ The logical structure of an argument. An inference starts with some premises and arrives at some conclusion An interpretation gives meaning to a sentence of predicate logic by assigning to each predicate a property and to each constant the name of an individual Γ ∩ Δ. The set of things in both Γ and in Δ An inference is invalid if there exists a counterexample to it “Both sentences are false” p ↓ q. Equivalent to ¬(p ∨ q). Like alternative denial, all connectives can be written using only joint denial Those symbols used to connect atomic sentences into more elaborate constructions.  ∧ ,  ∨ ,  → ,  ↔ … A sentence is logically false/true if it is false/true in every interpretation. A bit like a contradiction/tautology but for predicate logic. An interpretation of a set of sentences that makes all those sentences True A special case of tautological implication: gets us from p, p → q to q A special case of tautological implication: gets us from p → q, ¬q to ¬p P, Q, R… a letter that stands for a some property. Read “Pa” as meaning “individual a has property P” the formal system that replaces the atomic sentences of propositional logic with predicates, constants and variables and augments the language with quantifiers The starting point of an argument or inference A list of sentences that starts with 0 or more premises and ends with a conclusion Something that justifies a particular step in a proof The formal system that consists only of atomic sentences and logical connectives Something like “for all x” ∀x or “for some x” ∃x A special case of tautological implication: allows us to get from p → (q ∧ ¬q) to ¬p Γ ⊆ Δ: Γ is a subset of Δ if every element of Γ is also an element of Δ A sentence that is always true; regardless of the truth-values assigned to the atomic sentences. Its negation is a contradiction. A proof rule that allows you to conclude q from p1, p2…pn if (p1 ∧ p2… ∧ pn) → q is a tautology A Truth value assignment assigns to each atomic sentence a Truth value Γ ∪ Δ The set of things that are either in Γ or in Δ (or possibly both) A proof rule that gets you from Px to ∀xPx. This rule allows us to introduce a universal quantifier. Handle with care! Always read the small print “For all” ∀x A proof rule that gets you from ∀xPx to Px or to Pa or to Pα. The rule that allows us to eliminate a universal quantifier A placeholder standing for an individual An inference is valid if there is no counterexample to it. That is, if the Truth of the premises guarantees the Truth of the conclusion

If you think we are making use of other concepts which should be added to this glossary, let Alex know.

## Glossary of Distinguished Equivalences

The table below lists some of the most important equivalences which you will have to make use of in this course. You can also use any of these equivalences as instantiations of the rule of Tautological Implication. Note that the notation is slightly different from your lecture notes: conjunction is here denoted by the wedge (∧) instead of the ampersand (&). If you have doubts about any of these equivalences we encourage you to construct the appropriate truth table.

 p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p ¬¬p ≡ p (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p → (q ∧ ¬ q) ≡ ¬p p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∧ q) ≡ ¬p ∨ ¬q p ∨ q ≡ ¬(¬p ∧ ¬q) p ∧ q ≡ ¬(¬p ∨ ¬q) ¬(p → q) ≡ p ∧ ¬q p → q ≡ ¬p ∨ q p → (q → r) ≡ (p ∧ q) → r p → q ≡ ¬q → ¬p p → (q ∨ r) ≡ (p ∧ ¬q) → r p ↔ q ≡ (p → q) ∧ (q → p) p ↔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p) p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) ¬(p ↔ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q) p ∧ q ≡ ¬(p → ¬q) (p → q) ∧ (p → r) ≡ p → (q ∧ r) (p → r) ∧ (q → r) ≡ (p ∧ q) → r (p → q) ∨ (p → r) ≡ p → (q ∨ r) (p → r) ∨ (q → r) ≡ (p ∨ q) → r

In PH101 you only get a glimpse of what logic is. If you wish to explore further there are many excellent logic books on the market, and even some free ones available online. However, in consulting these you should keep in mind that every book is taking a different approach to logic and, more importantly, uses a different notation. For the PH101 exam you are not required to consult any of the below: the exam will test you on the way we have done things in the lectures, classes and, most importantly, in the Lecture Notes!

## Introductory Textbooks

Ian Chiswell and Wilfrid Hodges. Mathematical Logic. Oxford University Press, 2007. Introductory and accessible textbook also introducing key theorems.

Graeme Forbes. Modern Logic. Oxford University Press, 1994. The book I used in my very first logic course. Accessible and easy to use. Additional resources available here (includes, solutions, errata and software).

L.T.F. Gamut. Logic, Language, and Meaning. University of Chicago Press, 1991. Wide ranging, approachable, two volume textbook also covering modal logic and applications to linguistics.

Gary Hardegree. Symbolic Logic: A First Course. Mcgraw-Hill, 2011. Accessible introductory textbook with detailed solutions to exercises.

Colin Howson. Logic with Trees. Routledge, 1997. Similar in treatment with your lecture notes and contains a detailed presentation of semantic trees.

P.D. Magnus. forall x. Online. Introductory and very accessible textbook, similar in spirit to your Lecture Notes. Adapted to the Cambridge syllabus by Tim Button.

David Makinson. Sets, Logic and Maths for Computing. Springer, 2008. Introductory and accessible textbook also covering elementary mathematical reasoning. Currently used in PH217.

Patrick Suppes. Introduction to Logic. Van Nostrand Reinhold Company, 1957. Classic textbook, closest in treatment with your lecture notes. Currently available from Dover.

Paul Tomassi. Logic. Routledge, 1999. Accessible introductory textbook similar in spirit to your Lecture Notes. Also covers semantic trees.

George Boolos, John Burgess and Richard Jeffrey. Computability and Logic. Cambridge University Press, 1974. Standard textbook covering a lot of ground, including computability.

Peter Cameron. Sets, Logic and Categories. Springer, 1998. Accessible introduction to set theory and logic. Currently used in PH217. Solutions to exercises in chapters 1 | 2 | 3 | 4 and errata.

Dirk van Dalen. Logic and Structure. Springer, 1980. Introductory but mathematically sophisticated textbook also covering second-order and intuitionistic logic.

Keith Devlin. The Joy of Sets. Springer, 1993. Standard and approachable introduction to set theory. Do not read without the errata.

H. Ebbinghaus, J. Flum and W. Thomas. Mathematical Logic. Springer, 1996. Detailed survey of propositional and first-order logic also covering second-order logic, computability and model theory.

Herbert Enderton. A Mathematical Introduction to Logic. Harcourt, 1972. Standard textbook providing a detailed but approachable introduction to logic.

Paul Halmos. Naive Set Theory. Springer, 1960. Classic and approachable introduction to set theory. Currently used in PH217.

Wilfrid Hodges. Elementary Predicate Logic. In D. Gabbay and F. Guenthner. Handbook of Philosophical Logic, Volume 1. Springer, 2010. One of the most detailed surveys of first-order logic.

Elliott Mendelson. Introduction to Mathematical Logic. Chapman & Hall, 1964. Standard textbook introducing the basics and covering the most important results. Mathematically sophisticated.

## Logic for Philosophy

John Burgess. Philosophical Logic. Princeton University Press, 2012. Concise introduction to several systems, striking a good balance between philosophical motivations and technical details.

Lou Goble (ed.). The Blackwell Guide to Philosophical Logic. Wiley-Blackwell, 2001. Good survey of the landscape of logical systems, especially First and Second-Order Logic. Focus on philosophical applications.

Lloyd Humberstone. The Connectives. MIT Press, 2011. A tour de force in philosophical logic, covering more topics than any book in this selection. For the dedicated student.

Richard Kirkham. Theories of Truth: A Critical Introduction. The MIT Press, 1995. Standard introduction to theories of truth covering both the Liar paradox and Tarski's theory. Mostly philosophical.

Graham Priest. An Introduction to Non-Classical Logic. Cambridge University Press, 2008. Introduces many of the most philosophically salient logical systems. Both technical details and philosophical applications are covered.

Theodore Sider. Logic for Philosophy. Oxford, 2010. Survey of several systems of logic with applications to philosophical problems. Currently used in PH217. Errata

Douglas Hofsadter. Gödel, Escher, Bach. Basic Books, 1979. Currently available from Penguin. A captivating book about self-reference and recursion, winner of the Pulitzer prize.

Anita Feferman. From Trotsky to Gödel. A. K. Peters, 2000. Biography of Jean van Heijenoort, personal secretary of Trotsky, mathematical logician, editor and translator of several reference works in logic.

Apostolos Doxiadis and Christos Papadimitriou. Logicomix. Bloomsbury, 2009. Illustrated life of Bertrand Russell and the beginnings of modern logic. Short and entertaining.

Martin Gardner. My Best Mathematical and Logic Puzzles. Dover, 2003. The book series this is published in says it all: "Recreational Math."

Raymond Smullyan. What is the Name of This Book? Dover, 2011. Another title in Dover's "Recreational Math" series.

Raymond Smullyan. Forever Undecided. Oxford, 1988. An introduction to Gödel's theorems through logical puzzles.

Finally, when in doubt the first two ports of call should be the Stanford Encyclopedia of Philosophy (for philosophical problems) and Wikipedia (for technical problems). Despite the constant criticism of Wikipedia in academic circles, so far I have had only very good experiences with Wikipedia pages on mathematical and logical notions.

Many to thanks David Makinson, Seamus Bradley and James Nguyen for all of their excellent recommendations.

## You successfully passed the PH101 exam, what next?

The Department offers an advanced logic course, PH217 Set Theory and Further Logic taught by Miklós Rédéi (Set Theory, Michaelmas Term) and David Makinson (Further Logic, Lent Term). In 2014-2015 David Makinson will teach both parts of the course. PH101 is not a prerequisite for taking PH217 but it does provide you with the necessary basics. However, be mindful that:

1. The first part of PH217 is Set Theory. We only address set theory very briefly in the last two weeks (Exercise Sheets 20 and 21) and in Part 10, pp. 8-18 of the Lecture Notes. Being comfortable with the material we discuss there is necessary for PH217 but not sufficient. Therefore, before deciding to enrol, I recommend you consult the textbook currently used for the Set Theory part of that course, i.e. Makinsons's (2nd edition, 2012) Sets, Logic and Maths for Computing, chapters 1 to 4 - see Further Readings.
2. The second part of PH217 is Logic. You will go through the basics of propositional and first-order logic in a more mathematically precise way and at a much higher pace. Then you will prove some main classic theorems (e.g. completeness, which is briefly discussed in Part 5 , p. 3 of the Lecture Notes). Further you will learn about Gödel's Incompleteness Theorems and study some elementary Modal Logic. These are not covered in our course and you may want to consult the textbook used for the second part of PH217, i.e. Sider's Logic for Philosophy, chapters 1, 2, 4, and 6 - see Further Readings.
3. In PH101 we do very few and simple proofs (The Disjunctive Normal Form Theorem and other small results). However, in PH217 you will be required to follow, and in some cases be able to reproduce, more sophisticated proofs from set theory and first-order and propositional modal logic, as well as construct simple proofs of your own. This should not deter you from taking the course, but you should be confident in your formal abilities before doing so.

If you are still unsure whether you should enrol in PH217, I am happy to discuss it further with you (even if you are no longer my student). Of course, you are encouraged to (also) approach the course conveners.

## Philosophy of Logic

The LSE is not currently offering a course in either philosophy of logic or philosophical logic. Nevertheless, if you enjoyed PH101, you may want to reflect more on what you have learned so far. Here are some problems to provoke your philosophical curiosity.

##### What are logical constants?

In virtue of what are some symbols logical and others not? Logical symbols seem to be insensitive to the identity of objects. Alfred Tarski suggests that the logical symbols in an interpreted language are those whose meaning is invariant under permutations on the domain of objects.

What determines the meaning of a logical symbol? How about the rules governing its use in inference-making? Its introduction and elimination rules. Arthur Prior formulates introduction and elimination rules for a new connective, TONK, with devastating consequences: everything will be derivable from everything.

##### What did the Tortoise say to Achilles?

Lewis Carroll thinks the Tortoise challenged Achilles to produce the reason in virtue of which if she accepts the premises of a valid argument she is compelled to accept the conclusion.

##### Is Modus Ponens reliable?

Many classically valid inferences are questionable. But modus ponens seems to be a bedrock of reliable reasoning. Van McGee devises some plausible counterexamples.

##### Forever undecided
Can we ascertain about any first order formula whether it is provable (or true under all possible interpretations)? Alonzo Church reached a disturbing conclusion: no!

##### Reaching the limits

First-Order Logic cannot express basic mathematical notions such as "finitude" and "countability." Higher-order logics are more expressive. Stewart Shapiro goes Second-Order.

##### Is logical empirical?
Quine famously claimed that principles of logic are revisable when confronted with the tribunal of experience. Hilary Putnam suggests that Classical logic should be replaced by Quantum Logic.

##### Is there a One True Logic?

Nonmonotonic, intuitionistic and classical systems answer differently to the question: "Is argument X valid?" Does that mean that there is no unique answer? J.C. Beall and Greg Restall make the case.

##### Can there be paradox without self-reference?

Stephen Yablo found one.

##### Beyond ∃ and ∀
Why are ∃ and ∀ privileged? How about "at least 2" or "the majority"? Stanley Peters and Dag Westerstähl investigate.

There is a rich literature on all of these and I only direct you to the most influential paper or book on each topic and the most relevant section of the Stanford Encyclopedia of Philosophy . If you are interested in reading more, do contact me.

## Smullyan's three gods

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for "yes" and "no" are "da" and "ja," in some order. You do not know which word means which.

➥ Boolos calls this the Hardest Logical Puzzle Ever. Give it your best shot! Afterwards you can read Boolos's solution here. A more recent take on the puzzle is due to Rabern and Rabern with a proposed solution by Uzquiano. I also encourage you to read more of Smullyan's puzzles (see Further Readings).

## When is a set small?

I want to classify all subsets of {1, 2, 3, . . .} as small or large, such that any set with zero or one member is small; any union of two small sets is small; and a set is small if and only if its complement is large. Does there exist a classification scheme satisfying all three rules?

➥ Consider the following possible meanings small might be assigned: "finite," "not containing 1," and "containing at most one element from the set {1,2,3}." Do any of these satisfy all three rules? Read Eric Schechter's explanation of why such a scheme exists and consult Chapter 5 of his book for the technical details.

## How did the error in Lésniewski's theorem enter modern logic?

G. A. Cohen explains in the words of Alfred Tarski:

## How to book a room in Hilbert's Hotel?

The German mathematician, David Hilbert came up with this thought experiment to help you grasp the depths of infinity:

## Achilles and the Tortoise

Before asking Achilles about the foundations of deduction, the Tortoise challenged the hero to a race. This Zeno's commentary:

## The distance between two primes

In our interpretations we keep referring to numbers 'being prime'. Here is a fascinating recent result on the distance between two primes due to Yitang Zhang.