ISSN:
1432-0665
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Description / Table of Contents:
Zusammenfassung In der vorliegenden Arbeit stellen wir gewisse bis jetzt nicht veröffentlichte Forschungsergebnisse von Harvey Friedman vor. Diese Ergebnisse liefern die eindrucksvollsten bis jetzt gefundenen Beispiele von mathematisch bedeutsamen Sätzen der endlichen Kombinatorik, die in gewissen logischen Systemen nicht beweisbar sind. Die betroffenen logischen SystemeATR 0 und Π 1 1 —CA 0 sind als verhältnismäßig starke Teilsysteme der Arithmetik der zweiten Stufe bekannt. Die nicht beweisbaren kombinatorischen Sätze haben mit Einbettbarkeitseigenschaften endlicher Bäume zu tun. Friedmans Methode gründet sich zum Teil auf eine enge Verbindung zwischen endlichen Bäumen einerseits und den Ordinalzahlbezeichnungssystemen andererseits, die in der an Gentzen anknüpfenden Beweistheorie vorkommen.
Notes:
Abstract In this paper we exposit some as yet unpublished results of Harvey Friedman. These results provide the most dramatic examples so far known of mathematically meaningful theorems of finite combinatorics which are unprovable in certain logical systems. The relevant logical systems,ATR 0 and Π 1 1 —CA 0, are well known as relatively strong fragments of second order arithmetic. The unprovable combinatorial theorems are concerned with embeddability properties of finite trees. Friedman's method is based in part of the existence of a close relationship between finite trees on the one hand, and systems of ordinal notations which occur in Gentzen-style proof theory on the other.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02007556
Permalink