Effective Axiomatizations of Simple Ordered Structures
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Advisor
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Open Access
Terms of Use
Tripod URL
Identifier
Abstract
Axiomatization in finite model theory is the process of finding a set of axiom formulas from which all other formulas in a theory can be derived. Applied to the theory of a structure like "binary strings" or "natural number arithmetic," this allows us to find the precise minimal mathematical definition of that structure. This has consequences on the computability of a structure; if a theory has a recursively enumerable axiomatization, then it is itself recursively enumerable. For example, the theory of binary strings can be axiomatized using just the axioms of a linear order, definable induction, and a maximal element. To do this, a technique called an “Ehrenfeucht-Fraisse game" is required, which shows that different models are equivalent for all formulas with at most n unique variables.However, the pigeonhole principle is logically equivalent to definable induction, so anything which can be derived from definable induction can be derived from the pigeonhole principle. Thus, it should be possible to axiomatize the theory of binary strings with the pigeonhole principle instead of definable induction, with interesting consequences and extensions as the pigeonhole principle (unlike induction) applies to sets without a linear order. For example, the same axiomatization technique can be applied to other ordered structures, like trees, which have a very different form of order.