Math 736, Model-Theory, 2001, fall. Here are some additional notes on terms and formulas; Problems 5 and 6 constitute Homework II. Revised, 25 October 2001.

Fix a signature L. Let c, f and R range respectively over the constant-, function- and relation-symbols of L; let M range over 𝔐𝔬𝔡(L); let i, k, m, and n range over ω.

For each n, we want to define a set Tm^{n}(L), of n-ary terms of L. Each t in Tm^{n}(L) should have, for each M, an interpretation t^{M}, which is an n-ary function on M. We want the terms and their interpretations to satisfy the following requirements.

0. For each c, there is t in Tm^{0}(L) such that t^{M} is c^{M} for each M.

1. If f is n-ary, then there is t in Tm^{n}(L) such that t^{M} is f^{M} for each M.

2. There is t in Tm^{1}(L) such that t^{M} is id_{M} for each M.

3. For every function σ : m → n, and for every u in Tm^{m}(L), there is t in Tm^{n}(L) such that t^{M} is

a ↦ u^{M}(a_{σ(0)}, …, a_{σ(m−1)}) : M^{n} → M

for each M.

4. For each u in Tm^{m}(L), and for any t_{0}, …, t_{m−1} in Tm^{n}(L), there is t in Tm^{n}(L) such that t^{M} is u^{M} ∘ (t_{0}^{M}, …, t_{m−1}^{M}) for each M.

5. No terms t exist whose interpretations t^{M} are not required by the preceding clauses.

Then the sets Tm^{n}(L) of n-ary terms t, and their interpretations t^{M}, can be defined as follows.

(a) Tm^{0}(L) contains the symbols c (each a string of length 1).

(b) Tm^{i+1}(L) contains the symbol x_{i} (a string of length 1).

(c) Tm^{n+1}(L) includes Tm^{n}(L).

(d) If f is m-ary, and u_{0}, …, u_{m−1} are in Tm^{n}(L), then Tm^{n}(L) contains fu_{0} ⋯ u_{m−1} (the concatenation of the strings f, u_{0}, …, u_{m−1}).

(e) Tm^{n}(L) contains no other strings than those required by the preceding clauses, and if t ∈ Tm^{n}(L), then for every M, the interpretation t^{M} is:

• a ↦ c^{M}, if t is c;

• a ↦ a_{i}, if t is x_{i};

• f^{M} ∘ (u_{0}^{M}, …, u_{m−1}^{M}), if t is fu_{0} ⋯ u_{m−1} (where f is m-ary and

the u_{i} are in Tm^{n}(L)).

The definition of the interpretations of terms depends on how terms can be analyzed; so the validity of the definition must be checked. To do this, one can use the following.

Lemma. A proper initial segment of a term is not a term; that is, if a string α_{0}α_{1} ⋯ α_{n} of symbols α_{i} is a term, and m < n, then α_{0}α_{1} … α_{m} is not a term.

Proof. The claim is trivially true for terms of length 1. Suppose it is false for a term t of length k+1. Then t is ft_{0} ⋯ t_{n−1} for some terms t_{i}, but t has a proper initial segment of the form fu_{0} ⋯ u_{m−1}, where the u_{i} are terms. Then there is some least i such that t_{i} is not u_{i}; but then also one of these is an initial segment of the other. Thus the claim fails for a term of length k or less—if it fails for a term of length k + 1. By induction, the claim holds for terms of all lengths.

Lemma (unique readability of terms). Every term is uniquely of the form c, x_{i} or ft_{0} ⋯ t_{n−1}, where the t_{i} are terms.

Proof. If the analysis of a term as ft_{0} ⋯ t_{n−1} is not unique, then (as in the proof of the previous lemma) one of the t_{i} can be assumed to be a proper initial segment of another term.

Finally, by induction on the length of terms, every n-ary term is also n+ 1-ary and has an interpretation as such. So terms and their interpretations are well-defined. Now we can check that the several numbered requirements of terms are met:

0. Let t be c.

1. Let t be fx_{0} ⋯ x_{n−1}.

2. Let t be x_{0}.

3. The required term t can be denoted u(x_{σ(0)}, …, x_{σ(m−1)}), and can be defined inductively:

• If u is c, then t is c.

• If u is x_{i}, then t is x_{σ(i)}.

• If u is fu_{0} ⋯ u_{k−1}, then t is ft_{0} ⋯ t_{k−1}, where t_{i} is u_{i}(x_{σ(0)}, …, x_{σ(m−1)}).

4. The required term t can be denoted u(t_{0}, …, t_{m−1}), and can be defined inductively:

• If u is c, then t is c.

• If u is x_{i}, then t is t_{i}.

• If u is fu_{0} ⋯ u_{k−1}, then t is fv_{0} ⋯ v_{k−1}, where v_{i} is u_{i}(t_{0}, …, t_{m−1}).

5. Every interpretation t^{M} satisfies one of the requirements:

(a) The nullary term c is a term t such that t^{M} = c^{M}.

(b) Let u be the unary term x_{0} (whose interpretation in M, or id_{M}, is required); let σ be the map from 1 to i + 1 such that σ(0) = i; then x_{i} is an i + 1-ary term t such that t^{M} is a ↦ u^{M}(a_{σ(0)}).

(c) if an n-ary term t has a required interpretation, then the interpretation of t as an n + 1-ary term is also required, since this interpretation is a ↦ t^{M}(a_{σ(0)}, …, a_{σ(n−1)}), where σ is the inclusion of n in n + 1.

(d) Let u be fx_{0} ⋯ x_{m−1}; then its interpretation in M, namely f^{M}, is required. Suppose the interpretations of the terms t_{i} are required; then so is the interpretation of ft_{0} ⋯ t_{m−1}, since this interpretation is u^{M} ∘ (t_{0}^{M}, …, t_{m−1}^{M}).

Now we can move on to formulas. For each n, we want to define a set Fm^{n}(L), comprising the n-ary formulas of L. Each ϕ in Fm^{n}(L) should have, for each M, an interpretation ϕ^{M}, which is an n-ary relation on M. We want the formulas and their interpretations to satisfy the following requirements.

0. There is ϕ in Fm^{2}(L) such that ϕ^{M} is {(a, b) ∈ M^{2} : a = b} for each M.

1. If R is n-ary, then there is ϕ in Fm^{n}(L) such that ϕ^{M} is R^{M} for each M.

2. For any m-ary term F of the signature of Boolean algebras, and for any ψ_{0}, …, ψ_{m−1} in Fm^{n}(L), there is ϕ in Fm^{n}(L) such that ϕ^{M} is F^{P(M^{n})}(ψ_{0}^{M}, …, ψ_{m−1}^{M}) for each M.

3. For any t_{0}, …, t_{m−1} in Tm^{n}(L), and for any ψ in Fm^{m}(L), there is ϕ in Fm^{n}(L) such that ϕ^{M} is

{a ∈ M^{n} : (t_{0}^{M}(a), …, t_{m−1}^{M}(a)) ∈ ψ^{M}}

for each M.

4. For any u_{0}, …, u_{n−1} in Tm^{m}(L), and for any ψ in Fm^{m}(L), there is ϕ in Fm^{n}(L) such that ϕ^{M} is

{(u_{0}^{M}(a), …, u_{n−1}^{M}(a)) ∈ M^{n} : a ∈ ψ^{M}}

for each M.

5. No formulas ϕ exist whose interpretations ϕ^{M} are not required by the preceding clauses.

To meet these requirements, we propose to define the sets Fm^{n}(L) of n-ary formulas ϕ, and their interpretations ϕ^{M}, as follows.

(a) Fm^{n}(L) contains (t = u) whenever t and u are in Tm^{n}(L).

(b) Fm^{n}(L) contains Rt_{0} ⋯ t_{m−1} whenever R is m-ary and t_{0}, …, t_{m−1} are in Tm^{n}(L).

(c) Fm^{0}(L) contains ⊥ and ⊤; and Fm^{n}(L) contains ¬ψ and (ψ ∧ χ) and (ψ ∨ χ) whenever ψ, χ ∈ Fm^{n}(L). (The symbols ⊥ and ⊤ and ¬ and ∧ and ∨ can be supposed distinct from any symbols in L.)

(d) Fm^{n}(L) contains ∃x_{n} ψ and ∀x_{n} ψ whenever ψ ∈ Fm^{n+1}(L).

(e) Fm^{n}(L) contains no other strings of symbols than those required by the preceding clauses, and if ϕ ∈ Fm^{n}(L), then for every M the interpretation ϕ^{M} is:

• {a ∈ M^{n} : t^{M}(a) = u^{M}(a)}, if ϕ is (t = u);

• {a ∈ M^{n} : (t_{0}^{M}(a), …, t_{m−1}^{M}(a)) ∈ R^{M}}, if ϕ is Rt_{0} ⋯ t_{m−1};

• ∅, if ϕ is ⊥;

• ∅^{c}, if ϕ is ⊤;

• (ψ^{M})^{c}, if ϕ is ¬ψ;

• ψ^{M} ∩ χ^{M}, if ϕ is (ψ ∧ χ);

• (¬(¬ψ ∧ ¬χ))^{M}, if ϕ is (ψ ∨ χ);

• {a ∈ M^{n} : (a, b) ∈ ψ^{M}, some b in M}, if ϕ is ∃x_{n} ψ;

• (¬∃x_{n} ¬ψ)^{M}, if ϕ is ∀x_{n} ψ.

Problem 5. Show that the proposed definition of Fm^{n}(L) is valid and meets the requirements.

Now let Fm_{0}^{n}(L) be the smallest subset of Fm^{n}(L) that contains the formulas Rt_{0} ⋯ t_{m−1} and (t = u) and that contains ¬ψ and (ψ ∧ χ) and (ψ ∨ χ) when it contains ψ and χ. Let Fm_{p}^{n}(L) be the smallest subset of Fm^{n}(L) such that:

• Fm_{0}^{n}(L) ⊆ Fm_{p}^{n}(L);

• Fm_{p}^{n}(L) contains ⊥ and ⊤;

• Fm_{p}^{n}(L) contains ∃x_{n} ψ and ∀x_{n} ψ when ψ ∈ Fm_{p}^{n+1}(L).

(The subscript p stands for prenex, which describes the elements of Fm_{p}^{n}(L).) Say that n-ary formulas ϕ and ψ are equivalent if their interpretations in M are the same, for every M.

Problem 6. Show that for every formula in Fm^{n}(L) there is an equivalent formula in Fm_{p}^{n}(L).