Skip to content

Lecture Notes 11/14 – 11/30

Lecture Notes 11/14 – 11/30 (the dynamical systems approach to Ramsey theory) are available.

Final Exam Preparation

Here are the preparation pages for the final exam.

Lecture Notes 11/09

Lecture Notes 11/04 – 11/09 (the Paris-Harrington Theorem) are available.

Homework 11

Homework 11, the final homework set, is now available and is due 12/05.

Solutions to HW 10 are also available.

Lecture Notes 11/02

Lecture Notes 11/02-11/09 (Basic facts about first-order logic) are available.

Hints Homework 10

Problem 2

As we saw in class, you can define the {\leq} relation using the formula {\varphi(x,y) \equiv \exists z ( x+z =y)}. Furthermore, given any number {n \in {\mathbb N}}, we can represent it as {\underline{n} = S(S \dots S(\underline{0}))}, where we apply {S} {n}-times.

Now show that {\mathsf{PA} \models \forall x ( \underline{0} < x \; \Rightarrow \underline{1} \leq x)}.

Problem 3

For any specific finite number {n}, you can find a formula that says: “There exist exactly {n} distinct elements”.

Problem 4

One direction is trivial. For the other direction, use the completeness theorem. Argue that a theory {T} is consistent if and only if it has a model. Then use the fact that proofs are finite, in particular can use at most finitely many formulas.

Problem 5

Extend the language of arithmetic by a new constant symbol {\underline{c}}. Add sentences of the form {\underline{0} < \underline{c}}, {\underline{1} < \underline{c}}, {\underline{2} < \underline{c}}, … to {T_{\mathbb N}}. Apply the compactness theorem.

Homework 10

Homework 10 (due 11/14) is available.