Problems to turn in: Please edit the project template to include (a preliminary version of) each of the following. Then, EMAIL me the resulting pdf file or print it our and bring it to class.

• Title
• Section names (the first will be "Introduction," but you should have at least one more section)
• The first 1 or 2 paragraphs of your introduction

Reading: Section 4.2 ...Pay attention to where negations can occur in $\Sigma$- and $\Pi$-formulas!

Problems to turn in: 4.2.1 #1 and the following:

Extra Problem 1. Write down each of the following: a tentative name for your project (this should more detailed that what I have listed on the website); and a 3–5 sentence description of your project, in your own words.

Reading: Section 4.1

Problems to turn in:

Problem 1. Let $\mathbb{R}^*$ denote the hyperreals as constructed in class. Recall that $a\in \mathbb{R}^*$ is infinitesimal if $0< a < r$ for all $r\in \mathbb{R}$. (Also remember that $0< a < r$ is really shorthand for $0< a < c_r^{\mathbb{R}^*}$.)

(a) Using the fact that addition is commutative in $\mathbb{R}$, prove that addition is also commutative in $\mathbb{R}^*$.

(b) Let $a\in \mathbb{R}^*$ be infinitesimal. Prove that the product $100 a$ is also infinitesimal. (You may want to argue by contradiction.)

Reading: Review what we've done so far in the course. Did you have a favorite topic? (...please say yes...) Any lingering questions? Answers to these could be a good starting point for a project, but I have some ideas too.

Problems to turn in: None. (But don't forget the writing assignment.)

Reading: Section 3.3

Problems to turn in:

Problem 1. Let $\mathcal{L}_{Order} = \{< \}$. The axioms for a linear order are as follows.

• $\lambda_1:\equiv (x< y)\vee(x = y) \vee (y< x)$
• $\lambda_2:\equiv \neg(x< x)$
• $\lambda_3:\equiv (x< y)\wedge(y < z) \rightarrow (x< z)$

(a) Give an example of a linear ordering with 4 elements by defining a universe $\mathcal{M}$ and the ordering $<^\mathcal{M}$.

(b) Prove that there does not exist a set of $\mathcal{L}_{Order}$-formulas $\Sigma$ such that $\mathcal{M}\models \Sigma$ if and only if $\mathcal{M}$ is a finite linear order.

Hint: argue by contradiction. Assume such a $\Sigma$ exists; that is, $\mathcal{M}\models \Sigma$ if and only if $\mathcal{M}$ is a finite linear order. Next, enlarge $\Sigma$ to $\widehat{\Sigma}$ by adding in formulas $\alpha_k$ expressing that a model has at least $k$ elements. Now, like we did in class, use Compactness to show $\widehat{\Sigma}$ has a model, and tie it all together. When you use Compactness, you will need to create some finite linear orders, but remember that you are good at creating models (you did that a lot before).

Reading: Start reading Section 3.3

Problems to turn in: None. (But don't forget the writing assignment.)

Reading: Finish Reading Section 3.2

Problems to turn in:

• 2.8.1 #7

  The point: you may feel like the set of axioms $N$ describes the natural numbers $\mathbb{N}$ quite thoroughly, but in fact, $N$ cannot prove may things you know about $\mathbb{N}$, like $x\nleq x$. (By Soundness, this is because $x\nleq x$ is not true in every model of $N$, as you will show in this exercise.)

Reading: Start Reading Section 3.2

Problems to turn in: None

Reading: Read Section 2.8 (this is an important section to read!)

Problems to turn in:

• 2.7.1 #4

  Hint: there is a hint in the back of the book, but if you do use it, please fill in the details and make it your own. Also, like we did in class, you can use $\perp$ in place of $[(\forall x) x = x] \wedge \neg [(\forall x) x = x]$.

• 2.8.1 #2

Reading: Re-read Section 2.7

Problems to turn in:

• 2.7.1 #1, #6

  Note: yes, there is a solution to #6 in the back of the book, but try not to use it. Or, if you do look, try to find a different deduction, perhaps a shorter one.

Reading: Re-read Section 2.5

Problems to turn in:

• 2.5.1 #1

  Clarification: the intention is that you reflect on what Ingrid said in the context of the Soundness Theorem. Does it contradict the Soundness Theorem? Why or why not?

Reading: Read Section 2.5

Problems to turn in:

• 2.4.3 #4, #5

  Hint: there is a hint in the back of the book for #4, but if you choose to look, please make sure to fill in all details. Also, note that by Definition 1.8.2, $\neg(\phi^x_t)$ is the same formula as $(\neg\phi)^x_t$.

Reading: Read Section 2.4

Problems to turn in:

• 1.8.1 #2, #3

  Please prove #3 carefully, using induction on the number of quantifiers/connectives appearing in $\phi$.

Reading: Read Section 2.2

Problems to turn in:

• 1.8.1 #1, #6
• 2.2.1 #1

Reading: Read Section 1.8 and 1.9

Problems to turn in:

• 1.9.1 #4
• And the problem below.

Problem 1. Work in $\mathcal{L}_{NT}$. Consider the following formulas: $$\begin{align} \phi & :\equiv (\forall x)((0< x) \rightarrow(0< S x))\\ \alpha & :\equiv (\forall x)(0 < SS x))\\ \beta & :\equiv (\neg (0 < S 0)) \vee (0< SS 0) \end{align}$$

(a) True or False (and explain): $\phi \rightarrow \alpha$ is logically valid, i.e. $\vDash (\phi \rightarrow \alpha)$.

(b) True or False (and explain): $\phi \rightarrow \beta$ is logically valid, i.e. $\vDash (\phi \rightarrow \beta)$.

Reading: Read Section 2.1

Problems to turn in:

• 1.7.1 #5
• And the problems below.

Problem 1. Let $\mathcal{L} = \{c,g\}$ where $c$ is a constant symbol and $g$ is a unary function symbol. $$\phi :\equiv (\forall x)(\exists y)[(x\neq c)\rightarrow ((y \neq g(x))\wedge (y\neq c))].$$ Prove that there exists an $\mathcal{L}$-structure $\mathcal{M}$ such that $\mathcal{M}\not\vDash \phi$.

Hint: this is similar to 1.7.1 #4. Note that proving $\mathcal{M}\not\vDash \phi$ is the same as proving $\mathcal{M}\vDash (\neg\phi)$. As we saw in class, a good starting point is to carefully "simplify" $\neg \phi$ using rules from an Intro. to Proof class (like our Math 108).

Problem 2. Let $\mathcal{L} = \{c,g\}$ where $c$ is a constant symbol and $g$ is a unary function symbol. Define $\phi$ as before: $$\phi :\equiv (\forall x)(\exists y)[(x\neq c)\rightarrow ((y \neq g(x))\wedge (y\neq c))].$$ Also, define $$\psi :\equiv (\exists x_1)(\exists x_2)(\exists x_3)[(x_1\neq x_2)\wedge(x_2\neq x_3)\wedge(x_3\neq x_1)].$$ Prove that if $\mathcal{M}\vDash \psi$ then $\mathcal{M}\vDash \phi$.

Reading: Reread Section 1.7

Problems to turn in: 1.7.1 #2, #4

Reading: Section 1.7

Problems to turn in:

Problem 1. Let $\mathcal{L} = \{c,g,P\}$; $c$ is a constant symbol, $g$ is a unary function symbol, and $P$ is a unary relation symbol. Also,

• $\phi :\equiv (\forall x)(\forall y)[(g(x) = g(y))\rightarrow (x = y)]$
• $\psi :\equiv (\exists x)(\exists y)(\forall w)[P(w) \leftrightarrow ((w = x) \vee (w = y) \vee (w = c))]$.

Define two $\mathcal{L}$-structures $\mathcal{M}$ and $\mathcal{N}$ such that

• $\mathcal{M}$ has a finite universe, $\mathcal{M}\vDash \phi$, and $\mathcal{M}\not\vDash \psi$.
• $\mathcal{N}$ has an infinite universe, $\mathcal{N}\not\vDash \phi$, and $\mathcal{N}\vDash \psi$.

Definition (needed for the Problem 2). If $\phi(x)$ is an $\mathcal{L}$-formula with free variable $x$, $\mathcal{M}$ is an $\mathcal{L}$-structure, and $m\in M$, then $\phi(m)$ is the new formula obtained by replacing all occurrences of $x$ with $m$. For example, if $\phi(x) :\equiv (\exists y)(x+y < x\cdot y)$, then $\phi(3) :\equiv (\exists y)(3+y < 3\cdot y)$.

Problem 2. Recall that $\mathcal{L}_R = \{0,1,-,+,\cdot\}$ where $0$ and $1$ are constant symbols, $-$ is a unary function symbol, and $+$ and $\cdot$ are binary function symbols. Let $\mathbb{R}$ be the real numbers considered in the usual way as an $\mathcal{L}_R$-structure (so $-$ means "negative").

Prove that there is an $\mathcal{L}_R$-formula with free variable $x$ such that for every $r\in \mathbb{R}$,

$r$ is positive if and only if $\mathbb{R} \vDash \phi(r)$.

Hint: First, remember that $<$ is NOT in the language, so you need to find a way to describe the positive numbers using only $0,1,-,+,\cdot$. Second, feel free to use all connectives and quantifiers explicitly, e.g. $\exists$, $\rightarrow$, etc.

Definition (needed for Problem 3). Remember that if $\phi$ is an $\mathcal{L}$-sentence and $\mathcal{M}$ an $\mathcal{L}$-structure, we write $\mathcal{M} \vDash \phi$ if $\phi$ is a true statement about $\mathcal{M}$. Now, if $\Delta$ is a (possibly infinite) set of $\mathcal{L}$-sentences, we write $\mathcal{M} \vDash \Delta$ if every sentence in $\Delta$ is a true statement about $\mathcal{M}$.

Problem 3. Let $\mathcal{L}$ be any language and $\mathcal{M}$ any $\mathcal{L}$-structure. Find a set of $\mathcal{L}$-sentences $\Delta$ (which can be finite or infinite) such that

the universe of $\mathcal{M}$ is infinite if and only if $\mathcal{M} \vDash \Delta$.

Reading: Section 1.6

Problems to turn in:

Problem 1. Let $\mathcal{L} = \{c,g,E\}$ where $c$ is a constant symbol, $g$ is a unary function symbol, and $E$ is a binary relation symbol. Define an $\mathcal{L}$-structure $\mathcal{M}$ meeting the following criteria:

• the universe of $\mathcal{M}$ has exactly four elements,
• $c^\mathcal{M} = g(c^\mathcal{M})$, and
• for every $m$ in the universe of $\mathcal{M}$, $(m,g(m)) \in E$.