Model Theory

Basic Theorems

• (6.9) Compactness Theorem - Let $K$ be an infinite set of sentences. If every finite subset of $K$ is satisfiable, then $K$ is satisfiable
• (6.10) Löwenheim–Skolem theorem - if a theory $K$ has an infinite model, then it has also countable model
  • (6.10’) if a theory $K$ has an infinite model, then for every infinite cardinality $\alpha$, the theory has model with cardinality $\alpha$
• (q6.6) Given a predicate language $L$ and a set of sentences $K$ and let $L^{\prime }$ be the language obtained by adding constants, functions, and predicates to $L$. let $\phi$ be a sentence in $L$. Thentodo
• (6.11)
  • (A.) There is no theory force a model to be the set of all natural numbers:
    • Let $L$ a predicate language such that the set of all natural numbers is the domain of some model of $L$. Let $T$ be the set of all sentences in $L$ that are true in the model. Then $T$ has also models which are not countable. Moreover, $T$ has models in every infinite cardinality.
  • (B.) There is no theory force a model to be the set of all real numbers:
    • Let $L$ a predicate language such that the set of all real numbers is the domain of some model of $L$. Let $T$ be the set of all sentences in $L$ that are true in the the model. Then $T$ has also models which are countable.
• (6.12) It is impossible to characterize in the language the finite models: For every theory $K$, one and only one of the following holds:
  • there exists $k\in \mathbb{N}$ such that $T⊢{\psi }_n$, where ${\psi }_n$ is a sentence that says “there at most $n$ obejct, such that every model of T has at most $n$ objects”. or,
  • T has models in every infinite cardinalities
• (6.13) Let $T$ be a theory that has finite models. (i.e. for all $n$ there exists a finite model of $T$ with domain of size at least $n$). Let $\Phi =\{{\phi }_n\mid n\in \mathbb{N}\}$ such that ${\phi }_n$ is a sentence that says “there at least $n$ obejcts in the domain”. Then:
  • (A.) $T\cup \Phi$ is a theory whose models are exactly the finite models of $T$.
  • (B.) There is no theory (finite or infinite) ${\Phi }^{\prime }$ such that the models of $T\cup {\Phi }^{\prime }$ are exactly the finite models of $T$.
  • (C.) There is no finite set ${\theta }_1,\dots ,{\theta }_k$ such that the models of $T\cup \{{\theta }_1,\dots ,{\theta }_k\}$ are exactly the infinite models of $T$.

Exapmles

Here are some example first-order theories that are important in mathematics.

Equivalence Relation

• (Language) The non-logical symbols of $L$ contains only one predicate symbol: $\sim$
• (Axioms)
  • $\forall x(x\sim x)$ (reflexivity)
  • $\forall x\forall y(x\sim y\to y\sim x)$ (symmetry)
  • $\forall x\forall y\forall z((x\sim y\wedge y\sim z)\to x\sim z)$ (transitivity)

Graph Theory (Simple Undirected)

• (Language)
  • Predicate symbols: $E$ (binary)
• (Axioms)
  • $\forall x\forall y(E(x,y)\leftrightarrow E(y,x))$ (edges are undirected)
  • $\forall x(\neg E(x,x))$ (no loops)

Graph Theory (Directed)

• (Language)
  • Predicate symbols: $E$ (binary)
• (Axioms) No axioms (!)

Theories of Order

In the language there is one binary relation symbol $<$. (we prefer to denote $t<s$ instead of $<(t,s)$)

Partial Order

• $T_{\text{order}}$, has two axioms:
  • $\forall v_0\neg (v_0<v_0)$ (irreflexivity)
  • $\forall v_0\forall v_1\forall v_2((v_0<v_1)\wedge (v_1<v_2))\to (v_0<v_2)$ (transitivity)

See also: Transitive Relations (strict partial order)

Exercise

Prove that $T_{\text{order}}⊢\forall v_0\forall v_1((v_0<v_1)\to \neg (v_1<v_0))$

Linear Order (Total Order)

• $T_{\text{LO}}$=$T_{\text{order}}\cup \{\forall v_0\forall v_1(v_0=v_1)\vee (v_0<v_1)\vee (v_1<v_0)\}$ (totality)

See also: Transitive Relations (strict total order)

Exercise

(1.) Show that for all $n$, $T_{\text{LO}}$ has a model with domain of size $n$. (every two such are isomorphic). (2.) There is also infinite models. Show two such models. (which are not isomorphic)

Dense Linear Order

• $T_{\text{DLO}}$ is $T_{\text{LO}}$ with the following axioms:
  • $\forall v_0\forall v_1((v_0<v_1)\to \exists v_2((v_0<v_2)\wedge (v_2<v_1)))$ (dense)
  • $\forall v_0\exists v_1\exists v_2((v_0<v_1)\wedge (v_2<v_0))$ (no first or last element)

Exercise

Prove that every model of $T_{\text{DLO}}$ is infinite.

Theories of Groups

• (Language)
  • Constant: $0$
  • Function Symbols: $-$ (unary), and $+$ (binary).

Group Theory

• $T_{\text{G}}$ has the following axioms:
  • $\forall x\forall y\forall z(((x+y)+z)=x+(y+z))$ (associativity)
  • $\forall x(x+0)=x$ (identity)
  • $\forall x((-x+x)=0)$ (inverse)

Exercise

Prove that $T_{\text{G}}⊢\forall x\forall y\forall z(((x+y)=(x+z))\to (y=z))$ (cancellation law)

See also: Group Theory

Commutative Group Theory

• $T_{\text{CG}}=T_{\text{G}}\cup \{\forall x\forall y((x+y)=(y+x))\}$ (commutativity)

Theory of Fields

The language is the same as the group theory with an additional binary function symbol, $\cdot$, and a constant symbol, $1$.

The axioms of the theory $T_{\text{F}}$ are the axioms of the commutative group theory with the following additional axioms:

• $\forall x\forall y\forall z((x\cdot (y\cdot z))=((x\cdot y)\cdot z))$ (associativity)
• $\forall x(x\cdot 1)=x$ (identity)
• $\forall x(\neg (x=0)\to (\exists y(x\cdot y)=1))$ (inverse)
• $\forall x\forall y((x\cdot y)=(y\cdot x))$ (commutativity)
• $\forall x\forall y\forall z((x\cdot (y+z))=((x\cdot y)+(x\cdot z)))$ (distributivity)

Imortant models of the theory are the rational numbers, the real numbers, and the complex numbers. But there are also finite models, such as $Z_p$ (the integers modulo $p$) for a prime number $p$. Exmaple for sentence that is true in the field of real numbers but not in the field of rational numbers: $\exists y(y\cdot y=1+1)$. (see more in Completeness of R)

See also: Field

Exercise

Prove that $T_{\text{F}}⊢\forall x(x\cdot 0=0)$. (zero property)

Peano Axioms

• (Language)

  • Constant: $0$
  • Function Symbols: $s$ (unary), $+$ (binary), and $\cdot$ (binary).
  • Predicate Symbols: $<$ (binary).

• (Axioms)

  • $\forall x(\neg (s(x)=0))$ (zero is not a successor)
  • $\forall x\forall y(s(x)=s(y)\to x=y)$ (successor is injective)
  • $\forall x(x+0=x)$ (zero is identity for addition; base step of addition definition)
  • $\forall x\forall y(x+s(y)=s(x+y))$ (addition successor; recursive step of addition)
  • $\forall x(x\cdot 0=0)$ (base step of multiplication definition)
  • $\forall x\forall y(x\cdot s(y)=(x\cdot y)+x)$ (multiplication successor; recursive step of multiplication)
  • $\forall x(\neg (x<0))$ (non-negativity)
  • $\forall x\forall y[(x<s(y))\leftrightarrow ((x<y)\vee (x=y))]$
  • Axiom schema: For every formula $\phi [x_1,\dots ,x_k,y]$, we have $\forall x_1\dots \forall x_k\forall y((\phi [0/y]\wedge \forall y(\phi \to \phi [s(y)/y]))\to \forall y\phi )$

• todo

  • only 0 has no predecessor: $\forall x(x\ne 0\to \exists y(x=s(y)))$
  • $\forall x\forall y(x\ne s(y)+x)$
  • Addition
    • Associativity $\forall x\forall y\forall z((x+y)+z=x+(y+z))$
    • Commutative $\forall x\forall y(x+y=y+x)$
  • Multiplication
    • Associativity $\forall x\forall y\forall z((x\cdot y)\cdot z=x\cdot (y\cdot z))$
    • Commutative $\forall x\forall y(x\cdot y=y\cdot x)$
  • multiplication is distributes over addition: $\forall x\forall y\forall z(x\cdot (y+z)=x\cdot y\cdot +x\cdot z)$
  • Exp
    • $\forall x\forall y\forall z(x^y\cdot x^z=x^{y+z})$
    • $\forall x\forall y\forall z((x^y{)}^z=x^{y\cdot z})$
    • $\forall x\forall y\forall z((x\cdot z{)}^y=x^y\cdot x^z)$
  • $\forall x\forall y(x<y\leftrightarrow \exists z(x+S(z)=y))$
  • the relation $<$ is a strict total order relation
    • irreflexivity $\forall x\neg (x<x)$
    • transitivity $\forall x\forall y\forall z((x<y\wedge y<z)\to (x<z))$
    • $\forall x\forall y((x<y)\vee (x=y)\vee (x>y))$
  • is $P$ a complete theory?
  • consistency

Set Theory (ZFC)

• (Language)
  • Predicate Symbols: $\in$ (binary)
• (Axioms)
  • $\forall A\forall B(\forall x(x\in A\leftrightarrow x\in B)\to A=B)$ (extensionality)
  • $\exists y(\forall x(\neg (x\in y)))$ (empty set)
  • (Axiom schema of specification)todo

Definable set

Set of Models

• Given a set of sentences $\Sigma$, the set $\text{Mod}(\Sigma )=\{M\mid M\models \Sigma \}$ is called the class of models of $\Sigma$.
  • Example: $\text{Mod}(\{\forall x\forall y(x=y)\})$ is the class of all models in which the domain consists of exactly one element.

Definable Set of Models

• Given a set of models $K=\{M_1,M_2,\dots \}$, if there exists a set of sentences $\Sigma$ such that $K=\text{Mod}(\Sigma )$, then we say that $K$ is definable (גדירה) by $\Sigma$.

Examples (the language is FOL with equality)

• Ex. We denote $K_{\ge m}$ the set of models in $K$ with domain of size at least $m$.
• ${\phi }_m=\exists x_1\exists x_2\dots \exists x_m\underset{1\le i<j\le m}{\bigwedge }(x_i\ne x_j)$
• The set $K_{\ge m}$ is definable by the set $\Sigma \cup \{{\phi }_m\}$
• Ex. The set $K_{\ge 2}$ is definable by ${\psi }_2=\{\forall x_1\forall x_2\forall x_3(x_1=x_2)\vee (x_1=x_3)\vee (x_2=x_3)\}$
• Ex. The set $K_{\le m}$ is definable by ${\psi }_m=\{\forall x_1\forall x_2\dots \forall x_m\underset{1\le i<j\le m+1}{\bigvee }(x_i=x_j)\}$
• Ex. The set $K_n$ (the set of models with domain of size $n$) is definable by $\Sigma =\{{\psi }_n,{\phi }_n\}$.
• Ex. The set $K_{\infty }$ (the set of all infinite models) is definable by $\Sigma =\{{\phi }_1,{\phi }_2,\dots \}$. (i.e. $K_{\infty }=\text{Mod}(\{{\phi }_1,{\phi }_2,\dots \})$)
• Ex. The set $K_{\text{finite}}$ (the set of all finite models) is not definable. (#todo prove it using compactness theorem)

Definable Set of Constants, Functions, and Relations in a Model

• Given a language $L$ and a model $M=⟨D;\dots ⟩$ where $D$ is the domain of $M$.
  • An element $a\in D$ is definable if there exists a formula $\phi (x)$ such that $M\models \phi (a)$, and for every $b\in D$ we have $M\models \phi (b)$ if and only if $a=b$.
  • A set $A\subseteq D$ is definable if there exists a formula $\phi (x)$ such that $M\models \phi (a)$ if and only if $a\in A$.
  • A $n$-ary predicate $P$ in the model $M$ is definable if there exists a formula $\phi (x_1,\dots ,x_n)$ such that $M\models \phi (a_1,\dots ,a_n)$ if and only if $(a_1,\dots ,a_n)\in P$.

NOTE

• Exercies:
  • Given a language $L=\{F,G,N,a,p\}$ where $F$ and $G$ are binary function symbols, $N$ is a unary function symbol, $a$ and $p$ are constants symbols.
  • Given a model $M=⟨\mathbb{N};+,\cdot ,s(x)=x+1,0,1⟩$ where $\mathbb{N}$ is the set of natural numbers.
    • Is $0$ definable in $M$?
      • Yes, by the formula $\phi (x):=(x=0)$
    • Is $3$ definable in $M$?
      • Yes, by the formula $\phi (x):=(x=s(s(1)))$
    • Is the set $\{1,3\}$ definable in $M$?
      • Yes, by the formula $\phi (x):=((x=1)\vee (x=s(s(1))))$
    • Is the set of even numbers definable in $M$?
      • Yes, by the formula $\phi (x):=(\exists y(x=y+y))$
    • Is the set of odd numbers definable in $M$?
      • Yes, by the formula $\phi =(\exists y(x=s(y+y)))$ or by $\phi (x):=\neg (\exists y(x=y+y))$
    • Is the set of prime numbers definable in $M$?
      • Yes, by the formula $\phi (x):=(\forall y\forall z(x=y\cdot z)\to ((y=x)\vee (z=x))\wedge \neg (x=0)\wedge \neg (x=1))$
    • Is the predicate $<$ definable in $M$?
      • Yes, by the formula $\phi (x,y):=(\exists z(x+z=y)\wedge \neg (z=0))$
• Exercies: Given a language $L=\{F\}$ where $F$ is a binary function symbol. And given a model $M=⟨\mathbb{N};+⟩$ where $\mathbb{N}$ is the set of natural numbers.
  • Is $0$ definable in $M$?
    • Yes, by the formula $\phi (x):=F(x,x)=x$
• Exercies: Given a language $L=\{R\}$ where $R$ is a binary relation symbol. And given a model $M=⟨\mathbb{N};<⟩$ where $\mathbb{N}$ is the set of natural numbers.
  • Is $0$ definable in $M$?
    • Yes, by the formula $\phi (x):=\neg (\exists y(R(x,y)))$
• Exercies: Given a language $L=\{R\}$ where $R$ is a binary relation symbol. And given a model $M=⟨\mathbb{Z};<⟩$ where $\mathbb{Z}$ is the set of integers.
  • Is $0$ definable in $M$? No.
• Exercies: Given model $M=⟨\mathbb{R};N,+,\cdot ,⟩$ where $\mathbb{R}$ is the set of real numbers, and $N$ an unary relation symbol that indicates if a number is a natural number.
  • Define the relation $<$ in $M$ on the set of natural numbers.
    • By the formula $\phi (x,y):=(N(x)\wedge N(y)\wedge \exists z(N(z)\wedge x+z=y)\wedge \neg (x=y))$
  • Define the division on real numbers in $M$.
    • By the formula $\phi (x,y):=(\exists z(x\cdot z=y))$

Submodels

• A model $M^{\prime }=⟨B,\dots ⟩$ is a submodel of a model $M=⟨A,\dots ⟩$ if $B\subseteq A$ the interpretation of the symbols in $M^{\prime }$ is the same as in $M$:
  • For every constant symbol $c$ in $L$, we have $c^M=c^{M^{\prime }}$
  • For every n-ary function symbol in $L$, and for all $a_1,\dots ,a_n\in B$ we have: $f^M(a_1,\dots ,a_n)=f^{M^{\prime }}(a_1,\dots ,a_n)$
  • For every n-ary relation symbol in $L$, and for all $a_1,\dots ,a_n\in B$ we have: $(a_1,\dots ,a_n)\in R^M⟺(a_1,\dots ,a_n)\in R^{M^{\prime }}$

Universal and Existential Formulas

The following terminology is intenal to the book and not (necessarily) standard in the literature.

• A quantifier-­free formula is a formula that obtained from atomic formulas by using only the binary connectives and the negation connective, but not the quantifiers.
• If $\phi$ is a quantifier-free formula then the formula $\exists x_1\dots \exists x_n\phi$ is called a prenex-existential formula.
  • A formula that obtained from a prenex-existential formula by a sequence of Boolean operations $\wedge ,\vee$ and adding $\exists$ quantifiers is called a existential formula.
• If $\phi$ is a quantifier-free formula then the formula $\forall x_1\dots \forall x_n\phi$ is called a prenex-universal formula.
  • A formula that obtained from a prenex-universal formula by a sequence of Boolean operations $\wedge ,\vee$ and adding $\forall$ quantifiers is called a universal formula

Submodel Theorems

• (8.1) Let $M^{\prime }=⟨B,\dots ⟩$ be a submodel of a model $M=⟨A,\dots ⟩$, and $a_1,\dots ,a_n\in B$, and $x_1,\dots ,x_n$ are variables. Let be substitutions $S$ and $S^{\prime }$ in $M$ and $M^{\prime }$ respectively, s.t. $S(x_i)=S^{\prime }(x_i)=a_i$ for all $i\le n$. Then:
  • If $t$ is a term in variables $x_1,\dots ,x_n$, then $S(t)=S^{\prime }(t)$.
  • If $\phi$ is a quantifier-free formula in variables $x_1,\dots ,x_n$, then $S\models \phi ⟺S^{\prime }\models \phi$.
  • If $\phi$ is an universal formula in variables $x_1,\dots ,x_n$, then $S\models \phi ⟹S^{\prime }\models \phi$.
  • If $\phi$ is an existential formula in variables $x_1,\dots ,x_n$, then $S\models \phi ⟸S^{\prime }\models \phi$.

When we say that a formula is in variables $x_1,\dots ,x_n$, we mean that the formula contains only the variables $x_1,\dots ,x_n$ ????todo

• Let $A$ be a set, and $\mathbb{F}$ be a family of functions on $A$. For every set $B\subseteq A$, we denote $B^{\prime }$ the set $B$ with its images, i.e. $B^{\prime }=B\cup \{f(a_1,\dots ,a_{n_f})\mid a_1,\dots ,a_{n_f}\in B,f\in \mathbb{F}\}$. (where $n_f$ is the arity of $f$). For every set $B_0\subseteq A$, we define using induction increasing sequence of sets $B_{n+1}=(B_n{)}^{\prime }$. We define $\overline{B_0}={\bigcup }_{n\in \mathbb{N}}{B}_n$. We say that $\overline{B_0}$ is the closure of $B_0$ under the functions in $\mathbb{F}$.

• The closure has the following properties:

  • $B_0\subseteq \overline{B_0}$
  • $\overline{B_0}$ is closed under the functions in $\mathbb{F}$.
  • $\overline{B_0}$ is the minimal set with this property: If $B_0\subseteq C\subseteq A$ and $C$ is closed under the functions in $\mathbb{F}$, then $\overline{B_0}\subseteq C$.
  • ($\overline{B_0}$ is not “very big” in terms of cardinality) If $B_0$ and $\mathbb{F}$ are countable, then $\overline{B_0}$ is countable. (If $\mathbb{F}$ is countable but $B_0$ is not, then $\overline{B_0}$ and $B_0$ have the same cardinality)

• (8.2)

  • (A.) Let $L$ be a language with at least one constant symbol, and let $M=⟨A,\dots ⟩$ be a model of $L$. Let $A_0$ be the set of all elements of $A$ that interpret constant symbols without variables, i.e. $A_0=\{t^M\mid t\text{ is a term without variables}\}$. Then $A_0$ is the domain of a submodel $M_0$ of $M$, and $M_0$ is the minimal submodel of $M$, that is $M_0$ is also a submodel of every submodel of $M$.
  • (B.) Let $M=⟨A,\dots ⟩$ be a model of $L$, and let $B\subseteq A$, and let $B_0$ be the set $B$ with the terms $c^M$, let $\overline{B}$ be the closure of $B_0$ under the functions in $L$. Then $\overline{B}$ is the domain of the minimal submodel of $M$ that contains $B$, and this submodel is the submodel generated by $B$.

• If $M$ is a model such that it has no proper submodels, then $M$ is called minimal model.