## 502 – Notes on compactness

October 1, 2009

The goal of this note is to present a proof of the following fundamental result. A theory ${T}$ is said to be satisfiable iff there is a model of ${T.}$

Theorem 1 (Compactness) Let ${T}$ be a first order theory. Suppose that any finite subtheory ${T_0\subseteq T}$ is satisfiable. Then ${T}$ itself is satisfiable.

As indicated on the set of notes on the completeness theorem, compactness is an immediate consequence of completeness. Here I want to explain a purely semantic proof, that does not rely on the notion of proof.

The argument I present uses the notion of ultraproducts. Although their origin is in model theory, ultraproducts have become an essential tool in modern set theory, so it seems a good idea to present them here. We will require the axiom of choice, in the form of Zorn’s lemma.

The notion of ultraproduct is a bit difficult to absorb the first time one encounters it. I recommend working out through some examples in order to understand it well. Here I confine myself to the minimum necessary to make sense of the argument.

## 502 – Compactness

September 25, 2009

First, two exercises to work some with the notion of ultrapower: Check that $|\prod_n M_n/{\mathcal U}|=|{\mathbb R}|$ whenever ${\mathcal U}$ is a nonprincipal ultrafilter on the natural numbers, and

1. $M_n={\mathbb N}$ for all $n,$ or
2. $\lim_{n\to\infty}|M_n|=\infty.$

Our argument for compactness required the existence of nonprincipal ultrafilters. One might wonder whether this is a necessity or just an artifact of the proof. It is actually necessary. To see this, I will in fact show the following result as a corollary of compactness:

Theorem.  If ${\mathcal F}$ is a nonprincipal filter on a set $I,$ then there is a nonprincipal ultrafilter on $I$ that extends ${\mathcal F}.$

(Of course, this is a consequence of Zorn’s lemma. The point is that all we need is the compactness theorem.)

Proof. Consider the language ${\mathcal L}=\{\hat X\mid X\subseteq I\}\cup\{c,\hat\in\}.$ Here, each $\hat X$ is a constant symbol, $c$ is another constant symbol, and $\hat\in$ is a symbol for a binary relation (which we will interpret below as membership).

In this language, consider the theory $\Sigma=\{c\hat\in\hat X\mid X\in {\mathcal F}\}\cup{\rm Th}(I\cup{\mathcal P}(I),\in,X\mid X\subseteq I).$ A model $M$ of this theory $\Sigma$ would look a lot like $I\cup{\mathcal P}(I),$ except that the natural interpretation of ${\mathcal F}$ in $M,$ namely, $\{\hat X^M\mid X\in{\mathcal F}\}$ is no longer nonprincipal in $M$, because $c^M$ is a common element of all these sets.

Note that there are indeed models $M$ of $\Sigma,$ thanks to the compactness theorem.

If $M\models\Sigma,$ let ${\mathcal U}=\{X\subseteq I\mid M\models c\hat\in \hat X\},$ and note that ${\mathcal U}$ is a nonprincipal ultrafilter over $I$ that contains ${\mathcal F}.$ $\Box$

## 502 – Propositional logic (3)

September 11, 2009

Example 13 ${\lnot(A\land B)\leftrightarrow(\lnot A\lor\lnot B)}$ is a tautology. This is an example of De Morgan’s laws.

Example 14 ${A\lor(B\land C)\leftrightarrow(A\lor B)\land(A\lor C)}$ is a tautology.

Definition 19 A formula ${A}$ is satisfiable iff there is some valuation ${v}$ such that ${v\models A.}$ Otherwise, we say that ${A}$ is contradictory, or unsatisfiable.

Remark 7 ${A}$ is unsatisfiable iff ${\lnot A}$ is a tautology.

Example 15 ${(p\rightarrow q)\rightarrow(q\rightarrow p)}$ is not a tautology, but it is satisfiable.

Definition 20 If ${v}$ is a valuation and ${S}$ is a set of formulas, ${v\models S}$ iff ${v\models A}$ for all ${A\in S.}$ For a given ${S,}$ if there is such a valuation ${v,}$ we say that ${S}$ is satisfiable, or has a model, and that ${v}$ is a model of ${S.}$ Otherwise, ${S}$ is unsatisfiable or contradictory.

## 580 -Cardinal arithmetic (11)

March 12, 2009

4. Strongly compact cardinals and ${{sf SCH}}$

Definition 1 A cardinal ${kappa}$ is strongly compact iff it is uncountable, and any ${kappa}$-complete filter (over any set ${I}$) can be extended to a ${kappa}$-complete ultrafilter over ${I.}$

The notion of strong compactness has its origin in infinitary logic, and was formulated by Tarski as a natural generalization of the compactness of first order logic. Many distinct characterizations have been found.