[Zurück]


Zeitschriftenartikel:

A. Beckmann, S Buss, C Pollett:
"Ordinal Notations and Well-Orderings in Bounded Arithmetic";
Annals of Pure and Applied Logic, 120 (2003), S. 197 - 222.



Kurzfassung deutsch:
In diesem Artikel werden
Wohlordnungen und spezielle Notationen dafuer bezueglich ihrer
Eigenschaften in schwachen Fragmenten der Arithmetik (Bounded
Arithmetic) hin untersucht. Diese treten natuerlich in der
Ordinalzahlanalyse von mathematischen Theorien auf, konkret
werden hier neben allgemeinen Ueberlegungen auch die schon von G.
Gentzen bestimmte bekannte Ordinalzahl \epsilon_0 der Peano
Arithmetik, als auch die Ordinalzahl \Gamma_0 (Grenze der
Praedikativitaet) studiert. Das Herz dieser Arbeit sind
polynomial-Zeit Algorithmen, die diese Ordinalzahlnotationen auf
endlichen Domains ordnungstreu in die natuerliche Ordnung <
einbetten. Also Konsequenz wird gezeigt, das gewisse Suchklassen
(PLS - polynomial local search) sich auf Suchklassen
verallgemeinern lassen, die nun lokale Minima bezueglich solchen
Ordinalzahlnotationen suchen, ohne an Staerke zu gewinnen.

Kurzfassung englisch:
Ordinal notations and provability of well-foundedness have been a
central tool in the study of the consistency strength and
computational strength of formal theories of arithmetic. This
development began with Gentzen's consistency proof for Peano
arithmetic based on the well-foundedness of ordinal notations up
to $\epsilon_0$. Since the work of Gentzen, ordinal notations and
provable well-foundedness have been studied extensively for many
other formal systems, some stronger and some weaker than Peano
arithmetic. In the present paper, we investigate the provability
and non-provability of well-foundedness of ordinal notations in
very weak theories of bounded arithmetic, notably the theories
$S^i_2$ and $T^i_2$ with $1\le i \le 2$. We prove several results
about the provability of well-foundedness for ordinal notations;
our main results state that for the usual ordinal notations for
ordinals below $\epsilon_0$ and $\Gamma_0$, the theories $T^1_2$
and $S^2_2$ can prove the ordinal $\Sigma^b_1$-minimization
principle over a bounded domain. PLS is the class of functions
computed by a polynomial local search to minimize a cost
function. It is a corollary of our theorems that the cost
function can be allowed to take on ordinal values
below~$\Gamma_0$, without increasing the class PLS.


Online-Bibliotheks-Katalog der TU Wien:
http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404634


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.