Dissertation/Thesis Abstract

Nonstandard models of the weak second order theory of one successor
by Kern, Thomas Robert, Ph.D., Cornell University, 2016, 149; 10183827
Abstract (Summary)

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.

Indexing (document details)
Advisor:
Commitee:
School: Cornell University
Department: Mathematics
School Location: United States -- New York
Source: DAI-B 78/04(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Mathematics, Computer science
Keywords: Automata, Model theory, Monadic second order, Nonstandard, Theory of one successor
Publication Number: 10183827
ISBN: 978-1-369-31948-4
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest