# MATH 220BC: Mathematical Logic - Course Review

** Published:**

This is a review and summary for course MATH 220BC, given by Professor Artem Chernikov and Andrew Marks.

In this post, I listed important theorems (in my mind) like a dictionary, so I can recall what I learnt when I read this in future. Only the overview and summary may be useful to other people.

# Overview

This is the first math course I took at UCLA. Due to time schedule, I didn’t take 220A, but I read though a online note and memorized important conclusions. I could somehow catch up with B and C part.

220B is based on the textbook *A First Journey through Logic*. The book is too brief, but the professor’s lectures are clear. This part is more related to computer science, as we discussed computability and Turing machines. I heard that CS 181 covers something similar, but I think 220B is more on the math side.

220C is the most tough course I have ever took. The professors made really great lectures, but the course material is very complex and counterintuitive. (Well, maybe because I don’t have *correct* intuitions) I feel that this part is more related to analysis.

# Basic Model Theory

Model theory works on formal theories and their models. Most of the following results depend on infinite models. For exmaple, compactness does not hold if we require every model to be finite.

## First Order Logic

First order logic is obtained by augmenting propositional logic with two quantifiers: the existential quantifier and the universal quantifier. These quantifiers iterate over all possible values (the base set), but cannot refer to propositional formulas. There are redundencies in logic connectors and quantifiers. A minimal definition of a FOL *language* $\mathcal{L}$ will contain the following:

- Logical symbols (shared by all languages)
- Equality relation: $=$
- Connectives: $\neq$, $\wedge$
- The existential quantifier: $\exists$
- The variable set: $v_n$, $n\in\mathbb{N}$

- The
*signature*of $\mathcal{L}$- A set of constant symbols, $\mathcal{C}$.
- Sets of functions, $\mathcal{F}_n$ for $n$-ary functions.
- Sets of relations, $\mathcal{R}_n$ for $n$-ary relations.

We can define *disjunction* $\vee$, *implication* $\rightarrow$, *equivalence* $\leftrightarrow$ and the *universal quantifier* $\forall$ based on these symbols.

We can define *terms* and *formulas* of this language:

- A
*term*is something that can be interpreted as some value. It can be one of the following:- A variable.
- A constant symbol.
- A function call: $f(t_1,\ldots, t_n)$, where $f\in\mathcal{F}_n$ and $t_i$ is a term.

- An
*atomic formula*is some elementary proposition:- $t_1 = t_2$, with $t_1,t_2$ terms.
- $R(t_1, \ldots, t_n)$, where $r\in\mathcal{R}_n$ and $t_i$ is a term.

- A
*formula*is a**finite**composition of atomic formulas:- $\phi$, where $\phi$ is an atomic formula.
- $\neg\phi$, where $\phi$ is an atomic formula.
- $\phi\wedge\chi$, where $\phi,\chi$ are atomic formulas.
- $\exists x\phi$, where $\phi$ is an atomic formula and $x$ is a variable.

- We can define
*free occurrence*,*bound occurrence*,*similtaneous substitution*just as we do in programming languages. - A
*sentence*is a formula with no free variables.

A language decides what formula we can write, but does not specify its meaning. An interpretation of this language, is an $\mathcal{L}$-*structure* $\mathfrak{A}$:

- $\mathfrak{A}$ has a non-empty
*base set*$A$. - $\mathfrak{A}$ maps every constant to an element in $A$: $c^{\mathfrak{A}}\in A$ for all $c\in\mathcal{C}$.
- $\mathfrak{A}$ maps every $n$-ary function to a (well-defined) $n$-ary function on $A$: $f^{\mathfrak{A}}: A^n\to A$ for all $f\in\mathcal{F}_n$.
- $\mathfrak{A}$ maps every $n$-ary relation to a (well-defined) $n$-ary relation on $A$: $r^{\mathfrak{A}}\subseteq A^n$ for all $r\in\mathcal{R}_n$.

Then, we can define semantics:

- An
*assignment*is a function $\alpha$ that maps variables to the base set. - Given a term $t$, a model $\mathfrak{A}$ and an assignment $\alpha$, we can calculate the value of $t$, $t^{\mathfrak{A}}[\alpha ]$ be substitute the variables with assignments.
- Similarly, we can decide the truth value of a formula. Denote $\mathfrak{A}\models \phi[\alpha ]$ if its true.
- A formula is
*universally valid*, i.e. tautology, if true in all structures.- Propositional tautologies, equality axioms and quantifier axioms are always universally valid.

## Completeness and Soundness

An $\mathcal{L}$-*theory* $T$ is a set of $\mathcal{L}$-sentences. Its elements are called axioms. A $T$-*model* is an $\mathcal{L}$-structure where every axiom of $T$ is true.

Any sentence $\phi$ in a theory $T$ can be one of the **three** different cases:

- True in all $T$-models. Then, $\phi$ is called a $T$
**-theorem**. - False in all $T$-models. Equivalent to that $\neg\phi$ is a theorem.
- True in some models, but false in others. Then, $\phi$ is called
**independent**of $T$.

A *formal proof* is a **finite** sequence of sentences, where each sentence is obtianed by any of the following:

- An axiom of $T$.
- A predicate calculus tautology, an equality axiom, or a quantifier axiom
- Modus Ponens (MP) from two previous sentences.
- Universal generalization from a previous sentences. (From $\phi$ to $\forall x\phi$).

If a formal proof of $T$ ends in $\phi$, then $T$ proves $\phi$: $T\vdash \phi$. A theory is *consistent* if it cannot prove $\phi\wedge\neg\phi$ for any $\phi$. The following theorems show that a sentence has a formal proof iff it’s true in all models.

**Soundness**: If $T\vdash\phi$, $\phi$ is true in all models.

**Gödel’s Completeness Theorem** or **Model existence theorem**: Every consistent theory has a model. Hence, a sentence that is true in all models can always be proven.

This is proven by constructing a model for an arbitrary theory. See also: Henkin witness

**Craig’s Interpolation Theorem**: Let $\phi$ be a $\mathcal{L}_1$-sentence and $\psi$ be a $\mathcal{L}_1$-sentence. Suppose $\models \phi\to\psi$. Then, there exists a $\mathcal{L}_0 := \mathcal{L}_1\cap\mathcal{L}_2$ sentence $\rho$ s.t. $\models\phi\to\rho$ and $\models\rho\to\psi$.

## Compactness & Up and Down

**Compactness Theorem**: A theory is consistent if and only if every **finite** subset of it is consistent.

This is equivalent to the completeness theorem, as *every formal proof must be finite*. On the other hand, we can also use Łoś’s Theorem to give a direct model.

- Two structures $\mathfrak{M}$ and $\mathfrak{N}$ are
*elementarily equivalent*$\mathfrak{M}\equiv\mathfrak{N}$, if they satisfy the same sentences. - If for every formula $\phi(x_1,\ldots, x_n)$ and $\bar{a}\in M^n$, $\mathfrak{M}\models\phi(\bar{a})$ iff $\mathfrak{N}\models\phi(\bar{a})$, then $\mathfrak{M}$ is an
*elementary substructure*(or*submodel*) of $\mathfrak{N}$: $\mathfrak{M}\prec\mathfrak{N}$. - CLearly, elementary substructures are equivalent. But the reverse is not true, i.e. subset + elementary equivalent ≠ elementary substructure.
- For example, $\mathfrak{M} = (\mathbb{N}_+, <)$ and $\mathfrak{N} = (\mathbb{N}, <)$ are isomorphic and equivalent, but $\mathfrak{M}$ is not a elementary substructure of $\mathfrak{N}$. Consider $\phi(y) := \exists x(x< y)$ and $y=1$.

**Tarski-Vaught Test**: Suppose $\mathfrak{M}\subseteq \mathfrak{N}$. Consider formula $\phi(x_1,\ldots, x_n,y)$ and $\bar{a}=(a_1,\ldots,a_n)\in M^n$. If whenever there exists some $u\in N$ satisfying $\phi(\bar{a},y)$ ($\mathfrak{N}\models\exists y\phi(\bar{a}, y)$), there also exists some $v\in M$ satisfying $\phi(\bar{a},y)$ ($\mathfrak{M}\models\exists y\phi(\bar{a}, y)$), then $\mathfrak{M}\prec\mathfrak{N}$.

**Downward Löwenheim–Skolem theorem**: Let $\mathfrak{M}$ be a $\mathcal{L}$-structure and $A\subseteq M$. Then, for any cardinal $\kappa$ s.t. $\max\{|\mathcal{L}|,|A|\}\leq \kappa\leq |M|$, there is an elementary submodel of $\mathfrak{M}$ of size $\kappa$ containing $A$.

Note: *every language is at least countable*.

*Proof sketch*: For every existence formula $\phi:=\exists y\psi(x_1,\ldots, x_n,y)$, define Skolem function $f_{\phi}: M^n\to M$ as follows: if there exists some $b$ s.t. $\psi(a_1,\ldots, a_n,b)$ is true, let $f_{\phi}(a_1,\ldots, a_n)$ be any $b$; if there does not exists such $b$, let $f_{\phi}(a_1,\ldots, a_n)$ be any element. Take a superset $S\subseteq S’$ s.t. $|S’| = \kappa$. Take the closure of $S’$ under $f_{\phi}$ of all possible $\phi$ (at most $|\mathcal{L}|$ many).

*Note*: though this proof uses AC, there exists a proof without AC for the countable case.

**Upward Löwenheim–Skolem theorem**: Let $\mathfrak{M}$ be a $\mathcal{L}$-structure. Then, for any cardinal $\kappa$ s.t. $|M|\leq \kappa$, there is an elementary extension of $\mathfrak{M}$ of size $\kappa$.

*Proof idea*: Use diagram method.

**Omitting Types Theorem(型排除定理)**:

- A
**partial n-type**(in theory $T$) is a (usually infinite) set of $n$-variable formulas $\pi$ consistent with $T$. Formally, $T\cup\{\exists \bar{v}\bigwedge_{\phi\in\pi_k} \phi\}$ is consistent for all finite subset $\pi_k$. - A model $\mathfrak{M}$
**realizes**$\pi$ if it is satisfiable in $\mathfrak{M}$; otherwise, $\mathfrak{M}$**omits**$\pi$. - $\pi$ is
**isolated**if there is a single formula $\phi$ that is equivalent to $\pi$, i.e. $T\vdash \exists\bar{v}(\phi\to\psi)$ for all $\psi\in\pi$. - A
**complete n-type**is a maximal partial n-type $\pi$. That is, for all $n$-formula $\phi(\bar{v})$, either $\phi(\bar{v})\in\pi$ or $\neg\phi(\bar{v})\in\pi$.

The theorem states that for a theory $T$ of a countable language and any countably many non-isolated partial types, there exists a model of $T$ that omits all given types.

**Saturated Model**: Suppose there is an $\mathcal{L}$-structure $\mathfrak{M}$.

- For $A\subseteq M$, an
**partial n-type**(*of*$\mathfrak{M}$)**over**$A$ is a set of $n$-formulas $\pi(\bar{x})$ in language $\mathcal{L}_A := \mathcal{L}\cup\{c_a: a\in A\}$, that is consistent with the theory of $\mathfrak{M}$. Formally, for all finite subset $\pi_k$, there is some $b\in M$ s.t. $\mathfrak{M}\models\pi_k(b)$. - A
**complete n-type over**$A$ is a maximal partial $n$-type over $A$. - We define the term
**realize**,**omit**and**isolate**similar to types of theories. - $\mathfrak{M}$ is $\kappa$
**-saturated**if for all $|A|\leq \kappa$, every 1-type over $A$ is realized. - $\mathfrak{M}$ is
**recursively saturated**if all recursively definable 1-type is realized.

**Lindström’s Theorem**: FOL is the strongest logic satisfying both compactness and Downward Löwenheim–Skolem property.

## Algebraic Closed Field

**Quantifier elimination**: A structure or a theory admits *quantifier elimination* if every formula is equivalent to a quantifier-free formula. It is proven that if every formula in the form $\exists x\phi$ with $\phi$ quantifier free has a quantifier free form, then the theory or structure admits quantifier elimination.

**Algebraically closed field**: A field is *algebraically closed* if every non-constant polynomial has a root.

The theory of algebraically closed field, ACF, admits quantifier elimination.

**Lefschetz principle**: For a $\mathcal{L}_{ring}$-formula $\phi$, the following are equivalent:

- $\phi$ is true in some ACF of characteristic 0.
- $\phi$ is true in every ACF of characteristic 0.
- $\phi$ is true in ACFs of characteristic $p$ for arbitrarily large $p$. (i.e. for an infinite set of prime numbers)
- $\phi$ is true in ACFs of characteristic $p$ for sufficiently large $p$. (i.e. for all $p>N$)

**Ax’s theorem**: For all polynomial functions $f:\mathbb{C}^n\to\mathbb{C}^n$, if $f$ is injective, then $f$ is also surjective.

# Recursion Theory

Recursion theory studies computability and computable functions.

## Primitive Recursive Functions

**Primitive recursive functions**: A primitive recursive function is a $n$-ary function on natural numbers obtained by the following:

- Basic functions:
- Successor $S := \lambda x. x+1$;
- Constant zero $C^0_0 := \lambda. 0$;
- Projection $P^n_j:=\lambda x_1\cdots x_n.x_j$

- Composition of p.r. functions:
- $f := g(h_1,\ldots, h_n)$

- Recursion:
- $f(x_1,\ldots, x_n, 0) := g(x_1,\ldots, x_n)$;
- $f(x_1,\ldots, x_n, y+1) := h(x_1,\ldots, y, f(x_1,\ldots, x_n,y))$

A subset of $\mathbb{N}^n$ is p.r. iff its characteristic function is p.r.

One can prove that p.r. functions and sets are stable under:

- Boolean combinations ($\cap$, $\cup$, $\setminus$)
- Definition by cases
- Bounded sums and products
- Bounded $\mu$-operator: $f(\bar{x},z):=(\mu t\leq z)((\bar{x},t)\in X)$
- $f(\bar{x},z)$ is the smallest natural number s.t. $(\bar{x},t)\in X$; 0 if there does not exist.

- Bounded quantification.

We can also define the following functions:

- Combine $n$ numbers into one.
- Functions $\alpha_n, \beta^n_i$ s.t. $\beta^n_i(\alpha_n(x_1,\ldots, x_n)) = x_i$.

- Finite sequences of natural numbers, Gödel number.
- $\langle \cdot \rangle$ s.t. $\langle x_1,\ldots, x_n \rangle$ is a natural number
- $\text{lg}(\langle x_1,\ldots, x_n \rangle) = n$
- $(\langle x_1,\ldots, x_n \rangle)_i = x_i$

**Ackermann function**: $\xi:\mathbb{N}^2\to\mathbb{N}$ defined as follows:

- $\xi_0(x) = \xi(0, x) := 2^x$;
- $\xi_y(0) = \xi(y, 0) := 1$;
- $\xi_{y+1}(x+1) = \xi(y+1, x+1) := \xi(y, \xi(y+1, x))$.

This version is designed for the sake of proof, not the version that people generally use. In this version, $\xi_0$ is exponentiation, $\xi_1$ is (basically) tetration, and $\xi_2$ is (basically) pentation.

The finite powers of Ackermann functions, $\xi^k_n = \xi_n\circ\cdots\circ\xi_n$ for $k$ times, give bounds of p.r. functions.

- A function $f\in\mathcal{F}_1$
*dominates*$g\in\mathcal{F}_n$ if $g(\bar{x}) \leq f(\max(\bar{x},N))$ for some $N$. - If $f$ is obtained by no more than $n$ times of recursions, then there exists some $k\in\mathbb{N}$ s.t. $\xi_n^k$ dominates $f$.

One can prove that all $\xi_n$ are p.r., but $\xi$ itself is not, because $\xi^k_n$ cannot bound itself $\xi$.

More generally, we cannot define “computable functions” concept, say set $F$, with all of the following properties:

- $F$ is countable: $F = \{f_0, f_1,\ldots\}$.
- $F$ is closed under desired operations like recursion, composition, etc.
- There is a “computer”: $u\in F$, $u(n, \bar{x}) = f_n(\bar{x})$.
- All functions on $F$ are total: $f_i$ terminates on all inputs.

This is because $\lambda n. u(n,n)+1$ does not equal to any $f_i$. We cannot drop 2 and 3, and 1 is implied by 3. Thus, to properly define the concept of “computability”, we have to drop 4.

## Partial Recursive Functions

A *partial function* from $\mathbb{N^n}\to\mathbb{N}$ is a function $f:A\to \mathbb{N}$ for some $A\subseteq\mathbb{N^n}$. We use $f\in\mathcal{F}^*_n$ to denote the set of partial functions. We say $f$ *converges* at $p$, $f(p)\downarrow$, for $p\in A$; $f$ *diverges* at $p$, $f(p)\uparrow$, for $p\notin A$.

The set of *partial recursive functions* is the smallest set $E$ satisfying the following:

- $E$ contains the basic functions.
- $E$ is stable under composition (of partial functions).
- $E$ is stable under recursion (of partial functions).
- $E$ is stable under (unbounded) $\mu$-operator: $g(\bar{x}) := \mu y(f(\bar{x},y)=0)$ is defined as
- $g(\bar{x}) = z$ if $z$ is the minimal element s.t. $f(\bar{x},z) = 0$ and $f(\bar{x},y)$ is defined for all $y\leq z$.
- $g(\bar{x})\uparrow$ is not defined otherwise.

A total function is *(total) recursive* if it is a partial recursive function.

Recursive functions are computable functions. (Church’s Thesis) Every intuitively computable function is recursive.

## Universal Functions

**Universal Functions**: There exists $\varphi^p\in\mathcal{F}^*_{p+1}$ s.t. every $f\in \mathcal{F}^*_{p}$ that is partial recursive equals to some $\varphi^p_i = \lambda \bar{x}.\varphi^p(i,\bar{x})$. Moreover, $\varphi^p$ is partial recursive.

**s-m-n Theorem**: For any natural numers $m$ and $n$, there exists a p.r. function $s^m_n\in\mathcal{F}_{n+1}$ s.t.

In programming world, this is partial application, or currying.

**Kleene’s Fixed Point Theorem**: For any total recursive function $\alpha\in\mathcal{F}_1$ and $m > 0$, there exists $i\in\mathbb{N}$ s.t. $\varphi^m_{i} = \varphi^m_{\alpha(i)}$.

**Elimination of Recursion**: The set of *total* recursive functions is the smallest set that

- Contains $S$, $C^0_0$, $P^n_i$;
- Contains $+$, $\cdot$, $1_=$, $1_<$;
- Is stable under composition;
- Is stable under total $\mu$-operator.
- Total $\mu$-operator is the unbounded $\mu$-operator but only applicable when it always converges.

In other words, recurion is only used to define addition, multiplication and comparison.

## Recursively Enumerable Sets

**Recursively enumerable sets** have many equivalent definitions. Suppose $S\subseteq\mathbb{N}^n$, then the following are equivalent:

- $S$ is either empty or the range of a total recursive function $f:\mathbb{N}\to\mathbb{N}^n$.
- That is, there exists a recursive function that enumerates elements of $S$, but not necessarily in order.

- $S$ is either empty or the range of a p.r. function.
- $S$ is a projection of some recursive set $T\subset\mathbb{N}^{n+1}$.
- $S$ is a projection of some p.r. set $T\subset\mathbb{N}^{n+1}$.
- $S$ is the domain of a partial recursive function $f: \mathbb{N}^n\to\mathbb{N}$.

The set of r.e. sets is stable under intersection, union, projection, bounded universal quantification, image (replacement) under recursive functions.

**Theorem of the Complement**: A set $X\subseteq\mathbb{N}^n$ is recursive if and only if both $X$ and $\mathbb{N}^n\setminus X$ are r.e.

**the Halting Problem**: The domain of $\varphi^n$ is a r.e. set but not recursive. The set of indices of Turing machines that halt on the empty input is r.e. but not recursive.

**Rice’s Theorem**: Suppose $\chi$ is a set of one-variable partial recursive functions that is non-empty nor full. Then, the indices $I = \{i: \varphi^1_i\in\chi\}$ is not recursive.

**Kolmogorov complexity**: Given $n\in\mathbb{N}$, let $K(n)$ be the least $i\in\mathbb{N}$ s.t. $\varphi^1_i(0) = n$. One can prove that there does not exist an infinite r.e. set $A\subseteq\mathbb{N}^2$ s.t. $K(n)=i$ for all $(n,i)\in A$.

# Models of Arithmetic

In this part, we study the models of natural numbers. Since we can encode all programs into natural numbers, we can bring them into FOL formulas and try to formally define “provability”.

## Decidability

If a language $\mathcal{L}$ has a finite signature, then we can assign each symbol to a Gödel number, and encode every term, formula, and proof into a natural number.

- The set of codes of formulas and logical axioms of $\mathcal{L}$ are p.r. sets
- There exist p.r. functions that simulate substitution of terms and formulas.
- The set of formal proofs $\mathrm{Prf}=\{(\#\#d, \#\phi): d\text{ is a formal proof of }\phi\}$ is a p.r. set.
- The set of tautologies $U=\{\#\phi:\ \vdash\varphi\}$ is r.e.

Given a $\mathcal{L}$-theory $T$,

- $T$ is
*recursive*if the code of axioms of $T$ is recursive. - $T$ is
*recursively*(or*effectively*)*axiomatizable*if there exists a recursive theory $T’$ that has the same theorem of $T$. - $T$ is
*decidable*if the set of codes of theorems $\#\mathrm{Thm}(T)$ of $T$ is recursive. - If $T$ is recursive, then the formal proofs of $T$, $\mathrm{Prf}(T)$, is recursive.
- $T$ is effectively axiomatizable iff $\#\mathrm{Thm}(T)$ is r.e.
- If $T$ is effectively axiomatizable and complete, then $T$ is decidable.
- If $T$ is decidable, then the theory of $T$ plus a finite set of axioms is also decidable.

## Peano Arithmetic

We work in the language of arithmetic $\mathcal{L}_{ar} = \{0,S,+,\cdot, < \}$. In this language, we can express any (standard) natural number $n\in\mathbb{N}$ as $\underline{n}$:

- $\underline{0} \equiv 0$;
- $\underline{n+1} \equiv S(\underline{n})$.

The **weak Peano axioms** is the finite theory $\mathrm{PA}_0$ consisting of the following 8 axioms:

- $0$ has no predecessor.
- (A1) $\forall x \neg Sx=0$

- Every non-zero number has a predecessor.
- (A2) $\forall x\exists y(\neg x=0\to Sy=x)$

- Two numbers with equal successors are equal.
- (A3) $\forall x\forall y(Sx=Sy\to x=y)$

- $0$ is the identity of addition.
- (A4) $\forall x\ x+0 = 0$

- Successor commutes with addition.
- (A5) $\forall x\forall y\ x+Sy =S(x+y)$

- $0$ is the zero of multiplication.
- (A6) $\forall x\ x\cdot 0 = 0$

- Multiplication is distributive over successor.
- (A7) $\forall x\forall y\ x\cdot Sy =x\cdot y + x$

- “Less” means “subtractable”.
- (A8) $\forall x\forall y(x< y\leftrightarrow \neq x=y\wedge (\exists z\ x+z=y))$

The **Peano axioms** is the infinite theory PA, consisting of $\mathrm{PA}_0$ and the *axiom (schema) of induction*.

- There exists a model of $\mathrm{PA}_0$ that both addition and multiplication are neither commutative nor associative, and $<$ is not a total order.
- The standard natural number $\mathbb{N}$ is isomorphic to an initial segment of any $\mathrm{PA}_0$ model.
- In a model of PA:
- Addition and multiplication are commutative and associative.
- Multiplication is distributive w.r.t. addition.
- $<$ is a total order.

**Arithmetical Hierarchy**: Every FOL formula $\phi$ can be classified into the following hierarchy:

- $\phi$ is $\Sigma_0 = \Pi_0 = \Delta_0$ if is is equivalent to a formula with only
*bounded*quantifiers; - $\phi$ is $\Sigma_{n+1}$, if it is equivalent to a formula in the form $\exists x_1\cdots\exists x_m\psi$, where $\psi$ is $\Pi_{n}$;
- $\phi$ is $\Pi_{n+1}$, if it is equivalent to a formula in the form $\forall x_1\cdots\forall x_m\psi$, where $\psi$ is $\Sigma_{n}$;
- $\phi$ is $\Delta_{n}$ if it is both $\Sigma_{n}$ and $\Pi_{n}$.
- Sometimes people write $\Sigma^0_n$, $\Pi^0_n$ and $\Delta^0_n$. The superscript $0$ means counting
*number quantifiers*instead of*function quantifiers*.

Any $\Sigma_1$ sentence satisfied in $\mathbb{N}$ is a theorem of $\mathrm{PA}_0$.

\[\mathbb{N}\models\phi[m_1,\ldots, m_n] \Rightarrow \mathrm{PA}_0\models\phi(\underline{m_1},\ldots, \underline{m_n})\]**Representability Theorem**: Every total recursive function is represented by a $\Sigma_1$ formula. A set is r.e. iff there is a $\Sigma_1$ formula defining it in $\mathbb{N}$. Here, $\phi$ “represent” $f$ means:

**Overspill**: Let $\mathfrak{M}$ be a *non-standard* model of PA and $\phi(x)$ a formula. If for all $n\in\mathbb{N}$, $\mathfrak{M}\models\phi(\underline{n})$, then there exists $c\in M$ non-standard s.t. $\mathfrak{M}\models\phi(c)$.

**Pigeonhole Principle**: For any PA model $\mathfrak{M}$, $\mathcal{L}_{ar}(M)$-formula $\theta(v,z)$ and $a\in M$:

In other words, if a predicate maps infinite many numbers ($z> x$) into a finite number of elements ($v< a$), then there exists a fixed number ($v$) that is the image of infinitely many numbers.

**MacDowell-Specker Theorem**: Any countable model of PA has an elementary end extension.

## First Incompleteness Theorem

**The Diagonal Argument**: For every formula $\phi(v)$, there exists a sentence $\Delta_{\phi}$ s.t. $\phi(\underline{\#\Delta_{\phi}})$ is equivalent to $\neg\Delta_{\phi}$ in $\mathrm{PA}_0$.

**Fixed Point Theorem**: For all $\phi(v)$, there exists a sentence $\psi$ s.t.

*Proof*: Take $\psi :\equiv \Delta_{\neg\phi}$.

**Tarski’s Theorem on the Non-definability of Truth**: In any model $\mathfrak{M}$ of $\mathrm{PA}_0$, there does not exist a formula $S(v)$ s.t. $\mathfrak{M}\models\phi$ iff $\mathfrak{M}\models S(\underline{\#\phi})$.

*Corollary*: The theorems of $\mathbb{N}$ are undecidable.

**Church’s Theorem**: Any consistent theory containing $\mathrm{PA}_0$ is undecidable.

*Corollary 1*: The tautologies of the finite language $\mathcal{L}_{ar}$ is undecidable.

*Corollary 2*: The tautologies of a language that consists only one binary relation is undecidable.

*Corollary 3*: The tautologies of a language that consists of a unary predicate and a constant is decidable.

**Gödel’s First Incompleteness Theorem**: Any consistent and recursive theory containing $\mathrm{PA}_0$ is incomplete.

**Rosser’s Variant**: Rosser writes down an independent sentence that witnesses this theorem. Let $T\supseteq \mathrm{PA}_0$ be consistent and recursive. Let $P_T(x,y)$ represents the set of formal proofs of $T$, i.e. $y$ proves $x$. Let $\nu(x, y)$ represents the negation of formula, i.e. $y$ is $\neg x$. Set:

That means,

- for standard numbers $x$ and $y$, $y$ proves $x$;
- for non-standard numbers $y$, there does not exist a proof $z$ for the negation of $x$.

Then, $\Delta_T^R :\equiv \Delta_{\exists y P^R_T(x,y)}$ is independent.

*Remark*: If we directly use $P^T$ as $\Delta_T :\equiv \Delta_{\exists y P_T(x,y)}$, then $T$ cannot prove $\Delta_T$, but $T$ may prove $\neg\Delta_T$. $P_T(\#\Delta_T, y)$ does not imply $T\vdash \Delta_T$ when $y$ is non-standard, so no contradiction.

## Second Incompleteness Theorem

Though general satisfiability is undecidable, if we limit the complexity of formula, we can get decidable results. For example, satisfiability of $\Sigma_1$ formulas.

**Provably Total $\Sigma_1$ Functions**: Suppose $\chi_f$ represents $f$. If PA proves that for any (even non-standard) numbers $x_1,\ldots, x_n$, there is exactly one $y$ that satisfies $\chi_f$, then $f$ is *provably total* $\Sigma_1$. Formally,

- Every p.r. function is provably total $\Sigma_1$
- Not every recursive function is provably total $\Sigma_1$ (though representable).
- There is a universal provably total $\Sigma_1$ function $g\in\mathcal{F}_3$, in the sense that: for every provably total $\Sigma_1$ function $f$ there exists $a,b\in\mathbb{N}$ s.t. $f = \lambda n.g(a,b,n)$.

**Definability of Satisfiability for $\Sigma_1$ Formulas**: There exists a $\Sigma_1$-formula $\mathrm{Sat}(v)$ s.t. for all $\Sigma_1$-sentence $\phi$,

The proof uses certificate method.

**Definition of Provability**: For a recursive theory $T$, there exists an operator $\Box_T$ on sentences s.t.

- If $\phi$ is a $\Sigma_1$-sentence, $\text{PA}\vdash \phi\to\Box_T\phi$;
- For any sentence $\psi$, $\mathbb{N}\models \Box_T\psi \iff T\vdash \psi$.

**Löb’s Axioms**: for any sentence $\phi,\psi$,

- (Necessitation Rule, N) $T\vdash \phi \Rightarrow T\vdash \Box_T\phi$;
- (Distribution Axiom, K) $T\vdash [\Box_T\phi\wedge \Box_T(\phi\to\psi)]\to \Box_T\psi$;
- (4) $T\vdash \Box_T\phi\to\Box_T\Box_T\phi$.

*Corollaries*:

- If $T\vdash \phi\to\psi$, then $T\vdash \Box_T\phi\to\Box_T\psi$;
- (GL) $T\vdash \Box_T(\Box_T\phi\to\phi)\to\Box_T\phi$;
- If $T\vdash \Box_T\phi\to\phi$, then $T\vdash \Box_T\phi$;
- If $T\vdash \neg\Box_T\phi$, then $T\vdash \Box_T\phi$.

See also: Modal Logic, Provability Logic, Kripke Semantics.

**Gödel’s Second Incompleteness Theorem**: Let $T$ be a computable theory. Then, it is impossible to prove $\Box_T\phi$ for any $\phi$ in $T$. More specifically, let $\text{Con}_T$ denote the consistency of $T$: $\text{Con}_T :\equiv \neg\Box_T(0=1)$. Then, $T$ cannot prove $\text{Con}_T$.

**Tenenbaum’s Theorem**: There is no recursive non-standard model of PA. That is, for any countable non-standard model of PA, there is no way to code the elements of the model as (standard) natural numbers such that either the addition or multiplication operation of the model is a computable on the codes.

SA: Non-standard model of arithmetic, Standard and Nonstandard Numbers.

# Set Theory

Axiomatic set theory studies models of set theory. Since the whole world of logic is built upon set theory, we cannot find a structure like $\mathbb{N}$ and define it as a “standard model”. However, assuming the consistency of the theory, there are models developed based on the universe that we are in.

## Cumulative Hierarchy

**Language of Set Theory**: $\mathcal{L}_{set} = \{\in \}$. Other symbols can be developed as abbreviations of $\mathcal{L}_{set}$-formulas.

**The Axiom Schema of Comprehension**: The only axiom for *naive* set theory, is that every logic formula $\phi$ has a set corresponding to it:

**Cantor’s Diagonal Argument**: For all set $X$, there is no surjection $f: X\to\mathcal{P}(X)$.

- Cantor’s paradox: Let $V = \{x: \forall x\}$. Then, $\mathcal{P}(V)$ is part of $V$.

**Russel’s Paradox**: Let $D = \{x: x\notin x\}$. Then, $D$ is not a set. This proves that the axiom schema of comprehension is inconsistent.

**The Axioms of ZF**: To avoid the inconsistency, the construction of sets must be limited. Basic axioms of axiomatic set theory include the following. Models of set theory generally satisfy all or a major part of them:

**The axiom of Extensionality**: Every set is determined by its members.- $\forall x\forall y[x=y \leftrightarrow \forall z(z\in x = z\in y)]$.

**The axiom of Foundation**: Every non-empty set contains a $\in$-minimal element.- Let $x\neq \varnothing$ abbreviate $\exists y(x\in x)$.
- $\forall x[x\neq\varnothing \to \exists y\in x\forall z\in x(z\notin y)]$

**The axiom of Pairing**: Given two sets, there is a set containing exactly them.- $\forall x\forall y\exists w[x\in w\wedge y\in w\wedge \forall z(z\in w\to z=x\vee z=y)]$.
- We can let $\{x,y\}$ denote this set; use $\{x\}$ denote $\{x,x\}$.
- We can define ordered pair $(x,y) = \{x, \{x, y\}\}$.

**The axiom of Union**: Given any set of sets $x$, there is set containing exactly all the element of these sets.- Let $y=\bigcup x$ denote $\forall z[z\in y\leftrightarrow \exists w\in x(y\in w)]$.
- $\forall x\exists y[y = \bigcup x]$.

**The axiom of Nullset**: There is a set with no elements.- $\exists x[x = \varnothing]$

**The axiom of Infinity**: There exists an**inductive**set.- $\exists x[\varnothing\in x\wedge\forall y(y\in x\to y\cup\{y\}\in x) ]$.

**The axiom of Powerset**: For every set x, there is a set containing all the subsets of this set.- Let $y\subseteq x$ abbreviate $\forall z(z\in x\to z\in y)$.
- Let $y=\mathcal{P}(x)$ abbreviate $\forall z(z\in y\leftrightarrow z\subseteq x)$.
- $\forall x\exists y[ y=\mathcal{P}(x)]$

**The axiom schema of Separation**: Every definable subset of a set exists.- $\forall x,\bar{w}\exists y\forall z[z\in y\leftrightarrow z\in x\wedge\phi(z, \bar{w})]$
- The collection of a formula is a
**class**$Y = \{z: \phi(z,\bar{w})\}$. - Let $z\in Y$ abbreviate $\phi(z,\bar{w})$.
- Note that a
*proper*class $Y$ “does not exist”: $\neg \exists y\forall x[x\in y\leftrightarrow x\in Y]$. - We can define cartesian products, relations and functions with this axiom schema.

**The axiom schema of Collection**: If $x$ is a set, and $\phi$ defines a class from each element of $x$, then there is a set which meets all these classes.- $\forall x,\bar{v}\exists y\forall z\in x[ \exists w\phi(w,z,\bar{v})\to \exists w\in y\phi(w,z,\bar{v})]$.

**The axiom schema of Replacement**: The image of a set under a definable class function is a set.- $\forall x,\bar{w}[((\forall a\in x)(\exists! y)\phi(a,y,\bar{w}))\to \exists z \forall y(y\in z\leftrightarrow (\exists a\in x)\phi(a,y,\bar{w})) ]$.
- This is equivalent to Seperation + Collection in ZF-(Sep+Col).

**Axiom of Choice (AC)**: Every set of pairwise disjoint nonempty sets has a “choice set”.

AC has many equivalent theorems. AC also has some pathological results. However, without a choice axiom, one cannot prove a countble union of countble set is countble. People developed ZF+DC+AD for set theory models that AC is not satisfied. AD is incompatible with AC.

- A
**strict partial order**is a irreflecive and transitive binary relation. - A strict partial order is
**linear**if any two elements are comparable. - A strict partial order is
**wellfounded**if every subset contains a minimal element. - A
**wellordering**is linear wellfounded strict partial order. *Theorem*: Given two wellorderings, either they two are isomorphic, or one is isomorphic to an initial segment of the other. Furthermore, the isomorphism is unique.

- A set $x$ is
**transitive**if forall $a\in x$, $b\in a$ implies $b\in x$.- Note: $\in$ is not necessarily a transitive relation on $x$. For exmaple, $\{\varnothing, \{\varnothing\}, \{\{\varnothing\}\}\}$.

- An
**ordinal**is a transitive set $\alpha$ s.t. $\in$ on $\alpha$ is a wellordering. - Let $\text{ORD}$ denote the class of ordinals.
- Define $\alpha < \beta$ iff $\alpha \in \beta$. Then, $<$ is a wellordering on $\text{ORD}$.
- Any wellordered set $P$ is isomorphic to a unique ordinal, called the
**order type**of $P$. - Let $\alpha+1 = \alpha\cup\{\alpha\}$.
- If $\alpha = \beta+1$, $\alpha$ is a
**successor ordinal**; - Otherwise, $\alpha$ is a
**limit ordinal**.

- If $\alpha = \beta+1$, $\alpha$ is a
- Let $\omega$ be the intersection of all inductive sets. Then, $\omega$ is the least non-zero limit ordinal. The elements of $\omega$ are
**natural numbers**. Let $0 := \varnothing$.

- A class $C$ is equal to ORD if it satisfies the following:
- $0\in C$;
- For all $\alpha$, $\alpha\in C\to \alpha+1\to C$;
- If $\lambda$ is a (non-zero) limit ordinal, $(\forall\alpha<\lambda) \alpha\in C\to\lambda\in C$.

- Let $G$ be a class function. Then, there is a unique class function $F$ s.t. for all $\alpha\in\text{ORD}$, $F(\alpha) = G(F\restriction\alpha)$.
*Note*: Generally, people prove uniqueness first, and then existence.

- We can define ordinal addition, multiplication and exponentiation by recursion.

**Cantor normal form**: For any ordinal $\alpha$, there *uniquely* exist natural numbers $n,k_0,\ldots, k_{n-1}$ and ordinals $\alpha \geq \beta_0 > \cdots > \beta_{n-1}$ s.t.

*Note*: It’s possible that $\alpha = \omega^{\alpha}$.

- For each ordinal $\alpha$, define set $V_{\alpha}$ as:
- $V_0 = \varnothing$;
- $V_{\alpha+1} = \mathcal{P}(V_{\alpha})$, for any $\alpha$;
- $V_{\lambda} = \bigcup_{\beta<\lambda}V_{\beta}$, for $\lambda$ a limit ordinal.

- Let the class $V$ be the union of all $V_{\alpha}$.
- For $x\in V$, define its
**rank**to be*the least ordinal*$\alpha$ that $x\in V_{\alpha}$.- One can verify that $\mathrm{rank}(x) = \sup\{\mathrm{rank}(y)+1: y\in x\}$

- The
**transitive closure**of $x$ is defined as the smallest transtive set containing $x$,- For any $x$, let $x_0 = x$ and $x_{n+1} = x_n\cup\bigcup x_n$. Then, the transitive closure is $\mathrm{TC}(x)=\bigcup_{n< \omega} x_n$.

- Assume $\text{ZF}^-$ (ZF minus Foundation), then the axiom of foundation is equivalent to $\forall x(x\in V)$.
*Note*: $x\in V$ is actually the shorthand for $\exists \alpha[\alpha\in\mathrm{ORD} \wedge x\in V_{\alpha}]$.

**Mostowski Collapse**: If a relation $R$ on a class $X$ is *wellfounded*, *setlike* and *extensional*, then there exists a unique transitive class $Y$ and a unique isomorphism $(X,R)\cong (Y,\in)$.

**wellfounded**: For every non-empty subset of $X$, there exists an $R$-minimal element.**setlike**: $R^{-1}(x)$ is always a set;**extensional**: $R^{-1}(x) = R^{-1}(y)$ iff $x=y$.

## Cardinal Arithmetic

**Equivalence of AC**:

**Zorn’s lemma**: Given a strict partial order, if every chain has an upper bound, then there is a maximal element.**Hausdorff Maximality principle**: Every partial ordered set has a maximal chain.**Zermelo’s wellordering theorem**or $\mathrm{AC}^+$: Every set can be well-ordered.*Note*: Whether there exists a*computable*well-ordering of $\mathbb{R}$ is independent of ZFC.

- The cardinalities of any pair of sets are comparable.
- For all infinite sets $X,Y$, $|X|+|Y| = |X|\times |Y|$.

AC also implies the **partition principle**: If there is a surjection from $X$ to $Y$, then there is an injection from $Y$ to $X$. But whether this principle implies AC is still open.

**Cantor-Shröder-Bernstein theorem**:

- Define $|X| = |Y|$ if there is a bijection.
- Define $|X| \leq |Y|$ if there is an injection from $X$ to $Y$.
- (ZF) If $|X| \leq |Y|$ and $|Y| \leq |X|$, then $|X| = |Y|$.

- An ordinal $\alpha$ is a cardinal if for all $\beta<\alpha$, $|\beta| < |\alpha|$.
- Let $\omega_{\alpha}$ denote the $\alpha$-th infinite cardinal; let $\aleph_{\alpha}$ denote its cardinality.
- Let $\kappa^+$ denote the least cardinal of cardinality greater than $\kappa$.
- Similarly, $\kappa^+$ is a
**successor cardinal**; A non-zero cardinal not in this form is a**limit cardinals**.

- Similarly, $\kappa^+$ is a
- $\aleph_{\alpha} + \aleph_{\beta} = \aleph_{\alpha} \cdot \aleph_{\beta} = \max\{\aleph_{\alpha}, \aleph_{\beta}\}$.

- (ZF) For any set $X$, there is an ordinal that cannot be injected into $X$.
- This ordinal is called
**Hartog’s number**$h(X)$.

- Given an ordinal $\alpha$ and $C\subseteq\alpha$, if there does not exist a $\beta\in\alpha$ that is strict greater than all elements of $C$, then $C$ is
**cofinal**in $\alpha$.- Since no one cares successor ordinals, an equivalent definition is $\sup C = \alpha$.

- The
**cofinality**$\mathrm{cf}(\alpha)$ is the minimum of order-types of the cofinal subsets of $\alpha$. - For all $\alpha$, $\mathrm{cf}(\mathrm{cf}(\alpha)) = \mathrm{cf}(\alpha)$.
- For all $\alpha$, $\mathrm{cf}(\alpha)$ is a cardinal not greater than $\alpha$.

- A cardinal $\kappa$ is
**regular**if $\mathrm{cf}(\kappa)=\kappa$; otherwise,**singular**. - (ZFC) Every successor cardinal is regular.
- $\kappa < \kappa^{\mathrm{cf}(\kappa)}$.
- (ZFC) $\mathrm{cf}(2^\kappa) > \kappa$.
- The
**gimel function**of an infinite cardinal $\kappa$ is: $\gimel(\kappa) = \kappa^{\mathrm{cf}(\kappa)}$.*Note*: If $\kappa$ is regular, $\gimel(\kappa) = \kappa^\kappa = 2^\kappa$.

**König’s theorem**: Suppose $\kappa_i < \lambda_i$ for all $i\in I$. Then,

**Cardinal powers**: Suppose $\kappa, \lambda$ are infinite cardinals, then $\kappa^{\lambda}$ can be one of the following:

- If $\kappa < \lambda$, then $\kappa^{\lambda} = 2^{\lambda}$.
- If $\kappa > \lambda$ and $(\exists \mu<\kappa)\mu^{\lambda} \geq \kappa$, then $\kappa^{\lambda} = {\mu}^{\lambda}$.
- If $\kappa > \lambda$ and $(\forall \mu<\kappa)\mu^{\lambda} < \kappa$,
- if $\mathrm{cf}(\kappa) > \lambda$, then $\kappa^{\lambda} = \kappa$.
- if $\mathrm{cf}(\kappa) \leq \lambda$, then $\kappa^{\lambda} = \kappa^{\mathrm{cf}(\kappa)}$.

**Generalized continuum hypothesis (GCH)**: GCH states that $2^{\kappa} = \kappa^+$ for all infinite $\kappa$.

- GCH implies that for $\kappa, \lambda$ infinite cardinals
- If $\lambda < \mathrm{cf}(\kappa)$, $\kappa^{\lambda} = \kappa$.
- If $\mathrm{cf}(\kappa)\leq \lambda <\kappa$, $\kappa^{\lambda} = \kappa^+$.
- If $\kappa \leq \lambda$, $\kappa^{\lambda} = \lambda^+$.

**Cardinal exponentiation**: Define $\kappa^{<\lambda} = \bigcup_{\mu<\lambda}\kappa^{\mu}$. Suppose $\kappa$ is an infinite cardinal.

- If $\kappa$ is regular, then $2^{\kappa} = \gimel(\kappa)$.
- If $\kappa$ is singular and $2^{\lambda}$ is eventually constant as $\lambda\to\kappa$ (so $2^{<\kappa}$ is this constant value), then $2^{\kappa} = 2^{<\kappa}$.
- If $\kappa$ is singular and $2^{\lambda}$ is not eventually constant as $\lambda\to\kappa$, then $2^{\kappa} = \gimel(2^{<\kappa})$.

**Singular cardinals hypothesis (SCH)**: If $\kappa$ singular and $2^{\mathrm{cf}(\kappa)} < \kappa$, then $\kappa^{\mathrm{cf}(\kappa)} = \kappa^+$.

- A (weak)
**limit cardinal**is a cardinal that is neither a successor cardinal nor zero. - A
**strong limit cardinal**$\kappa$ is not reachable by power: for all $\lambda<\kappa$, $2^{\lambda} < \kappa$. - A
*regular limit*cardinal is**weakly inaccessible**.- If $\kappa$ is an uncountable weakly inaccessible cardinal, then $L_{\kappa}$ is a model of ZFC.

- An uncountable
*regular*cardinal $\kappa$ is**strongly inaccessible**if it is a strong limit: for all $\lambda<\kappa$, $2^{\lambda} < \kappa$.- Then, $V_{\kappa}$ is a model of ZFC.

- ZFC cannot prove the existence of any uncountable inaccessible cardinal.

## Infinitary Combinatorics

- A
**filter**$F$ on a set $X$ is a collection of subsets of $X$ s.t.- $F$ is upward closed under $\subseteq$: $(A\in F\wedge B\subseteq X\wedge A\subseteq B)\to B\in F$.
- $F$ is non-empty: $X\in F$.
- $F$ is closed under finite intersections: $(A\in F\wedge B\in F)\to A\cap B\in F$.

- $F$ is
**non-trivial**if $\varnothing\notin F$. - Dually, we can define
**ideal**$I$ as a collection of subsets s.t. $I$ is downward closed, non-empty and closed under finite union. - Given a filter $F$, its
**dual ideal**is $\{X\setminus A: A\in F\}$. - Given an ideal $I$ and its dual filter $F$, a set $A\subseteq X$ is $I$
**-positive**/$F$**-positive**if $A\notin I$.- A filter is a collection of “large” sets; an ideal is “small”; $I$-positive sets are “not small”.

- For $S\subseteq\mathcal{P}(X)$, then $F = \{A\subseteq X: (\exists B\in S)(B\subseteq A)\}$ is the
**filter generated by**$S$. - A filter is $\kappa$
**-complete**if it is closed under intersections of size less than $\kappa$. - A
**ultrafilter**is a filter s.t. for all $A\subseteq X$, exactly one of $A\in F$ or $(X\setminus A)\in F$.- Ultrafilters are exactly the filters maximal w.r.t. $\subseteq$.

- (The ultrafilter lemma) (ZFC) every filter can be exteneded into an ultrafilter.
- An ultrafilter is
**principal**if there is $A\subseteq X$ s.t. $B\in F$ iff $A\subseteq B$.

- Suppose $F$ is a filter on $\omega$, $\langle a_n: n\in\omega \rangle$ is a sequence of real numbers. Then $\lim_F a_n = x$ iff for all $\varepsilon>0$, $\{n: |a_n - x| < \varepsilon \}\in F$.
- This limit satisfies all the usual limit laws.
- If $U$ is a non-principal ultrafilter on $\omega$, then any bounded sequence has an ultralimit $\lim_U a_n$.

- A cardinal $\kappa$ is
**measurable**if there is a $kappa$-complete ultrafilter on $\kappa$. - A cardinal $\kappa$ is called
**real-valued measurable**if there is a $\kappa$-additive probability measure on the power set of $\kappa$ that vanishes on singletons. - An
**atomless**measurement $\mu$ on $\kappa$ is that, for every $A\subseteq\kappa$ with $\mu(A)> 0$, there is $B\subseteq A$ with $0 < \mu(B) < \mu(A)$. - (Ulam) There are two cases for a real-valued measurable $\kappa$:
- $\kappa \leq 2^{\aleph_0}$, there is an atomless measurement on $\kappa$. There is also a measure on the full powerset $\mathcal{P}([0, 1])$ extending Lebesgue measure.
- $\kappa$ is measurable. $\kappa > 2^{\aleph_0}$ (actually a strong limit). Every measurement on $\kappa$ has an atom which yields a $\kappa$-additive $\kappa$-complete ultrafilter.

**Ultraproducts**: Suppose $\langle M_i: i\in I \rangle$ are $\mathcal{L}$ structures, and $U$ is an ultrafilter on $I$. Let $X$ be the set of $I$-sequences that pick one element from each structure:

Let $\sim$ be the equivalence relation on $X$ where $f\sim g$ iff they coincide at the ultrafilter $\{i: f(i)=g(i)\}\in U$. Now, let the **ultraproduct** $\prod_U M_i$ be the structure on universe $X/\sim$:

- For each constant $c$ of $\mathcal{L}$, let $c^{\prod_U M_i} = [i\mapsto c^{M_i} ]_{\sim}$;
- For each relation $R$ of $\mathcal{L}$, let $R^{\prod_U M_i}([f_1 ]_{\sim},\ldots,[f_n ]_{\sim})$ be true iff $\{i: R^{M_i}(f_1(i),\ldots,f_n(i))\}\in U$;
- For each function $g$ of $\mathcal{L}$, let $g^{\prod_U M_i}([f_1 ]_{\sim},\ldots,[f_n ]_{\sim})$ be $[i\mapsto g^{M_i}(f_1(i),\ldots,f_n(i)) ]_{\sim}$.

If $M_i = M$ for all $i\in I$, then $\prod_ U M$ is called the **ultrapower** of $M$ by $U$.

**Łoś’s Theorem**: For any $\mathcal{L}$-formula $\varphi$ and $[f_i ]_{\sim}\in X/\sim$, $\prod_ U M_i\models \varphi([f_1 ]_{\sim},\ldots, [f_n ]_{\sim})$ iff $\{i: M_i\models \varphi(f_1(i),\ldots,f_n(i)) \}\in U$. In particular, the ultraproduct models a sentence iff there is a “large” number of models modeling it.

**Keisler-Shelah isomorphism theorem**: Two structures $M$ and $N$ are elementarily equivalent $M\equiv N$ iff there is an ultrafilter $U$ s.t. the two ultraproducts are isomorphic $\lim_U M \cong \lim_U N$.

**Asympototic Cone**:

- Suppose $\langle X_n, d_n: n\in\omega \rangle$ is a sequence of metric spaces and $x_n\in X_n$ are base points. Let $X$ be the set of sequences $\langle a_n\in X_n: n\in\omega\rangle$ where the sequence $d_n(a_n, x_n)$ is bounded. Let $\sim$ be the equivalence relation that $\langle a_n\rangle \sim \langle b_n\rangle$ if $\lim_U d_n(a_n, b_n) = 0$. Let $d$ be the metric on $X/\sim$ where $d(\langle a_n\rangle, \langle b_n\rangle) = \lim_U d_n(a_n, b_n)$. We define
**ultraproduct**$\prod_U(X_n, d_n, x_n)$ to be $(X/\sim, d)$. - Suppose $(X, d)$ is a given metric space with a base point $p\in X$. The
**asymptotic cone**of $(X, d)$ is $\prod_U(X, d/n)$. - The asymptotic cone is a way of viewing $(X, d)$ from “infinitely far away”.
- The asymptotic cone of $\mathbb{Z}$ with usual metric is isomorphic to $\mathbb{R}$.

**Club**:

- Suppose $\lambda$ a limit ordinal (generally a
*regular uncountable cardinal*) and $C\subseteq \lambda$.- $C$ is
**closed**if it contains all its limit points less than $\lambda$. Formally, for all $\nu<\lambda$, $C\cap \nu$ being cofinal in $\nu$ implies $\nu\in C$. - $C$ is
**unbounded**if for all $\alpha<\lambda$, there exists $\beta\in C$ s.t. $\beta\not\leq \alpha$. - A closed unbounded subset is called a
**club set**.

- $C$ is
- Suppose $\lambda$ a limit ordinal with $\mathrm{cf}(\lambda)>\omega$. Then, the intersection of finitely many clubs is a club.
- Suppose $\lambda$ a cardinal with $\mathrm{cf}(\lambda)>\omega$. Then, for all $\beta< \mathrm{cf}(\lambda)$, the intersection of $\beta$ many clubs $\cap_{\alpha< \beta}C_{\alpha}$ is a club.

**Club filter**: Suppose $\kappa$ is a regular uncountable cardinal.

- The filter generated by the club sets on $\kappa$ is called the
**club filter**on $\kappa$. - The club filter is $\kappa$-complete.
- A subset of $\kappa$ is
**stationary**if it intersects with every club. In other words, club filter positive. - The dual ideal of the club filter is the
**nonstationary ideal**. *Note*: a set in the club filter is not necessarily a club. It’s a set containing club.

**Diagonal intersection**: Let $\langle X_{\alpha}: \alpha<\kappa \rangle$ be a sequence of $\kappa$ many subsets of $\kappa$. Their **diagonal intersection** is defined to be

- The diagonal intersection of $\kappa$ many clubs is a club.
- A filter is called
**normal**if it’s closed under diagonal intersection. The club filter is normal. - A non-trivial normal $\kappa$-complete filter on a regular uncountable cardinal $\kappa$ includes every club of $\kappa$.

**Properties of stationary sets**:

- Given a club $C$ and stationary set $S$, $C\cap S$ is stationary.
- A stationary set is unbounded.
- If $S$ is stationary, then $\{\lambda\in S: \lambda\text{ is a limit ordinal}\}$ is also stationary.
- If we partition a stationary set $S\subseteq\kappa$ into $\lambda<\kappa$ many sets, then one of them will be stationary.

- An ordinal function $f$ on a set $S$ is
**regressive**if $f(\alpha) < \alpha$ for every $\alpha\in S$, $\alpha > 0$. - If $f$ is a regressive function on a stationary set $S$ of $\kappa$, then there is a stationary subset that fixed $f$. Formally, there exists $\gamma < \kappa$ and a stationary set $T\subseteq S$ s.t. $f(\alpha) = \gamma$ for all $\alpha\in T$.
*Example*: Suppose there is a train passing through an infinite number of stations. At every station, there is exactly 1 person getting off, and then finitely many people getting on. We know that after $\omega$ stations there could be arbitrarily many people on the train. Fodor’s lemma shows that after $\omega_1$ stations, there must be 0 people on it.

- Suppose $X$ is a collection of sets. If for all distinct $A,B\in X$, $A\cap B = r$, we call $X$ a $\Delta$
**-system with root**$r$. - Suppose $X$ is an
*uncountable*set of*finite*sets. Then there are an uncountable subset $X’\subseteq X$ and a finite set $r$ s.t. $X’$ is a $\Delta$-system with root $r$. - Suppose $\kappa > \lambda$ are infinite regular cardinals s.t. for all $\delta<\kappa$, $\delta^{< \lambda} < \kappa$. Let $X$ be a collection of $\kappa$ many sets of cardinality less than $\lambda$. Then, there is a subset $X’$ of size $\kappa$ which is a $\Delta$-system.

**Silver’s Theorem**:

- If $\kappa$ is a singular cardinal of uncountable cofinality and $2^{\lambda} = \lambda^+$ for a stationary set of $\lambda < \kappa$, then $2^{\kappa} = \kappa^{+}$.
- If SCH holds for all singular cardinals of cofinality $\omega$, then it holds for all singular cardinals.

**Infinite trees**:

- A tree $T$ is a $\kappa$-tree if its height is $\kappa$ and every level has size less than $\kappa$.
**Kőnig’s lemma**: An $\omega$-tree has an infinite branch.**Aronszajn tree**: There is a $\omega_1$-tree with no branches of order type $\omega_1$.**Suslin line**- A linear order $<$ on $X$ is
**dense**if for all $a < b$ there exists $c\in X$ s.t. $a < c < b$. - A subset $A\subseteq X$ is
**dense in**$X$ if for all $a < b$ there exists $c\in A$ s.t. $a < c < b$. - A linear order $<$ is
**complete**if any set with an upper bound has a least one, and any set with a lower bound has a greatest one. - An
**endpoint**is a maximum or minimum element. - Any two countable dense linear orders without endpoints are isomorphic.
- $\mathbb{R}$ is isomorphic to any complete dense linear order without endpoints that has a countable dense subset.
- A linear order on $X$ is a
**Suslin line**if $<$ is a complete dense linear order without endpoints s.t. every set of disjoint open intervals is countable, but $<$ has no countable dense set (thus not isomorphic to $\mathbb{R}$).

- A linear order $<$ on $X$ is
**Suslin tree**- A
**Suslin tree**is an $\omega_1$-tree such that every chain and antichain is countable. - There is a Suslin line iff there is a Suslin tree.
- Suslin tree is independent of ZFC.

- A

- A $\diamondsuit$
**-sequence**is a sequence $\langle A_{\alpha}:\alpha<\omega_1\rangle$ where $A_{\alpha}\subseteq\alpha$ s.t. for all $X\subseteq\omega_1$, $\{\alpha: X\cap\alpha = A_{\alpha}\}$ is stationary. - $\diamondsuit$ is the statement that there exists a $\diamondsuit$-sequence.
- $\diamondsuit$ implies CH.
- $\diamondsuit$ implies there is a Suslin tree.
- A $\diamondsuit^+$
**-sequence**is a sequence $\langle \mathcal{A}_{\alpha}:\alpha<\omega_1\rangle$ where $\mathcal{A}_{\alpha}\subseteq\mathcal{P}(\alpha)$ s.t. for all $X\subseteq\omega_1$, there exists a club $C\subseteq\omega_1$ s.t. for all $\alpha\in C$, both $X\cap \alpha$ and $C\cap\alpha$ are in $\mathcal{A}_{\alpha}$. - A $\diamondsuit^-$
**-sequence**is a sequence $\langle \mathcal{A}_{\alpha}:\alpha<\omega_1\rangle$ where $\mathcal{A}_{\alpha}\subseteq\mathcal{P}(\alpha)$ s.t. for all $X\subseteq\omega_1$, $\{\alpha: X\cap\alpha \in \mathcal{A}_{\alpha}\}$ is stationary. - $\diamondsuit^+$ is the statement that there exists a $\diamondsuit^+$-sequence; $\diamondsuit^-$ is the statement that there exists a $\diamondsuit^-$-sequence.
- $\diamondsuit^+$ implies $\diamondsuit$; $\diamondsuit^-$ is equivalent to $\diamondsuit$.

## Constructible Hierarchy

- By the downward L-S theorem, there exists a countable model of ZFC. However, ZFC proves there exist uncountable ordinals.
- This is not a real paradox, because given the same sets $A, B$, it is possible that in $V$ there exists a bijection from $A$ to $B$, but an inner model lacks this bijection.
- Cardinality is not absolute.

- (
*Theorem*) By compactness, there exists a model $(M, E)$ of ZFC s.t. $E$ is not well-founded.- Such models are not necessarily recursive.

- (
*Theorem*) By Mostowski collapse, every well-founded model $(M, E)$ is isomorphic to some $(N, \in\restriction N)$. - A model $(N, \in\restriction N)$ when $N$ is a transitive set is called a
**transitive model**.- A countable transitive model is often abbreviated as
**ctm**.

- A countable transitive model is often abbreviated as
*Note*: ZFC+Con(ZFC) does not imply there is a well-founded set model of ZFC.

**Models relation**:

- By Tarski’s undefinability of truth, $\models$ is a well-defined relation only if $N$ is a set.
- For any sentence $\phi$, let $\phi^N$ denote the sentence where all quantifiers $\forall x$ and $\exists x$ are replaced with $\forall x\in N$ and $\exists x\in N$.
- For any transitive set model, $N\models \phi$ iff $\phi^N$ is true.
- When $N$ is a proper class, we use $N\models \phi$ to abbreviate $\phi^N$.

**The Lévy hierarchy**: Similar to arithmetic hierarchy, every formula in set theory is categorized into $\Sigma_n$, $\Pi_n$ and $\Delta_n$.

- If $\phi(v_1,\ldots, v_n)$ is a $\Delta_0$ formula and $M$ is a transitive class. Then for all $x_1,\ldots,x_n\in M$, we have $\phi(x_1,\ldots, x_n)$ iff $\phi^M(x_1,\ldots, x_n)$.
- Suppose $N$, $M$ are transitive classes and $N\subseteq M$.
- If $\phi$ is $\Sigma_1$, then $\phi^N$ implies $\phi^M$. (upward absoluteness)
- If $\phi$ is $\Pi_1$, then $\phi^M$ implies $\phi^N$. (downward absoluteness)
- If $\phi$ is $\Delta_1$, then $\phi^M\leftrightarrow\phi^N$.

**The model** $V_\alpha$:

- If $\alpha$ is a limit ordinal, then $V_\alpha$ is a model of Extensionality, Foundation, Pairing, Union, Nullset, Separation, and Powerset.
- If $\alpha>\omega$, then $V_\alpha$ is a model of Infinity.
- If $\alpha$ is a strongly inaccessible cardinal, then $V_\alpha$ is a model of Collection.

**The model** $H_\kappa$:

- If $\kappa$ is a cardinal, then $H_\kappa$ is the collection of sets whose transitive closure has size less than $\kappa$.
- For every regular cardinal $\kappa$, $H_\kappa$ is a model of ZFC - Powerset.

- Suppose $\langle M_{\alpha}: \alpha\in\text{ORD}\rangle$ is a
**cumulative hierarchy**:- $M_{\alpha}$ is transitive.
- For all $\alpha < \beta$, $M_{\alpha}\subseteq M_{\beta}$.
- (Continuous) If $\lambda$ is a limit, $M_{\lambda} = \bigcup_{\alpha < \lambda} M_{\alpha}$.

- Let $M = \bigcup M_{\alpha}$. Then for every formula $\varphi$, there exists a closed and unbounded set of ordinals $\alpha$, s.t. for all sets $\bar{X}\in M_{\alpha}$, $M_{\alpha}\models\varphi(\bar{x})$ iff $M\models\varphi(\bar{x})$.
*Corollary*: For every finite set of axioms of ZFC, ZFC proves that there is a ctm of these axioms.*Note*: One must give the axioms first, and then find the set.*Note*: It is “For all …, ZFC proves that …”, but not “ZFC proves that for all …”. Therefore, the compactness theorem does not work here.

*Corollary*: ZFC is not finitely axiomatizable.

**Gödel’s** $L$:

- For a set $M$, let $\mathrm{Def}(M)$ be the set of definable sets over $(M, \in)$ with parameters of $M$. The function $M\mapsto\mathrm{Def}(M)$ is $\Delta_1$.
- Replace $\mathcal{P}$ with $\mathrm{Def}$ in the definition of $V$, and we will get the
**constructible universe**$L$.- $L_0 = \varnothing$.
- $L_{\alpha+1} = \mathrm{Def}(L_{\alpha})$, for any $\alpha$;
- $L_{\lambda} = \bigcup_{\beta<\lambda}L_{\beta}$, for $\lambda$ a limit ordinal;
- $L = \bigcup_{\alpha} L_{\alpha}$.

**Properties of** $L$:

- (ZF) For all ordinals $\alpha$,
- $L_{\alpha} \subseteq V_{\alpha}$
- $L_{\alpha}$ and $L$ are transitive. $L$ is a cumulative hierarchy.
- $L_{\alpha}\cap\mathrm{ORD} =\alpha$, so $L$ contains all ordinals.

- $|L_{\alpha}| = |\alpha|$ for each infinite $\alpha$.
- (ZF) $L$ is a model of ZF.
- Define a strict partial order $<_L$ on $L$ as follows: $x <_L y$ if the rank of $x$ in $L$ is less than that of $y$; or they have the same $L$-rank but the minimal number of formula defining $x$ is less than that of $y$. Then, $<_L$ is a well-ordering on $L$.
- (ZF) $L\models \mathrm{AC}$.

- Let $V=L$ abbreviate $\forall x\exists \alpha\in\mathrm{ORD}\ x\in L_{\alpha}$.
- (The absoluteness of constructibility) If $M$ is a transitive class inner model of ZF that contains all ordinals, then $L^M = L$. Further, $(V=L)^L$.
*Corollary*: $L$ is the smallest transitive inner model that contains all ordinals.

- There is a finite set $S$ of axioms of ZF-Powerset s.t. if $M\models S$ and $M\models V=L$, then $M=L_{\lambda}$ for some limit ordinal $\lambda$.
- There is a $\Sigma_2$ sentence $\varphi$ s.t. for every transitive set $M$, $M\models\varphi$ iff $M = L_{\lambda}$ for some limit ordinal $\lambda$.
- For every limit ordinal $\lambda$, if $M\prec (L_\lambda)$ is an elementary submodel, then the transitive collaps of $M$ is $L_\gamma$ for some limit ordinal $\gamma \leq \lambda$.
- Assume $V=L$. If $\kappa$ is a cardinal and $x\subseteq\kappa$, then $x\in L_{\lambda}$ for some $\lambda < \kappa^+$.
- $L$ models GCH.
- $\text{Con}(\text{ZF})\to\text{Con}(\text{ZFC})\to\text{Con}(\text{ZFC}+\text{GCH})$.

- If $\kappa$ is an uncountable regular cardinal, then $L_{\kappa}$ models ZF-Powerset.
- If $V=L$, then $H_{\kappa} = L_{\kappa}$ for all cardinals.

**Other properties of** $L$:

- $V=L$ implies $\diamondsuit^+$.
- If $\kappa$ is weakly inaccessible, then $L_{\kappa}$ models ZFC.
- $V=L$ implies there is no measurable cardinals.

## Forcing

I don’t fully understand this topic, so only put basic ideas here.

Forcing is a secret weapon of the logicians. To show that a sentence $\phi$ is consistent of $T$,

- First, start with a model $M$ in which $\phi$ is not necessarily true.
- Punch new elements into $M$ and get a structure $N$, where $\phi$ is true.
- Show that $N$ is still a model of $T$.

Since downward absolute sentences cannot be forced, forcing only works for “complex enough” sentences.

Since we must “understand” the elements we want to add into $M$, we cannot choose $M = V$. To have more choices on the missing elements, we want $M$ as simple as possible. Therefore, we can use a ctm $M$. The consistency of ZFC does not promise the existence of ctm, but that’s a minor issue that can be fixed.

Now, suppose that we want to prove the negation of CH. Observe that:

- $M$ has $\omega$, since it’s absolute.
- $M$ does not have all subsets of $\omega$, because otherwise $M$ cannot be countable.
- In $V$, there is an injection from $\omega_2^M$ to $\mathcal{P}(\omega)$, but $M$ cannot see it.

Now, we want to inject this injection into $M$. We cannot directly take a union, because there is no guarantee that we can have a model. Therefore, we use the idea of compactness here: Let $\mathbb{P}$ be finite partial functions $\omega\times\omega_2^M\to 2$. Define a partial relation $<$ to be the reverse of inclusion. (Due to historical reasons, we want small elements be finer) Then,

- There is a unique maximal $1_{\mathbb{P}} = \varnothing$.
- Every element is part of a multimap from $\omega_2$ to $\omega$, $\omega\times\omega_2$.
- Let $f(\alpha) = \{n: p(n, \alpha) = 1\}$, then $f$ will be a partial function $\omega_2\to\mathcal{P}(\omega)$.

- $\mathbb{P}$ in $M$, because both $\omega$ and $\omega_2$ are in $M$.
- If $p\leq q$, then we say $p$
**extends**$q$ or $p$**refines**$q$. - If there is some $r$ extends both $p$ and $q$, we say $p$ and $q$ are
**compatible**.- Intuitively, two compatible elements look like in a sublattice, though there does not exist a real lattice. For example, $p = \{(0,0)\mapsto 1, (0,\omega)\mapsto 0\}$ and $q = \{(0,0)\mapsto 1, (1,1)\mapsto 0\}$. Then, $r = p\cup q$ refines both $p$ and $q$.

- A subset $F$ of $\mathbb{P}$ is called
**filter**if it’s upward closed and pointwise compatible.- This is similar to a lattice filter: nonempty, upward closed, and closed under join $\vee$.
- $f = \bigcup F$ is a partial function $\omega\times\omega_2^M\to 2$.

Now we want to make sure that

- The union of $F$ is a total function $\omega\times\omega_2^M\to 2$.
- The function $\omega_2\to\mathcal{P}(\omega)$ that the union of $F$ leads to is an injection.
- By augmenting $M$ with $F$, we can get a ZFC model.

The concept of *generics* solves these issues:

- A subset $X\subseteq\mathbb{P}$ is
**dense**if it can refine every element of $\mathbb{P}$. - $X$ is
**dense below**$p$ if it can refine every element $q\leq p$. - Suppose $M$ is a transitive model containing $\mathbb{P}$. A filter $G\subseteq\mathbb{P}$ is $M$
**-generic**if it meets every dense set. That is, for all dense $D\subseteq\mathbb{P}$ in $M$, we have $G\cap D\neq\varnothing$. - For each $(n,\alpha)\in\omega\times\omega_2$, the set $\{p\in\mathbb{P}: (n,\alpha)\in\mathrm{dom}(p)\}$ is dense. Thus, $g = \bigcup G$ is a total function.
- For all $\alpha, \beta< \omega_2$, the set $\{p\in\mathbb{P}: (\exists n)(n,\alpha)\in\mathrm{dom}(p)\wedge (n,\beta)\in\mathrm{dom}(p)\wedge p(n,\alpha)\neq p(n,\beta) \}$ is also dense. Thus, the function $f(\alpha) := \{n: g(n,\alpha) = 1\}$ is an injection from $\omega_2$ to $\mathcal{\omega}$.

Now we go back to augment $M$. We want to get a new model $M[G ]$ s.t. $M\subseteq M[ G]$ and $G\in M[G ]$. Intuitively, consider that we put associate each element and each formula with a “probability”. (See Boolean-valued model. Not every textbook discusses this because the evil in details often makes things more complicated.) For every $m\in M$, we bind a “probability” $p\in\mathbb{P}$ to it as $(m, p)$. However, we cannot use $\{(m, p): m\in M\wedge p\in\mathbb{P}\}$ because it’s clearly not a model: Let $a = (m_1, p_1)$ and $b = (m_2, p_2)$, then $\{a, b\}$ cannot be represented. Therefore, we need to define a cumulative hierarchy:

- A set $\tau$ is a $\mathbb{P}$
**-name**if every element in $\tau$ is an ordered pair $(\sigma, p)$, where $\sigma$ is a $\mathbb{P}$-name and $p\in\mathbb{P}$. - Equivalently, we have the following hierarchy:
- $V^{P}_0 = \varnothing$;
- $V^{P}_{\alpha+1} = \mathcal{P}(V^{P}_{\alpha}\times \mathbb{P})$;
- $V^{P}_{\lambda} = \bigcup_{\alpha< \lambda} V^{P}_{\alpha}$;
- $V^{P} = \bigcup_{\alpha} V^{P}_{\alpha}$;
- Since being a $\mathbb{P}$-name is absolute, the set of $\mathbb{P}$-names in $M$ equals $V^{P}\cap M$.

What we define is like the language $\mathcal{L}_{M}$, but works on a “fuzzy” structure with “probabilities”. If we cut the “probability” with a “threshold”, then hopefully we will get a definite model.

- Let $G\subseteq\mathbb{P}$ be a $M$-generic. For every $\mathbb{P}$-name $\tau$, the
**value of**$\tau$**under**$G$ is defined by recursion: $\tau[ G] = \{\sigma[ G]: (\sigma, p)\in\tau\wedge p\in G\}$. - For example, let $\tau = \{(\varnothing, p), (\{(\varnothing, 1)\}, g)\}$. Suppose $g\in G$. Then $\{(\varnothing, 1)\}[ G] = 0$ is in $\tau[ G]$. Hence, if $p\notin G$, $\tau[ G] = \{ 0\}$; otherwise, $\tau[ G] = 2$.
- Let $M[ G]$ be the set of $\tau[ G]$ for every $\mathbb{P}$-name $\tau$ that is in $M$.

Intuitively, $M[G ]$ is like a threshold cut, plus Mostowski collapse.

Now we have:

- $M[ G]$ is transitive.
- By the hierarchical definition of values.

- $M\subseteq M[ G]$.
- Let $\check{x} = \{(\check{y}, 1_{\mathbb{P}}): y\in x\}$ for $x\in M$. Then $\check{x}[G ] = x$. Because the maximal $1$ is always in $G$, just like probability 1.

- $G\in M[ G]$.
- Let $\tau = \{(\check{p}, p): p\in\mathbb{P} \}$. Then, $\tau[ G] = G$.

- $\mathrm{ORD}\cap M = \mathrm{ORD}\cap M[ G]$

Such $G$ is not constructibly defined, but always exists, because the following lemma:

- If $M$ is a ctm, then for every forcing poset $\mathbb{P}$ and $p\in P$, there is a $M$-generic filter $G$ containing $p$.
*Note*: the existence of generic filters comes from that $M$ can only see finite subsets of $\mathbb{P}$. For example, let $\mathbb{P}$ be an infinite binary tree. If $\mathcal{P}(\mathbb{P})^M = \mathcal{P}(\mathbb{P})^V$, then there do not exist a generic filter. Because for every filter $F$, the complement set $\mathbb{P}\setminus F$ is dense.

Now we need to show that $M[ G]$ is a model of ZFC. To show this, we simulate the “threshold cut” process for formulas: for each formula, we define a “probabilistic” value, and then cut it with $G$. Formally, we define the **forcing relation** $\Vdash$ s.t.

Note that $\Vdash$ is well-defined in $M$, since every $\mathbb{P}$-name and $p$ is in $M$. The only thing $M$ does not know is $G$.

We define it as follows:

- Atomic formula $\tau\in\sigma$:
- An element is in a set if it equals to some element in the set.
- $\| \tau\in\sigma \| = \bigvee_{(\sigma’, p’)\in\sigma}\left( I_{p’}\cap \| \tau = \sigma’ \| \right)$, where $I_{p}$ is the principal ideal $\{q\in \mathbb{P}: q\leq p’\}$.
*Note*: in a complete boolean algebra generated by a poset topological space, $\wedge$ is $\cap$, but $\vee$ is not $\cup$. Actually, $p\vee q$ is $(p\cup q)^{\bot\bot}$. Here, $\bot$ means the complement set of its closure. And of course, $\neg$ is $\bot$. For example, in a poset of finite binary strings, $I_{00}\cup I_{01}$ does not include the string $0$, but $I_{00}\vee I_{01} = I_{0}$.*Note*; To understand why here we use $I_p$, consider that an event with probability $p$. It happens when $p$ is greater than the cut $G$, which is equivalent to $G\leq p$.

- $p\Vdash \tau\in\sigma$ iff $\bigcup_{(\sigma’, p’)\in\sigma} \{q \leq p’: q\Vdash \tau = \sigma’ \}$ is dense below $p$.
- $p\Vdash \tau\in\sigma$ iff $\{ q\leq p: \exists (\sigma’, p’)\in\sigma [q\leq p’\wedge q\Vdash \tau = \sigma’]\}$ is dense below $p$.

- Atomic formula $\tau = \sigma$:
- A set $x$ is equal to $y$ if $z\in x \leftrightarrow z\in y$.
- $\| \tau = \sigma \| = \bigcap_{(\tau’, p’)\in\tau}(I_{p’}\rightarrow \|\tau’\in\sigma\|)\cap \bigcap_{(\sigma’, p’)\in\sigma}(I_{p’}\rightarrow \|\sigma’\in\tau\|)$
- Here, $x \rightarrow y$ means $\neg x\vee y$.

- $p\Vdash \tau = \sigma$ iff for all $(\pi, \_)\in \tau\cup\sigma$ and all $q\leq p$, $q\Vdash \pi\in\tau \leftrightarrow q\Vdash \pi\in\sigma$.
- $p\Vdash \tau = \sigma$ iff for all $(\tau’, p’)$, $\{q\in\mathbb{P}: q\leq p’\to q\Vdash\tau’\in\sigma \}$ is dense below $p$, and for all $(\sigma’, p’)$, $\{q\in\mathbb{P}: q\leq p’\to q\Vdash\sigma’\in\tau \}$ is dense below $p$.

- Formula $\varphi\wedge\psi$:
- $\| \varphi\wedge\psi \| = \|\varphi\|\cap \|\psi\|$.
- $p\Vdash \varphi\wedge\psi$ iff $p\Vdash\varphi$ and $p\Vdash\psi$.

- Formula $\varphi\vee\psi$:
- $\| \varphi\vee\psi \| = \|\varphi\|\vee \|\psi\|$.
- $p\Vdash \varphi\vee\psi$ iff $\{q\in\mathbb{P}: q\Vdash\varphi\}\cup\{q\in\mathbb{P}: q\Vdash\psi\}$ is dense below $p$.

- Formula $\neg\varphi$:
- $\| \neg\varphi \| = \neg \| \varphi \|$
- $p\Vdash \neg\varphi$ iff there is no $q\leq p$ s.t. $q\Vdash \varphi$

- Formula $\exists x\ \varphi(x)$:
- $\| \exists x\ \varphi(x) \| = \bigvee_{\tau} \| \varphi[ \tau] \|$.
- $p\Vdash \exists x\ \varphi(x)$ iff the set of $q\leq p$ s.t. there exists a $\mathbb{P}$-name $\tau$ satisfying $q\Vdash \varphi[ \tau]$ is dense below $p$.

- Formula $\forall x\ \varphi(x)$:
- $\| \forall x\ \varphi(x) \| = \bigcap_{\tau} \| \varphi[ \tau] \|$.
- $p\Vdash \forall x\ \varphi(x)$ iff for all $\mathbb{P}$-name $\tau$, $p\Vdash \varphi[ \tau]$.

The forcing relation has the following properties:

**Force = Truth**lemma. Described above.**Definability**. $\Vdash$ is a well-defined relation in $M$.**Coherence**.- If $p\Vdash\varphi$, then for all $q\leq p$, $q\Vdash\varphi$.
- If the set $q\Vdash\varphi$ is dense below $p$, then $p\Vdash\varphi$.

Now we can prove that $M[ G]$ is a model by showing evidence as $\mathbb{P}$-names in $M$.

*Lemma*: If $M$ is a transitive model and $G$ is a $M$-generic, then $M[ G]\models\mathrm{ZFC}$.

One thing we need to ensure is that in $M[ G]$, $\omega_2$ is the $\omega_2$ in $M$. This is given by ccc.

**Countable chain condition (ccc)**:

- A poset $\mathbb{P}$ is
*ccc*if every*strong***anti***chain*is countable. - A strong antichain is an antichain whose elements are pairwise
*incompatible*. - If $M$ proves $\mathbb{P}$ is ccc, then $M$ and $M[ G]$ have exactly the same cardinals.

At last, let’s handle the existence of ctm. Not every model of ZFC has a ctm. However, from a metatheorem’s view, the reflection theorem ensure that arbitrarily large finite subsets of ZFC axioms have a ctm. If the subset is large enough s.t. whatever we used till now is included, then we can force $|\mathcal{P}(\omega)| = \aleph_2$. Then, by the conpactness theorem, $\neg\mathrm{CH}$ must be consistent with ZFC.

# Summary

Things I have learnt:

- Have a basic understanding of mathematical logic. Know what mathematicians in the last century did.
- Logic objects are often organized in an infinite hierarchy. There does not exist an ultimate theory.
- Most useful theory is not complete. There are always not expected models.
- Therefore, the strenth of the theory limits what we can prove.

- Infinite numbers are often counterintuitive.
- The existence of something does not imply is understandable by human beings.
- In different universe, people have different views of the same concept.

# References

- Martin Hils, and François Loeser. A First Journey through Logic. American Mathematical Society, 2019.
- Andrew Marks. Set Theory Notes. 2020.
- There are some typos, but none of them will affect the understanding.

- Yiannis N. Moschovakis. Lecture Notes in Logic. 2014.
- Robert I. Soare. Turing Computability: Theory and Applications (1st. ed.). Springer, 2016.
- Thomas Jech. Set Theory: The Third Millennium Edition, revised and expanded. Springer, 2003.