Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε 0 -recursive function [] 0 : T → ω so that a reduces to b implies [a] $_0 > [b]_0$ . The construction of [] 0 is based on a careful analysis of the Howard-Schütte (...) treatment of Gödel's T and utilizes the collapsing function ψ: ε 0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [] 0 is also crucially based on ideas developed in the 1995 paper "A proof of strongly uniform termination for Gödel's T by the method of local predicativity" by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper. Indeed, for given n let T n be the subsystem of T in which the recursors have type level less than or equal to n+2. (By definition, case distinction functionals for every type are also contained in T n .) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the T n -derivation lengths in terms of ω n+2 -descent recursive functions. The derivation lengths of type one functionals from T n (hence also their computational complexities) are classified optimally in terms of $ -descent recursive functions. In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T 0 is primitive recursive, thus any type one functional a in T 0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T 1 in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the IΣ n+1 -provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO ( $\varepsilon_0) \vdash \Pi^0_2$ - Refl(PA) and PRA + PRWO ( $\omega_{n+2}) \vdash \Pi^0_2$ - Refl(I Σ n+1 ), hence PRA + PRWO( $\epsilon_0) \vdash$ Con(PA) and PRA + PRWO( $\omega_{n+2}) \vdash$ Con(IΣ n+1 ). For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity. (shrink)

Inspired by Pohlers' proof-theoretic analysis of KPω we give a straightforward non-metamathematical proof of the (well-known) classification of the provably total functions of $PA, PA + TI(\prec\lceil)$ (where it is assumed that the well-ordering $\prec$ has some reasonable closure properties) and KPω. Our method relies on a new approach to subrecursion due to Buchholz, Cichon and the author.

We survey a selection of results about majorization hierarchies. The main focus is on classical and recent results about the comparison between the slow and fast growing hierarchies.

This book provides a comprehensive account of Kant’s development from the 1755/56 metaphysics to the cosmological antinomy of 1781. With the Theory of the Heavens (1755) and the Physical Monadology (1756), the young Kant had presented an ambitious approach to physical cosmology based on an atomistic theory of matter, which contributed to the foundations of an all-encompassing system of metaphysics. Why did he abandon this system in favor of his critical view that cosmology runs into an antinomy, according to the (...) Critique of Pure Reason (CPR)? This book answers this question by focusing on Kant’s methodology and the internal problems of his 1755/56 theory of nature. A decisive role for Kant’s critical turn plays the argument from incongruent counterparts (1768), which drew much attention among philosophers of science, though not sufficiently in Kant research. Furthermore, the book analyses the genesis of the cosmological antinomy in the 1770s, the logical structure of the antinomy in the CPR, its relation to transcendental idealism, as explained in the “experiment of pure reason” (1787), and its role for the teleology of human reason. The book is addressed to Kant scholars, philosophers of science, and students of Kant’s philosophy. (shrink)

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Godel's system T of primitive recursive functionals of finite types by constructing an $\varepsilon_0$-recursive function [ ]$_0$: T $\rightarrow \omega$ so that a reduces to b implies [a]$_0 > [b]_0$. The construction of [ ]$_0$ is based on a careful analysis of the Howard-Schutte treatment of Godel's T and (...) utilizes the collapsing function $\psi: \varepsilon_0 \rightarrow \omega$ which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of []$_0$ is also crucially based on ideas developed in the 1995 paper "A proof of strongly uniform termination for Godel's T by the method of local predicativity" by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper. Indeed, for given n let T$_n$ be the subsystem of T in which the recursors have type level less than or equal to n+2. As a corollary of the main theorem of this paper we obtain optimal bounds for the T$_n$-derivation lengths in terms of $\omega_{n+2}$-descent recursive functions. The derivation lengths of type one functionals from T$_n$ are classified optimally in terms of $< \omega_{n+2}$-descent recursive functions. In particular we obtain that the derivation lengths function of a type one functional a $\in T_0$ is primitive recursive, thus any type one functional a in T$_0$ defines a primitive recursive function. Similarly we also obtain a full classification of T$_1$ in terms of multiple recursion. As proof-theoretic corollaries we reobtain the classification of the I$\Sigma_{n+1}$-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Godel's T we reobtain additionally that PRA + PRWO \vdash \Pi^0_2$ - Refl and PRA + PRWO \vdash \Pi^0_2$ - Refl, hence PRA + PRWO \vdash$ Con and PRA + PRWO \vdash$ Con$. For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity. (shrink)

Let $R$ be a (finite) rewrite system over a (finite) signature. Let $\succ$ be a strict well-founded termination ordering on the set of terms in question so that the rules of $R$ are reducing under $\succ$ . Then $R$ is terminating. In this article it is proved for a certain class of far reaching termination orderings (of order type reaching up to the first subrecursively inaccessible ordinal, i.e. the proof-theoretic ordinal of $ID_{<\omega}$ ) that – under some reasonable assumptions which (...) are met in current applications – the derivation lengths function for $R$ is bounded by a function from the slow growing hierarchy of level determined by the order type of the underlying termination ordering. This result is a (correction of the proof of and a) strong generalization of theorem 8.1 in Cichon's article Termination orderings and complexity characterisations. Leeds, Proof Theory 1990, (Aczel, Simmons, and Wainer, editors), Cambridge University Press 1992, 171-193. (shrink)

The slow growing hierarchy is commonly defined as follows: G0 = 0, Gx−1 := Gx + 1 and Gλ := Gλ[x] where λ<0 is a limit and ·[·]:0∩ Lim × ω → 0 is a given assignment of fundamental sequences for the limits below 0. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and (...) easy to prove that for the standard assignment of fundamental sequence the hierarchy x<0 is slow growing, i.e. each Gx is majorized by a Kalmar elementary recursive function.It is shown in this paper that the slow growing hierarchy x<0 — when it is defined with respect to the norm-based assignment of fundamental sequences which is defined in the article by Cichon — is actually fast growing, i.e. each PA-provably recursive function is eventually dominated by Gx for some α<0. The exact classification of this hierarchy, i.e. the problem whether it is slow or fast growing, has been unsolved since 1992. The somewhat unexpected result of this paper shows that the slow growing hierarchy is extremely sensitive with respect to the choice of the underlying system of fundamental sequences.The paper is essentially self-contained. Only little knowledge about ordinals less than 0 — like the existence of Cantor normal forms, etc. and the beginnings of subrecursive hierarchy theory as presented, for example, in the 1984 textbook of Rose — is assumed. (shrink)

This article provides a detailed comparison between two systems of collapsing functions. These functions play a crucial role in proof theory, in the analysis of patterns of resemblance, and the analysis of maximal order types of well partial orders. The exact correspondence given here serves as a starting point for far reaching extensions of current results on patterns and well partial orders. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

We introduce strong Goodstein principles which are true but unprovable in strong impredicative theories like IDn.

Let T be the standard Veblen 1908 ordinal notation system for Γ0 as defined, for example, in Schütte's 1977 textbook [13] on Proof Theory. We define a slight modification of the standard assignment of fundamental sequences for the limit ordinals in T and prove that Γ0 is subrecursively inaccessible for this assignment, i.e. the induced slow and fast growing hierarchy match up at Γ0 for the first time.The results of this paper also indicate that φε00 may be considered as a (...) new slow growing ordinal of PA in the sense that the induced slow growing hierarchy up to φε00 classifies the PA-provablyrecursive functions.We show how the results of this paper can be used to bui d a subrecursive hierarchyover the predicative ordinals in the spirit of Wainer's 1970 abstract [16 ]. (shrink)

In this article we define a new and transparent concept of total collapsing functions for an ordinal notation system which is characteristic for the theory (Δ 2 1 -CA)+(BI). We show that our construction allows the application of Pohler's method of local predicativity as presented in [2] which yields a perspicious proof-theoretic analysis of (Δ 2 1 -CA)+(BI) being not much more complicated than for ID1.

This book, first published in 2000, offers translations of the initial critical reactions to Kant's philosophy. Also included is a selection of writings by Kant's contemporaries who took on the task of defending the critical philosophy against early attacks. The first aim of this collection is to show in detail how Kant was understood and misunderstood by his contemporaries. The second aim is to reveal the sorts of arguments that Kant and his first disciples mounted in their defense of the (...) theoretical philosophy. The third aim of the book is to contribute to an understanding of the development of Kant's critical philosophy after its initial formulation in the Critique of Pure Reason, and in particular why Kant made the changes he did in the second edition of the work in 1787. This collection, which includes a glossary of key terms and biographical sketches of the critics on both sides of the debate, is a major addition to Kant scholarship and should be seen as a companion volume to the Cambridge Edition of the Works of Immanuel Kant. (shrink)

Selbstgerechtes Wohlwollen in der Psychoanalyse - J. Körner: Mitleid. Das Ende der Empathie - II. Moral und das Böse - P. Stoellger: Lesarten des Bösen - R. Bittner: Verwüstung durch Moral? - III. Moral als Gewalt?

Walter Benjamin, der Traum und das Bild des Weiblichen Geschichtsphilosophie aus gendertheoretischer Perspektive. 0Karin Stögner: 0Beschädigtes Leben und antisemitische „Schiefheilung". Freud und Adorno revisited.0Ljiljana Radonic: 0Autonomie versus Engagement? Über Adorno und Brecht. 0Gerhard Scheit: 0„Une promesse de bonheur". Herbert Marcuses „Über den affirmativen Charakter der Kultur".0Daniela Berner und Florian Wagner: 0Gebrochene Geschichte, Bedrängte Gegenwart. Möglichkeiten und Grenzen eines fremdgestellten Blicks 0auf die nationalsozialistische Vergangenheit im Film. 0Tobias Ebbrecht-Hartmann: 0Das drastische Medium. Über Adornos Kritik des Films. 0Christoph Hesse: 0Träumerinnen im Wachen. (...) Die „Kollektivträume" der Comics und die Kritische Theorie. 0Barbara Eder : 0Verehrte Unsichtbare!"0Über die Kunst des Hörens bei Walter Benjamin und Theodor W. Adorno 0Christine Ehardt: 0Exkursion 0Shopping Mall, mit Walter Benjamin u.a. 0Anette Baldauf : 0Zum Einbruch des.Realen' in die Gegenwart 0Eingedenken, Erinnern, Katharsis 0Sara Vorwalder und Veronika Zangl : 0„Alles wirklich Brauchbare besteht in Aushilfen". Zwei Lektüren zu Oskar Negt und Alexander Kluges Geschichte und Eigensinn 0Valentin Mertes und Michael Paninski : 0„Die Nord-West-Passage der Revolution" 0Herrschaftsverhältnisse und die situationistische Kartographierung 0der Stadtlandschaft 0Brigitte Marschall: 0. (shrink)

Die Arbeit untersucht die auflagenstärkste und international bekannteste deutsche Zeitung des 18. Jahrhunderts, die "Staats- und Gelehrte Zeitung des Hamburgischen unpartheyischen Correspondenten", mit dem Ziel, ihre Rolle als Instrument der Aufklärung zu analysieren. Basis der Studie sind als regelmäßige Stichprobe die Jahrgänge 1731, 1741,..., 1781. Auf einen ersten Teil, der sich mit der Unternehmensgeschichte der Zeitung, ihrer Konzeption sowie den Prinzipien der 'unpartheylichen' Nachrichtenmeldung in der politischen Berichterstattung und der 'unpartheylichen' Kritik in den Rezensionen des "Hamburgischen Correspondenten" beschäftigt, folgt ein (...) zweiter inhaltsanalytischer Teil. Dort liegt das Interesse nicht primär auf der Rezeption bestimmter Ereignisse oder Schriften, die von der Forschung als 'Meilensteine' der Aufklärungsbewegung ausgemacht wurden. Vielmehr werden in fünf zentralen Themenbereichen (Wissenschaftsverständnis, Literaturkritik, Rezeption staatswissenschaftlicher und ökonomischer Theorieelemente, bürgerliches Selbstverständnis, Frauenbild) für die Aufklärung typische Argumentationsmuster und Werte nachgewiesen, die den Zeitungslesern durch wiederholte Lektüre so vertraut werden mußten, daß sie ihre Weltanschauung im Sinne der Aufklärung beeinflussen konnten. (shrink)

Does incommensurability threaten the realist’s claim that physical magnitudes express properties of natural kinds? Some clarification comes from measurement theory and scientific practice. The standard theory of measurement is metaphysically neutral. But its representational operational and axiomatic aspects give rise to several kinds of a one-sided metaphysics. In scientific practice. the scales of physical quantities are indeed constructed from measuring methods which have incompatible axiomatic foundations. They cover concepts which belong to incomensurable theories. I argue, however, that the construction of (...) such scales conmmits us to a modest version of scientific realism. (shrink)

It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for $\Gamma_0$. Let T be the set-theoretic ordinal notation system for $\Gamma_0$ and $T^{tree}$ the tree ordinal representation for $\Gamma$. It is shown in this paper that $_{\alpha \in T}$ matches up with the class of functions which are elementary (...) recursive in the Ackermann function as does $_{\alpha \in T^{tree}}$. By thinning out terms in which the addition function symbol occurs we single out subsystems $T* \subseteq T$ and $T^{tree*} \subseteq T^{tree}$ and prove that $_{\alpha \in T^{tree*}}$ still matches up with $_{\alpha \in T^{tree}}$ but $_{\alpha \in T*}$ now consists of elementary recursive functions only. We discuss the relationship between these results and the $\Gamma_0$-based termination proof for the standard rewrite system for the Ackermann function. (shrink)

This is the first day of our confinement here in Paris, which soon will feel a bit like house arrest. So, to help cheer you up, in these times of doom and gloom, I have decided to bring the museum to you in the form of a virtual exhibition thrice weekly. I have picked 25 photos from a work in progress I started years ago. The photos are portraits of visitors or guards in museums. It's candid photography, capturing life on (...) the run, a moment in time. I hope you will find many other ways to - Résidence numérique - Brigitte Cavanagh. (shrink)

La Renaissance commence vraiment avec Pléthon, contemporain de Nicolas de Cues et qui se voulait comme lui romain, mais du point de vue de Constantinople. Pléthon a conçu le modèle d'une constitution qui permettrait à tous les peuples de coexister en paix. Au temps où l'Occident latin est largement aristotélicien, il plaide pour le retour à Platon, l'idéalisme, la théologie affirmative.

This paper is intended to give for a general mathematical audience a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality and renormalization issues (...) in this context. Finally, we indicate how regularity properties of ordinal count functions can be used to prove logical limit laws. (shrink)

For α less than ε0 let $N\alpha$ be the number of occurrences of ω in the Cantor normal form of α. Further let $\mid n \mid$ denote the binary length of a natural number n, let $\mid n\mid_h$ denote the h-times iterated binary length of n and let inv(n) be the least h such that $\mid n\mid_h \leq 2$ . We show that for any natural number h first order Peano arithmetic, PA, does not prove the following sentence: For all (...) K there exists an M which bounds the lengths n of all strictly descending sequences $\langle \alpha_0, ..., \alpha_n\rangle$ of ordinals less than ε0 which satisfy the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid \cdot \mid i\mid_h$ . As a supplement to this (refined Friedman style) independence result we further show that e.g., primitive recursive arithmetic, PRA, proves that for all K there is an M which bounds the length n of any strictly descending sequence $\langle \alpha_0,..., \alpha_n\rangle$ of ordinals less than ε0 which satisfies the condition that the Norm $N\alpha_i$ of the i-th term αi is bounded by $K + \mid i \mid\cdot inv(i)$ . The proofs are based on results from proof theory and techniques from asymptotic analysis of Polya-style enumerations. Using results from Otter and from Matou $\breve$ ek and Loebl we obtain similar characterizations for finite bad sequences of finite trees in terms of Otter's tree constant 2.9557652856... (shrink)

Let $\Omega:= \aleph_1$ . For any $\alpha \Omega:\xi = \omega^\xi\}$ let EΩ (α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let $\alpha^\ast:= \max (E_\Omega(\alpha) \cup \{0\})$ . A function f: εΩ + 1 → Ω is called essentially increasing, if for any $\alpha < \varepsilon_{\Omega + 1}; f(\alpha) \geq \alpha^\ast: f$ is called essentially monotonic, if for any $\alpha,\beta < \varepsilon_{\Omega + (...) 1}$; $\alpha \leq \beta \wedge \alpha^\ast \leq \beta^\ast \Rightarrow f(\alpha) \leq f(\beta).$ Let Clf(0) be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions: (a) $\alpha,\beta \epsilon \mathrm{Cl}_f(0) \Rightarrow \omega^\alpha + \beta \epsilon \mathrm{Cl}_f(0)$ , (b) $E_\Omega\alpha \subseteq \mathrm{Cl}_f(0) \Rightarrow f(\alpha) \epsilon \mathrm{Cl}_f(0)$ . Let ϑεΩ + 1 be the Howard-Bachmann ordinal, which is, for example, defined in [3]. The following theorem is shown: If f:εΩ + 1 → Ω is essentially monotonic and essentially increasing, then the order type of Clf(0) is less than or equal to ϑεΩ + 1. (shrink)

In this paper we calibrate the exact proof-theoretic strength of Kruskal's theorem, thereby giving, in some sense, the most elementary proof of Kruskal's theorem. Furthermore, these investigations give rise to ordinal analyses of restricted bar induction.

Adam Smith's metaphor of the "invisible hand" and its analogue in classical physics are investigated in detail. Smith's analogue was the mechanics of the solar system. What makes the analogy fail are not the idealisations in the caricature-like model of the rational economic man . The main problem rather is that the metaphor does not employ the correct analogue, which belongs to thermodynamics and statistics. In the simplest macro-economic model, the business cycle has the same formal structure as the heat (...) flow between two heat reservoirs and a business cycle of growing efficiency works like a refrigerator: it pumps money from the poor to the rich. More complicated models do not give a friendlier image. Due to technological push, an economic system behaves like a thermodynamic system far from the equilibrium, showing chaotic behaviour and developing into unpredictable states. (shrink)

The termination of rewrite systems for parameter recursion, simple nested recursion and unnested multiple recursion is shown by using monotone interpretations both on the ordinals below the first primitive recursively closed ordinal and on the natural numbers. We show that the resulting derivation lengths are primitive recursive. As a corollary we obtain transparent and illuminating proofs of the facts that the schemata of parameter recursion, simple nested recursion and unnested multiple recursion lead from primitive recursive functions to primitive recursive functions.

We classify the phase transition thresholds from provability to unprovability for certain Friedman-style miniaturizations of Kruskal's Theorem and Higman's Lemma. In addition we prove a new and unexpected phase transition result for ε0. Motivated by renormalization and universality issues from statistical physics we finally state a universality hypothesis.

In this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number-theoretic functions and we show the equivalence of the new approach with the classical one.