Friday, October 21, 2011

Model theory

1Model theory stuff¶

Terms - defined inductively (recursively), use constants, and function symbols

Example with the natural numbers: $\mathcal{N} = \{\mathbb{N}, S^{\mathcal{N}}, +^{\mathcal{N}}, *^{\mathcal{N}}, <^{\mathcal{N}}, 0^{\mathcal{N}} \}$. Let $t^{\mathcal{N}}(x_1, x_2, x_3) = S(x_1, x_2) + (S0 + x_3)$. So to evaluate $t^{\mathcal{N}}(3, 5, 2)$, we do it recursively or something ... $t_1^{\mathcal{N}}(3, 5, 2) = 0^{\mathcal{N}}$, $t_2^{\mathcal{N}}(x_1, x_2, x_3) = S0 = 1$, etc. I'm missing something here.

The $\models$ ("models") symbol means that the formula $\sigma$ is true within the structure $\mathcal{M}$ in the expression $\mathcal{M} \models \sigma$.

Twin primes conjecture: does $\mathcal{N} \models \forall z ( \exists x (z < x \land \Pi(x) \land \Pi(SSx)))$? That is, is that sentence true for the natural numbers? Status: unknown.

Say $M = \{ \alpha, \beta, \gamma, \delta \}$ (trying to prove the twin primes conjecture for this set, instead of $\mathbb{N}$, and let $\Sigma = \{ P, f, c \}$ (a binary predicate symbol, a unary function symbol and a constant symbol, respectively). Let $P^{\mathcal{N}}$ be such that everything is related to everything else.

This is a toy structure to be continued next class.