The strength of compactness for countable complete linear orders

Abstract

We investigate the statement “the order topology of every countable complete linear order is compact” in the framework of reverse mathematics, and we find that the statement’s strength depends on the precise formulation of compactness. If we require that open covers must be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ . If open covers need not be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ . This answers a question of François Dorais.

Keywords

Reverse mathematics linear orders order topology

1. Introduction

Every linear order $(L, ≺)$ can be equipped with its order topology, where the basic open sets are the open intervals $\begin{array}{l} (a, \infty) = {x \in L : a ≺ x} for a \in L; \\ (- \infty, b) = {x \in L : x ≺ b} for b \in L; \\ (a, b) = {x \in L : a ≺ x ≺ b} for a, b \in L with a ≺ b . \end{array}$

Call a linear order $(L, ≺)$ complete if whenever L is partitioned as $L = A^{-} \cup A^{+}$ with $\begin{array}{l} (\forall x \in A^{-}) (\forall y \in A^{+}) (x ≺ y), \end{array}$ it is the case that either $A^{-}$ has a greatest element or $A^{+}$ has a least element. It is well-known (see for example [8, Theorem 27.1]) that the order topology of a non-empty linear order is compact if and only if the linear order is complete in the above sense. Our goal is to characterize the logical strength of this fact when restricting to countable linear orders.

This work is an example of reverse mathematics, which is the project of classifying mathematical theorems phrased in second-order arithmetic by the strengths of the axiom systems that are required to prove the theorems. Reverse mathematics was introduced by H. Friedman [3], and the standard reference is Simpson’s [9]. Formally, the only mathematical objects that second-order arithmetic allows are natural numbers and sets of natural numbers. Nevertheless, straightforward coding techniques available in weak background theories allow us to discuss tuples and sequences of natural numbers; functions $f : N^{m} \to N^{n}$ ; countable algebraic or combinatorial objects such as countable groups, rings, fields, graphs, trees, partial orders, linear orders; and more. By coding a real number as a rapidly converging Cauchy sequence of rational numbers and by coding a basic open subset of $R^{n}$ as an $(n + 1)$ -tuple of rational numbers (representing an open ball of rational radius whose center has rational coordinates), we may discuss $R^{n}$ , its topology, continuous functions $f : R^{m} \to R^{n}$ , and so forth. We may even discuss arbitrary complete separable metric spaces by specifying a space’s countable dense set and a metric on that dense set. To date, most work in reverse mathematics involving topology has been confined to complete separable metric spaces. Few attempts have been made to study general topology in second-order arithmetic. One excellent example is Mummert’s and Simpson’s work on filter spaces [6,7]. Here we take up Dorais’s framework of countable second-countable topological spaces [1].

Dorais’s idea is to study general topology in second-order arithmetic by restricting to the topological spaces that can be straightforwardly represented in second-order arithmetic. These are the countable second-countable spaces: the topological spaces with countably many points and with countable bases. The countable second-countable spaces framework of course comes with its own limitations (it is not a good approach to studying connectivity, for example), but it has the advantage of representing topological notions directly, and it works well for analyzing theorems whose proofs largely concern the combinatorics of open sets and closed sets. This framework was used in [4] to analyze topological spaces arising from quasi-orders, for example. Here we study countable linear orders and their order topologies. This could be done in a completely ad hoc manner, as a linear order’s order topology is easy to describe. However, the order topologies of countable linear orders fit very nicely into the countable second-countable spaces framework, as shown by the many examples in [1].

In [1], Dorais considers a notion of compactness in which the open sets of an open cover are explicitly presented as unions of basic open sets. We call this notion compactness with respect to honest open covers. The idea is that a sequence of open sets is honest if it comes with an explanation of how each open set in the sequence can be written as a union of basic open sets. Dorais observes that the base theory ${RCA}_{0}$ proves that if the order topology of a countable linear order is compact with respect to honest open covers, then that linear order is complete (see Lemma 3.12 below). He then asks for the axiomatic strength of the converse, that is, for the strength of the statement “the order topology of every countable complete linear order is compact with respect to honest open covers.” Dorais shows that ${RCA}_{0}$ does not suffice to prove this statement. In fact, he shows that, over ${RCA}_{0}$ , the statement implies that there is no set of maximum Turing degree [1, Example 7.8]. We answer Dorais’s question by showing that the statement “the order topology of every countable complete linear order is compact with respect to honest open covers” is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ .

Dorais also considers a stronger notion of compactness, here simply called compactness, where the open sets of an open cover need not be uniformly presentable as unions of basic open sets [2]. We show that with this notion of compactness, the statement “the order topology of every countable complete linear order is compact” is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .

2. Preliminaries for working in second-order arithmetic

We remind the reader of the axiom systems ${RCA}_{0}$ , ${WKL}_{0}$ , and ${ACA}_{0}$ . Simpson’s [9] provides many more details concerning these and other systems, including many examples of theorems that can be proven in them.

The language of second-order arithmetic contains two sorts of variables: first-order variables intended to range over the natural numbers and second-order variables intended to range over sets of natural numbers. Typically, but not always, lower-case letters a, b, c, x, y, z, etc. denote first-order variables, and capital letters A, B, C, X, Y, Z, etc. denote second-order variables. The symbol $N$ is notational shorthand for the first-order part of whatever structure is implicitly under consideration.

The language of second-order arithmetic contains constant symbols 0 and 1, binary function symbols + and ×, and binary relation symbols =, <, and ∈. The constants 0 and 1 name numbers, and the functions and relations +, ×, =, and < only apply to numbers. The relation ∈ relates numbers to sets, and equality between sets is defined in terms of ∈.

${RCA}_{0}$ (standing for recursive comprehension axiom) is an axiom system designed to capture computable mathematics. Roughly speaking, to prove that some set exists when working in ${RCA}_{0}$ , one must show how to compute that set, possibly using as an oracle some other set that has already been shown to exist. The axioms of ${RCA}_{0}$ consist of

a first-order sentence expressing that the numbers form a discretely ordered commutative semi-ring with identity;

the $Σ_{1}^{0}$ induction scheme (denoted $I Σ_{1}^{0}$ ), which consists of the universal closures (by both number and set quantifiers) of all formulas of the form $\begin{array}{l} [φ (0) \land \forall n (φ (n) \to φ (n + 1))] \to \forall n φ (n), \end{array}$ where φ is $Σ_{1}^{0}$ ; and

the $Δ_{1}^{0}$ comprehension scheme, which consists of the universal closures (by both number and set quantifiers) of all formulas of the form $\begin{array}{l} \forall n (φ (n) \leftrightarrow ψ (n)) \to \exists X \forall n (n \in X \leftrightarrow φ (n)), \end{array}$ where φ is $Σ_{1}^{0}$ , ψ is $Π_{1}^{0}$ , and X is not free in φ.

{RCA}_{0}

is the usual base system or background theory in reverse mathematics. Many theorems in reverse mathematics have the form

{RCA}_{0} ⊢ φ \leftrightarrow ψ

, where φ and ψ are two well-known mathematical statements. If

{RCA}_{0} ⊢ φ \leftrightarrow ψ

, we say that φ and ψ are equivalent over

{RCA}_{0}

, and we interpret this as meaning that φ and ψ have equivalent logical strength. The ‘0’ in ‘

{RCA}_{0}

’ refers to the restriction of the induction scheme to

Σ_{1}^{0}

formulas.

${RCA}_{0}$ proves several induction schemes, least element principles, bounding schemes, and bounded comprehension principles in addition to $I Σ_{1}^{0}$ . Here the relevant schemes are the $Π_{1}^{0}$ induction scheme (denoted $I Π_{1}^{0}$ ), the $Σ_{1}^{0}$ least element principle, the $Σ_{1}^{0}$ bounding scheme (denoted $B Σ_{1}^{0}$ ), and the bounded $Σ_{1}^{0}$ comprehension scheme. The $Π_{1}^{0}$ induction scheme is as the $Σ_{1}^{0}$ induction scheme, but the formula φ is required to be $Π_{1}^{0}$ . The $Σ_{1}^{0}$ least element principle consists of the universal closures of all formulas of the form $\begin{array}{l} \exists n φ (n) \to \exists n [φ (n) \land (\forall m < n) (\neg φ (m))], \end{array}$ where φ is $Σ_{1}^{0}$ . The $Σ_{1}^{0}$ bounding scheme consists of the universal closures of all formulas of the form $\begin{array}{l} \forall a [(\forall n < a) (\exists m) φ (n, m) \to \exists b (\forall n < a) (\exists m < b) φ (n, m)], \end{array}$ where φ is $Σ_{1}^{0}$ and a and b are not free in φ. The $Σ_{1}^{0}$ bounded comprehension scheme consists of the universal closures of all formulas of the form $\begin{array}{l} \forall b \exists X \forall n [n \in X \leftrightarrow (n < b \land φ (n))], \end{array}$ where φ is $Σ_{1}^{0}$ and X is not free in φ. See [5, Section I.2] and [9, Section II.3] for further details.

${RCA}_{0}$ suffices to code a finite set of numbers as a single number and a finite sequence of numbers as a single number in the usual way. In ${RCA}_{0}$ , we can thus code the set $N^{< N}$ of all finite sequences as well as its subset $2^{< N}$ of all finite binary sequences. We now fix our notation and terminology for (coded) sequences. For $σ, τ \in N^{< N}$ , $| σ |$ denotes the length of σ, $σ \subseteq τ$ denotes that σ is an initial segment of τ, and $σ^{⌢} τ$ denotes the concatenation of σ and τ. For $σ \in N^{< N}$ and $n ⩽ | σ |$ , $σ ↾ n = ⟨ σ (0), \dots, σ (n - 1) ⟩$ denotes the initial segment of σ of length n. Likewise, if $f : N \to N$ is a function and $n \in N$ , $f ↾ n = ⟨ f (0), \dots, f (n - 1) ⟩$ denotes the sequence consisting of the first n values of f.

In ${RCA}_{0}$ , we define a tree to be a set $T \subseteq N^{< N}$ that is closed under initial segments: $\forall σ \forall τ [(σ \in T \land τ \subseteq σ) \to τ \in T]$ . A function $f : N \to N$ is an infinite path through a tree T if every initial segment of f is in T: $\forall n (f ↾ n \in T)$ . We can now define weak König’s lemma to be the statement “every infinite subtree of $2^{< N}$ has an infinite path.” The system ${WKL}_{0}$ is obtained by adding weak König’s lemma to the axioms of ${RCA}_{0}$ .

Lastly, the system ${ACA}_{0}$ (standing for arithmetical comprehension axiom) is obtained by augmenting ${RCA}_{0}$ by the arithmetical comprehension scheme, which consists of the universal closures of all formulas of the form $\begin{array}{l} \exists X \forall n (n \in X \leftrightarrow φ (n)), \end{array}$ where φ is an arithmetical formula in which X is not free.

${WKL}_{0}$ is strictly stronger than ${RCA}_{0}$ , and ${ACA}_{0}$ is strictly stronger than ${WKL}_{0}$ (see [9, Remark I.10.2 and Section VIII.2]). A helpful characterization of ${ACA}_{0}$ is that, over ${RCA}_{0}$ , it is equivalent to the statement “every injection has a range.”

Lemma 2.1 ([9, Lemma III.1.3]).

The following are equivalent over ${RCA}_{0}$ .

${ACA}_{0}$ .

If $f : N \to N$ is an injection, then there is a set X such that $\forall n (n \in X \leftrightarrow \exists s (f (s) = n))$ .

Thus to show that some statement implies ${ACA}_{0}$ over ${RCA}_{0}$ , it suffices to show that the statement implies that every injection has a range.

We make use of König’s lemma and bounded König’s lemma in addition to weak König’s lemma. Call a tree $T \subseteq N^{< N}$ finitely-branching if every $σ \in T$ has at most finitely many immediate successors: $(\forall σ \in T) (\exists n) (\forall m) [σ^{⌢} ⟨ m ⟩ \in T \to m < n]$ . Furthermore, call a finitely-branching tree $T \subseteq N^{< N}$ bounded if it comes equipped with a function bounding its branching, i.e., if there is a function $g : N \to N$ such that $(\forall σ \in T) (\forall n < | σ |) [σ (n) < g (n)]$ . König’s lemma is the statement “every infinite finitely-branching subtree of $N^{< N}$ has an infinite path,” and bounded König’s lemma is the statement “every infinite bounded subtree of $N^{< N}$ has an infinite path.”

Theorem 2.2.

König’s lemma is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ (see [ 9 , Theorem III.7.2]).

Bounded König’s lemma is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ (see [ 9 , Lemma IV.1.4]).

3. Countable second-countable topological spaces

We introduce the countable second-countable topological spaces framework from [1].

Definition 3.1 ( ${RCA}_{0}$ ; [1, Definition 2.1]).

A strong base (or simply base) for a topology on a set X is an indexed sequence $U = {(U_{i})}_{i \in I}$ of subsets of X together with a function $k : X \times I \times I \to I$ such that the following properties hold.

If $x \in X$ , then $x \in U_{i}$ for some $i \in I$ .

If $x \in U_{i} \cap U_{j}$ , then $x \in U_{k (x, i, j)} \subseteq U_{i} \cap U_{j}$ .

Definition 3.2 ( ${RCA}_{0}$ ; [1, Definition 2.2]).

A strong countable second-countable space (or simply countable second-countable space) is a triple $(X, U, k)$ where $U = {(U_{i})}_{i \in I}$ and $k : X \times I \times I \to I$ form a base for a topology on the set X.

We have no use for the empty space, so we always assume that a countable second-countable space is non-empty.

Dorais also defines the notion of a weak base for a topology on a set X and the corresponding notion of a weak countable second-countable space [2]. The distinction is that a weak base for a topology on X is a uniformly enumerable sequence of subsets of X rather than a sequence of literal subsets of X. So in a weak base, membership in a basic open set is a $Σ_{1}^{0}$ property, whereas in a strong base, membership in a basic open set is a $Δ_{1}^{0}$ property. It is natural and straightforward to define a strong base for the order topology of a countable linear order in ${RCA}_{0}$ (see Definition 3.11 below), so in this work we need only consider strong bases and strong countable second-countable spaces.

Open subsets of countable second-countable spaces are coded by enumerations of indices of basic open sets. Thus we must first define coded enumerable sets.

Definition 3.3 ( ${RCA}_{0}$ ).

Let $A \subseteq N$ , and let $P_{f} (A)$ denote the set of finite subsets of A.

An enumerable subset of A is coded by a function $h : N \to P_{f} (A)$ , where h codes $A_{h} = ⋃_{n \in N} h (n)$ .

A sequence of uniformly enumerable subsets of A is coded by a function $h : N \times N \to P_{f} (A)$ , where, for each m, $h (m, \cdot)$ codes the mth set in the sequence: $A_{g (m, \cdot)} = ⋃_{n \in N} h (m, n)$ . Denote this sequence by $(A_{h (m, \cdot)} : m \in N)$ .

In general, ${ACA}_{0}$ is required to prove that $A_{h} = ⋃_{n \in N} h (n)$ exists as a set for every $A \subseteq N$ and every $h : N \to P_{f} (A)$ . Thus the expressions ‘ $a \in A_{h}$ ’ and ‘ $a \in ⋃_{n \in N} h (n)$ ’ must be interpreted as abbreviations for the formula ‘ $\exists n (a \in h (n))$ .’ The reason we consider functions $h : N \to P_{f} (A)$ rather than functions $h : N \to A$ is that with functions $h : N \to P_{f} (A)$ , we may easily represent ∅ by the function with constant value ∅.

Definition 3.4 ( ${RCA}_{0}$ ; [1, Definitions 2.3 and 2.4]).

Let $(X, U, k)$ be a countable second-countable space, where $U = {(U_{i})}_{i \in I}$ . An effectively open subset of X is coded by an enumerable subset of I, i.e., by a function $h : N \to P_{f} (I)$ . An $x \in X$ is a member of the effectively open subset of X coded by h if there are an $n \in N$ and an $i \in h (n)$ such that $x \in U_{i}$ . Let $G_{h} = ⋃_{n \in N} ⋃_{i \in h (n)} U_{i}$ denote the open subset of X coded by h.

Again, ${ACA}_{0}$ is required to show that $G_{h}$ exists as a set for every countable second-countable space $(X, U, k)$ and function $h : N \to P_{f} (I)$ . Thus the expression ‘ $x \in G_{h}$ ’ must be interpreted as an abbreviation for the formula ‘ $(\exists n) (\exists i \in h (n)) (x \in U_{i})$ .’

Let $(X, U, k)$ be a countable second-countable space. Every open subset of X is an enumerable subset of X, meaning that for every $h : N \to P_{f} (I)$ , there is an $\hat{h} : N \to P_{f} (X)$ such that $X_{\hat{h}} = G_{h}$ : $\begin{array}{l} \forall x [(\exists n) (x \in \hat{h} (n)) \leftrightarrow (\exists n) (\exists i \in h (n)) (x \in U_{i})] . \end{array}$ Furthermore, we may interpret any double-sequence $h : N \times N \to P_{f} (I)$ as a sequence $(G_{h (m, \cdot)} : m \in N)$ of open sets, where the mth open set in the sequence is $G_{h (m, \cdot)} = ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ . Each such sequence may also be thought of as a uniformly enumerable sequence of subsets of X. That is, there is an $\hat{h} : N \times N \to P_{f} (X)$ such that, for all $m \in N$ , $X_{\hat{h} (m, \cdot)} = G_{h (m, \cdot)}$ . However, there may be sequences $(X_{ℓ (m, \cdot)} : m \in N)$ of uniformly enumerable subsets of X where each individual $X_{ℓ (m, \cdot)}$ is open, but there is no uniform way to code each $X_{ℓ (m, \cdot)}$ as a union of basic open sets. That is, it could be that for every m there is an $h : N \to P_{f} (I)$ such that $X_{ℓ (m, \cdot)} = G_{h}$ , but there is no $h : N \times N \to P_{f} (I)$ such that for every m, $X_{ℓ (m, \cdot)} = G_{h (m, \cdot)}$ . We call a sequence of open subsets of X honest if each set in the sequence is uniformly coded as a union of basic open sets.

Definition 3.5 ( ${RCA}_{0}$ ).

Let $(X, U, k)$ be a countable second-countable space, where $U = {(U_{i})}_{i \in I}$ . A sequence $(X_{ℓ (m, \cdot)} : m \in N)$ of uniformly enumerable subsets of X is an honest sequence of open subsets of X if there is a function $h : N \times N \to P_{f} (I)$ such that for all m, $X_{ℓ (m, \cdot)} = G_{h (m, \cdot)}$ .

Dorais gives two notions of compactness for countable second-countable spaces, corresponding to whether or not we require open covers to be honest. We warn the reader that Dorais’s original definition of compactness [1, Definition 3.1] considers only honest open covers, so the definition of ‘compact’ in [1,4] corresponds to the definition of ‘compact with respect to honest open covers’ here.

Definition 3.6 ( ${RCA}_{0}$ ).

Let $(X, U, k)$ be a countable second-countable space.

A sequence $(X_{h (m, \cdot)} : m \in N)$ of uniformly enumerable subsets of X is an open cover of X if $X_{h (m, \cdot)}$ is an open subset of X for each m and if $X = ⋃_{m \in N} X_{h (m, \cdot)}$ (i.e., $(\forall x \in X) (\exists m) (x \in X_{h (m, \cdot)})$ ).

An open cover $(X_{h (m, \cdot)} : m \in N)$ of X is honest if $(X_{h (m, \cdot)} : m \in N)$ is an honest sequence of open subsets of X.

The space $(X, U, k)$ is compact if for every open cover $(X_{h (m, \cdot)} : m \in N)$ of X there is an $M \in N$ such that $X = ⋃_{m < M} X_{h (m, \cdot)}$ .

The space $(X, U, k)$ is compact with respect to honest open covers if for every honest open cover $(X_{h (m, \cdot)} : m \in N)$ of X there is an $M \in N$ such that $X = ⋃_{m < M} X_{h (m, \cdot)}$ .

In terms of basic open sets, an honest open cover of $(X, U, k)$ is an open cover of the form $X = ⋃_{m \in N} ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ for a function $h : N \times N \to P_{f} (I)$ . Thus $(X, U, k)$ is compact w.r.t. honest open covers if and only if whenever $h : N \times N \to P_{f} (I)$ is such that $X = ⋃_{m \in N} ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ , there is an $M \in N$ such that $X = ⋃_{m < M} ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ . A double-sequence of basic open sets may be rewritten as a single sequence of basic open sets, which means that a countable second-countable space is compact w.r.t. honest open covers if and only if it is compact w.r.t. honest open covers by basic open sets.

Proposition 3.7 ( ${RCA}_{0}$ ).

Let $(X, U, k)$ be a countable second-countable space with $U = {(U_{i})}_{i \in I}$ . Then $(X, U, k)$ is compact w.r.t. honest open covers if and only if for every $g : N \to I$ such that $X = ⋃_{m \in N} U_{g (m)}$ , there is an $M \in N$ such that $X = ⋃_{m < M} U_{g (m)}$ .

Proof.
Every open cover of the form $X = ⋃_{m \in N} U_{g (m)}$ is an honest open cover. So if $(X, U, k)$ is compact w.r.t. honest open covers, then for every $g : N \to I$ such that $X = ⋃_{m \in N} U_{g (m)}$ , there is an $M \in N$ such that $X = ⋃_{m < M} U_{g (m)}$ .

For the converse, suppose that $X = ⋃_{m \in N} ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ for some function $h : N \times N \to P_{f} (I)$ . Fix $m_{0}$ and $n_{0}$ such that $h (m_{0}, n_{0}) \neq \emptyset$ , and fix an $i_{0} \in h (m_{0}, n_{0})$ . For the purposes of this argument, let $⟨ \cdot, \cdot, \cdot ⟩ : N^{3} \to N$ denote a bijection. Define $g : N \to I$ by $\begin{array}{l} g (⟨ m, n, s ⟩) = \{\begin{matrix} the (s + 1) th smallest member of h (m, n) & if | h (m, n) | ⩾ s + 1, \\ i_{0} & otherwise . \end{matrix} \end{array}$ Then $X = ⋃_{p \in N} U_{g (p)}$ , so there is a $P \in N$ such that $X = ⋃_{p < P} U_{g (p)}$ . For every $p < P$ there are m and n such that $g (p) \in h (m, n)$ . By $B Σ_{1}^{0}$ , there is an $M \in N$ such that for every $p < P$ , there are an $m < M$ and an n such that $g (p) \in h (m, n)$ . Therefore $X = ⋃_{m < M} ⋃_{n \in N} ⋃_{i \in h (m, n)} U_{i}$ . □

In light of the above proposition, we typically think of compactness w.r.t. honest open covers in terms of covers of the form $X = ⋃_{m \in N} U_{g (m)}$ for functions $g : N \to I$ . Equivalently, we may also think of compactness w.r.t. honest open covers in terms of covers of the form $X = ⋃_{n \in N} ⋃_{i \in h (n)} U_{i}$ for functions $h : N \to P_{f} (I)$ , as was (implicitly) done in Dorais’s original definition [1, Definition 3.1] and in [4].

When working with compactness in ${RCA}_{0}$ , there is the added wrinkle that it may or may not be possible to uniformly determine whether or not a given finite collection of basic open sets covers the whole space. If it is possible, then we say that the space’s base has a finite cover relation.
Definition 3.8 ( ${RCA}_{0}$ ; [1, Definition 2.13]).

Let $(X, U, k)$ be a countable second-countable space with $U = {(U_{i})}_{i \in I}$ . $U$ has a finite cover relation if there is a set $C \subseteq P_{f} (I)$ such that, for all ${i_{0}, \dots, i_{n - 1}} \subseteq I$ , ${i_{0}, \dots, i_{n - 1}} \in C$ if and only if $X = ⋃_{j < n} U_{i_{j}}$ .

Every honest open cover of a countable second-countable space is also an open cover of the space, so ${RCA}_{0}$ proves that a compact countable second-countable space is also compact w.r.t. honest open covers. Unsurprisingly, ${ACA}_{0}$ is required to prove that every countable second-countable space that is compact w.r.t. honest open covers is compact. This fact follows from [1, Example 5.4], but we find it instructive to present a similar yet somewhat more straightforward proof. It is convenient to first introduce notions of discreteness.

Definition 3.9 ( ${RCA}_{0}$ ; [1, Definition 5.1]).

Let $(X, U, k)$ be a countable second-countable space with $U = {(U_{i})}_{i \in I}$ .

$(X, U, k)$ is discrete if for every $x \in X$ there is an $i \in I$ such that $U_{i} = {x}$ .

$(X, U, k)$ is effectively discrete if there is a function $d : X \to I$ such that, for every $x \in X$ , $U_{d (x)} = {x}$ .

We readily see that an infinite discrete countable second-countable space is not compact and that an infinite effectively discrete countable second-countable space is not compact w.r.t. honest open covers.

Proposition 3.10.
The statement “every countable second-countable space that is compact w.r.t. honest open covers is compact” is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .
Proof.
For the forward direction, when working in ${ACA}_{0}$ it is routine to show that every sequence of open subsets of a countable second-countable space is honest. Thus ${ACA}_{0}$ proves that compactness and compactness w.r.t. honest open covers are equivalent.

For the reverse direction, let $f : N \to N$ be an injection. We appeal to Lemma 2.1 and show that the range of f exists. Define a countable second-countable space $(X, U, k)$ by $X = N$ , $I = {0, 1, 2} \times N$ , and $\begin{array}{l} U_{⟨ 0, n ⟩} = {n} \cup {t : (\exists s ⩽ t) (f (s) = n)} \\ U_{⟨ 1, ⟨ n, s ⟩ ⟩} = \{\begin{matrix} {n} & if f (s) = n, \\ \emptyset & if f (s) \neq n, \end{matrix} \\ U_{⟨ 2, s ⟩} = {t : t ⩾ s} . \end{array}$

The function k is computed as follows. To check that k behaves as intended, it is helpful to observe that if $x \in U_{⟨ 0, n ⟩}$ but $x \neq n$ , then $U_{⟨ 2, x ⟩} \subseteq U_{⟨ 0, n ⟩}$ .
For $k (x, ⟨ 0, m ⟩, ⟨ 0, n ⟩)$ :

If $m = n$ , then output $⟨ 0, m ⟩$ .

If $m \neq n$ and either $x = m$ or $x = n$ , then check if there is an $s ⩽ x$ such that $f (s) = x$ . If so, output $⟨ 2, x ⟩$ . If not, output $⟨ 0, x ⟩$ .

If $m \neq n$ , $x \neq m$ , and $x \neq n$ , then output $⟨ 2, x ⟩$ .

For $k (x, ⟨ 0, m ⟩, ⟨ 1, ⟨ n, s ⟩ ⟩)$ and $k (x, ⟨ 1, ⟨ n, s ⟩ ⟩, ⟨ 0, m ⟩)$ : Output $⟨ 1, ⟨ n, s ⟩ ⟩$ .

For $k (x, ⟨ 0, m ⟩, ⟨ 2, s ⟩)$ and $k (x, ⟨ 2, s ⟩, ⟨ 0, m ⟩)$ :

If $x = m$ , check if there is a $t ⩽ x$ such that $f (t) = x$ . If so, output $⟨ 2, x ⟩$ . If not, output $⟨ 0, x ⟩$ .

If $x \neq m$ , output $⟨ 2, x ⟩$ .

For $k (x, ⟨ 1, ⟨ m, s ⟩ ⟩, ⟨ 1, ⟨ n, t ⟩ ⟩)$ , output $⟨ 1, ⟨ m, s ⟩ ⟩$ .

For $k (x, ⟨ 1, ⟨ m, s ⟩ ⟩, ⟨ 2, t ⟩)$ and $k (x, ⟨ 2, t ⟩, ⟨ 1, ⟨ m, s ⟩ ⟩)$ , output $⟨ 1, ⟨ m, s ⟩ ⟩$ .

For $k (x, ⟨ 2, s ⟩, ⟨ 2, t ⟩)$ , output $⟨ 2, max {s, t} ⟩$ .

The space $(X, U, k)$ is discrete because for every n, either $U_{⟨ 0, n ⟩} = {n}$ or there is an s such that $U_{⟨ 1, ⟨ n, s ⟩ ⟩} = {n}$ . Thus $(X, U, k)$ is not compact, and therefore it is not compact w.r.t. honest open covers. Let $h : N \to I$ be such that $X = ⋃_{m \in N} U_{h (m)}$ , but such that there is no $M \in N$ for which $X = ⋃_{m < M} U_{h (m)}$ . Notice that every basic open set is either finite or cofinite. If $U_{h (m)}$ is cofinite for some m, then by using $B Σ_{1}^{0}$ and the assumption $X = ⋃_{m \in N} U_{h (m)}$ , we may conclude that there is an $M \in N$ such that $X = ⋃_{m < M} U_{h (m)}$ , which is a contradiction. Thus $U_{h (m)}$ is finite for every m. Consider an $n \in X$ . There must be an m such that $n \in U_{h (m)}$ . If there is an s such that $f (s) = n$ , then the only finite basic open set that contains n is $U_{⟨ 1, ⟨ n, s ⟩ ⟩}$ , so in this case it must be that $h (m) = ⟨ 1, ⟨ n, s ⟩ ⟩$ . If instead there is no s such that $f (s) = n$ , then the only finite basic open set that contains n is $U_{⟨ 0, n ⟩}$ , so in this case it must be that $h (m) = ⟨ 0, n ⟩$ . Therefore $\begin{array}{l} \exists s (f (s) = n) \Leftrightarrow \exists m \exists s (h (m) = ⟨ 1, ⟨ n, s ⟩ ⟩) \Leftrightarrow \forall m (h (m) \neq ⟨ 0, n ⟩) . \end{array}$ Thus the range of f exists by $Δ_{1}^{0}$ -comprehension. □

Dorais’s [1, Example 5.4] shows that, over ${RCA}_{0}$ , ${ACA}_{0}$ is equivalent to the statement “every infinite countable second-countable space that is compact w.r.t. honest open covers and whose base has a finite cover relation is not discrete.” The proof of Proposition 3.10 may also be seen as a proof of this fact, as one may check that the constructed $U$ has a finite cover relation.

This work concerns the order topologies of countable linear orders, which give natural examples of (strong) countable second-countable spaces.
Definition 3.11 ( ${RCA}_{0}$ ; [1, Definition 7.1]).

Let $(L, ≺)$ be a linear order. The base for the order topology on L is given by $U = {(U_{i})}_{i \in I}$ and $k : L \times I \times I \to I$ , where

$I = (L \cup {- \infty, \infty}) \times (L \cup {- \infty, \infty})$ ,

$U_{⟨ a, b ⟩} = (a, b) = {x \in L : a ≺ x ≺ b}$ , for $⟨ a, b ⟩ \in I$ , and

$k (x, ⟨ a_{0}, b_{0} ⟩, ⟨ a_{1}, b_{1} ⟩) = ⟨ max (a_{0}, a_{1}), min (b_{0}, b_{1}) ⟩$ for $x \in L$ and $⟨ a_{0}, b_{0} ⟩, ⟨ a_{1}, b_{1} ⟩ \in I$ .

The ordered space associated with L is the countable second-countable space

(L, U, k)

In the above definition, $- \infty$ and ∞ are (codes for) two distinct fresh symbols not in L. We extend ≺ to $L \cup {- \infty, \infty}$ by setting $- \infty ≺ x ≺ \infty$ for all $x \in L$ . Note that, as a matter of convenience, we allow $⟨ a, b ⟩ \in I$ even when $b ≺ a$ , in which case $U_{⟨ a, b ⟩} = \emptyset$ . As the basic open subsets of L are particularly easy to describe, we dispense with the notational encumbrances of Definition 3.4 and simply write an enumeration of basic open sets as $((a_{n}, b_{n}) : n \in N)$ , with the understanding that $a_{n}, b_{n} \in L \cup {- \infty, \infty}$ for each n. Notice that the base of an ordered space always has a finite cover relation [1, Proposition 7.5].

As mentioned above, Dorais observes that ${RCA}_{0}$ proves that if the order topology of $(L, ≺)$ is compact w.r.t. honest open covers, then $(L, ≺)$ is complete.

Lemma 3.12 ([1, Section 7]).

${RCA}_{0}$ proves the statement “for every countable linear order $(L, ≺)$ , if the order topology of $(L, ≺)$ is compact w.r.t. honest open covers, then $(L, ≺)$ is complete.” It follows that ${RCA}_{0}$ also proves the statement “for every countable linear order $(L, ≺)$ , if the order topology of $(L, ≺)$ is compact, then $(L, ≺)$ is complete.”

Proof.
We prove the contrapositive. Suppose that $(L, ≺)$ is not complete, and let $A^{-} \cup A^{+} = L$ be a partition where $(\forall x \in A^{-}) (\forall y \in A^{+}) (x ≺ y)$ , but is such that $A^{-}$ has no maximum element and $A^{+}$ has no minimum element. Then any enumeration of the basic open sets of the form $(- \infty, b)$ for $b \in A^{-}$ and $(a, \infty)$ for $a \in A^{+}$ is an honest open cover of L by basic open sets that has no finite subcover. Thus the order topology of $(L, ≺)$ is not compact w.r.t. honest open covers. □

We show the following in the next section.
The statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact w.r.t. honest open covers” is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ .

The statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact” is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .

4. The strength of compactness for complete linear orders

First, we show that ${WKL}_{0}$ proves that the order topology of a complete linear order is compact w.r.t. honest open covers. It follows that ${ACA}_{0}$ proves that the order topology of a complete linear order is compact. The proof is essentially an implementation of the usual argument as found, for example, in the proof of [8, Theorem 27.1].

Lemma 4.1.
${WKL}_{0}$ proves the statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact w.r.t. honest open covers.”
Proof.
We prove the contrapositive of the statement in ${WKL}_{0}$ . Suppose that the order topology of $(L, ≺)$ is not compact w.r.t. honest open covers, and let $((a_{n}, b_{n}) : n \in N)$ be an open cover of L by basic open sets with no finite subcover. Assume that 0 is the minimum element of L and that 1 is the maximum element of L, for if either L has no minimum or L has no maximum, then $(L, ≺)$ is not complete, as desired.

Define a linkage in L to be a finite sequence $((a_{n_{i}}, b_{n_{i}}) : i < k)$ of intervals from the cover such that $(\forall i < k - 1) (a_{n_{i + 1}} ≺ b_{n_{i}} ≺ b_{n_{i + 1}})$ . Say that an $ℓ \in L$ is in a linkage $((a_{n_{i}}, b_{n_{i}}) : i < k)$ if $(\exists i < k) (a_{n_{i}} ≺ ℓ ≺ b_{n_{i}})$ (i.e., if $ℓ \in ⋃_{i < k} (a_{n_{i}}, b_{n_{i}})$ ). Notice that no linkage contains both 0 and 1 because such a linkage would be a finite subcover of $((a_{n}, b_{n}) : n \in N)$ . A straightforward application of $Π_{1}^{0}$ induction on the length of a linkage shows that the union of a linkage is an interval, meaning that if $((a_{n_{i}}, b_{n_{i}}) : i < k)$ is a linkage, if x and y are both in the linkage, and if $x ≺ y$ , then every $z \in (x, y)$ is also in the linkage.

We define the tree $T \subseteq 2^{< N}$ consisting of all sequences σ that look like initial segments of sets that contain 0, do not contain 1, are ≺-downward-closed, and are closed under linkages. Let T be the set of all $σ \in 2^{< N}$ satisfying the following conditions.
If $| σ | > 0$ , then $σ (0) = 1$ .

If $| σ | > 1$ , then $σ (1) = 0$ .

For all $x < | σ |$ , if $x \notin L$ , then $σ (x) = 0$ .

For all $x, y < | σ |$ , if $x, y \in L$ , $x ≺ y$ , and $σ (y) = 1$ , then $σ (x) = 1$ .

For all $x, y < | σ |$ and for all finite sequences $⟨ n_{i} : i < k ⟩ < | σ |$ , if $x, y \in L$ , if $((a_{n_{i}}, b_{n_{i}}) : i < k)$ is a linkage containing both x and y, and if $σ (y) = 1$ , then $σ (x) = 1$ .
T is $Δ_{1}^{0}$ relative to $(L, ≺)$ and hence exists by $Δ_{1}^{0}$ comprehension. It is easy to see that T is closed under initial segments and hence is a tree. We show that T is infinite. To this end, let $n \in N$ , and let $\begin{array}{l} D = {x < n : (\exists ⟨ n_{i} : i < k ⟩) [((a_{n_{i}}, b_{n_{i}}) : i < k) is a linkage containing both 0 and x]} . \end{array}$ The set D exists by bounded $Σ_{1}^{0}$ comprehension. Let $σ \in 2^{< N}$ be the sequence of length n where, for all $x < n$ , $σ (x) = 1$ if $x \in D$ and $σ (x) = 0$ if $x \notin D$ . Then $σ \in T$ , which can be seen by noticing that $0 \in D$ (if $n > 0$ ); that $1 \notin D$ because 0 and 1 are not in a linkage together; and that D is ≺-downwards closed in $L \cap {0, 1, \dots, n - 1}$ because the union of any linkage containing 0 is an initial segment of L. Therefore, for every n there is a $σ \in T$ with $| σ | = n$ . Hence T is infinite.

Thus T is an infinite subtree of $2^{< N}$ . Apply weak König’s lemma to T to get an infinite path, and view that path as the characteristic function of a set $X \subseteq L$ . X contains 0, does not contain 1, is ≺-downward-closed, and is closed under linkages. By setting $A^{-} = X$ and $A^{+} = L ∖ X$ , we obtain a partition $L = A^{-} \cup A^{+}$ where $0 \in A^{-}$ , $1 \in A^{+}$ , and $(\forall x \in A^{-}) (\forall y \in A^{+}) (x ≺ y)$ .

We show that $A^{-}$ has no maximum element and that $A^{+}$ has no minimum element. First, suppose for a contradiction that $A^{-}$ has a maximum element ℓ. As $((a_{n}, b_{n}) : n \in N)$ is a cover, let $(a_{n_{0}}, b_{n_{0}})$ be such that $ℓ \in (a_{n_{0}}, b_{n_{0}})$ . We cannot have that $b_{n_{0}} = \infty$ , for otherwise ℓ and 1 are both in the linkage $(a_{n_{0}}, b_{n_{0}})$ , which implies that $1 \in A^{-}$ because $A^{-}$ is linkage-closed. Thus $b_{n_{0}} \in L$ , so let $(a_{n_{1}}, b_{n_{1}})$ be such that $b_{n_{0}} \in (a_{n_{1}}, b_{n_{1}})$ . Then $(a_{n_{0}}, b_{n_{0}}), (a_{n_{1}}, b_{n_{1}})$ is a linkage containing both ℓ and $b_{n_{0}}$ . Thus $b_{n_{0}} ≻ ℓ$ is in $A^{-}$ because $A^{-}$ is linkage-closed. This contradicts that ℓ is the maximum of $A^{-}$ . Now suppose for a contradiction that $A^{+}$ has a minimum element ℓ. Again by the fact that $((a_{n}, b_{n}) : n \in N)$ is a cover, let $(a_{m_{1}}, b_{m_{1}})$ be such that $ℓ \in (a_{m_{1}}, b_{m_{1}})$ . We cannot have that $a_{m_{1}} = - \infty$ , for otherwise 0 and ℓ are both in the linkage $(a_{m_{1}}, b_{m_{1}})$ , which implies that $ℓ \in A^{-}$ because $0 \in A^{-}$ and $A^{-}$ is linkage-closed. Thus $a_{m_{1}} \in L$ , so let $(a_{m_{0}}, b_{m_{0}})$ be such that $a_{m_{1}} \in (a_{m_{0}}, b_{m_{0}})$ . Then either $b_{m_{0}} ≺ b_{m_{1}}$ , in which case $(a_{m_{0}}, b_{m_{0}}), (a_{m_{1}}, b_{m_{1}})$ is a linkage containing both ℓ and $a_{m_{1}}$ ; or $b_{m_{0}} ⪰ b_{m_{1}}$ , in which case $(a_{m_{0}}, b_{m_{0}}) \supseteq (a_{m_{1}}, b_{m_{1}})$ is a linkage containing both ℓ and $a_{m_{1}}$ . Thus $a_{m_{1}}$ is in a linkage with ℓ. However, $a_{m_{1}} \in A^{-}$ because $a_{m_{1}} ≺ ℓ$ and ℓ is the minimum element of $A^{+}$ . This contradicts that $A^{-}$ is linkage-closed. Thus $A^{-}$ has no maximum element, and $A^{+}$ has no minimum element. So $A^{-}$ and $A^{+}$ witness that $(L, ≺)$ is not complete. □
Corollary 4.2.
${ACA}_{0}$ proves the statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact.”
Proof.
${ACA}_{0}$ proves ${WKL}_{0}$ and that a countable second-countable space is compact if and only if it is compact w.r.t. honest open covers. □

We now give the reversals. The strategy is as follows. First, recall the Kleene–Brouwer ordering of finite sequences: $σ ⩽_{KB} τ$ if either σ is an extension of τ or σ is to the left of τ. That is, $σ ⩽_{KB} τ$ if $\begin{array}{l} σ \supseteq τ \lor (\exists n < min (| σ |, | τ |)) [σ (n) < τ (n) \land (\forall i < n) (σ (i) = τ (i))] . \end{array}$ Now, let $T \subseteq N^{< N}$ be an infinite finitely-branching tree. In the case of ${ACA}_{0}$ , we show that the order topology of $(T, <_{KB})$ is discrete, hence not compact. In the case of ${WKL}_{0}$ , we additionally assume that T is bounded, and we show that the order topology of $(T, <_{KB})$ is effectively discrete, hence not compact w.r.t. honest open covers. In both cases, we conclude that $(T, <_{KB})$ is not complete, which lets us extract an infinite path through T from a witnessing partition. The idea of last step of this strategy, to use a certain partition of a linear order on T to find a path through T, also appears in Simpson and Yokoyama’s analysis of Peano categoricity [10].
Lemma 4.3 ( ${RCA}_{0}$ ).

Let $T \subseteq N^{< N}$ be an infinite, finitely-branching tree, and for each $σ \in T$ , let $T_{σ} = {τ \in T : τ \supseteq σ}$ denote the full subtree of T above σ. Assume that every $T_{σ}$ has a $<_{KB}$ -least element. Then the order topology of $(T, <_{KB})$ is discrete. Moreover, if T is bounded, then the order topology of $(T, <_{KB})$ is effectively discrete.

Proof.
The lemma follows from two claims. Claim.
If $σ \in T$ is not $<_{KB}$ -least, then σ has a $<_{KB}$ -immediate predecessor. If T is bounded, then the $<_{KB}$ -immediate predecessor can be found effectively. That is, if T is bounded, then there is a function $ℓ : T \to T \cup {- \infty}$ such that $\begin{array}{l} ℓ (σ) = \{\begin{matrix} σ ’s <_{KB} -immediate predecessor & if σ is not <_{KB} -least, \\ - \infty & if σ is <_{KB} -least . \end{matrix} \end{array}$
Proof of Claim.
Consider a $σ \in T$ that is not $<_{KB}$ -least. If σ is not a leaf, then its rightmost child is its $<_{KB}$ -immediate predecessor. In this case, the rightmost child exists because T is finitely-branching.

Suppose that σ is a leaf. Let $i < | σ |$ be greatest such that for some $m < σ (i)$ , ${(σ ↾ i)}^{⌢} m \in T$ . Such an i exists by the assumption that σ is not $<_{KB}$ -least (and that σ is a leaf). Given this greatest i, let $m < σ (i)$ be greatest such that ${(σ ↾ i)}^{⌢} m \in T$ . Then this $τ = {(σ ↾ i)}^{⌢} m$ is σ’s $<_{KB}$ -immediate predecessor. To see this, suppose that $α <_{KB} σ$ for some $α \in T$ . Let j be such that $α ↾ j = σ ↾ j$ and $α (j) < σ (j)$ . Then $j ⩽ i$ by the maximality of i. If $j = i$ , then $α ⩽_{KB} τ$ by the maximality of m. If $j < i$ , then $α <_{KB} τ$ because $α ↾ j = σ ↾ j = τ ↾ j$ but $α (j) < σ (j) = τ (j)$ .

If T is bounded by f, then f can be used to determine whether or not σ is a leaf and, if not, determine σ’s rightmost child. If σ is a leaf, no further use of f is required to produce the $<_{KB}$ -immediate predecessor τ because in this case σ itself provides the necessary bounds. □
Claim.
If $σ \in T$ is not $<_{KB}$ -greatest (i.e., if $σ \neq \emptyset$ ), then σ has a $<_{KB}$ -immediate successor. If T is bounded, then the $<_{KB}$ -immediate successor can be found effectively. That is, if T is bounded, then there is a function $r : T \to T \cup {\infty}$ such that $\begin{array}{l} r (σ) = \{\begin{matrix} σ ’s <_{KB} -immediate successor & if σ \neq \emptyset, \\ \infty & if σ = \emptyset . \end{matrix} \end{array}$
Proof of claim.
Here we use the ad hoc notation ‘ $α! i$ ’ to denote the sequence obtained by changing the last entry of $α \neq \emptyset$ to i.

Consider a $σ \in T$ that is not ∅. If there is no $m > σ (| σ | - 1)$ such that $σ! m \in T$ , then $σ ↾ (| σ | - 1)$ is σ’s $<_{KB}$ -immediate successor.

If there is an $m > σ (| σ | - 1)$ such that $σ! m \in T$ , then let m be the least such m. Then σ’s $<_{KB}$ -immediate successor is the $<_{KB}$ -least element τ of $T_{σ! m}$ , which exists by assumption. To see this, suppose that $α >_{KB} σ$ for some $α \in T$ . If $α ⊊ σ$ , then $α ⊊ σ! m \subseteq τ$ , so $α >_{KB} τ$ . Otherwise, there is a j such that $α ↾ j = σ ↾ j$ and $α (j) > σ (j)$ . If $j < | σ | - 1$ , then $α >_{KB} σ! m ⩾_{KB} τ$ . If $j = | σ | - 1$ , then either $α (j) > m$ or $α (j) = m$ . If $α (j) > m$ , then again $α >_{KB} σ! m ⩾_{KB} τ$ . If $α (j) = m$ , then $α \in T_{σ! m}$ , so $α ⩾_{KB} τ$ by the choice of τ.

If T is bounded by f, then f can be used to determine whether or not there is an $m > σ (| σ | - 1)$ with $σ! m \in T$ . Furthermore, f can be used to find the $<_{KB}$ -least element of any subtree $T_{η}$ . The $<_{KB}$ -least element of $T_{η}$ is the leftmost leaf of $T_{η}$ , which can be found by starting at η and following the leftmost child until reaching a leaf. The bound f can be used to determine whether or not a given element of T is a leaf, so this search is effective. □

Consider now the order topology of $(T, <_{KB})$ , and consider a $σ \in T$ . If σ is neither $<_{KB}$ -least nor $<_{KB}$ -greatest, then σ has a $<_{KB}$ -immediate predecessor τ and a $<_{KB}$ -immediate successor η. In this case, ${σ} = (τ, η)$ is a basic open set. If σ is $<_{KB}$ -least, then σ has a $<_{KB}$ -immediate successor η. In this case, ${σ} = (- \infty, η)$ is a basic open set. If σ is $<_{KB}$ -greatest, then σ has a $<_{KB}$ -immediate predecessor τ. In this case ${σ} = (τ, \infty)$ is a basic open set. Thus the order topology of $(T, <_{KB})$ is discrete. Furthermore, if T is bounded, then ${σ} = (ℓ (σ), r (σ))$ for every $σ \in T$ . Thus the order topology of $(T, <_{KB})$ is effectively discrete via the function $d (σ) = ⟨ ℓ (σ), r (σ) ⟩$ . □
Lemma 4.4 ( ${RCA}_{0}$ ).

Let $T \subseteq N^{< N}$ be an infinite finitely-branching tree. If the linear order $(T, <_{KB})$ is not complete, then T has an infinite path.

Proof.

Let $A^{-}$ and $A^{+}$ witness that $(T, <_{KB})$ is not complete. Notice that $A^{+}$ is non-empty (because $\emptyset \in A^{+}$ , as otherwise it would be the greatest element of $A^{-}$ ) and that $A^{+}$ is closed under initial segments (because it is $<_{KB}$ -upward closed). Define a set $X \subseteq N^{< N}$ by putting $σ \in X$ if and only if $\begin{array}{l} σ \in A^{+} \land (\forall i < | σ |) (\forall n < σ (i)) [{(σ ↾ i)}^{⌢} n \notin A^{+}] . \end{array}$ For every n, the set X contains at most one sequence of length n, which can be seen from the definition of X and the fact that $A^{+}$ is closed under initial segments. Using $I Σ_{1}^{0}$ , we show that, for every n, X contains at least one sequence of length n. For the base case, ∅ is a sequence in X of length 0. For the inductive case, suppose that X contains a sequence σ of length n. Then $σ \in A^{+}$ and, as $A^{+}$ has no $<_{KB}$ -least element, there must be a sequence $τ \in A^{+}$ with $τ <_{KB} σ$ . The sequence τ cannot be to the left of σ because this would contradict $σ \in X$ . Therefore it must be that $τ \supseteq σ$ . It follows that there is an m such that $σ^{⌢} m \in A^{+}$ . Let m be least such that $σ^{⌢} m \in A^{+}$ . Then $σ^{⌢} m$ is in X and has length $n + 1$ . This completes the induction.

The set X thus contains exactly one sequence of each length. As X is closed under initial segments, it follows that if $σ, τ \in X$ are such that $| σ | ⩽ | τ |$ , then $σ \subseteq τ$ . Thus if we let $σ_{i}$ be the sequence in X of length i, then $σ_{0} \subseteq σ_{1} \subseteq σ_{2} \subseteq \dots$ defines an infinite path through T. □

Theorem 4.5.

The statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact w.r.t. honest open covers” is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ .

The statement “for every countable linear order $(L, ≺)$ , if $(L, ≺)$ is complete, then the order topology of $(L, ≺)$ is compact” is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ .

Proof.

The forward direction of item (i) is Lemma 4.1, and the forward direction of item (ii) is Corollary 4.2.

For the reversal of item (ii), let $T \subseteq N^{< N}$ be an infinite finitely-branching tree. By Theorem 2.2 item (i), it suffices to show that T has an infinite path. Recall that, for $σ \in T$ , $T_{σ} = {τ \in T : τ \supseteq σ}$ denotes the full subtree of T above σ. Suppose that there is a $σ \in T$ such that $T_{σ}$ has no $<_{KB}$ -least element. Then setting $A^{-} = \emptyset$ and $A^{+} = T_{σ}$ gives a partition of $T_{σ}$ witnessing that the linear order $(T_{σ}, <_{KB})$ is not complete. By Lemma 4.4, there is an infinite path through $T_{σ}$ , which is an infinite path through T. Suppose instead that $T_{σ}$ has a $<_{KB}$ -least element for every $σ \in T$ . Then the order topology of $(T, <_{KB})$ is discrete by Lemma 4.3. Therefore the order topology of $(T, <_{KB})$ is not compact. We assume that the order topology of a complete linear order is compact, so $(T, <_{KB})$ is not complete. Therefore T has an infinite path by Lemma 4.4.

The reversal of item (i) is analogous. Let $T \subseteq N^{< N}$ be an infinite bounded tree. By Theorem 2.2 item (ii), it suffices to show that T has an infinite path. As above, if there is a $σ \in T$ such that $T_{σ}$ has no $<_{KB}$ -least element, then the linear order $(T_{σ}, <_{KB})$ is not complete, so $T_{σ}$ , and therefore T, has an infinite path by Lemma 4.4. If $T_{σ}$ has a $<_{KB}$ -least element for every $σ \in T$ , then the order topology of $(T, <_{KB})$ is effectively discrete by Lemma 4.3. Therefore the order topology of $(T, <_{KB})$ is not compact w.r.t. honest open covers. Therefore the linear order $(T, <_{KB})$ is not complete. Therefore T has an infinite path by Lemma 4.4. □

Footnotes

Acknowledgements

We thank François Dorais and Giovanni Soldà for helpful discussions. This project was partially supported by a grant from the John Templeton Foundation (“A new dawn of intuitionism: mathematical and philosophical advances” ID 60842). The opinions expressed in this work are those of the author and do not necessarily reflect the views of the John Templeton Foundation.

References

F.G.

Dorais, Reverse mathematics of compact countable second-countable spaces, 2011, arXiv:1110.6555v1.

F.G.

Dorais, 2018, Personal communication.

Friedman, Some systems of second order arithmetic and their use, in: Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, Canad. Math. Congress, Montreal, Que, 1975, pp. 235–242.

Frittaion,

Hendtlass,

Marcone,

Shafer and

Van der Meeren, Reverse mathematics, well-quasi-orders, and Noetherian spaces, Archive for Mathematical Logic 55(3–4) (2016), 431–459. doi:10.1007/s00153-015-0473-4.

Hájek and

Pudlák, Metamathematics of First-Order Arithmetic, 2nd edn, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998, p. xiv+460. ISBN 3-540-63648-X.

Mummert, Reverse mathematics of MF spaces, Journal of Mathematical Logic 6(2) (2006), 203–232. doi:10.1142/S0219061306000578.

Mummert and

S.G.

Simpson, Reverse mathematics and

Π_{2}^{1}

comprehension, Bulletin of Symbolic Logic 11(4) (2005), 526–533. doi:10.2178/bsl/1130335208.

J.R.

Munkres, Topology, 2nd edn, Prentice Hall, Inc., Upper Saddle River, NJ, 2000, p. xvi+537. ISBN 0-13-181629-2.

S.G.

Simpson, Subsystems of Second Order Arithmetic, Perspectives in Logic, 2nd edn, Cambridge University Press, Cambridge, 2009, p. xvi+444. ISBN 978-0-521-88439-6.

10.

S.G.

Simpson and

Yokoyama, Reverse mathematics and Peano categoricity, Annals of Pure and Applied Logic 164(3) (2013), 284–293. doi:10.1016/j.apal.2012.10.014.

The strength of compactness for countable complete linear orders

Abstract

Keywords

1. Introduction

2. Preliminaries for working in second-order arithmetic

Lemma 2.1 ([9, Lemma III.1.3]).

Theorem 2.2. König’s lemma is equivalent to ACA 0 over RCA 0 (see [ 9 , Theorem III.7.2]). Bounded König’s lemma is equivalent to WKL 0 over RCA 0 (see [ 9 , Lemma IV.1.4]). 3. Countable second-countable topological spaces

Definition 3.1 ( RCA 0 ; [1, Definition 2.1]).

Definition 3.2 ( RCA 0 ; [1, Definition 2.2]).

Definition 3.3 ( RCA 0 ).

Definition 3.4 ( RCA 0 ; [1, Definitions 2.3 and 2.4]).

Definition 3.5 ( RCA 0 ).

Definition 3.6 ( RCA 0 ).

Proposition 3.7 ( RCA 0 ).

Definition 3.9 ( RCA 0 ; [1, Definition 5.1]).

Lemma 3.12 ([1, Section 7]).

Footnotes

Acknowledgements

References

Theorem 2.2.

König’s lemma is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ (see [ 9 , Theorem III.7.2]).

Bounded König’s lemma is equivalent to ${WKL}_{0}$ over ${RCA}_{0}$ (see [ 9 , Lemma IV.1.4]).

3. Countable second-countable topological spaces

Definition 3.1 ( ${RCA}_{0}$ ; [1, Definition 2.1]).

Definition 3.2 ( ${RCA}_{0}$ ; [1, Definition 2.2]).

Definition 3.3 ( ${RCA}_{0}$ ).

Definition 3.4 ( ${RCA}_{0}$ ; [1, Definitions 2.3 and 2.4]).

Definition 3.5 ( ${RCA}_{0}$ ).

Definition 3.6 ( ${RCA}_{0}$ ).

Proposition 3.7 ( ${RCA}_{0}$ ).

Definition 3.9 ( ${RCA}_{0}$ ; [1, Definition 5.1]).