**Maintainer:**admin

*1*Conjectures 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.1*Defineable 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$.