Definition:Model (Logic)

Definition

Logical Formula

Let $P$ be a logical formula whose set of atoms is $\left\{{p_1, p_2, \ldots, p_n}\right\}$.

Let $P$ be satisfiable by some boolean interpretation $\mathcal M \left({p_1, p_2, \ldots, p_n}\right) \to \left\{{T, F}\right\}$.

That is, $\mathcal M \left({P}\right) = T$.

Then $\mathcal M$ is called a model (or propositional model) for $P$, and is denoted:

$\mathcal M \models P$

We can say: $\mathcal M$ satisfies $P$, or $\mathcal M$ models $P$.

If $\mathcal M \left({P}\right) = F$ then $\mathcal M$ is not a model for $P$ and we write:

$\mathcal M \not \models P$

We can say: $\mathcal M$ does not satisfy $P$, or $\mathcal M$ does not model $P$.

Set of Logical Formulas

Let $U$ be a set of logical formulas.

Let $U$ be mutually satisfiable for some boolean interpretation $\mathcal M$.

Then $\mathcal M$ is a model for $U$ and is denoted:

$\mathcal M \models U$

We can say: $\mathcal M$ satisfies $U$, or $\mathcal M$ models $U$.

If there exists $Q \in U$ such that $\mathcal M \not \models Q$ then $\mathcal M$ is not a model for $U$ and we write:

$\mathcal M \not \models U$

We can say: $\mathcal M$ does not satisfy $U$, or $\mathcal M$ does not model $U$.

Propositional Calculus

When discussing propositional calculus as a formal system, it becomes convenient to discuss a model for the entire alphabet.

Let $\mathcal P_0$ be the set of letters of an exposition of propositional calculus.

A model for $\mathcal P_0$ is a boolean interpretation $\mathcal M$ which assigns each element of $\mathcal P_0$ a value $T$ or $F$.

That is, a boolean function:

$\mathcal M: \mathcal P_0 \to \left\{{T, F}\right\}$

The truth value of an atom $p \in \mathcal P_0$ under a model $\mathcal M$ can be written $p_{\mathcal M}$.

Similarly, the truth value of a propositional WFF $\mathbf{A}$ under a model $\mathcal M$ can be written $\mathbf{A}_{\mathcal M}$.

Such a model is called a model for propositional calculus or a model for propositional logic.

Predicate Calculus

Let $\mathcal P$ be the predicate symbols of a vocabulary of predicate calculus.

A model for predicate logic of type $\mathcal P$ is a system $\mathcal M$ consisting of:

A non-empty set $M$ called the universe of the model $\mathcal M$;

A function which assigns an $n$-ary relation $q^{\mathcal M}$ to each $n$-ary predicate symbol $q$ of $\mathcal P$.

Only the universe set $M$ is required to be non-empty. A unary relation $p^{\mathcal M}$ may be any subset of $M$ at all, which includes either empty or not.

Such a model is called a model for predicate calculus or a model for predicate logic.

Examples

• The sentence $\exists x: p \left({x}\right)$ is true in a model $\mathcal M$ iff $p^{\mathcal M}$ is a non-empty subset of $M$.

• The sentence $\forall x: p \left({x}\right)$ is true in a model $\mathcal M$ iff $p^{\mathcal M} = M$.

• A propositional symbol $q$ will be true in a model $\mathcal M$ iff $q^{\mathcal M} = M^0$, that is, $q^{\mathcal M}$ contains the null sequence, or $\left({}\right) \in q^{\mathcal M}$.

• Suppose $\mathcal P$ consists of one unary predicate symbol $p$.

Then a model $\mathcal M$ of type $\mathcal P$ consists of:

A nonempty set $M$;

One subset $p^{\mathcal M}$ (empty or not) of $M$.

If $M$ has $n$ elements, then from Cardinality of Power Set there are $2^n$ different models of type $\mathcal P$ with universe $M$, one for each subset $p^{\mathcal M}$ of $M$.

Given an infinite set $M$, there are then infinitely many different models of type $\mathcal P$ with universe $M$.

• Suppose $\mathcal P$ consists of two unary predicate symbols $p$ and $q$.

Then a model $\mathcal M$ of type $\mathcal P$ consists of:

A nonempty set $M$;

Two subsets $p^{\mathcal M}$ and $q^{\mathcal M}$ of $M$.

If $M$ has $n$ elements, then there are $\left({2^n}\right)^2$ different models of type $\mathcal P$ with universe $M$.

• Suppose $\mathcal P$ consists of one binary predicate symbol $p$.

Then a model $\mathcal M$ of type $\mathcal P$ consists of:

A nonempty set $M$;

One subset $p^{\mathcal M}$ of $M \times M$.

If $M$ has $n$ elements, then there are $2^{\left({n^2}\right)}$ different models of type $\mathcal P$ with universe $M$.

Sources

• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.5$, $\S 1.7$, $\S 2.4$