116b- Lecture 20 « Computability Theory

116b- Lecture 20

By andrescaicedo

Given any complete, consistent extension $T$ of ${\sf 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{\sf PA}$ , let $SSy(M)$ , the standard system of $M$ , be the set of those $A\subseteq{\Bbb N}$ coded by elements of $M$ , where $a\in M$ codes $A$ iff $A=\{i\in{\Bbb N}:(a)_i\ne0\}$ . Thus $SSy({\Bbb N})$ is the class of finite sets. We showed that if $M\models{\sf PA}$ is nonstandard, $SSy(M)$ contains all recursive sets, and that for any non-recursive $S$ there is a nonstandard $M\models{\sf PA}$ such that $S\notin SSy(M)$ .

This entry was posted on March 13, 2008 at 1:33 pm and is filed under 116b. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Computability Theory

116b- Lecture 20

Leave a Reply