Files in this item



application/pdf8409843.pdf (2MB)Restricted to U of Illinois
(no description provided)PDF


Title:On Weak Number Theories
Author(s):Tung, Shih-Ping
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Abstract: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.
Z. Adamowicz constructed a model which has some induction schemes but Matijasevic's theorem fails in this model. In order to prove her induction schemes she has to assume a very strong unproved conjecture, namely Schinzel's hypothesis H. With a result we prove in Chapter 1 we can prove the same induction schemes without assuming hypothesis H.
Issue Date:1984
Description:58 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984.
Other Identifier(s):(UMI)AAI8409843
Date Available in IDEALS:2014-12-16
Date Deposited:1984

This item appears in the following Collection(s)

Item Statistics