23 Predicate Logic Reintroduced, Syntax, Semantics, Universe Size

Lecture from: 04.12.2024 | Video: Videos ETHZ

Recall that a proof system $\Pi =(\mathcal{S},\mathcal{P},\tau ,\varphi )$ consists of statements, proofs, a semantic interpretation function ($\tau$), and a proof verification function ($\varphi$). A statement might take the form $M\models G$, where $M$ is a set of formulas, and $G$ is a logical consequence of $M$.

We’re now focusing on predicate logic and formalizing its syntax and semantics. A key difference from propositional logic is the distinction between terms (representing objects) and formulas (representing statements about objects). We’re defining the syntax of formulas, not yet delving into proofs or the verification function.

As discussed previously, we need to define both syntax (what constitutes a well-formed formula) and semantics (how to interpret and assign truth values to formulas). Semantics is defined by the valuation function: $\sigma (F,\mathcal{A})$ or $\mathcal{A}(F)$, which requires the concepts of matching interpretations and free variables.

Predicate Logic: Syntax and Semantics

Predicate logic is more expressive than propositional logic, allowing us to reason about objects, properties, and relationships.

Syntax: Defining Terms and Formulas

The alphabet $\Lambda$ of predicate logic includes:

• Variable Symbols: $x_i$ for $i\in \mathbb{N}$ (often represented as $x,y,z,...$).
• Function Symbols: $f_i^{(k)}$ (often $f,g,h,...$), where $k$ indicates the arity (number of arguments).
• Predicate Symbols: $P_i^{(k)}$ (often $P,Q,R,...$), where $k$ is the arity. Constants are 0-ary predicate symbols (e.g., $a,b,c$).
• Logical Connectives: $\neg ,\wedge ,\vee ,\to$ (as in propositional logic).
• Quantifiers: $\forall ,\exists$.
• Parentheses: $(,)$.

Terms

Terms represent objects in the universe of discourse. They are defined inductively:

1. Variable Symbols: Every variable symbol $x_i$ is a term.
2. Function Applications: If $f_i^{(k)}$ is a function symbol of arity $k$, and $t_1,t_2,...,t_k$ are terms, then $f_i^{(k)}(t_1,t_2,...,t_k)$ is a term.

• Example: $f(g(x),h(y,z))$ is a syntactically valid term, assuming the arities of $f$, $g$, and $h$ match.

Formulas

Formulas represent statements about objects. They are defined inductively:

1. Atomic Formulas: If $P_i^{(k)}$ is a predicate symbol of arity $k$ and $t_1,t_2,...,t_k$ are terms, then $P_i^{(k)}(t_1,t_2,...,t_k)$ is an atomic formula.

2. Logical Connectives: If $F$ and $G$ are formulas, then $\neg F$, $F\wedge G$, $F\vee G$, and $F\to G$ are formulas.

3. Quantifiers: If $F$ is a formula and $x_i$ is a variable symbol, then $\forall x_{i}F$ and $\exists x_{i}F$ are formulas.

• Example: $\forall x(P(x)\wedge \exists yQ(x,f(y)))$. We represent the structure using a syntax tree:

Semantics: Interpreting Formulas

Free Variables

A variable is free in a formula if it’s not bound by a quantifier. We define a function $free(F)$ that returns the set of free variables in a formula $F$.

• Example: In $P(x,y)\vee \exists x\forall yQ(x,y,z)$, the free variables are $free(P(x,y)\vee \exists x\forall yQ(x,y,z))=\{\underline{P},\underline{Q},\underline{x},\underline{y},\underline{z}\}$. While $x$ and $y$ appear within the scope of quantifiers, these are different instances of the variables $x$ and $y$ and have no effect on the free variables $x$ and $y$. The predicate symbols are considered free variables analogous to the atomic formulas from propositional logic.

Interpretations

An interpretation $\mathcal{A}$ assigns meaning to the symbols in a formula. Formally, $\mathcal{A}=(U,\varphi ,\psi ,\xi )$, where:

• $U$: The universe (domain of discourse).
• $\varphi$: Assigns concrete functions to function symbols ($f^{\mathcal{A}}=\varphi (f)$).
• $\psi$: Assigns concrete predicates to predicate symbols ($P^{\mathcal{A}}=\psi (P)$).
• $\xi$: Assigns values from the universe to free variables ($x^{\mathcal{A}}=\xi (x)$). We avoid this complicated notation and denote by $f^{\mathcal{A}}$ the meaning of $f$ under interpretation $\mathcal{A}$. Similar $U^{\mathcal{A}}$ gives us the universe and $x^{\mathcal{A}}$ the meaning of $x$.

An interpretation is matching if it assigns values to all free variables of the formula.

Example: Interpretation and Informal Evaluation

Consider the formula $F=\forall x(P(x)\vee P(f(x,a)))$. Let’s define a matching interpretation $\mathcal{A}$:

• $\mathcal{A}$:
  • $U^{\mathcal{A}}=\mathbb{N}$
  • $a^{\mathcal{A}}=3$
  • $f^{\mathcal{A}}(x,y)=x+y$
  • $P^{\mathcal{A}}(x)=1⟺x\text{ is even}$

This interpretation is matching because it provides meanings for all free variables ($\underline{P}$, $\underline{f}$, and $\underline{a}$). Now, let’s informally evaluate the formula under this interpretation.

The formula states that for all natural numbers $x$, either $P(x)$ is true (meaning $x$ is even) or $P(f(x,a))$ is true (meaning $f(x,a)=x+3$ is even). For any natural number $x$, either $x$ is even, or $x$ is odd. If $x$ is odd, then $x+3$ is even. If $x$ is even, then the formula is already satisfied. Thus the formula is indeed satisfied under the interpretation $\mathcal{A}$. This implies that the statement is true thus $\mathcal{A}(F)=1$.

Now let’s consider a different interpretation, $\mathcal{B}$:

• $\mathcal{B}$:
  • $U^{\mathcal{B}}=\mathbb{R}$
  • $a^{\mathcal{B}}=2$
  • $f^{\mathcal{B}}(x,y)=x\cdot y$
  • $P^{\mathcal{B}}(x)=1⟺x\ge 0$

Under this interpretation, the formula becomes $\forall x(x\ge 0\vee 2x\ge 0)$. Let’s analyze this:

• If $x\ge 0$, then the formula is true.
• If $x<0$, then $2x<0$, so the formula is false. Since our universe is $\mathbb{R}$ it is possible for $x$ to be negative thus the interpretation $\mathcal{B}$ does not model the formula $F$. Therefore, $\mathcal{B}(F)=0$. This example shows how the same formula can have different truth values under different interpretations.

Formal Definition of the Valuation Function ($\sigma$)

The valuation function $\sigma (F,\mathcal{A})$, or simply $\mathcal{A}(F)$, formally defines how to determine the truth value of a formula $F$ under an interpretation $\mathcal{A}$. This definition is recursive, mirroring the inductive definition of formulas.

1. Terms

First, we define how to interpret terms within an interpretation. The interpretation of a term is a value in the universe $U^{\mathcal{A}}$.

• Variable: If we have a variable symbol $x$, then $\mathcal{A}(x)=x^{\mathcal{A}}$ (the value assigned to $x$ by $\mathcal{A}$). If $x$ is a free variable and but has not been assigned a value, then the interpretation is not matching and hence $\mathcal{A}(F)$ is undefined.

• Function Application: If $t$ is a function application $f(t_1,...,t_k)$, then:

  $\mathcal{A}(f(t_1,...,t_k))=f^{\mathcal{A}}(\mathcal{A}(t_1),...,\mathcal{A}(t_k))$

  This means we first evaluate the arguments $t_1,...,t_k$ recursively under $\mathcal{A}$, obtaining values from the universe. Then, we apply the function $f^{\mathcal{A}}$ (the interpretation of the function symbol $f$) to these values.

2. Atomic Formulas

If $F$ is an atomic formula $P(t_1,...,t_k)$, then:

$\mathcal{A}(P(t_1,...,t_k))=1⟺(\mathcal{A}(t_1),...,\mathcal{A}(t_k))\in P^{\mathcal{A}}$

This means we first evaluate the terms $t_1,...,t_k$ under $\mathcal{A}$. Then, we check if the resulting tuple of values belongs to the relation $P^{\mathcal{A}}$ (the interpretation of the predicate symbol $P$).

3. Logical Connectives

The semantics of logical connectives are defined as in propositional logic:

• $\mathcal{A}(\neg F)=1⟺\mathcal{A}(F)=0$
• $\mathcal{A}(F\wedge G)=1⟺\mathcal{A}(F)=1\text{ and }\mathcal{A}(G)=1$
• $\mathcal{A}(F\vee G)=1⟺\mathcal{A}(F)=1\text{ or }\mathcal{A}(G)=1$
• $\mathcal{A}(F\to G)=1⟺\mathcal{A}(F)=0\text{ or }\mathcal{A}(G)=1$

4. Quantifiers

To define the semantics of quantifiers, we introduce the notion of a modified interpretation: ${\mathcal{A}}_{[x\to u]}$. This is the interpretation $\mathcal{A}$ with the value of the variable $x$ changed to $u\in U^{\mathcal{A}}$, regardless of whether $x$ was free in the original interpretation or not.

• Universal Quantifier ($\forall$):

  $$\mathcal{A}(\forall xG)=\{\begin{array}{ll}1& \text{if }{\mathcal{A}}_{[x\to u]}(G)=1\text{ for all }u\in U^{\mathcal{A}}\\ 0& \text{otherwise}\end{array}$$

• Existential Quantifier ($\exists$):

  $$\mathcal{A}(\exists xG)=\{\begin{array}{ll}1& \text{if }{\mathcal{A}}_{[x\to u]}(G)=1\text{ for some }u\in U^{\mathcal{A}}\\ 0& \text{otherwise}\end{array}$$

This recursive definition of $\sigma$ (or $\mathcal{A}(F)$) provides a complete and rigorous way to evaluate the truth value of any well-formed predicate logic formula under a given interpretation. It combines the interpretations of terms, predicates, logical connectives, and quantifiers to determine the overall truth value.

Example: Tautology with and without Quantifiers

Let’s analyze the formula $P(x)\vee \neg P(x)$.

• Without a Quantifier: To evaluate $\mathcal{A}(P(x)\vee \neg P(x))$, we need a matching interpretation $\mathcal{A}$. This interpretation must specify:

  • A universe $U^{\mathcal{A}}$.
  • An interpretation for the predicate symbol $P$ (a unary relation $P^{\mathcal{A}}\subseteq U^{\mathcal{A}}$).
  • A value $x^{\mathcal{A}}\in U^{\mathcal{A}}$ for the free variable $x$.

  Given such a matching interpretation, the formula is indeed a tautology. It evaluates to true because for any value of $x^{\mathcal{A}}$, either $x^{\mathcal{A}}\in P^{\mathcal{A}}$ or $x^{\mathcal{A}}\notin P^{\mathcal{A}}$. Since $P(x)\vee \neg P(x)$ is a tautology, denoted as $\models F$, $F$ must also be satisfiable since there must exist at least one model, in fact there exist many, many models.

• With a Universal Quantifier: Now consider $\forall x(P(x)\vee \neg P(x))$. A matching interpretation $\mathcal{A}$ for this formula still needs to specify:

  • A universe $U^{\mathcal{A}}$.
  • An interpretation for the predicate symbol $P$ ($P^{\mathcal{A}}\subseteq U^{\mathcal{A}}$).

  The variable $x$ is no longer free, so $\mathcal{A}$ does not need to assign a value to $x$. The formula is still a tautology. For any value $u\in U^{\mathcal{A}}$, the modified interpretation ${\mathcal{A}}_{[x\to u]}$ will make $P(x)\vee \neg P(x)$ true (as explained above). Since this holds for all $u\in U^{\mathcal{A}}$, the universally quantified formula is also true.

Lemma: Tautology and Universal Quantifier

Lemma

For any formula $F$, $\models F$ if and only if $\models \forall xF$.

Proof

• ($⟹$) If $\models F$ ($F$ is a tautology), then for every matching interpretation $\mathcal{A}$, $\mathcal{A}(F)=1$. This includes all interpretations ${\mathcal{A}}_{[x\to u]}$ for any $u$ from the universe. Thus $\mathcal{A}(\forall xF)=1$. Hence $\models \forall xF$.
• ($⟸$) If $\models \forall xF$, this means that for every interpretation $\mathcal{A}$ it holds that $\mathcal{A}(\forall xF)=1$. This means that ${\mathcal{A}}_{[x\to u]}(F)=1$ for all $u$ from the universe. This also means that every interpretation where $x$ is a free variable and is assigned a fixed value must model $F$. Therefore, any interpretation $\mathcal{A}$ modelling $x$ as a free variable can also be described by ${\mathcal{A}}_{[x\to u]}$ for some $u$ from the universe $U^{\mathcal{A}}$, and ${\mathcal{A}}_{[x\to u]}$ models $F$, and since $u$ and $\mathcal{A}$ were chosen arbitrarily we must have $\models F$.

Key Distinction: While seemingly similar, the reasoning for why the two formulas are tautologies is subtly different. In the first case ($P(x)\vee \neg P(x)$), the tautology arises from considering all possible interpretations of $P$ and all possible assignments for $x$. In the second case ($\forall x(P(x)\vee \neg P(x))$), the tautology arises because, within any single interpretation, the formula holds for all possible values of $x$ in the universe. The universal quantifier internalizes the consideration of all possible values of $x$ within a single interpretation. Thus the interpretations of both are different which is the key.

Example: Enforcing Universe Size with a Formula

Can we construct a formula that forces any satisfying interpretation to have a universe of at least a certain size? Yes, we can.

Let’s consider the case where we want to enforce a universe size of at least three. The following formula achieves this:

$F=\forall xP(x,x)\wedge \exists x\exists y\exists z(\neg P(x,y)\wedge \neg P(x,z)\wedge \neg P(y,z))$

• Explanation:
  • $\forall xP(x,x)$: This part enforces reflexivity of the predicate $P$. In any satisfying interpretation, the predicate $P$ must relate every element in the universe to itself.
  • $\exists x\exists y\exists z(\neg P(x,y)\wedge \neg P(x,z)\wedge \neg P(y,z))$: This part asserts that there exist three distinct elements $x,y,z$ in the universe such that none of them are related by $P$ to any other (except themselves due to the first part of the formula).

Proof of Minimum Universe Size

The claim is that if $\mathcal{A}(F)=1$ (i.e., $\mathcal{A}\models F$), then $|U^{\mathcal{A}}|\ge 3$.

Suppose, for contradiction, that $|U^{\mathcal{A}}|<3$.

1. Case 1: $|U^{\mathcal{A}}|=1$: If the universe has only one element, say $u$, then the second part of the formula $\exists x\exists y\exists z(\neg P(x,y)\wedge \neg P(x,z)\wedge \neg P(y,z))$ cannot be satisfied, as we cannot find three distinct elements.
2. Case 2: $|U^{\mathcal{A}}|=2$: Let the universe be $\{u,v\}$. Because of the first part of the formula we must have $P(u,u)$ and $P(v,v)$. The second part requires us to have distinct $x,y,z$ such that $\neg P(x,y),\neg P(x,z),\neg P(y,z)$. Since our universe has only two distinct elements, we cannot choose 3 distinct $x,y,z$.

In both cases, the formula $F$ cannot be satisfied. Therefore, if $\mathcal{A}(F)=1$, we must have $|U^{\mathcal{A}}|\ge 3$.

Enforcing an Infinite Universe

We can also construct a set of formulas that forces the universe to be infinitely large. Consider the following set:

$M=\{\forall xP(x,f(x)),\forall x\neg P(x,x),\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\to P(x,z))\}$

• Explanation:
  • $\forall xP(x,f(x))$: Every element $x$ is related by $P$ to $f(x)$.
  • $\forall x\neg P(x,x)$: $P$ is irreflexive (no element is related to itself).
  • $\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\to P(x,z))$: $P$ is transitive.

Proof of Infinite Universe

Let’s prove that if $\mathcal{A}(M)=1$ for all formulas in M, then $|U^{\mathcal{A}}|$ must be infinite.

Suppose, for contradiction, that $U^{\mathcal{A}}$ is finite. Pick any $x\in U^{\mathcal{A}}$. By the first formula $P(x,f(x))$. By the second formula, we have $f(x)\ne x$. Since the universe is finite we must get after applying $f$ a finite number of times the initial $x$ again, meaning $f(f(...f(x)))=x$. Using the transitivity of P, we get that $P(x,x)$ which is a direct contradiction to the irreflexivity property stated by the second formula.

Therefore, $U^{\mathcal{A}}$ must be infinite.

• Example Interpretation: An example interpretation over the natural numbers that satisfies these formulas is:
  • $U=\mathbb{N}$
  • $f(x)=x+1$
  • $P(x,y)⟺x<y$

This ability to control the universe’s properties through logical formulas is a powerful feature of predicate logic.

Example: Showing Unsatisfiability

Consider the following predicate logic formula:

$F=\forall xP(x)\wedge \exists xQ(x)\wedge \forall x(Q(x)⟺\neg P(x))$

Let’s demonstrate that this formula is unsatisfiable, meaning there is no interpretation $\mathcal{A}$ such that $\mathcal{A}(F)=1$.

Proof of Unsatisfiability

We’ll proceed by contradiction. Suppose there exists an interpretation $\mathcal{A}$ such that $\mathcal{A}(F)=1$. This means all three conjuncts must be true under $\mathcal{A}$:

1. $\mathcal{A}(\forall xP(x))=1$: This means for all $u\in U^{\mathcal{A}}$, ${\mathcal{A}}_{[x\to u]}(P(x))=1$. In simpler terms, the predicate $P$ is true for every element in the universe under interpretation $\mathcal{A}$.

2. $\mathcal{A}(\exists xQ(x))=1$: This means there exists at least one element $v\in U^{\mathcal{A}}$ such that ${\mathcal{A}}_{[x\to v]}(Q(x))=1$. So, there’s at least one element for which the predicate $Q$ is true.

3. $\mathcal{A}(\forall x(Q(x)⟺\neg P(x)))=1$: This means for all $w\in U^{\mathcal{A}}$, ${\mathcal{A}}_{[x\to w]}(Q(x)⟺\neg P(x))=1$. The biconditional ($⟺$) means $Q(x)$ and $\neg P(x)$ have the same truth value for all elements in the universe. Thus, if $Q(x)$ is true for some $x$ then $P(x)$ is false and vice versa.

Now, let’s consider the element $v$ from step 2, for which $Q(v)$ is true. By step 3, since $Q(v)$ is true, $\neg P(v)$ must also be true, meaning $P(v)$ is false. However, this contradicts step 1, which states that $P(x)$ is true for all elements in the universe, including $v$.

We’ve reached a contradiction. Therefore, our initial assumption that there exists an interpretation $\mathcal{A}$ such that $\mathcal{A}(F)=1$ must be false. Hence, the formula $F$ is unsatisfiable.

Lemma: Equivalence of Universal and Existential Quantifiers

Proof of Equivalence

We’ll prove this equivalence by showing that the two formulas have the same truth value under any interpretation $\mathcal{A}$.

1. $\mathcal{A}(\forall xF)=1$: This means that for all $u\in U^{\mathcal{A}}$, ${\mathcal{A}}_{[x\to u]}(F)=1$. In other words, $F$ is true for every element in the universe under the modified interpretation.

2. $\mathcal{A}(\neg \exists x\neg F)=1$: This means that $\mathcal{A}(\exists x\neg F)=0$. By the definition of the existential quantifier, this means that there is no $u\in U^{\mathcal{A}}$ such that ${\mathcal{A}}_{[x\to u]}(\neg F)=1$. Equivalently, there is no $u\in U^{\mathcal{A}}$ such that ${\mathcal{A}}_{[x\to u]}(F)=0$. This means for every $u\in U^{\mathcal{A}}$, ${\mathcal{A}}_{[x\to u]}(F)=1$ must hold.

As we see from 1. and 2. both formulas say exactly the same thing under any arbitrary interpretation.

Since the truth values of the two formulas are the same under any interpretation, the formulas are equivalent: $\forall xF\equiv \neg \exists x\neg F$.

Continue here: 24 Evaluating and Proving Formulas in Predicate Logic, Equivalences, Transformations, Variable Substitution, Universal Instantiation, Equality, Prenex Normal Form