IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Combinatorial principles in second-order theories of bounded arithmetic

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/20320

Files in this item

File Description Format
PDF 9236438.pdf (3MB) Restricted to U of Illinois (no description provided) PDF
Title: Combinatorial principles in second-order 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 Urbana-Champaign
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: 2011-05-07
Identifier in Online Catalog: AAI9236438
OCLC Identifier: (UMI)AAI9236438
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 0
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key