Monday, October 24, 2011 CC-BY-NC
More on models

Maintainer: admin

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$.