General Information

Class times: Mon + Wed + Fri from 10:00–10:50 AM [Alpine 204]
Book: A Friendly Introduction to Mathematical Logic, 2nd Edition, by Christopher C. Leary and Lars Kristiansen. The book is free if you use the pdf version—a print version can be purchased for less than $35. Here is a link to the book.
Syllabus: Syllabus for Math 161

Instructor: Dr. Joshua Wiscons (he/him/his)
Email: joshua.wiscons@csus.edu
Office: Brighton Hall (BRH) Room 144
Student office hours:

• In person: Monday 2–3 PM and Wednesday 2–3 PM [Brighton 144]
• Virtual: Thursday 1–2 PM [only via Zoom]
• Also by appointment. Just send me an email.

Final Project

General guidance and rubrics for the paper and presentation can be found in the syllabus. You are not required to use $\LaTeX$, but if you do, here is a link to a template for the project. And here are a couple of resources for using $\LaTeX$: Some LaTeX Essentials and More LaTeX Symbols.

Tentative Project List

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

Homework 01

Please organize your work, justify your steps, and write in complete sentences with correct punctuation. Once you finish, please 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.3.1: Exercise 1
• Additional Problem 1: Write down 3 terms of $\mathcal{L}_{NT}$, each of which include at least one function symbol. Please write each term twice: once in prefix notation (also called Polish notation) and once the “usual” way with infix notation.
• Additional Problem 2: This problem has two parts. First 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 Goldbach’s Conjecture: “every even integer greater than 2 can be written as the sum of two primes.” 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 02

• 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 (like in Exercise 4) you want to prove a statement about all terms $t$, try doing induction on the number of function symbols appearing in $t$. Also, for Exercise 5, you may want to start by quickly explaining why every term in the language has only 1 symbol; then start an induction proof about the number of symbols in a formula.
• Section 1.5.1: Exercise 1
• 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 three elements;
  • $c^\mathcal{M} = g^\mathcal{M}(c^\mathcal{M})$;
  • for some $m\in M$, $m \neq g^\mathcal{M}(m)$;
  • for every $m$ in the universe of $\mathcal{M}$, $(g^\mathcal{M}(m),m) \in E^\mathcal{M}$;
  • $E^\mathcal{M}$ is a symmetric but not reflexive relation.

Homework 03

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

• 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. 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))]$.
• Problem 2: Let $\mathcal{L}$ be an arbitrary language and $\mathcal{M}$ an arbitrary $\mathcal{L}$-structure. Find an infinite set of $\mathcal{L}$-sentences $\Delta$ 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$.
• Problem 3: 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 a positive number 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$.
  • Note: remember that $<$ is NOT in the language, so you need to find a way to describe the positive numbers using only $0,1,-,+,\cdot$.

Homework 04

• Section 1.7.1: Exercise 4
• Section 1.8.1: Exercises 2,3
  • Please prove #3 carefully (though fairly quickly) using induction on the number of quantifiers/connectives appearing in $\phi$.
• Section 1.9.1: Exercises 4(b)
• Additional Problem 1: Work in \(\mathcal{L}_{NT}\). Consider the formulas below. Is it true that \(\phi \vDash \alpha\)? What about \(\phi \vDash \beta\)? Justify. (If false, give a structure showing that; if true, give a short proof.)
  \(\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}\)

Homework 05

• 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 06

• 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. (Since $(\exists x)\theta$ is in $\Sigma$, you certainly have that $\Sigma \vdash (\exists x)\theta$.) 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 07

Reading

• Read Section 2.8

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 can not prove may things you know about $\mathbb{N}$, like $x\not\lt x$ (which is equivalent to $\forall x(x\not\lt x)$). By Soundness, this is because $x\not\lt 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< x)$).
• Additional Problem 1: Write out a deduction from the axioms $N$ on page 68 to directly show \(N\vdash \neg(SS0 = S0)\). Please do not use Lemma 2.8.4. (In the notation of the section, you are proving that \(\bar{2} \neq \bar{1}\). This is a slightly simplified version of Exercise 6 in Section 2.8.1.)

Homework 08

• 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 09

• Section 4.2.1: Exercise 1, 3(c)
• Section 5.3.1: Exercise 2,7
• Additional Problem 1: Write down each of the following: a tentative title for your project and a 3–5 sentence description of your project.