PH217/PH419 - Set Theory and Further Logic
Information on the 2023 Summative Assessment
This year, the examination for PH217/PH419 will be moving to a "seen" format. This
means that students will be asked to answer questions in the examination that they have
seen in advance.
The exam will be sat in the Summer Term, in person, and will last three hours.
Candidates will be asked to answer FOUR questions.
Only four questions will be set. This means that candidates will have no choice
as to which questions to answer. However, the four questions will all be drawn from
a list of TWENTY possible questions, published in advance of the exam. This means
that candidates who prepare answers for all twenty questions will be guaranteed to have
practised all the questions on the exam.
The twenty possible exam questions are listed below. In the exam, two questions
will be asked on set theory (from Part A), and two on further logic (from Part B).
For questions about the exam, please contact the teacher responsible (Wes Wrigley).
Important Update: Due to the strike action affecting this course, the following
questions will not be asked in the exam: 8, 14, 15, 17, 18.
PART A: Set Theory
1. A What is the naive comprehension principle? Show how to derive Russell’s
paradox from it.
B What is the axiom of specification? Explain why your argument in part A.
does not work if we replace the naive comprehension principle with the axiom
of specification.
C “Russell’s paradox is not a genuine paradox. It is simply a theorem to the
effect that there is no set of a certain kind”. Do you agree with this statement?
If so, why, and if not, why not?
2. A Define the following notions: binary relation, equivalence relation, partition.
B State and prove the equivalence relation theorem.
C Outline a set-theoretic construction of a structure isomorphic to the integers
under their standard order with the operations of addition and multiplication.
3. A Define the following notions: |X| ≤ |Y |, |X| = |Y |.
B Prove the following for any sets X, Y, Z:
(i) |X| = |X|.
(ii) If |X| ≤ |Y | and |Y | ≤ |Z| then |X| ≤ |Z|.
(iii) If |X| ≤ |Y | and |Y | ≤ |X| then |X| = |Y |.
C Comment on the importance of these properties for the notion of cardinality.
4. A Define the following notions: Dedekind infinite, Peano infinite, at most count-
able.
B Prove that any set is Dedekind infinite if and only if it is Peano infinite.
C Show that a non-empty set is at most countable if and only if there is an injec-
tion from X to N and a surjection from N to X.
5. A Define the following notions: countable, uncountable.
B Prove that the Cartesian product of two countable sets is countable, and that
the union of a countable family of countable sets is countable.
C Prove that the set of all finite subsets of N is countable, and that |N| is the
smallest infinity.
6. A Use a diagonal argument to show that |N| < |R|.
B Prove that for all sets X , |X| < |P(X)|.
C Precisely state the continuum hypothesis, and define the notion of an inacces-
sible cardinal. Comment briefly on the status of these notions in set theory.
7. A Define the following notions: strict partial order, linear order, well-order.
B State and prove the transfinite induction principle.
C Prove that there is at most one isomorphism between any two well-ordered
sets. You should prove any lemmas referred to in the proof.
8. A Define the following notions: well-order, section, ordinal.
B Prove that any section of an ordinal is an ordinal, and if an ordinal α is a subset
of an ordinal β, then α is a section of β.
C Prove that for any two distinct ordinals, one is a section of the other.
9. A Define the following notions: ordinal, successor ordinal, limit ordinal.
B Prove that for any ordinals α and β, α ∈ β if and only if α ⊂ β if and only if
α < β.
C Prove the either-or Theorem for the ordinals.
10. A Precisely state the axiom of choice, Zorn’s lemma, and the well-ordering prin-
ciple.
B Prove that the well-ordering principle implies the axiom of choice, and vice-
versa.
C Critically discuss whether we should accept or reject the axiom of choice.
PART B: Further Logic
11. A Define what it is for a deductive system for sentential logic to be strongly
sound with respect to its semantics. State a Hilbert-style deductive system for
classical sentential logic.
B Prove that this deductive system is strongly sound.
C State and prove the deduction theorem for classical sentential logic.
12. A Define what it is for a set of CSL sentences Γ to be maximally consistent.
Show that if Γ is a maximally consistent set of sentences and φ is a sentence,
exactly one of φ or ¬φ is a member of Γ. From this, prove that (φ→ ψ) ∈ Γ
if and only if φ 6∈ Γ or ψ ∈ Γ.
B Prove that any consistent set of CSL sentences is a subset of a maximally
consistent set of CSL sentences.
C Show that for every maximal consistent Γ, there is a valuation v+ such that for
all φ, φ ∈ Γ if and only if v+(φ) = 1. Deduce the completeness theorem for
sentential logic.
13. A Two standard axiom schemata for the universal quantifier are ∀vφ → φ[t/v]
and ∀v(φ→ ψ)→ (φ→ ∀vψ). Carefully state the proviso on the use of each
of these, defining any technical terminology you use. For each proviso, give
an example of what could go wrong if we omitted the proviso.
B State the UG inference rule. Demonstrate using a counterexample that Fx→
∀xFx is not a logical truth of first order logic. Given your counterexample,
carefully explain why the UG rule is nonetheless legitimate.
C Carefully outline the differences between the substitutional and x-variant se-
mantics for the universal quantifier. Critically reflect on whether one method
is preferable to the other.
14. A Define what it is for a deductive system for classical predicate logic to be
strongly complete with respect to its semantics.
B Give a sketch of Henkin’s proof that every consistent set of sentences in pred-
icate logic is true in a structure.
C From this, deduce the strong completeness of classical predicate logic.
15. A Prove that classical predicate logic is compact. You may assume that it is
strongly complete.
B Deduce that the quantifier finitely many cannot be expressed in predicate logic.
C Is it desirable that our logical system be compact, or complete?
16. A State the Downward Löwenheim-Skolem Theorem.
B What is Skolem’s paradox? Is it genuinely a paradox? Justify your answer,
and clearly state any technical details your argument relies on.
C Does Skolem’s paradox show that the notion of uncountability is relative?
Would it be a problem for set theory if some of its core notions were relative
in this sense?
17. A Define the notion of a first-order structure and a variable assignment over it.
Define what it is for a formula to be true in a structure.
B State and prove Tarski’s theorem on the undefinability of truth. You should
prove the inexpressibility lemma if your argument relies upon it.
C In part A of this question, you showed how to define the notion of truth for
a formal language. In part B of this question, you showed that the notion of
truth could not be defined for some particular formal language. Write a short
essay on how these two facts can be reconciled.
18. A Let T be a first-order theory with intended model M .
(i) Define consistency and negation-completeness for T , and also soundness
and completeness of T with respect to M .
(ii) Why does soundness of T with respect to M imply its consistency, and
completeness of T with respect to M imply its negation-completeness?
(iii) Why should we not in general expect the converses of the statements you
proved in A.ii?
(iv) Show that, however, consistency together with completeness does imply
soundness.
B (i) Define the notion of ω-consistency for first-order arithmetic.
(ii) Show that the soundness of first-order arithmetic with respect to its in-
tended model implies its ω-consistency.
(iii) Show that the ω-consistency of the theory implies its consistency.
C State the axioms of Robinson Arithmetic. Prove that Robinson Arithmetic is
not negation-complete.
19. A What does it mean to say that a set of natural numbers is expressible in the
language of first-order Peano arithmetic?
B Outline Gödel’s “Master Argument” for his first incompleteness theorem (se-
mantic version).
C Comment on the strengths and limitations of the Master Argument compared
with the “official” proof published by Gödel.
20. A Give a clear statement of Gödel’s second incompleteness theorem. Sketch its
proof.
B What is Hilbert’s programme in the foundations of mathematics?
C Write an essay discussing whether Gödel’s second incompleteness theorem
shows that Hilbert’s programme cannot be carried out.