Key Concepts
\(\mathcal{L}\)-structures: Provide a realm to interpret \(\mathcal{L}\)-formulas over.
- non-empty universe \(M\),
- interpretation of all constant, function, and relation symbols over \(M\).
structure isomorphism: bijection \(\pi\) between the universes of two \(\mathcal{L}\)-structures that preserves interpretations of symbols. General version of the well-known idea of isomorphism of mathematical structures.
assignment: function \(\alpha: \mathcal{V} \to M\) that assigns all variables values in the universe of a structure. Recursively extends to terms.
satisfaction relation: \(\mathcal{M} \models \varphi[\alpha]\) means the \(\mathcal{L}\)-formula \(\varphi\) is true when interpreted in the \(\mathcal{L}\)-structure \(\mathcal{M}\) and all variables are assigned values according to assignment \(\alpha\). This is defined recursively over the structure of a formula.
Problems
We warm up with a quote often attributed to Lincoln.
Exercise 1
You can fool all the people some of the time, and some of the people all the time, but you cannot fool all the people all the time.
Define a suitable language and formalize this statement in first-order logic.
Next, a couple of problems to see the definition of structures and the satisfaction relation \(\models\) at work.
Exercise 2
Let \(\mathcal{L} = \{ \Box, \triangle, c\}\), where \(\Box\) is a binary relation symbol, \(\triangle\) is a binary function symbol, and \(c\) is a constant symbol.
For each of the following formulas, find two \(\mathcal{L}\)-structures and (if necessary) assignments to the free variable(s) such that the formula holds in one structure but fails in the other.
\[\begin{aligned}
\varphi & \equiv \forall x \exists y \: \Box \, \triangle x y \, c \\
\psi & \equiv \exists x \forall y ( x = c \: \wedge \: \Box \, \triangle zc \, y )
\end{aligned}\]
Next, let’s see some general properties of structures we can describe through first-order formulas.
Exercise 3
Let \(n\) be a natural number and let \(\mathcal{L}\) be any language. Find formulas \(, \psi^{\geq}, \psi^{\leq}, \psi^=\) such that, for any \(\mathcal{L}\)-structure \(\mathcal{M}\),
\[\begin{aligned}
\mathcal{M} \models \psi^{\geq} & \iff \; |M| \geq n \\
\mathcal{M} \models \psi^{\leq} & \iff \; |M| \leq n \\
\mathcal{M} \models \psi^{=} & \iff \; |M| = n \\
\end{aligned}\]
Can we find a formula \(\theta\) such that
\[
\mathcal{M} \models \theta \; \iff \; |M| \text{ is finite}?
\]
We will answer this question in a few weeks…
Exercise 4
Let \(\mathcal{L} = \{\cdot , e\}\) be the language of groups. Show that there is a sentence \(\varphi\) such that \(\mathcal{M} \models \varphi\) if and only if
\[M \cong \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}.\]
- Let \(\mathcal{L}\) be any finite language and let \(\mathcal{M}\) be a finite \(\mathcal{L}\)-structure. Show that there is an \(\mathcal{L}\)-sentence \(\varphi\) such that
\[
\mathcal{N} \models \varphi \; \iff \; \mathcal{N} \cong \mathcal{M}.
\]
- Give an example of a language \(\mathcal{L}\) and an \(\mathcal{L}\)-sentence \(\psi\) such that
- there is at least one \(\mathcal{L}\)-structure \(\cal A\) such that \(\cal A \models \psi\),
- for all \(\cal L\)-structures \(\cal A\), if \(\cal A \models \psi\), then the universe \(A\) of \(\cal A\) is infinite.