We study the reverse mathematics of interval orders. We establish the logical strength of the implications among various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain 2 \oplus 2. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it (...) contains neither 2 \oplus 2 nor 3 \oplus 1. (shrink)

In this article we provide an intrinsic characterization of the famous Howard–Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face Π11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi ^1_1$$\end{document}-comprehension.

We present a list of open questions in reverse mathematics, including some relevant background information for each question. We also mention some of the areas of reverse mathematics that are starting to be developed and where interesting open question may be found.

We propose a new method for constructing Turing ideals satisfying principles of reverse mathematics below the Chain–Antichain (CAC) Principle. Using this method, we are able to prove several new separations in the presence of Weak König’s Lemma (WKL), including showing that CAC+WKL does not imply the thin set theorem for pairs, and that the principle “the product of well-quasi-orders is a well-quasi-order” is strictly between CAC and the Ascending/Descending Sequences principle, even in the presence of WKL.

We prove Fraïssé’s conjecture within the system of Π11-comprehension. Furthermore, we prove that Fraïssé’s conjecture follows from the Δ20-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the Δ20-bqo-ness of 3 is a Π21-statement strictly weaker than Π11-comprehension.

A quasi-order Q induces two natural quasi-orders on $${\mathcal{P}(Q)}$$, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on $${\mathcal{P}(Q)}$$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on $${\mathcal{P}(Q)}$$ are Noetherian, which means that they contain no (...) infinite strictly descending sequences of closed sets. We analyze various theorems of the form “if Q is a well-quasi-order then a certain topology on (a subset of) $${\mathcal{P}(Q)}$$ is Noetherian” in the style of reverse mathematics, proving that these theorems are equivalent to ACA 0 over RCA 0. To state these theorems in RCA 0 we introduce a new framework for dealing with second-countable topological spaces. (shrink)

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ2, the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in +“φ2 is well-ordered” and, over , implies +“φ2 is well-ordered”.

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.

In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We (...) show that the left to right directions of these theorems are equivalent to ACA0 and ATR0, respectively. On the other hand, the opposite directions are both provable in WKL0, but not in RCA0. We also prove the equivalence with ACA0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains. (shrink)