2026-09-21T12:53:23Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/71214 2023-07-11 col_2142_5131 col_2142_16340 com_2142_5130 com_2142_16339 com_2142_8903

Tung, Shih-Ping 2014-12-16T06:18:06Z 2014-12-16T06:18:06Z 10000-01-01 1984 1984 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. Made available in DSpace on 2014-12-16T06:18:06Z (GMT). No. of bitstreams: 1 8409843.pdf: 1697356 bytes, checksum: 721dee83a5926fc1c1994e4eb4942c1a (MD5) Previous issue date: 1984 Embargo set by: Seth Robbins for item 71380 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 58 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984. http://hdl.handle.net/2142/71214 (UMI)AAI8409843 Mathematics On Weak Number Theories text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.