Anton Freund
YOU?
Author Swipe
View article: REVERSE MATHEMATICS OF A UNIFORM KRUSKAL–FRIEDMAN THEOREM
REVERSE MATHEMATICS OF A UNIFORM KRUSKAL–FRIEDMAN THEOREM Open
The Kruskal–Friedman theorem asserts: in any infinite sequence of finite trees with ordinal labels, some tree can be embedded into a later one, by an embedding that respects a certain gap condition. This strengthening of the original Krusk…
View article: Induction on Dilators and Bachmann-Howard Fixed Points
Induction on Dilators and Bachmann-Howard Fixed Points Open
One of the most important principles of J.-Y. Girard's $Π^1_2$-logic is induction on dilators. In particular, Girard used this principle to construct his famous functor $Λ$. He claimed that the totality of $Λ$ is equivalent to the set exis…
View article: More conservativity for weak Kőnig's lemma
More conservativity for weak Kőnig's lemma Open
We prove conservativity results for weak Kőnig's lemma that extend the celebrated result of Harrington (for $Π^1_1$-statements) and are somewhat orthogonal to the extension by Simpson, Tanaka and Yamazaki (for statements of the form $\fora…
View article: Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I
Fraïssé's conjecture, partial impredicativity and well-ordering principles, part I Open
Fraïssé's conjecture (proved by Laver) is implied by the $Π^1_1$-comprehension axiom of reverse mathematics, as shown by Montalbán. The implication must be strict for reasons of quantifier complexity, but it seems that no better bound has …
View article: Dilators and the reverse mathematics zoo
Dilators and the reverse mathematics zoo Open
A predilator is a particularly uniform transformation of linear orders. We have a dilator when the transformation preserves well-foundedness. Over the theory $\mathsf{ACA}_0$ from reverse mathematics, any $Π^1_2$-formula is equivalent to t…
View article: What is effective transfinite recursion in reverse mathematics?
What is effective transfinite recursion in reverse mathematics? Open
In the context of reverse mathematics, effective transfinite recursion refers to a principle that allows us to construct sequences of sets by recursion along arbitrary well orders, provided that each set is Δ¹₀‐definable relative to the pr…
View article: An Introduction to Mathematical Logic
An Introduction to Mathematical Logic Open
This introduction begins with a section on fundamental notions of mathematical logic, including propositional logic, predicate or first-order logic, completeness, compactness, the Löwenheim-Skolem theorem, Craig interpolation, Beth's defin…
View article: Well ordering principles for iterated $$\Pi ^1_1$$-comprehension
Well ordering principles for iterated $$\Pi ^1_1$$-comprehension Open
We introduce ordinal collapsing principles that are inspired by proof theory but have a set theoretic flavor. These principles are shown to be equivalent to iterated $$\Pi ^1_1$$ -comprehension and the existence of admissible sets, ov…
View article: WEAK WELL ORDERS AND FRAÏSSÉ’S CONJECTURE
WEAK WELL ORDERS AND FRAÏSSÉ’S CONJECTURE Open
The notion of countable well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with…
View article: Provable better quasi orders
Provable better quasi orders Open
It has recently been shown that fairly strong axiom systems such as $\mathsf{ACA}_0$ cannot prove that the antichain with three elements is a better quasi order ($\mathsf{bqo}$). In the present paper, we give a complete characterization of…
View article: Weak well orders and Fraïssé's conjecture
Weak well orders and Fraïssé's conjecture Open
The notion of well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with Fraïssé's…
View article: The logical strength of minimal bad arrays
The logical strength of minimal bad arrays Open
This paper studies logical aspects of the notion of better quasi order, which has been introduced by C. Nash-Williams (Mathematical Proceedings of the Cambridge Philosophical Society 1965 & 1968). A central tool in the theory of better qua…
View article: Bachmann–Howard derivatives
Bachmann–Howard derivatives Open
It is generally accepted that H. Friedman’s gap condition is closely related to iterated collapsing functions from ordinal analysis. But what precisely is the connection? We offer the following answer: In a previous paper we have shown tha…
View article: Normal functions and maximal order types
Normal functions and maximal order types Open
Transformations of well partial orders induce functions on the ordinals, via the notion of maximal order type. In most examples from the literature, these functions are not normal, in marked contrast with the central role that normal funct…
View article: The uniform Kruskal theorem: between finite combinatorics and strong set existence
The uniform Kruskal theorem: between finite combinatorics and strong set existence Open
The uniform Kruskal theorem extends the original result for trees to general recursive data types. As shown by A. Freund, M. Rathjen and A. Weiermann, it is equivalent to $Π^1_1$-comprehension, over $\mathsf{RCA_0}$ with the chain antichai…
View article: On the logical strength of the better quasi order with three elements
On the logical strength of the better quasi order with three elements Open
The notion of better quasi order ($\mathsf{BQO}$), due to Nash-Williams, is very fruitful mathematically and intriguing from the standpoint of logic, due to several long-standing open problems. In the present paper, we make a significant s…
View article: Higman's lemma is stronger for better quasi orders
Higman's lemma is stronger for better quasi orders Open
We prove that Higman's lemma is strictly stronger for better quasi orders than for well quasi orders, within the framework of reverse mathematics. In fact, we show a stronger result: the infinite Ramsey theorem (for tuples of all lengths) …
View article: Impredicativity and Trees with Gap Condition: A Second Course on Ordinal Analysis
Impredicativity and Trees with Gap Condition: A Second Course on Ordinal Analysis Open
These lecture notes introduce central notions of impredicative ordinal analysis, such as the Bachmann-Howard ordinal and the method of collapsing, which transforms uncountable proof trees into countable ones. Specifically, we analyze param…
View article: R.E. Bruck, proof mining and a rate of asymptotic regularity for ergodic averages in Banach spaces
R.E. Bruck, proof mining and a rate of asymptotic regularity for ergodic averages in Banach spaces Open
We analyze a proof of Bruck to obtain an explicit rate of asymptotic regularity for Cesàro means in uniformly convex Banach spaces. Our rate will only depend on a norm bound and a modulus $η$ of uniform convexity. One ingredient for the pr…
View article: Bounds for a nonlinear ergodic theorem for Banach spaces
Bounds for a nonlinear ergodic theorem for Banach spaces Open
We extract quantitative information (specifically, a rate of metastability in the sense of Terence Tao) from a proof due to Kazuo Kobayasi and Isao Miyadera, which shows strong convergence for Cesàro means of non-expansive maps on Banach s…
View article: R.E. Bruck, proof mining and a rate of asymptotic regularity for ergodic averages in Banach spaces
R.E. Bruck, proof mining and a rate of asymptotic regularity for ergodic averages in Banach spaces Open
We analyze a proof of Bruck to obtain an explicit rate of asymptotic regularity for Cesàro means in uniformly convex Banach spaces.Our rate only depends on a norm bound and a modulus η of uniform convexity.One ingredient for the proof by B…
View article: Reverse mathematics of a uniform Kruskal-Friedman theorem
Reverse mathematics of a uniform Kruskal-Friedman theorem Open
The Kruskal-Friedman theorem asserts: in any infinite sequence of finite trees with ordinal labels, some tree can be embedded into a later one, by an embedding that respects a certain gap condition. This strengthening of the original Krusk…
View article: Well ordering principles for iterated $Π^1_1$-comprehension
Well ordering principles for iterated $Π^1_1$-comprehension Open
We introduce ordinal collapsing principles that are inspired by proof theory but have a set theoretic flavor. These principles are shown to be equivalent to iterated $Π^1_1$-comprehension and the existence of admissible sets, over weak bas…
View article: Ackermann and Goodstein go functorial
Ackermann and Goodstein go functorial Open
We present variants of Goodstein's theorem that are equivalent to arithmetical comprehension and to arithmetical transfinite recursion, respectively, over a weak base theory. These variants differ from the usual Goodstein theorem in that t…
View article: Unprovability in Mathematics: A First Course on Ordinal Analysis
Unprovability in Mathematics: A First Course on Ordinal Analysis Open
These are the lecture notes of an introductory course on ordinal analysis. Our selection of topics is guided by the aim to give a complete and direct proof of a mathematical independence result: Kruskal's theorem for binary trees is unprov…
View article: A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH
A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH Open
We present a new manifestation of Gödel’s second incompleteness theorem and discuss its foundational significance, in particular with respect to Hilbert’s program. Specifically, we consider a proper extension of Peano arithmetic ( $\mathbf…
View article: Bachmann-Howard Derivatives
Bachmann-Howard Derivatives Open
It is generally accepted that H. Friedman's gap condition is closely related to iterated collapsing functions from ordinal analysis. But what precisely is the connection? We offer the following answer: In a previous paper we have shown tha…
View article: A note on ordinal exponentiation and derivatives of normal functions
A note on ordinal exponentiation and derivatives of normal functions Open
Michael Rathjen and the present author have shown that ‐bar induction is equivalent to (a suitable formalization of) the statement that every normal function has a derivative, provably in . In this note we show that the base theory can be …