Files in this item
Files  Description  Format 

application/pdf 9236438.pdf (3MB)  (no description provided) 
Description
Title:  Combinatorial principles in secondorder theories of bounded arithmetic 
Author(s):  De Castro, Rodrigo 
Doctoral Committee Chair(s):  Jockusch, Carl G., Jr. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics 
Abstract:  An attempt is made to study the mathematical strength of the weak second order theories of Bounded Arithmetic U$\sbsp{2}{i}$ and V$\sbsp{2}{i}$, i $\geq$ 0, introduced by S. Buss. It is first shown that U$\sbsp{2}{1}$ can $\Sigma\sbsp{1}{1,b}$define the functions in the second class of Grzegorczyk, $\varepsilon\sp2$, or, equivalently, the class of $\Sigma\sbsp{1}{1,b}$definable functions in U$\sbsp{2}{1}$ is closed under bounded recursion. It is shown next that U$\sbsp{2}{1}$ proves the $\Delta\sbsp{1}{1,b}$pigeonhole principle. Two general combinatorial principles, the $\Delta\sbsp{1}{1,b}$partition principle and the $\Delta\sbsp{1}{1,b}$equipartition principle, are obtained from it thereby demonstrating that the $\Delta\sbsp{1}{1,b}$PHP embodies a strong notion of cardinality. The introduction of these principles is motivated with some examples, notably by showing that Euler's theorem is provable in U$\sbsp{2}{1}$. The provability of Euler's theorem in weak first order fragments of Peano Arithmetic is an open problem. A theory of polynomials is developed in U$\sbsp{2}{1}$ and it is proved that U$\sbsp{2}{1}$ + B $\vdash$ "existence of primitive roots" where formula B asserts that a nontrivial polynomial of degree n can have at most n solutions modulo p if p is a prime. By an essential use of the $\Delta\sbsp{1}{1,b}$PHP and the $\Delta\sbsp{1}{1,b}$partition principle it is shown that V$\sbsp{2}{1}\/\vdash$ B, hence V$\sbsp{2}{1}\/\vdash$ "existence of primitive roots". 
Issue Date:  1992 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/20320 
Rights Information:  Copyright 1992 De Castro, Rodrigo 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9236438 
OCLC Identifier:  (UMI)AAI9236438 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics