Show simple item record

dc.contributor.authorKern, Thomas
dc.identifier.otherbibid: 9597272
dc.description.abstractIn this paper, we seek to classify the nonstandard models of the weak (monadic) second order theory of one successor (WS1S), the theory of the two-typed structure consisting of natural numbers and finite sets of natural number equipped with a successor (+1) operation, and membership relation between the two types. This will require an automata-theoretic approach. Chapter 1 will provide an introductory background to the intersection of automata theory and model theory. In chapter 2, we use the Krohn-Rhodes Theorem and an observation about the powerset determinization construction to prove what will be essentially be a quantifier-elimination type result for our theory, although since the result is of independent interest, it will be presented in a more general automata-theoretic context as a generating set for the regular functions under composition. In chapter 3, we provide an axiomatization for WS1S. In chapter 4, we apply this axiomatization to prove a number of key theorems regarding nonstandard models of WS1S. This includes a classification of the possible first order types, tools for completely classifying nonstandard models, an exploration of countable nonstandard models with the simplest nontrivial first order type, and a tool for producing new nonstandard models given old nonstandard models.
dc.titleNonstandard Models Of The Weak Second Order Theory Of One Successor
dc.typedissertation or thesis
dc.description.embargo2021-05-30 University of Philosophy D., Mathematics
dc.contributor.committeeMemberKozen,Dexter Campbell
dc.contributor.committeeMemberShore,Richard A

Files in this item


This item appears in the following Collection(s)

Show simple item record