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.

Read the rest of this entry »


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.

Read the rest of this entry »

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.

Read the rest of this entry »