Today I Learned

Some of the things I've learned every day since Oct 10, 2016

Category Archives: model theory

179: Universal Axiomatization and Substructures

Definition universal sentence is a first-order sentence of the form \forall \bar{v} \phi (\bar{v}), where \phi has no quantifiers.

Definition We say an \mathcal{L}-theory T has a universal axiomatization if there’s a set \Gamma of universal \mathcal{L}-sentences such that \mathcal{M} \vDash T if and only if \mathcal{M} \vDash \Gamma.

With the above definitions, an \mathcal{L}-theory  T has a universal axiomatization if and only if wherever \mathcal{M} \vDash T and \mathcal{N \subseteq M} we have that \mathcal{N} \vDash T. In the words of Marker’s Model Theory, “a theory is preserved under substructure if and only if it has a universal axiomatization.”

Advertisements

177: Elementary Embeddings, Elementary Substructures

In logic and model theory, an embedding \gamma : \mathcal{M} \rightarrow \mathcal{N} between \mathcal{L}-structures \mathcal{M, N} is called an elementary embedding if

\mathcal{M} \vDash \phi(a_1, \dots, a_n) \Leftrightarrow \mathcal{N} \vDash \phi(\gamma(a_1), \dots, \gamma(a_n))

for any \mathcal{L}-sentence \phi and a_1, \dots, a_n \in M. A substructure \mathcal{M} \subseteq \mathcal{N} is called an elementary substructure, denoted \mathcal{M} \preceq \mathcal{N}, if the inclusion map is an elementary embedding.

174: Decidability of Recursive, Complete, Satisfiable Theories

It’s pretty much in the title. If T is an \mathcal{L}-theory which is recursive, complete, and satisfiable, then T is decidable. That is, there’s an algorithm which takes an \mathcal{L}-sentence \phi and outputs whether or not T \vDash \phi.

(T being recursive means that there’s an algorithm which similarly takes \phi as input but outputs whether \phi \in T.)

173: Vaught’s Test

In model theory, Vaught’s Test (also known as the Łoś–Vaught test) determines whether certain \mathcal{L}-theories T are complete. It states that if T is satisfiable, has no finite models, and is \kappa-categorical for some \kappa \geq |\mathcal{L}|, then T is complete.

Proof outline Assume T isn’t complete. Then there’s a sentence \phi such that T \nvDash \phi, T \nvDash \neg \phi, meaning T \cup \{\phi\}, T \cup \{\neg \phi \} are satisfiable, meaning both have infinite models (since T has no finite models), so by [172] we can find models \mathcal{M}, \mathcal{N} of cardinality \kappa which respectively satisfy these theories. But since \mathcal{M}, \mathcal{N} disagree on \phi, they are not elementarily equivalent and hence not isomorphic, contradicting the assumption that T is \kappa-categorical. Thus T must be complete.

172: Infinite Models of L-Theories (Variation of Lowenheim-Skolem)

Suppose \mathcal{L} is a first-order language and T is an \mathcal{L}-theory with an infinite model. Then for every infinite cardinal \kappa \geq |\mathcal{L}|, T has a model of cardinality \kappa.

This result — a variation of the Löwenheim–Skolem theorem — implies that theories with infinite models can’t have unique models up to isomorphism.

169: Finiteness of Logical Implication

Suppose T is an \mathcal{L}-theory and T \vDash \phi. Then \Delta \vDash \phi for some finite \Delta \subseteq T.

Proof Let \Delta \subseteq T be finite and suppose \Delta \nvDash \phi. Then \Delta \cup \{\neg \phi\} is satisfiable, so T \cup \{ \neg \phi \} is finitely satisfiable and by the compactness theorem T \nvDash \phi.

166: Elementary Equivalence and Isomorphism between Finite Structures

Let \mathcal{L} be a first-order language. In general, it is true that if two \mathcal{L}-structures \mathcal{M, N} are isomorphic, then they are elementarily equivalent. However, elementary equivalence does not in general imply isomorphism.

When \mathcal{M, N} are finite structures, however, the two conditions are equivalent. That is,

\mathcal{M} \equiv \mathcal{N} \Leftrightarrow \mathcal{M} \cong \mathcal{N}.

165: The Compactness Theorem (Henkin Construction)

In logic, the Compactness Theorem states that a first-order theory is satisfiable if and only if it is finitely satisfiable. Here we give a sketch of a proof for the Theorem using Henkin construction. (The full proof is very syntax-heavy and I’m too lazy to type that much LaTeX, but this is the overall idea of the method.)

Let \mathcal {L} be a first-order language and T be a finitely satisfiable \mathcal{L}-theory.

We can construct a language \mathcal{L}^* \supseteq \mathcal{L} and a finitely-satisfiable \mathcal{L}^*-theory T^* \supseteq T such that any \mathcal{L}^*-theory extending T^* has the witness property. The way we do this is by first adding a constant symbol c_\varphi to \mathcal{L} for each \mathcal{L}-formula \varphi with a single free variable, calling the result \mathcal{L}_1. For each such \varphi we also add to T the \mathcal{L}_1-sentence

(\exists v \varphi (v)) \rightarrow \varphi (c_\varphi ),

calling the resulting \mathcal{L}_1-theory T_1. We then keep doing this indefinitely and call the unions of all such languages and theories \mathcal{L}^* and T^*, respectively, with the result that T^* is finitely satisfiable and any extension thereof has the witness property.

We then extend T^* to a finitely-satisfiable and maximal \mathcal{L}^*-theory T^\prime which by the above will also have the witness property. The way we do this is by adding either \varphi or \neg \varphi to T^* for each \mathcal{L}^*-sentence \varphi (exactly one of which will keep the theory finitely satisfiable).

Now that we have an extended theory (within an extended language) which is finitely satisfiable, maximal, and has the witness property, we show there is a model \mathcal{M} of it, which will obviously also be a model of our original theory T.

We define the universe of \mathcal{M} to be the set of constant symbols of \mathcal{L}^* modulo \sim, where \sim is the relation such that

c \sim d \Leftrightarrow T^\prime \vDash c = d.

We also define

f^\mathcal{M} (t_1 / \sim \dots t_n / \sim) = f(t_1 \dots t_n) / \sim,

(t_1/\sim \dots t_n/\sim) \in R^\mathcal{M} \Leftrightarrow T^\prime \vDash R(t_1 \dots t_n),

where f is a function symbol and R is a relation symbol of \mathcal{L}^*.

We then proceed to show by induction on terms and formulas that

\mathcal{M} \vDash \varphi \Leftrightarrow T^\prime \vDash \varphi

for all \mathcal{L}^* sentences \varphi. This shows that \mathcal{M} is a model of T^\prime, and thus is a model of T, which is what we wanted.

156: Expanding a Finitely Satisfiable L-Theory

Let T be a finitely satisfiable \mathcal{L}-theory and \phi an \mathcal{L}-sentence. Then either T \cup \{\phi\} or T \cup \{ \neg \phi\} is finitely satisfiable, with the or obviously being exclusive.

Proof If T \cup \{\phi\} is not finitely satisfiable, then there is a finite subset \Delta thereof for which \Delta \vDash \neg \phi. In fact, it must be that \Delta \subseteq T. Let \Sigma be a finite subset of T. Since \Delta \cup \Sigma is a finite subset of T it is satisfiable, and we also have that \Sigma \cup \Delta \vDash \neg \phi, so we have that \Sigma \cup \{\neg \phi \} is satisfiable. Thus T \cup \{\neg \phi\} is finitely satisfiable.

This fact can be used to expand a finitely satisfiable theory to a maximal finitely satisfiable theory, one element at a time.

152: The Compactness Theorem

In logic, the Compactness Theorem states that a theory (a set of sentences in a first-order language) is satisfiable (has a model) if and only if every finite subset of it is satisfiable. The Theorem is notable for being “the cornerstone of model theory”.

That finite subsets of a satisfiable theory are satisfiable is trivial, so proofs of the Theorem focus on the converse implication. One popular choice of proof makes use of the Completeness Theorem, but it is also possible to sidestep the Completeness Theorem entirely and instead give a proof using Henkin construction.