Homework III, Math 736, Model-Theory.

These notes present an alternative approach to compactness and completeness. The proofs of the lemmas are exercises (not necessarily to be turned in).

Let Fm^{n}(L) comprise the n-ary formulas of L, defined as in the notes (‘Homework II’) as strings of symbols, but with formulas (ϕ → ψ) allowed as well, with (ϕ → ψ)^{M} = (¬ϕ ∨ ψ)^{M}. We may leave off outer brackets when writing formulas, and write ϕ_{0} ∧ ϕ_{1} ∗ ϕ_{2} for (ϕ_{0} ∧ ϕ_{1}) ∗ ϕ_{2}, where ∗ is ∧ or →. Let Fm(L) be the union of the chain Fm^{0}(L) ⊆ Fm^{1}(L) ⊆ . . .. We shall assume that all tuples, terms and formulas have the arities they must, for what we say to make sense.

Let Γ be a subset of Fm(L), and let ϕ be in Fm(L). We can define

Γ ⊧ ϕ

to mean that, for every M in 𝔐𝔬𝔡(L), and for every sequence (a_{i} : i ∈ ω) of elements of M, if M ⊧ ψ(a) for each ψ in Γ, then M ⊧ ϕ(a). This agrees with the definition given in class when all formulas are sentences. We can also say that M is a model of Γ, writing

M ⊧ Γ,

if there is some sequence (a_{i} : i ∈ ω) of elements of M such that M ⊧ ψ(a) for each ψ in Γ.

We now define

Γ ⊢ ϕ

to mean that ϕ is derivable from Γ, in a sense to be specified presently. The point of these notes will be to prove that this definition agrees with the one given in class. That ϕ is derivable from Γ will mean that there is a proof of ϕ from Γ, namely a finite sequence of formulas, ending with ϕ, of which each formula:

• is in Γ,

• is an axiom, or

• follows from previous formulas in the sequence by a rule of inference.

Before naming the axioms and rule(s) of inference, we can already check the following.

Lemma 1. If Γ ⊢ ϕ, then ϕ is derivable from a finite subset of Γ.

Lemma 2. Derivability is transitive, in the sense that, if each formula in a set Θ is derivable from Γ, and ϕ is derivable from Θ, then Γ ⊢ ϕ.

We shall use a single rule of inference, namely Modus Ponens:

{ϕ, (ϕ → ψ)} ⊢ ψ.

Our axioms will be the following (where, throughout, t_{i}, u_{i}, t, u and v are terms, and ϕ and ψ are formulas of appropriate arities):

2 Model-theory homework III

• the tautologies, namely formulas F (ϕ_{0}, …, ϕ_{n−1}), where F is a tautologous n-ary propositional formula (an n-ary term of the language of Boolean algebras whose interpretation in F_{2} is the constant-function 1);

• the axioms of equality, namely:

– (t_{0} = u_{0}) ∧ ⋯ ∧ (t_{n−1} = u_{n−1}) → (ϕ(t) → ϕ(u));

– t = t;

– (t = u) → (u = t);

– (t = u) ∧ (u = v) → (t = v);

• the axioms of quantification, namely:

– ϕ(x, t) → ∃x_{n} ϕ;

– ∀x_{n} ¬ϕ → ¬∃x_{n} ϕ;

– ϕ → ∀x_{n} ϕ, where ϕ is n-ary;

– ∀x_{n} (ϕ → ψ) → (∀x_{n} ϕ → ∀x_{n} ψ);

– ∀x_{n} ϕ, where ϕ is an axiom. Lemma 3. Γ ⊢ ϕ ⟹ Γ ⊧ ϕ.

Changing a notation used in class, let us write

ϕ ≈ ψ

if ϕ^{M} = ϕ^{M} for all M, and let us now use

ϕ ∼ ψ

to mean that {ϕ} ⊢ ψ and {ψ} ⊢ ϕ. Both ≈ and ∼ are equivalence-relations (and will turn out to be the same). Lemma 4. ϕ ∼ ψ ⟹ ϕ ≈ ψ. Lemma 5. If Γ ⊢ ϕ, then Γ′ ⊢ ϕ′, where Γ′ is got from Γ by replacing each an element with a ∼-equivalent one, and ϕ′ ∼ ϕ.

So, as far as derivability and interpretations are concerned, we can identify formulas with their ∼-classes. One point of doing this is the following. Lemma 6. Fm(L)/∼ is naturally the universe of a Boolean algebra.

Now define

⟨Γ⟩ = {ϕ : Γ ⊢ ϕ}.

Say that Γ is consistent if ⊥ ∉ ⟨Γ⟩. Lemma 7. If Γ is consistent, then the image of ⟨Γ⟩ in Fm(L)/ ∼ is the smallest filter containing the images of the formulas in Γ.

Now we can prove compactness—that every consistent set of formulas has a model—just as in class; but we have to do more work at some points.

Derivability depends a priori on signature. We must rule out the possibility that there is a proof of ϕ from Γ in a signature larger than L, but not in L itself. Lemma 8. Suppose Γ ⊆ Fm^{n}(L), and ϕ ⊆ Fm^{n+k+1}(L), and c is a k + 1tuple of constant-symbols not in L.

• If Γ ⊢ ϕ, then Γ ⊢ ∀x_{n} … ∀x_{n+k} ϕ.

• If Γ ⊢ ϕ(x, c) in L ∪ {c_{0}, …, c_{k}}, then Γ ⊢ ∀x_{n} … ∀x_{n+k} ϕ in L.

Suppose L ⊆ L′, and L′ − L contains only constant-symbols. Lemma 9. The inclusion of Fm(L) in Fm(L′) induces an embedding of Fm(L)/∼ in Fm(L′)/∼.

For any consistent set T of formulas of L′, there is a relation on constantsymbols given by

c ∼ d ⟺ T ⊢ c = d.

(This is distinct from the relation ∼ on formulas.) Lemma 10. The relation ∼ on constant-symbols is an equivalence-relation.

Suppose in particular that L has a constant-symbol c_{ϕ} for each unary formula ϕ, and suppose Γ is a consistent set of formulas of L. Lemma 11. There is a consistent set T of formulas of L′ such that:

• Γ ⊆ T;

• T ⊢ ∃x_{0} ϕ → ϕ(c_{ϕ}) for each unary formula ϕ;

• T is maximally consistent: the image of ⟨T ⟩ in Fm(L′)/∼ is an ultra-

filter. Lemma 12. Suppose T is a maximally consistent set of formulas of L′ such that T ⊢ ∃x_{0} ϕ → ϕ(c_{ϕ}) for each unary formula ϕ. Then:

• There is a unique model M of T whose universe M comprises the ∼-

classes of the constant-symbols c_{ϕ}, and such that – c^{M} = c/∼ for each constant-symbol c,

– f^{M}(c/∼) = d/∼ if T ⊢ fc_{0} … c_{n−1} = d, for all function-symbols f, and

– (c/∼) ∈ R^{M} if T ⊢ Rc_{0} … c_{n−1}, for all relation-symbols R.

• If M is this model, then ϕ^{M} = {(c/∼) : T ⊢ ϕ(c)} for all formulas ϕ.