MATH 220BC: Mathematical Logic - Course Review

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:

1. $F$ is countable: $F = \{f_0, f_1,\ldots\}$.
2. $F$ is closed under desired operations like recursion, composition, etc.
3. There is a "computer": $u\in F$, $u(n, \bar{x}) = f_n(\bar{x})$.
4. 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.

$$\varphi^{n+m}_i(x_1,\ldots,x_n,y_1,\ldots,y_m) = \varphi^{m}_{s^m_n(i,x_1,\ldots,x_n)}(y_1,\ldots,y_m)$$

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:

1. $0$ has no predecessor.

• (A1) $\forall x \neg Sx=0$

2. Every non-zero number has a predecessor.

• (A2) $\forall x\exists y(\neg x=0\to Sy=x)$

3. Two numbers with equal successors are equal.

• (A3) $\forall x\forall y(Sx=Sy\to x=y)$

4. $0$ is the identity of addition.

• (A4) $\forall x\ x+0 = 0$

5. Successor commutes with addition.

• (A5) $\forall x\forall y\ x+Sy =S(x+y)$

6. $0$ is the zero of multiplication.

• (A6) $\forall x\ x\cdot 0 = 0$

7. Multiplication is distributive over successor.

• (A7) $\forall x\forall y\ x\cdot Sy =x\cdot y + x$

8. "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:

$$\mathrm{PA}_0\models \forall y\left[ \phi(\underline{n_1},\ldots,\underline{n_p},y) \leftrightarrow y = \underline{f(n_1,\ldots, n_p)} \right]$$

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

$$\mathfrak{M}\models \left[ \forall x(\exists z>x)(\exists v< a)\theta(v,z) \right] \to (\exists v< a)\forall x(\exists z>x)\theta(v,z)$$

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.

$$\mathrm{PA}_0\vdash \phi(\underline{\#\psi})\leftrightarrow\psi$$

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:

$$P^R_T(x,y) :\equiv P_T(x,y)\wedge\neg(\exists z\leq y)\exists u(P_T(u,z)\wedge \nu(x,u))$$

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,

$$\text{PA}\vdash \forall x_1,\ldots,x_n\exists !y\ \chi_f(x_1,\ldots, x_n,y)$$

• 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$,

$$\mathrm{PA}\vdash \phi\leftrightarrow \mathrm{Sat}(\underline{\#\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$,

1. (Necessitation Rule, N) $T\vdash \phi \Rightarrow T\vdash \Box_T\phi$;
2. (Distribution Axiom, K) $T\vdash [\Box_T\phi\wedge \Box_T(\phi\to\psi)]\to \Box_T\psi$;
3. (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:

$$\forall\bar{w}\exists y\forall z\ (z\in y\leftrightarrow \phi(z, \bar{w}))$$

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.

Wellordering:

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

Ordinals:

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

Transfinite Induction:

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

$$\alpha = \omega^{\beta_0}\cdot k_0 + \cdots + \omega^{\beta_{n-1}}\cdot k_{n-1}$$

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

The cumulative hierarchy:

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

Cardinal:

• 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.
• $\aleph_{\alpha} + \aleph_{\beta} = \aleph_{\alpha} \cdot \aleph_{\beta} = \max\{\aleph_{\alpha}, \aleph_{\beta}\}$.

Hartogs's theorem:

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

Cofinality:

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

Regular cardinals:

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

$$\sum_{i\in I} \kappa_i < \prod_{i\in I} \lambda_i$$

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

Inaccessible cardinals:

• 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

Filters:

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

Ultralimits:

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

Measurable cardinal:

• 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$:
  1. $\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.
  2. $\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:

$$X = \{ f: \mathrm{dom}(f)=I\wedge (\forall i\in I)(f(i) \in M_i) \}$$

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

$$\bigtriangleup_{\alpha< \kappa} X_{\alpha} = \left\{ \beta< \kappa: \beta\in\bigcap_{\alpha< \beta} X_{\alpha} \right\} = \bigcap_{\alpha < \kappa}\left( X_{\alpha}\cup\{\beta: \beta\leq\alpha\} \right)$$

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

Fodor's lemma:

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

The ∆-system lemma:

• 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}$).
• 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.

Diamond:

• 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

Skolem's paradox:

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

Transitive model:

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

Absoluteness:

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

The reflection theorem

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

Condensation:

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

$$M[ G]\models\varphi(\tau_1[ G],\ldots, \tau_n[ G]) \iff (\exists p\in G)\ p\Vdash^{\mathbb{P}}\varphi(\tau_1,\ldots, \tau_n)$$

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