Models

Recall the valid argument from the previous section:

All Philosophy majors at UMD are required to take a logic course. Ann is a Philosophy major at UMD. So, Ann is required to take a logic course.

Using formulas of First Order Logic, this argument is represented as follows:

$$\forall x (M(x)\rightarrow L(x)), M(a)\models L(a).$$

The validity of this argument means that replacing $M$ and $L$ with any predicates and $a$ with any constant results in a valid argument. For instance, the following instances of the form of the above argument are all valid:

• All Philosophy majors at UMD are millionaires. Ann is a Philosophy major at UMD. So, Ann is a millionaire.
• All Democrats voted for Biden. Ann is a Democrat. So, Ann voted for Biden.
• All ravens are black. Tweety is a raven. So, Tweety is black.
• All prime number greater than 2 are odd. 7 is a prime number greater than 2. So, 7 is odd.

More generally, for any collection of objects or individuals associated with $M$ and $L$ and any object or individual referred to by the name $a$, if everything in the $M$ collection is also in the $L$ collection and $a$ is in the $M$ collection, then $a$ is in the $L$ collection.

It is a good exercise to determine which of the following variants of the above argument are valid.

1. Is $\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow L(a)$ valid?

2. Is $\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow \forall x L(x)$ valid?

3. Is $\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow \exists x L(x)$ valid?

4. Is $\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow L(a)$ valid?

5. Is $\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow \exists x L(x)$ valid?

6. Is $\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow \forall x L(x)$ valid?

To verify that all Philosophy majors at UMD are required to take a logic course ($\forall x(M(x)\rightarrow L(x))$) is true. We need to check for each student at UMD, if that students is a Philosophy major, then that student is required to take a logic course.

In Propositional Logic, the truth-value of a formula depends on a truth-value assignment (i.e., a row of a truth table). The analogue of the truth-value assignment for First Order Logic is a model. There are two components of a model:

1. A collection of objects or items called the domain.
2. An interpretation that associates with each constant an element of the domain and with each predicate a collection of elements from the domain.

For example, suppose that the domain consists of the first 5 positive numbers: $1$, $2$, $3$, $4$ and $5$, that $a$ is interpretted as $2$, that $M$ is interpretted as the collection $2, 3$, and $4$ and that $L$ is interpretted as the collection $2, 3, 4$ and $5$. Then, every object in the domain that is an $M$ is also an $L$: The only objects that satisfy the predicate $M$ are $2, 3$, and $4$, and each of those objects are in the interpretation of $L$.

We can visualize a model using a table, where each row is labeled by an element of the domain and the columns are labeled with the constants and the predicates. Under the constant, there is a checkmark in the row labeled with the element of the domain that interprets the constant (so there is exactly one checkmark under each constant). Under the predicate, there is a $+$ in every row labeled by an element of the domain in the interpretation of the predicate and a $-$ in the rows labeled by elements not in the interpretation of the predicate. For instance, the above model can be visualized as follows:

	$a$	$M$	$L$
$1$		$-$	$-$
$2$	$\checkmark$	$+$	$+$
$3$		$+$	$+$
$4$		$+$	$+$
$5$		$-$	$+$

Then, $\forall x(M(x)\rightarrow L(x))$ is true in the above model since in every row, if there is a $+$ underneath $M$, then there is a $+$ underneath $L$. Furthermore, both $M(a)$ and $L(a)$ are true since the row labeled with $2$ has a $+$ underneath both $M$ and $L$.

Example

To see why $\forall x (M(x)\rightarrow L(x)), \exists x M(x)\not\models \forall x L(x)$, we can construct the following simple model:

	$M$	$L$
$1$	$+$	$+$
$2$	$-$	$-$

Then, we have that:

1. $\forall x (M(x)\rightarrow L(x))$ is true since in every row, if there is a $+$ underneath $M$, then there is a $+$ underneath $L$;
2. $\exists x M(x)$ is true since there is some row with a $+$ below $M$ (namely, the row labeled with $1$); and
3. $\forall x L(x)$ is false since it is not true that every row beneath $L$ is labeled with a $+$ (in particular, the row labeled with $2$ is not labeled with a $+$).

Truth in First Order Models

We have not given the full definition of when a formula is true in a model of First Order Logic. The full details of this definition are beyond the scope of this course. However, the examples above (and in the practice questions) should make it clear how to determine the truth value of formulas in simple models that can be visualized as a table.

An important thing to note about models is that the domain may be infinite. For instance, the domain may be the set of all positive numbers, the set of real numbers, etc. In these cases, you cannot use a table to visualize the model.

Putting everything together, we have the following definition of validity for arguments in First Order Logic:

Validity - First Order Logic

Suppose that $X_1, \ldots, X_n$ and $Y$ are First Order Formulas. The argument with premises $X_1, \ldots, X_n$ and conclusion $Y$ is valid, denoted $X_1, \ldots, X_n\models Y$ if there is no model in which all the premises $X_1, \ldots, X_n$ are true and $Y$ is false.

Example

Examples of valid arguments include:

1. $A(a)\models \exists x A(x)$
   $a$ is an $A$. So, there is some thing is an $A$

2. $\forall x (A(x)\rightarrow B(x)), \forall x(B(x)\rightarrow C(x))\models \forall x(A(x)\rightarrow C(x))$
   All $A$s are $B$s. All $B$s are $C$s. So, all $A$s are $C$s.

3. $\exists x(A(x)\wedge B(x)), \forall x (B(x)\rightarrow C(x))\models \exists x (A(x)\wedge C(x))$
   Some $A$ is a $B$. All $B$s are $C$s. So, some $A$ is a $C$.

4. $\forall x (A(x)\rightarrow B(x)), \neg \exists x(C(x)\wedge B(x))\models \neg \exists x(C(x)\wedge A(x))$
   All $A$s are $B$s. No $C$ is a $B$. So, no $C$ is an $A$.

Practice Questions

A. Consider the following model. Determine whether the following formulas are true or false in this model.

	$a$	$b$	$c$	$A$	$B$
$1$	$\checkmark$			$+$	$-$
$2$			$\checkmark$	$+$	$+$
$3$		$\checkmark$		$-$	$+$
$4$				$+$	$-$

1. $A(c)\wedge \neg B(a)$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   $c$ is interpreted as $2$ and $2$ is in the interpretation of $A$ and $a$ is interpreted as $1$ which is not in the interpretation of $B$; so the conjunction $A(c)\wedge \neg B(a)$ is true.

2. $A(a)\wedge \neg B(a)$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   $a$ is interpreted as $1$ and $1$ is in the interpretation of $A$ and not in the interpretation of $B$, so the conjunction $A(a)\wedge \neg B(a)$ is true.

3. $A(c)\wedge (B(b) \vee \neg A(a))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   $b$ is interpreted as $3$ and $3$ is in the interpretation of $B$, so $B(b)$ is true. This means that $B(b)\vee \neg A(a)$ is true; and since $c$ is interpreted as $2$ and $2$ is in the interpretation of $A$, the conjunction $A(c)\wedge (B(b) \vee \neg A(a))$ is true.

4. $A(a)\rightarrow A(b)$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   $a$ is interpreted as $1$ and $1$ is in the interpretation of $A$, but $b$ is interpreted as $3$ and $3$ is not in the interpretation of $A$, so the conditional $A(a)\rightarrow A(b)$ is false.

5. $A(a)\rightarrow (B(b)\wedge B(c))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   $a$ is interpreted as $1$ and $1$ is in the interpretation of $A$, so we must check whether $B(b)\wedge B(c)$ is true. The consequent is true since $b$ is interpreted as $3$ and $c$ is interpreted as $2$ and both $2$ and $3$ are in the interpretation of $B$.

B. Consider the following model. Determine whether the following formulas are true or false in this model.

	$a$	$b$	$c$	$A$	$B$	$C$
$1$	$\checkmark$			$+$	$+$	$+$
$2$			$\checkmark$	$+$	$+$	$+$
$3$		$\checkmark$		$-$	$+$	$-$
$4$				$+$	$-$	$+$

1. $\forall x(A(x)\rightarrow B(x))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   There is some element in the domain, namely $4$ that is in the interpretation of $A$ but not the interpretation of $B$.

2. $\exists x(B(x)\wedge \neg C(x))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   The element $3$ is in the interpretation of $B$ but not the interpretation of $C$.

3. $\forall x(A(x)\vee B(x))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   Every row in the table either has a pluse below $A$ or a plus below $B$.

4. $(\forall x A(x)\vee \forall x B(x))$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   The element $3$ is not in the interpretation of $A$, so $\forall x A(x)$ is false. The element $4$ is in the interpretation of $B$, so $\forall x B(x)$ is false. Since both disjuncts are false, the disjunction $(\forall x A(x)\vee \forall x B(x))$ is false.

5. $\neg \forall x C(x)$

   This formula is true in the above model.

   This formula is false in the above model

   ​

   The element $3$ is not in the interpretation of $C$, so not all of the elements are in the interpretaiton of $C$.

C. For each of the following formulas, find a model with at least two elements in the domain that makes the formula true and another model that makes the formula false.

1. $\exists x(A(x) \wedge B(x))$

2. $(\exists x A(x) \wedge \exists x B(x))$

3. $\forall x (A(x) \vee B(x))$

4. $(\forall x A(x) \vee \forall x B(x))$

5. $\neg \forall x(A(x)\rightarrow B(x))$

D. Suppose that $X$ and $Y$ are formulas of First Order Logic. We say $X$ and $Y$ are equivalent when every model assigns the same truth value to $X$ and $Y$. For each pair of formulas, determine whether the formulas are equivalent.

1. $\forall x A(x)$ and $\neg \exists x \neg A(x)$

   The formulas are not equivalent: There is a model that makes one of the formulas true and the other formula false.

   The formulas are equivalent: Every model either makes both formulas true or both formulas false.

   ​

   Every element is in the interpretation of $A$ is equivalent to there is no element that is not in the interpretation of $A$.

2. $\forall x (A(x)\wedge B(x))$ and $(\forall x A(x)\wedge \forall x B(x))$

   The formulas are not equivalent: There is a model that makes one of the formulas true and the other formula false.

   The formulas are equivalent: Every model either makes both formulas true or both formulas false.

   ​

   If element is both $A$ and $B$, then every element is an $A$ and every element is a $B$. We also have that if every element is an $A$ and every element is a $B$, then every element is both an $A$ and $B$.

3. $\forall x (A(x)\vee B(x))$ and $(\forall x A(x)\vee \forall x B(x))$

   The formulas are not equivalent: There is a model that makes one of the formulas true and the other formula false.

   The formulas are equivalent: Every model either makes both formulas true or both formulas false.

   ​

   The following models makes $\forall x (A(x)\vee B(x))$ true and makes $(\forall x A(x)\vee \forall x B(x))$ false.

   	$A$	$B$
   $1$	$-$	$+$
   $2$	$+$	$-$

4. $\exists x (A(x)\wedge B(x))$ and $(\exists x A(x)\wedge \exists x B(x))$

   The formulas are not equivalent: There is a model that makes one of the formulas true and the other formula false.

   The formulas are equivalent: Every model either makes both formulas true or both formulas false.

   ​

   The following models makes $(\exists x A(x)\wedge \exists x B(x))$ true and makes $\exists x (A(x)\wedge B(x))$ false (there is no element that is both $A$ and $B$, but there is an element that is an $A$ and an element that is a $B$).

   	$A$	$B$
   $1$	$-$	$+$
   $2$	$+$	$-$

5. $\exists x (A(x)\vee B(x))$ and $(\exists x A(x)\vee \exists x B(x))$

   The formulas are not equivalent: There is a model that makes one of the formulas true and the other formula false.

   The formulas are equivalent: Every model either makes both formulas true or both formulas false.

   ​

   If there is some element that is either $A$ or $B$, then either that element is an $A$ or that element is a $B$, so either there is some element that is an $A$ or some element that is a $B$. We also have that if either there is some element that is an $A$ or there is some element that is a $B$, then in both clases there is some element that is either $A$ or $B$.

E. Formalize the argument in the cartoon below and give a model that shows it is not a valid argument.