Show simple item record

dc.contributor.authorKern, Thomas
dc.date.accessioned2016-07-05T15:30:17Z
dc.date.issued2016-05-29
dc.identifier.otherbibid: 9597272
dc.identifier.urihttps://hdl.handle.net/1813/44393
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.language.isoen_US
dc.titleNonstandard Models Of The Weak Second Order Theory Of One Successor
dc.typedissertation or thesis
dc.description.embargo2021-05-30
thesis.degree.disciplineMathematics
thesis.degree.grantorCornell University
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Mathematics
dc.contributor.chairNerode,Anil
dc.contributor.committeeMemberKozen,Dexter Campbell
dc.contributor.committeeMemberShore,Richard A
dc.identifier.doihttps://doi.org/10.7298/X4XS5S91


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics