Monday, October 24, 2011
More on models
1Conjectures in model theory¶
Given this little toy structure:
$$M = \{ \alpha, \beta, \gamma, \delta\}$$
$$f\alpha = \beta, \, f\beta = \gamma, \, f\gamma = \delta, \, f\delta = \alpha$$
$$P^{\mathcal{M}} = \{(\alpha, \beta), (\alpha, \gamma), (\alpha, \delta), (\beta, \gamma), (\gamma, \delta) \}$$
$$c^{\mathcal{M}} = \gamma$$
and $\varphi (x, y) = \exists z (Pfxz \lor fy = c)$, list the ordered pairs $(a, b) \in M^2$ for which it is true that $M \models \varphi(a, b)$confirm use of models here.
| Ordered pair | True or false |
|---|---|
| $(\alpha, ...)$ | True ($z = \gamma$) |
| $(\beta, ...)$ | True ($z = \delta$) |
| $(\gamma, \alpha)$ | False |
| $(\gamma, \beta)$ | True (as $f\beta = \gamma$) |
| $(\gamma, \gamma)$ | False |
| $(\gamma, \delta)$ | False |
| $(\delta, ...)$ | True ($z = \alpha$) |
So $\varphi(\mathcal{M}) = \{$ those pairs $\}$.
Say $\sigma_1$ is the sentence $\forall x \exists y \varphi(x, y)$. Does $\mathcal{M} \models \sigma_1$? Yes.
Say $\sigma_2$ is the sentence $\forall x \forall y \varphi(x, y)$. No.
$\sigma_3$ is $\exists x \forall y \neg(x, y)$. Negation of $\sigma_1$, so, no. We could also check for each $x$ to show that it is false.
1.1Defineable subsets of a model¶
Let M be any structure for any signature $\Sigma$. Consider the defineable subsets of M. The collection of these always contains $\varnothing$, and $M^n$ itself. To define $M^n$, we could use the formula $x_1 = x_1$, for instance. To define the empty set, we could use something like $x_1 \neq x_1$.
If $S \subseteq M^n$ is defineable, then so is $M^n \backslash S$ (its complement). So if $\varphi(x_1, ... x_n)$ defines $S$, then $\neg \varphi(x_1, ... x_n)$ defines $M^n \backslash S$.
If $S_1$ and $S_2$ are both defineable, so are $S_1 \cap S_2$ ($\varphi_1 \land \varphi_2$) and $S_1 \cup S_2$ ($\varphi_1 \lor \varphi_2$). So this is a boolean algebra.
The set $\{(a_1, ... a_n): a_j = a_k \} \subseteq M^n$ is defineable. For example, in $\mathbb{R}^2$, this would be a line (so $\{(1, 1), (2, 2), (3, 3) ... \}$).
Also, if $S \subseteq M^{n+1}$ is defineable, then so is $T \subseteq M^n$ where $T = \{(a_1, ...a_n): (a_1, a_n, b) \in S\}$ for some $b \in M$ (projection to the first $n$ places). If, say, $\varphi(x_1, ... x_n, x_{n+1})$ defines $S$, then $\exists b(\bar x, b)$ defines its projection $T$.