Simple model-theoretic arguments in set theory

logicmodel-theoryset-theory

Consider the following simple proof that PA has models with nonstandard numbers.

The type $\{ x > n \mid n \in \mathbb{N} \}$ is finitely realizable, so there is an $M \models \mathrm{PA}$ which fully realizes it. Any realization of this type is larger than all the standard natural numbers. QED

Arguments of this kind, and analogous ones via omitting types instead of realizing them, are the bread and butter of model theory. My question is this. Are there any obvious reasons why simple arguments of this kind can't prove the basic results of undecidability?

Naively, "PA doesn't prove its own consistency" is equivalent to "there is $M \models \mathrm{PA}$ which contains a proof of 0=1". (Of course, such a proof would be nonstandard.) I tried for a bit to prove this by a type-realization argument like the one above, but couldn't. Are there known obstacles to such a strategy?

Relatedly, could there be a simple type realizing/omitting argument to construct an $M \models \mathrm{PA}$ which contains some sentence $\varphi$ such that, in M, there are no proofs of $\varphi$ nor $\lnot\varphi$? This wouldn't quite show incompleteness of PA (as $\varphi$ could be nonstandard) but it would be interesting to me.

In general, I guess I'm looking for a bit more of a connection between basic computability and basic model theory — even if the connection is, "here are good reasons why simple methods from the latter don't work in the former".

Best Answer

The point is that any technique for showing that (say) $\mathsf{PA}$ is incomplete must use something rather special about $\mathsf{PA}$, such as its computable axiomatizability. This is because there are in fact complete consistent extensions of $\mathsf{PA}$; the most obvious example is true arithmetic $\mathsf{TA}=Th(\mathbb{N};+,\times)$, but there are more exotic examples as well.

Basic model theory does provide us with quite flexible tools for building models with various sructural properties (compactness, Lowenheim-Skolem, omitting types). However, these tools are too flexible for establishing independence results: since they apply to all theories without finite models, including complete ones, they can't possibly be used to establish incompleteness.

Related Question