Mathematical Logic

Spring 2026

"The more I think about language, the more it amazes me that people ever understand each other at all." - Kurt Gödel

Contents
General Information • Homework Assignments

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:

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

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$.