Semantic

Model

A model $\mathcal{M}$ for a language $\mathcal{L}$ is a pair $(D,\mathcal{I})$ where:

• $D$ is a non-empty set called the domain of $\mathcal{M}$.
  • The elements of $D$ are called objects or individuals
  • (the notation $|\mathcal{M}|$ is sometimes used to denote the domain $D$, or its cardinality $|D|$)
• $\mathcal{I}$ is an interpretation function that:
  • For each constant symbol $c\in \mathcal{L}$, assigns an element $\mathcal{I}(c)\in D$.
  • For each $n$-ary function symbol $f\in \mathcal{L}$, assigns an $n$-ary function $\mathcal{I}(f):D^n\to D$.
  • For each $n$-ary predicate symbol $P\in \mathcal{L}$, assigns an $n$-ary relation $\mathcal{I}(P)\subseteq D^n$.
• For any non-logical symbol $s\in \mathcal{L}$, the object $\mathcal{I}(s)$ is called the interpretation of $s$ in $\mathcal{M}$.

Terminology

• domain: domain of discourse, universe, underlying set
• model: structure, interpretation, assignment
• interpretation function: interpretation, assignment function

If we don’t mention other, we are in first-order logic with equality, which means, the equality symbol ̇$=$ is defined as the identity relation $R=\{(x,x):x\in A\}$

Variable Assignment

• $V(\phi )$ is the set of variables which occur freely in $\phi$
• A (variable) assignment for a model $M$ with the domain $A$ is a mapping $S:\text{dom}(S)\to A$ where $\text{dom}(S)\subseteq VAR$
  • A (variable) assignment for a formula $\phi$ is a mapping $S:\text{dom}(S)\to A$ where $V(\phi )\subseteq \text{dom}(S)\subseteq VAR$
    • If $\phi$ is a sentence, then every assignment is for a formula $\phi$, because $V(\phi )=\varnothing$
  • If $S$ is an assignment for a model $M$, and $x\in \text{VAR}$, and $a\in A$ we denote $S⟨x|a⟩$ if $S(x)=a$

Truth Value

Truth Value in Assignment

Given model $M$, and an assignment $S$ for a formula $\phi$.

• If $\phi$ is an atomic formula $P(t_1,\dots ,t_n)$, then $\phi$ is true if $(t_1^S,\dots ,t_n^S)\in P^M$, otherwise $\phi$ is false
• If $\phi$ is the formula $\neg \psi$, then $\phi$ is true if is $\psi$ is false, otherwise $\phi$ is false. (similar way for the other connectives as in as in propositional logic)
• If $\phi$ is the formula $\exists x\psi$ then $\phi$ is true if and only if there exists an element $a\in A$ such that $\psi$ is true in $S⟨x|a⟩$
• If $\phi$ is the formula $\forall x\psi$ then $\phi$ is true if and only if for each element $a\in A$ the formula $\psi$ is true in $S⟨x|a⟩$
• The truth value of a formula is truth if it is true, and falsity
• Notaion: if $\phi$ is true we can denote $S(\phi )=\mathsf{T}$ or $S\models \phi$ or $M{\models }_S\phi$. If $\phi$ is false we denote $S(\phi )=\mathsf{F}$ or $S⊭\phi$ or $M{⊭}_S\phi$.
• Given model $M$, and two assignments $S_1$ and $S_2$ for a formula $\phi$, such that $S_1(x)=S_2(x)$ for each $x\in V(\phi )$, then $S_1(\phi )=S_2(\phi )$.

Truth Value in Model

Given a model $M$

• If $\phi$ is a sentence, then all assignments in $M$ give to $\phi$ the same value.
  • In case a sentence $\phi$ is true (in some assignment, and therefore in every assignment) then we say that the sentence $\phi$ is true in the model $M$, and denote $M\models \phi$.
  • Otherwise, if a sentence $\phi$ is false (in some assignment, and therefore in every assignment) then we say that the sentence $\phi$ is false in the model $M$, and denote $M⊭\phi$.
• A formula $\phi$ is true in $M$ (denoted by $M\models \phi$), if for every assignment $S$ we have $M{\models }_S\phi$
  • notation other terminology: $M$ satisfied $\phi$; $M$ is a model of $\phi$; $\phi$ holds in $M$
  • If $x$ is a variable, then $\phi$ is true in model $M$ if and only if $\forall x\phi$ is true in $M$
  • The formula $\phi$ is true in $M$ if and only if its universal closure $\forall x_1\dots \forall x_r\phi$ is true in $M$
• A model $M$ is said to be a model of a set of sentences $K$, (denoted by $M\models K$), if for each $\phi \in K$ we have $M\models \phi$

Satisfiability

• A formula $\phi$ is satisfiable if there exists a model $M$ and an assignment $S$ such that $M{\models }_S\phi$.
• A formula $\phi$ is unsatisfiable if for every model $M$ we have $M/\models \phi$.
• A set of sentences $K$ is said to be satisfiable if there exists a model $M$ such that $M\models K$
• A formula $\phi$ is falsifiable (denoted by $/\models \phi$) if $\phi$ is not logically valid
• Soundeness Theorem (6.2) - If $K$ is satisfiable, then it is consistent

Logical Validity

• (c5.6) A formula $\phi$ is logically valid (אמיתית לוגית) and denoted by $\models \phi$, if for every model $M$ we have $M\models \phi$.

A logically valid formula can also be called a tautology, but we avoid this term to prevent confusion with First-order Tautologies here or with tautology in propositional logic

Examples of logically valid formulas:

• $\forall x\phi \to \phi [t/x]$ (given $\phi [t/x]$ is a capture-avoiding substitution)
• $(\forall x\phi \leftrightarrow \forall y\phi [y/x])$ (given the variable $y$ is not appear in $\phi$)
• $(\neg \forall x\phi )\leftrightarrow (\exists x\neg \phi )$
• $(\forall x\phi )\leftrightarrow (\neg \exists x\neg \phi )$
• $(\neg \exists x\phi )\leftrightarrow (\forall x\neg \phi )$
• $(\exists x\phi )\leftrightarrow (\neg \forall x\neg \phi )$

Logical Equivalence

• Two formulas $\phi$ and $\psi$ are logically equivalent (denoted by $\phi \equiv \psi$) if and only if, $\phi \leftrightarrow \psi$ is logically valid. i.e.
  • $\phi \equiv \psi$ if and only if for each model $M$ and for each assignment $S$, we hold $S\models \phi$ if and only if $S\models \psi$
  • (Theorem 5.8)
    • if $\phi \equiv \psi$ then:
      • $\neg \phi \equiv \neg \psi$
      • $\text{varphi@}\theta \equiv \text{psi@}\theta$ and $\text{theta@}\phi \equiv \text{theta@}\psi$ (for any binary connective $@$)
      • $\forall x\phi \equiv \forall x\psi$ and $\exists x\phi \equiv \exists x\psi$ (for each varaible $x$)
    • If ${\phi }^{\prime }$ is arrived from $\phi$ by replacing sub-formula $\psi$ in ${\psi }^{\prime }$ where $\psi \equiv {\psi }^{\prime }$ then ${\phi }^{\prime }\equiv \phi$

Logical Implication

• A formula $\phi$ logically implies a formula $\psi$ (or $\psi$ logically implied by $\phi$), and denoted by $\phi ⟹\psi$ (or more common $\phi \models \psi$), if and only if, in every model $M$, if $M\models \phi$ then $M\models \psi$.

  • $\phi$ logically implies a formula $\psi$ if and only if $\phi \to \psi$ is logically valid
    • In other words, $\phi ⟹\psi$ if and only if $\models (\phi \to \psi )$

• (semantic consequence) A formula $\phi$ logically implied by a set of formulas $K$ (denoted by $K\models \phi$) if for every model $M$ such that $M\models K$ ($M$ is a model of $K$) we have $M\models \phi$ ($M$ is a model of $\phi$).

First-order Tautologies

• (5.9) Let $\phi$ be a proposition where all its elementary proposition are from $P_1,\dots ,P_n$. And Let ${\alpha }_1,\dots ,{\alpha }_n$ be formulas. And let ${\phi }^{\prime }$ be the string that is obtained by replacing each $P_i$ in $\phi$ by ${\alpha }_i$. Then:
  • ${\phi }^{\prime }$ is a formula
  • If $M$ is a model of the propositional logic, and $S$ is an assignment of the predicate logic, where $M(P_i)=S({\alpha }_i)$ for each $i\le n$, then $M(\phi )=S({\phi }^{\prime })$
  • If $\phi$ is a tautology then ${\phi }^{\prime }$ is logical valid and ${\phi }^{\prime }$ is called a first-order tautology.
• see also Predicate Calculus (6.1)