Course Information

Final Project

Tentative Project List

History: completeness & incompleteness (JA)	Nonstandard models of arithemtic (NA)
TBD (FB)	Other logics (WG)
Hyperreals (NG)	Nonstandard anaylsis (MZ)

Guidance and rubrics

• More guidance and a rubric for the presentation as well as guidance and a rubric for the paper can be found in the syllabus.

Template

Here is a link to a template for the project in LaTeX. A couple of resources for using $\LaTeX$ are included below

• Learning LaTeX
• Some LaTeX Symbols

Writing Assignments

Homework Assignments

Due dates and submissions are managed in Canvas. Let me know if you have any questions!

Jump to specific assigment: HW01 | HW02 | HW03 | HW04 | HW05 | HW06| HW07 | HW08 | HW09 | HW10

Homework 01

Reading

• Preface and Chapter 01: beginning through end of 1.3

Problem List

Please organize your work and justify your steps. Once your finish these problems, follow the directions in the Canvas assignment to submit them. If you have any questions (about the math or writing or submission process or anything), please let me know!

• Section 1.2.1: Exercises 2, 4
• Additional Problem 1: Read about Goldbach’s Conjecture on Wikipedia. Then, write out Goldbach’s Conjecture symbolically, and catalog all symbols you used.

Homework 02

Reading

• Chapter 01: through 1.4

Problem List

• Section 1.3.1: Exercises 1
• Additional Problem 1: Write down 3 terms of $\mathcal{L}_{NT}$. Make sure some of your terms include function symbols (and not just constants and variables). Please write each term twice: once in prefix notation (also called Polish notation) and once the “usual” way with infix notation.
• Additional Problem 2: Write down a unary formula of $\mathcal{L}_{NT}$ called $\mathbb{P}(x)$ with the intended meaning that $\mathbb{P}(x)$ is true if and only if $x$ is a prime number. Then write down a formula of $\mathcal{L}_{NT}$, using also $\mathbb{P}(x)$, with an intended meaning that expresses that there is no largest prime number. You can write these formulas using infix notation.
• Additional Problem 3: Write down a unary formula of $\mathcal{L}_{ST}$ (the language of set theory) called $C_5(x)$ with the intended meaning that $C_5(x)$ is true if and only if $x$ is a set containing exactly 5 elements. Do you think you could write down a formula $C_\infty(x)$ with the intended meaning that $C_\infty(x)$ is true if and only if $x$ is an infinite set? Explain a bit.

Homework 03

Reading

• Chapter 01: through 1.6

Problem List

• Section 1.4.1: Exercises 4,5
  • In class, to prove a statement about all formulas $\phi$, we did induction on the number of connectives and quantifiers appearing in $\phi$. If instead you want to prove a statement about all terms $t$, try doing induction on the number of function symbols appearing in $t$.
• Section 1.5.1: Exercises 1,2

Homework 04

Reading

• Chapter 01: through 1.9

Problem List

• Additional 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^\mathcal{M}(c^\mathcal{M})$, and
  • for every $m$ in the universe of $\mathcal{M}$, $(g^\mathcal{M}(m),m) \in E^\mathcal{M}$.

Note: on the next three problems, you do not need to use VAFs to prove that the structures satisfies the formulas.

• Additional Problem 2: Let $\mathcal{L} = \{c,g,P\}$; $c$ is a constant symbol, $g$ is a unary function symbol, and $P$ is a unary relation symbol. Let $\phi$ and $\psi$ be the sentences given below. Define an infinite $\mathcal{L}$-structure $\mathcal{M}$ such that $\mathcal{M}\vDash \phi$ and $\mathcal{M}\vDash \psi$.
  • $\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))]$.
• Additional Problem 3: Let $\mathcal{L}$ be an arbitrary language and $\mathcal{M}$ an arbitrary $\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$.
  • Note: $\mathcal{M} \vDash \Delta$ means that $\mathcal{M} \vDash \phi$ for all $\phi \in \Delta$.
• Additional Problem 4: 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”). Write down an $\mathcal{L}_R$-formula $\phi(x)$, with free variable $x$, such that for every $r\in \mathbb{R}$, $r$ is positive if and only if $\mathbb{R} \vDash \phi(r)$.
  • Note: $\phi(r)$ means that every free occurrence of $x$ in $\phi$ is replaced by $r$.

Homework 05

Reading

• Chapter 02: 2.1

Problem List

• Section 1.7.1: Exercise 4
• Section 1.8.1: Exercises 1,2,3
  • Please prove #3 carefully using induction on the number of quantifiers/connectives appearing in $\phi$.
• Additional Problem 1: Work in $\mathcal{L}_{NT}$. Consider the formulas below. Is it true that $\phi \vDash \alpha$? Explain. What about $\phi \vDash \beta$?
  • $\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) $

Homework 06

Reading

• Chapter 02: through 2.4

Problem List

• Section 2.2.1: Exercise 1
• Section 2.4.3: Exercises 4,5
  • There is a hint in the back of the book for #4, but if you 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$.

Homework 07

Reading

• Chapter 02: through 2.9 (but just skim 2.6)

Problem List

• Section 2.5.1: Exercise 1
• Section 2.7.1: Exercises 1,5,7
  • Regarding Exercise 1: to show that $\Sigma \vdash \exists x\theta$ does not imply $\Sigma \vdash \theta$, you may want to start by choosing $\Sigma$ and $\theta$ in some language $\mathcal{L}$ such that $\exists x\theta$ is in $\Sigma$ but $\theta$ is not. Then, to show $\Sigma \not\vdash \theta$, which is equivalent to $\Sigma \not\vdash \forall x \theta$, consider using (the contrapositive of) Soundness: show $\Sigma \not\vDash \forall x\theta$ (i.e. show that there is some $\mathcal{L}$-structure that satisfies $\Sigma$ but not $\forall x\theta$).

Homework 08

Reading

• Chapter 02: re-read 2.8
• Chapter 03: through 3.2

Problem List

• Section 2.8.1: Exercise 2,7
  • The point of Exercise 7 is that, although it may feel like the axioms on page 68 describe the natural numbers $\mathbb{N}$ quite well, these axioms cannot prove may things you know about $\mathbb{N}$, like $x\nleq x$ (which is equivalent to $\forall x(x\nleq x)$). By Soundness, this is because $x\nleq x$ is not true in every model of the axioms, as you will show. The book gives a suggestion on how to do this; adding to that suggestion, try thinking of the additional element $a$ as $\infty$ and define things according to your intuition (and then prove that your structure satisfies the axioms on page 68 and also satisfies $\exists x(x\leq x)$).

Homework 09

Reading

• Chapter 03: 3.3 and 3.4

Problem List

• Section 3.3.1: Exercise 5
  • Note: a nonstandard model of arithmetic is any $\mathcal{L}_{NT}$-structure $\mathcal{M}$ such that $\mathcal{M}\equiv \mathbb{N}$ (as $\mathcal{L}_{NT}$ structures) but $\mathcal{M}\not\cong \mathbb{N}$. This implies that each nonstandard $\mathcal{M}$ contains an “infinite” element $m$ such that $m > \overline{n}$ for every $n\in \mathbb{N}$; you don’t need to prove this (but do think about why it’s true). Now, to prove that $\mathcal{M}$ has an “infinite prime” start by writing down an $\mathcal{L}_{NT}$-sentence expressing that for each natural number $x$, $\mathbb{N}$ contains a prime larger than $x$; then use that $\mathcal{M}\equiv \mathbb{N}$.
• Additional 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)$
  1. Give an example of a linear order with 4 elements by defining a universe $\mathcal{M}$ and the ordering $<^\mathcal{M}$ such that $\mathcal{M}\models \{\lambda_1,\lambda_2,\lambda_3\}$. (When you’re done, think about how you could generalize your construction to create a linear order with $k$ elements; you’ll need to do that in the next part.)
  2. Prove that there does not exist a set $\Sigma$ of $\mathcal{L}_{order}$-formulas 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 various finite linear orders, but remember that you are good at creating models.
• Additional Problem 2: Let $\mathbb{R}^*$ denote the hyperreals as constructed in class. Recall that $a\in \mathbb{R}^*$ is a positive infinitesimal if $0< a < r$ for all positive $r\in \mathbb{R}$. (Also remember that $0< a < r$ is really shorthand for $\dot{0}^{\mathbb{R}^*}<^{\mathbb{R}^*} a <^{\mathbb{R}^*} \dot{r}^{\mathbb{R}^*}$.)
  1. Using the fact that addition is commutative in $\mathbb{R}$, prove that addition is also commutative in $\mathbb{R}^*$.
  2. Let $a\in \mathbb{R}^*$ be a positive infinitesimal. Prove that, for all positive $r\in \mathbb{R}$, the product $r a$ is also a positive infinitesimal. (You may want to argue by contradiction.)

Homework 10

Reading

• Chapter 04: up through 4.2

Problem List

• Section 4.2.1: Exercise 1
• Section 5.3.1: Exercise 7,8
• Additional 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.