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

Some links will only become active later in the term so only contact us about broken links if you think you should already be able to see the hyperlinked files.

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 book an appointment

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)

Class TeacherOffice HourLocationEmail Address
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.
  • print/download the lecture slides from Moodle.
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).
  • download/print the exercise sheet and attempt all exercises.
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 (&).

Alternative denial

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.

Antecedent

First half of a conditional. The “p” in p → q

Atomic sentence

"p, q, r” The smallest units of meaning in propositional logic. The building blocks of logic. Also called “propositional variables” or “elementary sentences”

Biconditional

“If and only if”, sometimes shortened to “Iff”. p ↔ q

Complement

Γ or Γc. The set of things not in Γ

Compound sentence

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.

Conclusion

The final sentence of an inference. The end point of an argument

Conditional

compound sentence of the form “If …then …” e.g. p → q

Conditional Proof

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.

Conjunct

Either half of a conjunction

Conjunction

An “and” sentence. p ∧ q

Consequent

Second half of a conditional The “q” in p → q

Consistency

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

Constant

A placeholder standing for some unspecified but determinate individual

Contingent

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.

Contradiction

A sentence that is always false; regardless of the truth-values assigned to the atomic sentences. Its negation is a tautology.

Counterexample

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 Δ ∪ {¬σ}

Disjunct

Either half of a disjunction

Disjunction

An “or” sentence. p ∨ q

Disjunctive syllogism

A special case of tautological implication: gets us from ¬p, p ∨ q to q

Domain

The Domain of an interpretation tells you what things the interpretation is about. If the domain were “Animals” then the quantifierx” would be interpreted as meaning “for all animals”

Element

a ∈ q: “a is an element of q”, “a is a member of q

Existential generalisation

A proof rule that allows us to deduce xPx from Px or from Pa. The rule allows us to introduce an existential quantifier

Existential quantifier

“There exists”

Existential specification

A proof rule that allows us to conclude Pα from premise xPx. This rule allows us to eliminate an existential quantifier

Independence

A sentence σ is independent of a set of sentences Δ when the inference from Δ to σ is invalid and so is the inference from Δ to ¬σ

Inference

The logical structure of an argument. An inference starts with some premises and arrives at some conclusion

Interpretation

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

Intersection

Γ ∩ Δ. The set of things in both Γ and in Δ

Invalid

An inference is invalid if there exists a counterexample to it

Joint denial

“Both sentences are false” p ↓ q. Equivalent to ¬(p ∨ q). Like alternative denial, all connectives can be written using only joint denial

Logical connective

Those symbols used to connect atomic sentences into more elaborate constructions.  ∧ ,  ∨ ,  → ,  ↔ …

Logically False/True

A sentence is logically false/true if it is false/true in every interpretation. A bit like a contradiction/tautology but for predicate logic.

Model

An interpretation of a set of sentences that makes all those sentences True

Modus ponens

A special case of tautological implication: gets us from p, p → q to q

Modus tollens

A special case of tautological implication: gets us from p → q, ¬q to ¬p

Predicate

P, Q, R a letter that stands for a some property. Read “Pa” as meaning “individual a has property P

Predicate logic

the formal system that replaces the atomic sentences of propositional logic with predicates, constants and variables and augments the language with quantifiers

Premise

The starting point of an argument or inference

Proof

A list of sentences that starts with 0 or more premises and ends with a conclusion

Proof rule

Something that justifies a particular step in a proof

Propositional logic

The formal system that consists only of atomic sentences and logical connectives

Quantifier

Something like “for all xx or “for some xx

Reductio ad absurdum

A special case of tautological implication: allows us to get from p → (q ∧ ¬q) to ¬p

Subset

Γ ⊆ Δ: Γ is a subset of Δ if every element of Γ is also an element of Δ

Tautology

A sentence that is always true; regardless of the truth-values assigned to the atomic sentences. Its negation is a contradiction.

Tautological implication

A proof rule that allows you to conclude q from p1, p2pn if (p1 ∧ p2… ∧ pn) → q is a tautology

Truth value assignment

A Truth value assignment assigns to each atomic sentence a Truth value

Union

Γ ∪ Δ The set of things that are either in Γ or in Δ (or possibly both)

Universal generalisation

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

Universal quantifier

“For all” x

Universal specification

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

Variable

A placeholder standing for an individual

Valid

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

Further readings

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!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Mendelson

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

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

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

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

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

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

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

Hofsadter

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.

Feferman

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.

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

Gardner

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

Smullyan

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

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

Tarski
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. SEP

Prior
The runabout inference ticket

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

Dodgson
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. SEP

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

Church

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! SEP

Shapiro
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. SEP

Putnam

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

Beall&Restall
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. SEP

Yablo
Can there be paradox without self-reference?

Stephen Yablo found one. SEP

Quantifiers

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

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 SEP. If you are interested in reading more, do contact me.

Smullyan's three gods

HardestProblem

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?

SmallSet

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.