On Weak Number Theories

Decidability and definability are two separate but quite related topics in logic. Many undecidability results are proved by positive definability results. In Chapter 1 we reformulate Schinzel's theorem about diophantine equations with parameters to get some number theoretic results. In later chapter we apply these results to solve various decidability and definability problems. In Chapter 2 we prove that (FOR ALL)('n)(THERE EXISTS) over Z is decidable, then we generalize this result to an arbitrary ring of integers of a finite extension of rational numbers. In Chapter 3 we give a necessary condition for a set to be (FOR ALL)('n)(THERE EXISTS)-diophantine definable over R. From this necessary condition we can show that many subsets of R including N and cofinite subsets, are not (FOR ALL)('n)(THERE EXISTS)-diophantine definable. We also characterize those subsets of N such that the set and its complement in N both are (THERE EXISTS)-diophantine definable over N. From this we can answer negatively the question asked by J. P. Jones {5}. In Chapter 4 we prove that the set of prime numbers cannot be defined by a formula containing but one quantifier ranging over N. So far this is the only definite subset of N we know which has this property.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Tung, Shih-Ping

• Mathematics

Identifier

(UMI)AAI8409843

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/71214