116b- Lecture 20

March 13, 2008

Given any complete, consistent extension T of \mathsf{PA}, we showed that there is a minimal model K_T of T. This model is unique up to (unique) isomorphism, it is rigid (i.e., it has no automorphisms other than the identity), and has no proper elementary substructures.

Given a model M\models\mathsf{PA}, let SSy(M), the standard system of M, be the set of those A\subseteq\mathbb{N} coded by elements of M, where a\in M codes A iff A=\{i\in\mathbb{N} : (a)_i\ne0\}. Thus SSy(\mathbb{N}) is the class of finite sets. We showed that if M\models\mathsf{PA} is nonstandard, SSy(M) contains all recursive sets, and that for any non-recursive S there is a nonstandard M\models \mathsf{PA} such that S\notin SSy(M).