- IDEALS Home
- Graduate Theses and Dissertations at Illinois
- Graduate Theses and Dissertations at Illinois
- View Item
Combinatorial principles in second-order theories of bounded arithmetic
Bookmark or cite this item:
http://hdl.handle.net/2142/20320
Files in this item
| File | Description | Format |
|---|---|---|
9236438.pdf
(3MB)
|
(no description provided) |
| 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 |
Items in IDEALS are protected by copyright, with all rights reserved, unless otherwise indicated.
This item appears in the following Collection(s)
-
Graduate Theses and Dissertations at Illinois
Graduate Theses and Dissertations at Illinois -
Dissertations and Theses - Mathematics
Item Statistics
- Total Downloads: 0
- Downloads this Month: 0
- Downloads Today: 0
