Back to search

Cornell University

Nonstandard Models Of The Weak Second Order Theory Of One Successor

Abstract

dc:description.abstract

In 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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mathematics
Grantor
Cornell University
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kern, Thomas
Chair dc:contributor.chair
  • Nerode,Anil
Committee members dc:contributor.committeemember
  • Kozen,Dexter Campbell
  • Shore,Richard A

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9597272

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kern, Thomas. Nonstandard Models Of The Weak Second Order Theory Of One Successor. Doctor of Philosophy thesis, Cornell University, 2016. https://hdl.handle.net/1813/44393