Today I Learned

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

Category Archives: logic

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.

162: Most Subsets of a Countable Structure Aren’t Definable Over a Finite Subset

Suppose \mathcal{M} is an \mathcal{L}-structure with universe M which is countably infinite, and suppose N is a finite subset of M. Recall that a subset X of M^p is definable over N iff there exists an \mathcal{L} formula \varphi and tuple (b_1, \dots, b_q) \in N^q such that

X = \{(a_1, \dots, a_p) \in M^p : \mathcal{M} \vDash \varphi(a_1, \dots, a_p, b_1, \dots, b_q)\}.

Suppose The set of subsets of M is a classic example of an uncountable set. However, there are only countably many \mathcal{L}-formulas and countably many tuples of any size from N, so it follows that there are at most countably many N-definable subsets of M. This means almost all subsets of M will be undefinable over any given finite subset N \subseteq M.

161: Elementary Substructures (Logic)

Suppose \mathcal{L} is a first-order language and \mathcal{M, N} are \mathcal{L}-structures with \mathcal{M} \subseteq \mathcal{N}. Then we say \mathcal{M} is an elementary substructure of \mathcal{N} if and only if for any \mathcal{L}-formula \varphi,

\mathcal{M} \vDash \varphi (a_1, \dots, a_k) \Leftrightarrow \mathcal{N} \vDash \varphi (a_1, \dots, a_k)

for a_i \in M. To denote this, we write \mathcal{M} \preceq \mathcal{N}.

159: Term Substitution (Logic)

Notation In a language \mathcal{L}, where \tau (x_1, \dots, x_n) is a term with free variables from x_1, \dots, x_n and \tau _1 , \dots, \tau _n are terms, let

\tau(x_1, \dots, x_n ; \tau _1, \dots, \tau _n)

denote the term resulting by simultaneously swapping every instance of x_i in \tau for \tau _i.

Further, let \nu be a map from the variables of our language to elements of an \mathcal{L}-structure \mathcal{M}, and \bar{\nu} be its natural extension to a map from terms to elements of \mathcal{M}.

Then we have that

\bar{\nu}(\tau(x_1, \dots, x_n ; \tau _1, \dots, \tau _n)) = \tau(\bar{\nu}(\tau_1), \dots, \bar{\nu}(\tau _n)).

That is, terms “behave well” under substitution.

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.