{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/44393"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/44393","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Nonstandard Models Of The Weak Second Order Theory Of One Successor","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Kern, Thomas"],"institution":"Cornell University","degree_name":"Ph. D., Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Nerode,Anil"],"committee_members":["Kozen,Dexter Campbell","Shore,Richard A"],"year":2016,"date_issued":"2016-05-29","date_published":"2016-05-29","updated_at":"2026-11-19T03:19:03Z","subjects":[],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/X4XS5S91"],"render_values":[{"text":"https://doi.org/10.7298/X4XS5S91","href":"https://doi.org/10.7298/X4XS5S91","code":true}]},{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9597272"],"render_values":[{"text":"9597272","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/44393","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/44393","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F44393","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Nerode,Anil"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Kozen,Dexter Campbell","Shore,Richard A"]},{"key":"dc:creator","label":"Author","values":["Kern, Thomas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-07-05T15:30:17Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2021-05-30T06:00:30Z"]},{"key":"dc:date.issued","label":"Date","values":["2016-05-29"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["9597272"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.7298/X4XS5S91"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/44393"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"2a70aa68-43a8-48e9-8564-947cba07dc8a\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Nonstandard Models Of The Weak Second Order Theory Of One Successor</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2016-05-29</PublicationDate> <DOI>https://doi.org/10.7298/X4XS5S91</DOI> <Authors> <Author> <DisplayName>Kern, Thomas</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Kern, Thomas"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Nonstandard Models Of The Weak Second Order Theory Of One Successor"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"2a70aa68-43a8-48e9-8564-947cba07dc8a\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Nonstandard Models Of The Weak Second Order Theory Of One Successor</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2016-05-29</PublicationDate> <DOI>https://doi.org/10.7298/X4XS5S91</DOI> <Authors> <Author> <DisplayName>Kern, Thomas</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Kern, Thomas"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Nerode,Anil"],"dc:contributor.committeemember":["Kozen,Dexter Campbell","Shore,Richard A"],"dc:creator":["Kern, Thomas"],"dc:date.accessioned":["2016-07-05T15:30:17Z"],"dc:date.available":["2021-05-30T06:00:30Z"],"dc:date.issued":["2016-05-29"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["9597272"],"dc:identifier.doi":["https://doi.org/10.7298/X4XS5S91"],"dc:identifier.uri":["https://hdl.handle.net/1813/44393"],"dc:language.iso":["en_US"],"dc:title":["Nonstandard Models Of The Weak Second Order Theory Of One Successor"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:19:03Z"}