Logics, Structures & Models

Languages

Vocabulary: A vocabulary or language is a set which contains the following: i) A set of function symbols $\mathcal{F}$ and positive integers $n_f$ for each $f\in \mathcal{F}$ ii) A set of relation symbols $\mathcal{R}$ and positive integers $n_R$ for each $R\in \mathcal{R}$ iii) A set of constant symbols $\mathcal{C}$ The numbers $n_f$ and $n_R$ tell us a function $f\in \mathcal{F}$ is a function of $n_f$ variables and a relation $R\in \mathcal{R}$ is a relation of $n_R$ variables.

Let $\tau$ denote the the vocabulary or language, then trivially $\mathcal{F}\subseteq \tau$, $\mathcal{R}\subseteq \tau$, and $\mathcal{C}\subseteq \tau$. The vocabulary is often denoted as $\tau =\{f,R,c\}$ (and sort symbols for many-sorted logic).

The empty language $\tau =\{\}$, is the language of equality.

Formulas and Sentences

$\tau$-terms: i) Constant symbols $c\in \tau$ are $\tau$-terms ii) Variable $v_1,\dots ,v_n$ are $\tau$-terms iii) If $v_1,\dots ,v_n$ are $\tau$-terms and $f\in \tau$ is a function symbol, then $f(v_1,\dots ,v_n)$ are $\tau$-terms

We say that $\varphi$ is an atomic formula if $\varphi$ is either of the form: i) $t_1=t_2$ where $t_1$ and $t_2$ are terms ii) $R(t_1,\dots ,t_{n_R})$, where $R\in \mathcal{R}$ and $t_1,\dots ,t_{n_R}$ are terms

We say that $\varphi$ is a $\mathcal{L}$-formula if $\varphi$ is atomic and i) If $\varphi$ is an $\mathcal{L}$-formula, then so it $\neg \varphi$ ii) If $\varphi$ and $\psi$ are atomic, then $(\varphi \wedge \psi )$ and $(\varphi \vee \psi )$ are $\mathcal{L}$-formulas iii) $\exists v_i\varphi$ and $\forall v_i\varphi$ are $\mathcal{L}$-formulas, where $i\in I=\{1,2,\dots \}$ (index)

Note: ‘Complex’ formulas (ones where no logical connectives: $\wedge ,\vee ,\neg ,\to ,\leftrightarrow$ are involved) may be logically equivalent to atomic formulas. E.g., Let $\varphi$ be an atomic formula, then the complex formula $\neg \neg \varphi$ (as the connective '$\neg$' is applied twice) is equivalent to $\varphi$ as according to double negation elimination, this is denoted as $\varphi \equiv \neg \neg \varphi$. $\to$ Logical connectives themselves are ‘truth function’ as they may be represented via truth tables (intakes truth values of atomic formulas and outputs the truth state of the entire complex formula)

Free variables: A formula has free variables if and only if some variables in it are not bound by quantifiers. $\to$ E.g., of a bound variable $\forall x(x>2)$, the expression "$x>2$" has the quantifier '$\forall$' attached to it.

Sentence: A sentence is a formula with no free variables (i.e., a formula is given by $\phi (v_1,\dots ,v_n)$, while a sentence is given by $\phi$). For a sentence $\phi$, we write $\mathcal{M}\models \phi$ if $\phi$ is true (or satisfied) in the structure $\mathcal{M}$.

Clarification

Let $\varphi$ be a formula w/ free variables from $\overline{v}=(v_{i_1},\dots ,v_{i_m})$ and let $\overline{a}=(a_{i_1},\dots ,a_{i_m})\in M^m$. $\mathcal{M}\models \varphi (\overline{a})$ is defined inductively as follows: i) If $\varphi$ is $t_1=t_2$, then $\mathcal{M}\models \varphi (\overline{a})$ if $t_1^{\mathcal{M}}(\overline{a})=t_2^{\mathcal{M}}(\overline{a})$ ii) If $\varphi$ is $R(t_1,\dots ,t_{n_R})$, then $\mathcal{M}\models \varphi (\overline{a})$ if $(t_1^{\mathcal{M}}(\overline{a}),\dots ,t_{n_R}^{\mathcal{M}}(\overline{a}))\in R^{\mathcal{M}}$ iii) If $\varphi$ is $\neg \psi$, then $\mathcal{M}\models \varphi (\overline{a})$ if $\mathcal{M}/\models \psi (\overline{a})$ iv) If $\varphi$ is $(\psi \wedge \theta )$, then $\mathcal{M}\models \varphi (\overline{a})$ if $\mathcal{M}\models \psi (\overline{a})$ and $\mathcal{M}\models \theta (\overline{a})$ v) If $\varphi$ is $(\psi \vee \theta )$, then $\mathcal{M}\models \varphi (\overline{a})$ if $\mathcal{M}\models \psi (\overline{a})$ and $\mathcal{M}\models \theta (\overline{a})$ vi) If $\varphi$ is $\exists v_j\psi (\overline{v},v_j)$, then $\mathcal{M}\models \varphi (\overline{a})$ if there is $b\in M$ such that $\mathcal{M}\models \psi (\overline{a},b)$ vii) If $\varphi$ is $\forall v_j\psi (\overline{v},v_j)$, then $\mathcal{M}\models \varphi (\overline{a})$ if $\mathcal{M}\models \psi (\overline{a},b)$ for all $b\in M$

The vocabulary/signature $\tau$ is the set of non-logical symbols as defined above, the language $\mathcal{L}$ is the set of logical & non-logical symbols, and so $\tau \subset \mathcal{L}$. The set of logical symbols (for first-order logic) contains connectives, logical constants, parentheses, equality relation ,quantifiers and variables (i.e., $\{\wedge ,\vee ,\neg ,\to ,\leftrightarrow ,(,),=,\exists ,\forall ,v_1,\dots \}$), these deal with the general syntax of the logic. There are a countably infinite number of logical symbols (unless one includes extensions to the logic w/ an uncountable amount of logical symbols) as there are an countably infinite number of variables. Thus, $|\mathcal{L}|\ge {\aleph }_0$, even when the vocabulary is finite, and hence, $|\mathcal{L}|=\tau +{\aleph }_0$. $\to$ ‘Extensions’ to first-order logic deal with the set of logical symbols and sentence formation rules, (i.e., in second-order logic we add infinitely-many second-order variables or predicates $P,Q,\dots ,$etc. to the language).

Note: Sometimes the $\mathcal{L}$-formulas are used interchangeably with $\tau$-formulas especially is the logic (and set of logical symbols) has been fixed. Even though this isn’t precise.

Structures

Structures: An $\mathcal{L}$-structure $\mathcal{M}$ is given by the following: i) A nonempty set $M$, which is the domain or underlying set of the structure ii) A function $f^{\mathcal{M}}:M^{n_f}\to M$ for each $f\in \mathcal{F}$ iii) A set $R^M\subseteq M^{n_R}$ for each $R\in \mathcal{R}$ iv) A element $c^{\mathcal{M}}\in M$ for each $c\in \mathcal{C}$ $f^{\mathcal{M}},R^{\mathcal{M}}$ and $c^{\mathcal{M}}$ denote the interpretation of the symbols $f,R,c$ in the vocabulary w/in the structure. A structure is often denoted $⟨M,f^{\mathcal{M}},R^{\mathcal{M}},c^{\mathcal{M}}⟩$, the domain and interpretations of non-logical symbol (which are syntactic objects) are semantic objects as they live in the model.

Let '$\tau$' denote the vocabulary of the logic (set of non-logical symbols). The following are examples: E.g., - The vocabulary/language of set theory is $\tau =\{\in \}$ - The language of graph theory is $\tau =\{R\}$ where $R$ is a binary relation - The language of arithmetic $\tau =\{+,\times ,S(x),0\}$ - The language of rings $\tau =\{+,-,\times ,0,1\}$ - The language of ordered rings $\tau =\{+,-,\times ,<,0,1\}$ - The language of pure set $\tau =\varnothing$ It can be observed that expanding the vocabulary $\tau$ to an expansion $\sigma \supset \tau$ will further increase the expressive power of the language as you are now able to talk about further intricacies of structure with the added function and relation symbols. It can also be observed that in this expanded language, the type of structure is further specified. i.e., every non-empty vocabulary describes sets with additional attached structure, thus, the empty language $\tau =\varnothing$, describes the most general type of structure of pure sets.

Model: A model of nonempty set of sentences $T$ (i.e., a theory) is a structure $\mathcal{M}$ for which $T$ is true in $\mathcal{M}$, denoted $\mathcal{M}\models T$, ”$\mathcal{M}$ satisfies $T$.”

Notation:

• $\mathcal{L}[\tau ]$ or ${\text{Sent}}_{\mathcal{L}}(\tau )$ denotes the class of $\mathcal{L}$-sentences of vocabulary $\tau$
• ${\text{Form}}_{\mathcal{L}}(\tau )$ denotes the class of $\mathcal{L}$-formulas of vocabulary $\tau$
• $\mathcal{L}(\tau )$ denotes the logic $\mathcal{L}$ of the vocabulary $\tau$
• Str$[\tau ]$ denotes the class of $\tau$-structures (if you want to specify the logic, then let Str${}_{\mathcal{L}(\tau )}$ denote the class of $\mathcal{L}(\tau )$-structures)
• Mod${}_{\mathcal{L}}^{\tau }(\phi )=\{\mathfrak{A}|\mathfrak{A}\models \phi \}$ for $\phi$ is an $\mathcal{L}$-sentence (in the vocabulary $\tau$), this notation can be generalized to sets of sentences $T\subseteq \mathcal{L}(\tau )$, consider Mod${}_{\mathcal{L}}^{\tau }(T)$.

Logics

Definition of a Logic: A logic $\mathcal{L}$ can be defined as a pair $(\mathcal{L},{\models }_{\mathcal{L}})$ where $\mathcal{L}$ is a mapping defined on vocabularies $\tau$ such that $\mathcal{L}[\tau ]$ is the class of $\mathcal{L}$-sentences of vocabulary $\tau$, and ${\models }_{\mathcal{L}}$, the satisfaction relation, is a (satisfaction) relation between structures and $\mathcal{L}$-sentences. i.e., i) $\mathcal{L}:\tau \to \mathcal{L}[\tau ];$ and ii) ${\models }_{\mathcal{L}}$ is a relation on ($St{r}_{\mathcal{L}(\tau )}\times \mathcal{L}[\tau ]$) Moreover, the following hold: i) if $\tau \subseteq \sigma$, then $\mathcal{L}[\tau ]\subseteq \mathcal{L}[\sigma ]$ ii) if $\mathfrak{A}{\models }_{\mathcal{L}}\phi ,$ then $\phi \in \mathcal{L}[{\tau }_{\mathfrak{A}}]$ where ${\tau }_{\mathfrak{A}}$ denotes the vocabulary of the structure $\mathfrak{A}$ iii) Isomorphism Property: if $\mathfrak{A}{\models }_{\mathcal{L}}\phi$ and $\mathfrak{A}\cong \mathfrak{B}$, then $\mathfrak{B}{\models }_{\mathcal{L}}\phi$ iv) Reduct Property: if $\phi \in \mathcal{L}[\tau ]$ and $\tau \subseteq {\tau }_{\mathfrak{A}}$, then $\mathfrak{A}{\models }_{\mathfrak{A}}\phi ⟺\mathfrak{A}\upharpoonright \tau {\models }_{\mathcal{L}}\phi$ v) Renaming Property: Let $\rho :\tau \to \sigma$ be a renaming. Then for each $\phi \in \mathcal{L}[\tau ]$ there is a sentence, ${\phi }^{\rho }\in \mathcal{L}[\sigma ]$ such that for all $\tau$-structures $\mathfrak{A}$, then $\mathfrak{A}{\models }_{\mathcal{L}}\phi ⟺{\mathfrak{A}}^{\rho }{\models }_{\mathcal{L}}{\phi }^{\rho }$ (i.e., allows for variables to be replaced to produce logically equivalent formulas, e.g., some simple examples are if $P\equiv R$ then $P\wedge Q\equiv P\wedge R$ or $\forall xP(x)\equiv \forall yP(y)$).

Reducts: Consider two $\sigma ,\tau$ such that vocabularies $\sigma \supseteq \tau$ and a $\sigma$-structure $\mathfrak{A}$, the $\tau$-reduct of $\mathfrak{A}$, denoted $\mathfrak{A}\upharpoonright \tau$ , is the structure obtained by the domain\underlying set $A$ interpreting the symbols in $\tau$, a subset of the full vocabulary $\sigma$. i.e., You are removing the symbol in $\sigma$\ $\tau$ and retaining the domain and the interpretation of symbols in $\tau$ E.g., Consider the field $R=⟨\mathbb{R},+,\cdot ,0,1,<⟩$, and some sub-vocabulary $\tau =\{+,\cdot \}$ (the language of rings), then the $\tau$-reduct of $R,R\upharpoonright \tau =⟨\mathbb{R},+,\cdot ⟩$, a ring (minus the constant symbols, constraints)

Similarly you may also define an ‘expansion’ by adding symbols to the vocabulary $\tau$ to obtain a new vocabulary $\sigma \supseteq \tau$, and for a $\tau$-structure $\mathfrak{A}$, the expansion to the vocabulary $\sigma$ is ${\mathfrak{A}}^{\prime }\succ \mathfrak{A}$ (not to be confused with an elementary extension).

E.g., From the example above, consider the ring $R=⟨\mathbb{R},+,\cdot ⟩$, then the expansion to the vocabulary $\sigma =⟨+,\cdot ,0,1,<⟩$ is the structure $R^{\prime }=⟨\mathbb{R},+,\cdot ,0,1,<⟩$

Many-Sorted Logic

Many-sorted logic introduces sort symbols $s_1,s_2\dots$ for every ‘sort’ of object. These symbols are added to the vocabulary of the logic. A vocabulary of many-sorted logic would look as follows: $\tau =\{s,\dots R,\dots ,f,\dots c,\dots \}$ for $s,\cdots \in S$, the set of sorts, $R,\cdots \in \mathcal{R}$, the set of relation symbols, $f,\cdots \in \mathcal{F}$, the set of function symbols, $c,\cdots \in \mathcal{C}$, the set of constant symbols ($0$-ary function symbols). As above, $S,\mathcal{R},\mathcal{F},\mathcal{C}\subseteq \tau$. Sort symbols are assigned…

A many-sorted structure is given as follows: $\mathfrak{A}=⟨A_s,\dots ,R^{\mathfrak{A}},\dots ,f^{\mathfrak{A}},\dots ,c^{\mathfrak{A}}⟩$ Where $A_s$ is the domain of each sort $s\in \tau$.

Let $R$ be a binary relation equipped w/ sort symbols $s_1,s_2$, $f$ a unary function symbol equipped w/ sort symbol $s_2$ whose argument place is equipped w/ $s_1$ and $c$ be a constant equipped w/ $s_1$. Then $\tau =\{s_1,s_2,s_3,R,f,c\}$ and so $R^{\mathfrak{A}}\subseteq A_{s_2}\times A_{s_1}$, $f^{\mathfrak{A}}:A_{s_1}\to A_{s_2}$, and $c^{\mathfrak{A}}\in A_{s_1}$.

Reducts may also be defined on many-sorted structures, and there may also remove sort symbols as well as relation, function and constant symbols.

E.g., $\mathfrak{A}=⟨A_{s_1,A_{s_2}},A_{s_3},R^{\mathfrak{A}},f^{\mathfrak{A}},c^{\mathfrak{A}}⟩\upharpoonright \{s_1,s_2,R\}=⟨A_{s_1},A_{s_2},R^{\mathfrak{A}}⟩$

Notion of (Model) Classes

Model Class

A ‘model class’ is a general term for classes of structures (models) of a given vocabulary, these classes may be arbitrary and not definable within the logic.

Elementary Class

Let $\mathcal{L}$ be a logic and $\mathcal{K}$ a class of $\tau$-structures ($\mathcal{K}\subseteq$ Str$[\tau ]$), $\mathcal{K}$ is an elementary class (or $\mathcal{K}$ is elementary in $\mathcal{L}$) iff there is a $\phi \in \mathcal{L}[\tau ]$ such that $\mathcal{K}=$ Mod${}_{\mathcal{L}}^{\tau }(\phi )$. That is, $\mathcal{K}=\{\mathfrak{A}|\mathfrak{A}\models \phi \text{ and }\phi \in \mathcal{L}[\tau ]\}$

Elementary classes are closed under isomorphisms (i.e., if $\mathfrak{A}\in \mathcal{K}$ and $\mathfrak{A}\cong \mathfrak{B},$ then $\mathfrak{B}\in \mathcal{K}$).

From the above fact, elementary classes may also equivalently be defined as a union of isomorphism types/classes.

$\mathcal{K}=\bigcup _{\mathcal{A}\in \mathcal{K}}[\mathcal{A}]$ Where $[\mathcal{A}]=$ {${\mathcal{A}}^{\prime }|{\mathcal{A}}^{\prime }\cong \mathcal{A}$} and $[\mathcal{A}]\models \phi$

Can also be seen as a union of sub-model classes (see below)

Note: Every Elementary class is a Model Class

Projective Class

Given a logic $\mathcal{L}$ and a vocabulary $\tau$, we say that $\mathcal{K}$ is a projective class in $\mathcal{L}$ (more precisely, $\mathcal{L}(\tau )$) iff there is a vocabulary $\sigma \supseteq \tau$, having the same sort symbols as $\tau$ in the many-sorted case, and a $\mathcal{L}(\sigma )$-elementary class $\mathcal{K}$ such that $\mathcal{K}=\{\mathfrak{A}\upharpoonright \tau |\mathfrak{A}\in {\mathcal{K}}^{\prime }\}$, the class of $\tau$-reducts of ${\mathcal{K}}^{\prime }$

Notes:

• A $\mathcal{L}(\tau )$-elementary class (or projective class), is a class of $\tau$-structures elementary in the logic $\mathcal{L}$
• If a class $\mathcal{K}$ is elementary in $\mathcal{L}$, then it is projective in $\mathcal{L}$ i.e., elementary class $⟹$ projective class

Relative Projective Classes

Given a logic $\mathcal{L}$ and a vocabulary $\tau$, a class of $\tau$-structures $\mathcal{K}$ is a relative projective class (RPC) in $\mathcal{L}$ iff there is a vocabulary $\sigma \supseteq \tau$, a unary predicate $U\in \sigma$/$\tau$ and a class ${\mathcal{K}}^{\prime }$ elementary in $\mathcal{L}(\tau )$ such that: $\mathcal{K}=\{\mathfrak{A}\upharpoonright \tau |U^{\mathfrak{A}}|\mathfrak{A}\in {\mathcal{K}}^{\prime }\text{ and }{U}^{\mathfrak{A}}\text{ is }\tau \text{-closed in }\mathfrak{A}\}$ In the many-sorted case $\mathcal{K}=\{\mathfrak{A}\upharpoonright \tau |\mathfrak{A}\in {\mathcal{K}}^{\prime }\}$

Every RPC is a projective class

Summary: RPC $⟹$ Projective class $⟹$ Elementary class $⟹$ model class

Expressive Power

The Notion of Expressive Power:

• A logic ${\mathcal{L}}^{\ast }$ is at least as strong as $\mathcal{L}$, $\mathcal{L}\le {\mathcal{L}}^{\ast }$, iff for every sentences $\phi \in \mathcal{L}[\tau ]$ ($\tau$ is some arbitrary vocabulary), there is a sentence of ${\phi }^{\ast }\in {\mathcal{L}}^{\ast }[\tau ]$ such that {$\mathfrak{A}|\mathfrak{A}\models \phi$} = {$\mathfrak{A}|\mathfrak{A}\models {\phi }^{\ast }$}. That is, for any $\mathcal{L}$-sentence $\phi$ there is a ${\mathcal{L}}^{\ast }$-sentence ${\phi }^{\ast }$ which has the same ‘meaning’ (semantically) as $\phi$
• Structures that can be distinguished in $\mathcal{L}$ can be distinguished in ${\mathcal{L}}^{\ast }$

More formally, Let $\mathcal{L},{\mathcal{L}}^{\ast }$ be logics, we say that ${\mathcal{L}}^{\ast }$ is at least as strong as $\mathcal{L}$, denoted $\mathcal{L}\le {\mathcal{L}}^{\ast }$, iff every elementary class in $\mathcal{L}$ is an elementary class in ${\mathcal{L}}^{\ast }$. $\mathcal{L}$ and ${\mathcal{L}}^{\ast }$ are equivalently strong, denoted $\mathcal{L}\equiv {\mathcal{L}}^{\ast }$, if both $\mathcal{L}\le {\mathcal{L}}^{\ast }$ and ${\mathcal{L}}^{\ast }\le \mathcal{L}$ ${\mathcal{L}}^{\ast }$ is stronger than $\mathcal{L}$, denoted $\mathcal{L}<{\mathcal{L}}^{\ast }$, if $\mathcal{L}\le {\mathcal{L}}^{\ast }$ and $\mathcal{L}\not\equiv {\mathcal{L}}^{\ast }$

A logic ${\mathcal{L}}^{\ast }$ is equivalently as strong as $\mathcal{L},\mathcal{L}{\le }_{\equiv }{\mathcal{L}}^{\ast },$ if for every $\tau$-structure $\mathfrak{A},\mathfrak{B}$, if $\mathfrak{A}{\equiv }_{{\mathcal{L}}^{\ast }}\mathfrak{B}$ then $\mathfrak{A}{\equiv }_{\mathcal{L}}\mathfrak{B},$ where ${\equiv }_{\mathcal{L}}$ is the relation asserting “satisfy the same $\mathcal{L}$-sentences” i.e., If for every sentence $\phi \in \mathcal{L}[\tau ],$ then there is a sentence $\psi \in {\mathcal{L}}^{\ast }[\tau ]$ which has the same meaning as $\phi$.

The strongest logic is one which characterizes all model classes, that is, the logic has a sentence for every for every isomorphism-closed class of structures (a sentence for each model class) For any structure $\mathfrak{A}$, there is a sentence ${\phi }_{\mathfrak{A}}$ such that ${\mathfrak{A}}^{\prime }\models {\phi }_{\mathfrak{A}}⟺{\mathfrak{A}}^{\prime }\cong \mathfrak{A}$

Such a logic would form a proper-class as already a logic which characterizes all structures is proper-classed size (e.g., ${\mathcal{L}}_{\infty ,\infty }$ characterizes all structures up to isomorphism, $|{\mathcal{L}}_{\infty ,\infty }[\tau ]|=\infty$).

Note: Characterizing all model classes $⟹$ characterizing all structure Consider the following model class

$\mathcal{K}=${$[\mathcal{A}]$}, the model class of a single isomorphism type To characterize a structure means to define the structure up to isomorphism (i.e., defining the isomorphism type)

For logics $\mathcal{L},{\mathcal{L}}^{\ast },\mathcal{L}{\le }_{R(PC)}{\mathcal{L}}^{\ast }$ iff every class that is $R(PC)$ in $\mathcal{L}$, is $R(PC)$ in ${\mathcal{L}}^{\ast }$

Other

Beth’s Definability Theorem: For a first-order theory $T$ in the language $\mathcal{L}(\sigma )\supseteq \mathcal{L}(\tau )$ and a formula $\phi \in {\text{Form}}_{\mathcal{L}}(\sigma )$, then the following are equivalent: i) For any two model $\mathcal{M},\mathcal{N}\models T$ such that $\mathcal{M}\upharpoonright \tau =\mathcal{N}\upharpoonright \tau$, it is the case that $\mathcal{M}\models \phi [\overline{a}]⟺\mathcal{N}\models \phi [\overline{a}]$ for all $n$-tuples $\overline{a}\in M^n$. ii) $\phi$ is equivalent modulo $T$ to a formula $\psi \in {\text{Form}}_{\mathcal{L}}(\sigma )$ i.e., a property is implicitly definable in a theory $T$ of the language $\mathcal{L}(\tau )$ via a formula $\phi$ of the extended language $\mathcal{L}(\sigma )$ only if that property is explicitly definable in the theory $T$ by a formula $\psi$ in the original language $\mathcal{L}(\tau )$.

References

Model Theoretic Logics.pdf Model Theory D.Marker.pdf Beth definability - Wikipedia