# HW19

Exercises

(not today)

Supplemental problems

1. $\star$ Show that $2$ is not definable in $(\QQ,+)$.
2. $\star\star$ Kunen, exercise II.15.5.
3. $\star\star\star$ Show that + is not definable in $(\NN,s)$, where $s(n)=n+1$ denotes the successor function.
4. $\star\star\star$ Is the ordering $<$ definable in $(\QQ,+,\times)$?

# HW18

Exercises (due Wednesday, April 23)

1. Show that the class of all finite graphs is not first-order axiomatizable (that is, there is no theory $\Sigma$ such that the models of $\Sigma$ are exactly the finite graphs).
2. Show that the class of all infinite graphs is not finitely axiomatizable (that is, there is no finite theory $\Sigma$ such that the models of $\Sigma$ are exactly the infinite graphs).

Supplemental problems

1. $\star$ Show that $\RR$ and $\RR\smallsetminus\{0\}$ are not isomorphic as linear orders.
2. $\star\star$ Show that the class of connected graphs is not first-order axiomatizable.
3. $\star\star$ Kunen, exercise II.3.8.
4. $\star\star$ Kunen, exercise II.13.11.
5. $\star\star\star$ Kunen, exercise II.13.12.

# HW17

Exercises (due Monday, April 21)

1. Show that relation defined by $\sigma\sim\tau$ if and only if $\Sigma\vdash\sigma=\tau$ is an equivalence relation.
2. Suppose $\Sigma$ is a complete theory with a finite model. Show that $\Sigma$ does not have any infinite models.

Supplemental problems

1. $\star$ Suppose $\Sigma$ is a complete theory with an infinite model. Can $\Sigma$ have any finite models?
2. $\star\star$ Kunen, exercise II.12.23.
3. $\star\star$ Let TA (true arithmetic) be the theory of the structure $(\NN,+,\cdot,0,1)$. Show that TA has a model $N$ containing $\NN$ and containing elements “larger” than $\NN$.
4. $\star\star\star$ Show that every model of TA (from the previous problem) has a copy of $\NN$ as an initial segment, and that this copy has no supremum.

# HW16

Exercises (due Monday, April 14)

1. Suppose that $P$ is a unary predicate and $Q$ is a propositional variable. Give a formal proof of the following: $(\forall x(P(x)\to Q))\to((\forall xP(x))\to Q)$.
2. Suppose that $R$ and $S$ are unary predicates. Use UG, EI and any other results you like to show there exists a formal proof of the following: $\forall x(R(x)\to S(x))\to(\exists x R(x)\to \exists x S(x))$.
3. Kunen, exercise II.11.16. Suppose $R$ is a binary predicate and use the soundness theorem to show that there does not exist a formal proof of $\forall y\exists x R(x,y)\to\exists x\forall y R(x,y)$.

Supplemental problems

1. $\star$ Show that logical axiom 3 is valid.
2. $\star$ Give an example of a structure $A$ and a formula $\phi(x)$ such that $A\models\exists x\phi(x)$ but there is no term $\tau$ such that $A\models\phi(\tau)$.
3. $\star\star$ Kunen, exercise II.10.6.
4. $\star\star$ Kunen, exercise II.11.15. Give a formal proof from ZF that $\exists y\forall x(x\notin y)$.
5. $\star\star\star$ Kunen, exercise II.11.11.

# HW15

Exercises (due Wednesday, April 9)

1. Show that the fourth structure on page 12 satisfies the formula $\forall x \exists y (yEx \wedge (\exists z) (z\neq x \wedge yEz))$ directly from the definition of $\models$.
2. Find a formula $\phi$ with one free variable $x$ such that $(\RR,+,\cdot)\models\phi[\sigma]$ iff $\sigma(x)=2$.

Supplemental problems

1. $\star$ Show that if $\Sigma$ has an infinite model then $\Sigma$ has an uncountable model.
2. $\star\star$ Kunen, exercise II.7.19.
3. $\star\star$ Complete Exercise 2 with the number $2$ replaced by an arbitrary rational number $a/b$.
4. $\star\star\star$ What are the limits of the previous problem?
5. $\star\star\star$ Kunen, exercise II.7.20.
6. $\star\star\star$ Kunen, exercise II.7.21.

# HW14

Exercises (due Monday, March 31)

1. Give a proof of Lemma II.5.4.
2. Let $L=\{E\}$ where $E$ is a binary relational symbol. Write a set of $L$-sentences $\Sigma$ such that the models of $\Sigma$ are precisely the equivalence relations with exactly $3$ equivalence classes.

Supplemental problems

1. $\star$ Prove that the connectives $\vee$, $\wedge$, and $\leftrightarrow$ can all be defined using only $\neg$ and $\rightarrow$.
2. $\star\star$ Prove that $(\QQ,<)$ is isomorphic to $(\QQ\smallsetminus\{0\},<)$, but that $(\RR,<)$ is not isomorphic to $(\RR\smallsetminus\{0\},<)$.
3. $\star$ Find a formula $\phi$ (in the trivial language) such that every model of $\phi$ has size exactly $5$.
4. $\star\star$ Find a language $L$ and a set of $L$-sentences $\Sigma$ such that for all $n\in\NN$, there is a model of $\Sigma$ if and only if $n$ is even.
5. $\star\star\star$ Prove that any partial order $R$ on a finite set can be extended to a linear order $R’\supset R$ on that set.

# HW13

Exercises (due Wednesday, March 19)

1. Convert the expressions from Polish to standard logical notation.
• $\forall a\forall b\rightarrow=n\times ab\vee =na=nb$
• $\forall a\rightarrow\in aS\leq ab$
2. For each of the following informal mathematical statements, define a Polish lexicon that would allow you to express the statement, and then do so.
• The polynomial $x^4+3x+5$ has a root.
• The number $n$ is the sum of four squares.

Supplemental problems

1. $\star\star$ Kunen, exercise II.4.7
2. $\star\star\star$ Write a computer program that takes a Polish lexicon and string of symbols as input, and determines whether the given string is a well-formed expression.

# HW12

Exercises
(not today)

Supplemental problems

1. $\star$ Kunen, exercise I.15.14.
2. $\star$ Kunen, exercise I.15.15.
3. $\star\star$ (via Andres) Let $S$ be the set of middle-third-intervals removed during the construction of the Cantor set. The elements of $S$ are strictly totally ordered from left to right. Show that $S$ with this ordering is isomorphic to $\QQ$ with its usual ordering.
4. $\star\star\star$ (via Andres) A train carries $\omega$ many passengers. It then passes $\omega_1$ many stations numbered $0,1,\ldots,\omega_1$. At each station one passenger gets off and then $\omega$ many passengers get on. How many passengers remain when the train pulls into the last station?
5. $\star\star\star$ (via Andres) Show in ZF that if there is an injective function
$\omega\to P(X)$ then there is an injective function $P(\omega)\to P(X)$.

# HW11

Exercises
(not today)

Supplemental problems

1. $\star$ Define $+$, $\times$, and $<$ on the rational numbers constructed in class.
2. $\star\star$ Define $+$, $\times$, and $<$ on the real numbers constructed in class.
3. $\star$ If $G_n$ are dense open subsets of $\RR$ then $\bigcap G_n$ is nonempty. [Hint: look up the Baire category theorem.]
4. $\star\star$ IF $G_n$ are dense open subsets of $\RR$ then $\bigcap G_n$ is uncountable and dense.
5. $\star\star$ Kunen, exercise I.15.10 (forget the last sentence).
6. $\star\star$ Kunen, exercise I.15.11 (forget the last sentence).
7. $\star\star$ Kunen, exercise I.15.12 (forget the last sentence).
8. $\star\star\star$ The last sentence of Kunen, exercises I.15.10–11.

# HW10

Exercises (due Monday, March 10)

1. Kunen, exercise I.14.9. If you know the rank of $x$, then what is the rank of $\bigcup x$? (As always, see the text for a more precise problem statement.)
2. For any $\alpha$ the Union axiom holds in $V_\alpha$.
3. If $\alpha$ is a limit then the Pairing axiom holds in $V_\alpha$.

Supplemental problems

1. $\star$ If $\alpha$ is a limit then the Power Set axiom holds in $V_\alpha$.
2. $\star$ If $\alpha$ is a limit and $x,y\in V_\alpha$ and $f$ is a function from $x$ to $y$ then $f\in V_\alpha$.
3. $\star\star$ If $\kappa$ is inaccessible then $|V_\kappa|=\kappa$
4. $\star\star$ Kunen, exercise I.14.14
5. $\star\star$ Kunen, exercise I.14.17
6. $\star\star\star$ Kunen, exercise I.14.19
7. $\star\star\star$ The rest of Kunen, exercise I.14.21. If $\gamma>\omega$ is a limit then $V_\gamma$ is a model of ZC. On the other hand Replacement does not hold in $V_{\omega+\omega}$.
8. You may also attempt any of the other exercises in this section.