Search

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, ) 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 over RCA. To state these theorems in RCA we introduce a new framework for dealing with second-countable topological spaces. [ABSTRACT FROM AUTHOR]

In (Fund Math 60:175-186 ), Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk's original result actually shows that every wpo has a strongly maximal chain, which we define below. We show that a set computes strongly maximal chains in all computable wpo if and only if it computes all hyperarithmetic sets. [ABSTRACT FROM AUTHOR]

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA to ATR. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR over RCA. [ABSTRACT FROM AUTHOR]

Abstract. We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement "every compact space is Lebesgue" is equivalent to WKL[sub 0]; the statements "every perfect Lebesgue space is compact" and "every perfect Atsuji space is compact" are equivalent to AGA[sub 0]; the statement "every Lebesgue space is Atsuji" is provable in FICA[sub 0]; the statement "every Atsuji space is Lebesgue" is provable in ACA[sub 0]. We also prove that the statement "the distance from a closed set is a continuous function" is equivalent to PI[sup 1, sub 1]-GA[sub 0]. [ABSTRACT FROM AUTHOR]