Notes - Logic MT24, First-order logic

A countable first-order language consists of two parts:

1. A countable set of non-logical symbols, each of which categorised as one of the following kinds:
   • Constant symbols: $c _ 0, c _ 1, \ldots$
   • $k$-ary predicate symbols for some $k \ge 1$: $P _ 0(\cdots), P _ 1(\cdots), \ldots$
   • $k$-ary function symbols for some $k \ge 1$: $f _ 0(\cdots), f _ 1(\cdots), \ldots$
2. The following (disjoint) set of logical symbols:
   • Connectives: $\to, \lnot$ (other connectives can be expressed by logically equivalent formulas)
   • Quantifier: $\forall$ (other quantifiers can be expressed by logically equivalent formulas)
   • Variables: $\{x _ i\} _ {i \in \mathbb N}$
   • Punctuation: “$,$”, “$($” and “$)$”.
   • Equality: $\doteq$

Recursively, a string in $\mathcal L$ is a $\mathcal L$-term if it has one of the following forms:

• A variable $x _ i$
• A constant symbol
• $f(t _ 1, \ldots, t _ k)$ where $f$ is a $k$-ary function symbol $\mathcal L$ and each $t _ i$ is a term

Any string of the form

\[P(t _ 1, \ldots, t _ k)\]

or

\[t _ 1 \doteq t _ 2\]

where each $t _ i$ is a $\mathcal L$-term.

A string is a $\mathcal L$-formula if it has one of the following forms:

• An atomic $\mathcal L$-formula
• $\lnot \phi$ or $(\phi \to \psi)$ where $\phi, \psi$ are $\mathcal L$-formulas
• $\forall x _ i \phi$ where $\phi$ is a $\mathcal L$-formula and $i \in \mathbb N$.

• A non-empty set $M$, called the domain of $\mathcal M$
• For each $k$-ary function symbol $f \in \mathcal L$, a $k$-ary function $f^\mathcal M : M^k \to M$
• For each $k$-ary predicate symbol $P \in \mathcal L$, a subset $P^\mathcal M \subseteq M^k$
• For each constant symbol $c \in \mathcal L$, an element $c^\mathcal M \in M$

A choice of $\mathcal L$-structure.

A structure in the language $\{f, P, c\}$.

An assignment in $\mathcal M$ is a function

\[a : \\{x _ 0, x _ 1, \ldots\\} \to M\]

(i.e. it assigns values to each of the variables in $\mathcal L$).

It recursively determines a function

\[\tilde a : \text{Terms}(\mathcal L) \to M\]

by:

• $\tilde a(x _ i) := a(x _ i)$ for $i = 0, 1, \ldots$
• $\tilde a(c) := c^\mathcal M$ where $c \in \mathcal L$ is a constant symbol
• $\tilde a(f(t _ 1, \ldots, t _ k)) := f^\mathcal M (\tilde a(t _ 1), \ldots, \tilde a(t _ k))$ where $f \in \mathcal L$ is a $k$-ary function symbol and $t _ i \in \text{Term}(\mathcal L)$.

Then whether

\[\mathcal M \models _ a \phi\]

is also determined recursively:

• $\mathcal M \models _ a P(t _ 1, \ldots, t _ k)$ iff $(\tilde a(t _ 1), \ldots, \tilde a(t _ k)) \in P^\mathcal M$
• $\mathcal M \models _ a t _ 1 \doteq t _ 2$ iff $\tilde a(t _ 1) = \tilde a(t _ 2)$
• $\mathcal M \models _ a \lnot \psi$ iff $\mathcal M \not\models _ a \psi$
• $\mathcal M \models _ a (\psi \to \chi)$ iff $\mathcal M \not\models _ a \psi$ or $\mathcal M \models _ a \chi$
• $\mathcal M \models _ a \forall x _ i \psi$ iff for all assignments $a^\star$ such that $a^\star(x _ j) = a(x _ j)$ for all $j \ne i$, $\mathcal M \models _ {a^\ast} \psi$ (i.e. under all possible assignments of $x _ i$ while keeping every other assignment the same, the formula holds)

\[a^\star(x _ j) = a(x _ j)\]

for all $j \ne i$.

The unique assignment such that $a [ m/x _ i ] \sim _ i a$ and $a [ m/x _ i ] (x _ i) = m$, i.e.

\[a [ m/x _ i ] (x _ j) = \begin{cases} a(x _ j) &\text{if } j \ne i \\\\ m &\text{if } j = i \end{cases}\]

\[\mathcal M \models _ a \phi\]

for all $\mathcal L$-structures $\mathcal M$ and for all assignments $a$ in $\mathcal M$.

\[\mathcal M \models _ a \phi\]

where $a$ is some assignment in $\mathcal M$ .

For all $\phi \in \Gamma$,

\[\mathcal M \models _ a \phi\]

For all $\mathcal L$-structures $\mathcal M$ and for all assignments $a$ in $\mathcal M$, then

\[\mathcal M \models _ a \Gamma \text{ implies } \mathcal M \models _ a \phi\]

\[\\{\phi\\} \models \psi \text{ and } \\{\psi\\} \models \phi\]

$\phi$ comes from putting first-order formulas into a logically valid propositional logic formula, i.e. there exists some logically valid propositional formula $\alpha \in \text{Form}(\mathcal L _ 0)$ containing propositional variables $p _ 1, \ldots, p _ n$ and some $\psi _ 0, \ldots, \psi _ n \in \text{Form}(\mathcal L)$ such that $\phi$ is obtained by substituting each occurrence of $p _ i$ by $\psi _ i$.

By the definition of $\phi$ being a tautology, there exists some logically valid propositional formula $\alpha \in \text{Form}(\mathcal L _ 0)$ containing propositional variables $p _ 1, \ldots, p _ n$ and some $\psi _ 0, \ldots, \psi _ n \in \text{Form}(\mathcal L)$ such that $\phi$ is obtained by substituting each occurrence of $p _ i$ by $\psi _ i$.

Take any structure $\mathcal M$ and a corresponding assignment $a$. Consider the propositional valuation

\[v(p _ i) = \begin{cases} \mathbf{true} & \text{if } \mathcal M \models _ a \psi _ i \\\\ \mathbf{false} & \text{otherwise} \end{cases}\]

Then it follows that

\[\tilde v(\alpha) = \mathbf{true}\]

by the validity of $a$. By the definition of $\models$, it follows that

\[\mathcal M \models _ a \phi\]

Since $a$ and $\mathcal M$ were arbitrary, $\phi$ is logically valid.

\[x _ 0 \doteq x _ 0\]

The only propositional formula that would work would $p _ 0$, which is not a valid propositional formula.

Either:

• $\phi$ is atomic
• $\phi = \lnot \psi$ and $x$ is free in $\psi$
• $\phi = (\psi \to \chi)$ and $x$ is free in $\psi$ or in $\chi$
• $\phi = \forall x _ i \psi$ and $x$ is free in $\psi$, and $x \ne x _ i$.

If $\phi$ is atomic, then all variables in $\phi$ must be free and so the result follows immediately since the assignments must actually be equal.

Induct on the length of $\phi$.

Case $\phi = \lnot \psi$: By the IH, it holds for $\psi$. Since whether $\mathcal M\models\lnot\psi$ is defined in terms of whether $\mathcal M \models \psi$, the result is immediate.

Case $\phi = (\psi \to \rho)$: By the IH, it holds for $\psi$ and $\rho$. Likewise, the result is immediate in this case.

Case $\phi = \forall x _ i \psi$: By the IH, it holds for $\psi$.

Suppose that $\mathcal M \models _ {a _ 1} \forall x _ i \psi$, we aim to show that $\mathcal M \models _ {a _ 2} \forall x _ i \psi$. By the definition of $\forall$, we need to show that for any assignment $a _ 2^\star$ where $a _ 2^\star \sim _ i a _ 2$, $\mathcal M \models a _ 2^\star \psi$.

Define

\[a _ 1^\star := a _ 1[a _ 2^\star(x _ i)/x _ i]\]

Then $\mathcal M \models _ {a _ 1^\star} \psi$ since $a _ 1^\star \sim _ i a _ 1$ (all variables are the same apart from $x _ i$).

By the inductive hypothesis, we must then have that $\mathcal M \models _ {a _ 2^\star} \psi$. To apply this, we need to show that $a _ 1^\star$ and $a _ 2^\star$ still agree on the free variables of $\psi$, i.e. if $x _ j$ occurs free in $\psi$, then $a _ 2^\star(x _ j) = a _ 1^\star (x _ j)$.

If $j = i$, this follows directly from the definition of $a _ 1^\star$. If $j \ne i$, then $x _ j$ occurs free in $\phi$ and so

\[a _ 2^\star (x _ j) = a _ 2(x _ j) = a _ 1(x _ j) = a _ 1^\star(x _ j)\]

Pick an arbitrary $\mathcal L$-structure $\mathcal M$ and an assignment $a$ such that

\[\mathcal M \models _ a \forall x _ i (\alpha \to \beta)\]

We aim to show that then:

\[\mathcal M \models _ a (\alpha \to \forall x _ i \beta)\]

To do this, suppose $\mathcal M \models _ a \alpha$. By the definition of $\forall$, we want to show that for all $a^\star \sim _ i a$, $\mathcal M \models _ {a^\star} \beta$. Since $a$ and $a^\star$ agree on all variables apart from $x _ i$ (which is not free in $\alpha$), by the result that says:

Suppose:

• $\mathcal L$ is a first-order language
• $\phi$ is a $\mathcal L$-formula
• $\mathcal M$ is a $\mathcal L$-structure
• $a _ 1$, $a _ 2$ are assignments in $\mathcal M$
• $a _ 1$ and $a _ 2$ agree on the free variables of $\phi$ (i.e. $a _ 1(x _ i) = a _ 2(x _ i)$ where $x _ i$ free) Then:

\[\mathcal M \models _ {a _ 1} \phi \text{ iff } \mathcal M \models _ {a _ 2} \phi\]

It follows that

\[\mathcal M \models _ {a^\star} \alpha\]

This is useful, because with the assumption that $\mathcal M \models _ a \forall x _ i (\alpha \to \beta)$ along with the definition of $\forall$ (using the reverse direction), it follows that

\[\mathcal M \models _ {a^\star} \beta\]

But unwinding everything we have shown so far, this means that

\[\mathcal M \models _ a (\alpha \to \forall x _ i \beta)\]

as required.

It contains no free variables.

Since $\phi$ is a sentence it contains no free-variables. Hence its truth-value does not depend on the choice of assignment.

\[\mathcal M \models \sigma\]

Replace each free occurrence of $x _ i$ in $\phi$ with the string $t$, as long as this does not introduce new bound occurrences of variables.

More precisely:

• If $\phi$ is atomic, $(\phi)[t/x _ i]$ is the result of replacing each instance of $x _ i$ in $\phi$ with $t$.
• $(\lnot \psi)[t/x _ i] := \lnot (\psi) [t/x _ i]$ (which is undefined if $(\psi)[t/x _ i]$ is)
• $((\psi \to \chi))[t/x _ i] := ((\psi)[t/x _ i] \to (\chi)[t/x _ i])$ (which is undefined if $(\psi)[t/x _ i]$ or $(\chi)[t/x _ i]$ is)
• $(\forall x _ i \psi)[t/x _ i] := \forall x _ i \psi$
• If $j \ne i$, then $(\forall x _ j \psi)[t/x _ i] := \forall x _ j (\psi) [t/x _ i]$, unless $x _ j$ occurs in $t$ and $x _ i$ occurs free in $\psi$ (in which case it is undefined).

\[a[\tilde a(t)/x _ i]\]

Suppose:

• $\mathcal L$ is a first-order language
• $\mathcal M$ is a $\mathcal L$-structure
• $\phi \in \text{Form}(\mathcal L)$
• $t \in \text{Term}(\mathcal L)$
• $\phi[t/x _ i]$ is defined

Then:

\[\mathcal M \models _ a \phi[t/x _ i] \text{ iff } \mathcal M \models _ {a[t/x _ i]} \phi\]

We proceed by induction on the length of $\phi$.

Base case: $\phi$ is atomic, say $\phi = P(t _ 1, \ldots, t _ k)$. For each $u \in \text{Term}(\mathcal L)$ we define $u[t/x _ i]$ by replacing each occurrence of $x _ i$ in $u$ by $t$.

Note that $\widetilde{a[t/x _ i]}(u) = \tilde a(u[t/x _ i])$ (this can be proved inductively, but is intuitive; replacing $x _ i$ by $t$ in $u$ when you “bottom out” in the recursion on the left hand side is the same as replacing all occurrences of $x _ i$ by $t$ at the start on the right hand side).

Then note that:

\[\begin{aligned} &\mathcal M \models _ {a[t/x _ i]} \phi \\\\ \text{iff }& (\widetilde{a[t/x _ i]}(t _ 1), \ldots, \widetilde{a[t/x _ i]}(t _ k)) \in P^M \\\\ \text{iff }& (\tilde a(t _ 1[t/x _ i]), \ldots,\tilde a(t _ k[t/x _ i])) \in P^M \\\\ \text{iff }& \mathcal M \models _ a P(t _ 1[t/x _ i], \ldots, t _ k[t/x _ i]) \\\\ \text{iff } & \mathcal M \models _ a \phi[t/x _ i] \end{aligned}\]

as required.

Likewise, if $t _ 1 \doteq t _ 2$, the same argument applies. So the lemma holds for atomic formulas.

Inductive hypothesis: The lemma holds for shorter formulas.

Case $\phi = \lnot \psi$: Follows from inductive hypothesis.

Case $\phi = (\psi \to \chi)$: Follows from inductive hypothesis.

Case $\phi = \forall x _ i \psi$ (note $x _ i$ is the same as the $x _ i$ in the statement): Then $\phi [t/x _ i] = \phi$, $x _ i \notin \text{Free}(\phi)$. Then $a$ and $a[t/x _ i]$ agree on all $x \in \text{Free}(\phi)$, so by the lemma that says:

Suppose:

• $\mathcal L$ is a first-order language
• $\phi$ is a $\mathcal L$-formula
• $\mathcal M$ is a $\mathcal L$-structure
• $a _ 1$, $a _ 2$ are assignments in $\mathcal M$
• $a _ 1$ and $a _ 2$ agree on the free variables of $\phi$ (i.e. $a _ 1(x _ i) = a _ 2(x _ i)$ where $x _ i$ free) Then:

\[\mathcal M \models _ {a _ 1} \phi \text{ iff } \mathcal M \models _ {a _ 2} \phi\]

it follows that

\[\begin{aligned} &\mathcal M \models _ {a[t/x _ i]} \phi \\\\ \text{iff }& \mathcal M \models _ a \phi \\\\ \text{iff }& \mathcal M \models _ a \phi[t/x _ i] \end{aligned}\]

as required.

Case $\phi = \forall x _ j \psi$, $j \ne i$: Expanding the definitions, note that $\phi [t/x _ i] = \forall x _ j (\psi)[t/x _ i]$.

If $x _ i$ is not free in $\psi$, then $\phi[t/x _ i] = \phi$ and we can argue identically to the previous case.

Now if $x _ i$ is free in $\psi$, then since $\phi[t/x _ i]$ is defined (by assumption), it follows that $x _ j$ does not occur in $t$.

We would like to argue like so:

\[\begin{aligned} &\mathcal M \models _ a \phi[t/x _ i] \\\\ \text{iff }& \mathcal M \models _ a \forall x _ j (\psi)[t/x _ i] && \text{by expanding out} \\\\ \text{iff }& \mathcal M \models _ {a^\star} \psi[t/x _ i] \text{ for all }a^\star \sim _ j a&& \text{by def. of }\forall \\\\ \text{iff }&\mathcal M \models _ {a^\star[t/x _ i]} \psi \text{ for all } a^\star \sim _ j a && \text{by inductive hypothesis} \\\\ \text{iff }&\mathcal M \models _ {a'} \psi \text{ for all } a' \sim _ j a[t/x _ i] &&\text{by }(\star) \\\\ \text{iff }&\mathcal M \models _ {a[t/x _ i]} \forall x _ j \psi &&\text{by def. of } \forall \\\\ \text{iff }& \mathcal M \models _ {a[t/x _ i]} \phi \end{aligned}\]

To see $(\star)$, it suffices to show that the following equality:

\[\\{a^\star [t/x _ i] \mid a^\star \sim _ j a\\} = \\{a' \mid a' \sim _ j a[t/x _ i]\\}\]

Suppose that $a^\star \sim _ j a$. Then $\tilde a^\star(t) = \tilde a(t)$, so $a^\star[t/x _ i] \sim _ j a[t/x _ i]$.

Likewise if $a’ \sim _ j a[t/x _ i]$, then $a’ = a^\star[t/x _ i]$ for some $a^\star \sim _ j a$, namely $a^\star = a[a’(x _ j)/x _ j]$, so we have the other conclusion.

This concludes the final case.

Fix an assignment $a$ in a $\mathcal L$-structure $\mathcal M$.

Suppose that $\mathcal M \models _ a \forall x _ i \phi$. Then $\mathcal M \models _ {a[t/x _ i]} \phi$ since $a[t/x _ i] \sim _ i a$. Therefore $\mathcal M \models _ a \phi[t/x _ i]$ by the substitution lemma.

It is of the form

\[Q _ 1 x _ {i _ 1} \cdots Q _ k x _ {i _ k} \psi\]

for quantifiers $Q _ 1, \ldots, Q _ k$, variables $x _ {i _ 1}, \ldots, x _ {i _ k}$ and a quantifier-free formula $\psi$.