Principles Weaker than BD-N

Robert S. Lubarsky and Hannes Diener Dept. of Mathematical Sciences Florida Atlantic University Boca Raton, FL 33431 Robert.Lubarsky@alum.mit.edu Department Mathematik, Fak. IV Emmy-Noether-Campus, Walter-Flex-Str. 3 University of Siegen 57068 Siegen, Germany diener@math.uni-siegen.de

February 28, 2012

Abstract

BD-N is a weak principle of constructive analysis. Several interesting principles implied by BD-N have already been identified, namely the closure of the anti-Specker spaces under product, the Riemann Permutation Theorem, and the Cauchyness of all partially Cauchy sequences. Here these are shown to be strictly weaker than BD-N, yet not provable in set theory alone under constructive logic. keywords: anti-Specker spaces, BD-N, Cauchy sequences, partially Cauchy, Riemann Permutation Theorem, topological models AMS 2010 MSC: 03F60, 03F50, 03C90, 26E40

1 Introduction

BD-N, first identified in [14] with a pre-history in [13], has turned out to be an important foundational principle, being equivalent to many statements in analysis having to do with continuity [15, 16, 17]. It is also weak, or deep, in that it holds in all major traditions of mathematics, including classical mathematics, intuitionism, and Russian constructivism (based on computability). As such a central and weak principle, it is reasonable to guess that most particular consequences of it would either imply it or be outright provable. A moment’s sober reflection would lead one to realize that BD-N is not an atom, or co-atom, in the Heyting algebra of statements, and that it would almost certainly just be a matter of time before natural intermediate statements were found. This note reports on exactly that.

The first example is the closure of the anti-Specker spaces under products. (For background, see [2, 3, 4, 8].) Douglas Bridges showed such closure under BD-N [9], speculating that they were equivalent. It was shown in [20] that in fact such closure does not imply BD-N. This still leaves open the question as to whether this closure is provable outright. We show below it is not.

The next example is the Riemann Permutation Theorem. For background, see [5, 6], where it is shown, among other things, that BD-N implies the RPT. We show that RPT does not itself imply BD-N, in a very similar manner to the anti-Specker property, and also that it is not itself provable.

Our final example has to do with a weakening of the definition of a Cauchy sequence, which was identified by Fred Richman (notes), who called such sequences partially Cauchy. He showed that under BD-N, all partially Cauchy sequences are Cauchy. A similar kind of sequence, an almost Cauchy sequence, has also been identified [7]. There it was shown that, under Countable Choice, all almost Cauchy sequences are Cauchy iff BD-N holds. It is shown below that the Cauchyness of all partially Cauchy sequences does not imply BD-N, and also that the Cauchyness of all partially Cauchy sequences is not itself provable on the basis of set theory alone.

We speculate that there is an intricate and interesting world of unprovable principles strictly weaker than BD-N. To carry this program out, several tasks need fulfilling. For one, we would like to see just how interesting the ones discussed here are, by how many interesting statements they’re equivalent with. We would also like to see other such intermediate statements. Of course, we need to know whether these intermediate properties are themselves mutually inequivalent, and, if so, what implications might hold under additional hypotheses, such as Countable Choice. As for an independence result in the general case, the obvious place to look first would be the models contained herein. These topological models have a claim at being the generic models for their specific purposes. As such, they naturally tend to keep principles not intended to be falsified true. So, for instance, you’d expect that, in the model falsifying RPT, partially Cauchy sequences would still be Cauchy, unless of course the latter assertion implied RPT. We do not attempt a thorough analysis of all of these issues here, prefering to leave this for future work.

Regarding the methods employed, any independence result of the form “A does not imply B” is shown here by providing a model of A in which B is false. These models are all topological models, which works essentially like forcing from classical set theory when you leave out that part of the basic theory where you mod out by the double negation, the purpose of which is only to model classical instead of just constructive logic, clearly a move which is anathema to our purposes. For background on topological models, see [11, 12] and the addendum to [19].

It would be interesting to see how these issues would play out with realizability models. The first models discovered falsifying BD-N were of this kind [1, 10, 18]. Each and every one of them also exhibits a separation of the kind proved here, depending on which among the anti-Specker closure property, RPT, and the partially Cauchy property hold in it. The extra challenge presented by this context is that realizability models seem not to be the canonical models for these properties, and they’re less flexible to deal with. By way of illustration, most of the topological models presented here and in [20] were not that difficult to come up with; in contrast, it seems completely unclear how to concoct a realizability model for the same purposes. As another illustration, as stated in [20], topological models seem to be canonical for their purposes, in that ground model properties tend to persist into the topological models, except of course for those that imply the property purposely being falsified. For instance, the three properties considered here are all true in the topological model of not BD-N, as predicted. In contrast, in the realizability models at hand, all bets are off as to which of those three hold there. The experts do not have a clear expectation of this outcome, and furthermore, at least in the one case tried (RPT in extensional K_{1} realizability), they have not been able to prove one way or the other whether it holds. On the other hand, many of these models are naturally occurring in and of themselves. Hence it would be nice to know which of the principles under consideration hold where, in order to understand these models better, as well as the computational content of the principles themselves.

The paper in organized as followed. Anti-Specker spaces are discussed in sec. 2. It was shown already in [20] that their closure under Cartesian product does not imply BD-N; here we see that such closure can fail under standard set theory (IZF). The following two sections are about the Riemann Permutation Theorem, first that it does not imply BD-N, and then that it can fail even under IZF. The two sections after that show the corresponding results for the assertion that all partially Cauchy sequences are Cauchy.

2 Anti-Specker spaces may not be closed under products

An anti-Specker space for our purposes is a metric space X such that, when you enlarge X by adding a single point ∗ at a distance of 1 away from every x ∈ X, then every countable sequence through X ∪ {∗} which is eventually apart from every point of X is eventually equal to ∗. (How you enlarge X might actually lead to different definitions.) Anti-Speckerhood is a form of compactness. As such, one might reasonably expect anti-Specker spaces to be closed under Cartesian product. We produce a topological space T such that the (full) model over T falsifies such closure.

Definition 2.1 Let T consist of ω-sequences (z_{n}) such that finitely many entries are pairs of real numbers ⟨x_{n}, y_{n}⟩ and the rest are ∗, which is taken by convention to equal ⟨∗, ∗⟩ (so every entry has both projections). We give the topology by describing a sub-basis. An open set in the sub-basis is given by the following information. The positive information is a finite sequence α_{n} (n < N), each entry of which is either ∗ or a pair of finite open intervals ⟨I_{n}, J_{n}⟩. A sequence (z_{n}) satisfies this positive constraint if z_{n} = ∗ whenever α_{n} = ∗ and z_{n} ∈ I_{n} × J_{n} otherwise (n < N). The negative information is an assignment to each of finitely many closed and bounded sets C_{i}(i ∈ I, I an index set) in ℝ^{2} of a natural number M_{i}. This negative information is satisfied by (z_{n}) if, for all n > M_{i}, z_{n} ∉ C_{i} (where ∗ ∉ ℝ^{2}). (Notice that the empty set is given by the intersection of two sub-basic open sets with incompatible positive information.)

An open set is said to be in normal form if the following conditions hold. For one, for m, n < N, either ⟨I_{m}, J_{m}⟩ = ⟨I_{n}, J_{n}⟩ or \overline{I_{m} × J_{m}} and \overline{I_{n} × J_{n}} are disjoint (where \overline{X} is the closure of X). Also, I is a singleton – that is, the negative information has only one closed set – and that unique closed set C is a (necessarily finite) rectangle. Finally, for m, n < N I_{m} × J_{n} ⊆ C. (Implicitly, when reference is made to ⟨I_{n}, J_{n}⟩ when α_{n} = ∗, that clause does not apply.)

C I_{0} × J_{0} (x_{0}, y_{0}) I_{1} × J_{1} = I_{4} × J_{4} (x_{1}, y_{1}) = (x_{4}, y_{4}) I_{3} × J_{3} (x_{3}, y_{3})

Figure 1: Open set in normal form containing the point ((x_{0}, y_{0}), (x_{1}, y_{1}), (x_{2}, y_{2}), …) with (x_{2}, y_{2}) = ∗.

Lemma 2.2 The opens in normal form constitute a sub-basis.

Proof: Given (z_{n}) ∈ O extend the positive information to include all of (z_{n})’s non-∗ entries. Then for ⟨x_{m}, y_{m}⟩ = ⟨x_{n}, y_{n}⟩ shrink I_{m} × J_{m} and I_{n} × J_{n} to be equal; for ⟨x_{m}, y_{m}⟩ ≠ ⟨x_{n}, y_{n}⟩ shrink I_{m} × J_{m} and I_{n} × J_{n} to satisfy the disjointness condition. Furthermore, if n > M_{i} then I_{n} × J_{n} must be shrunken to be disjoint from C_{i}. Then enclose all of the C_{i}’s by one rectangle C, also large enough to cover each I_{m} × J_{n}, and assign to C the length of the positive sequence.

Let G be the generic, which can be identified with a sequence (g_{n}). Let X be the set of reals from the first components of the g_{n}’s, and Y the reals from the second components.

Theorem 2.3 T ⊩ “X and Y are anti-Speacker spaces, and X × Y is not.”

Proof: Clearly, T ⊩ “(g_{n}) is a sequence through X × Y ∪ {∗}.” By considering the normal opens, (g_{n}) is eventually apart from each point in X × Y. In greater detail, suppose (z_{n}) ∈ O ⊩ (x, y) ∈ X × Y. Then some neighborhood of (z_{n}) forces x to be in some I_{m} and y to be in some J_{n}. Let U be a normal open subset of that neighborhood containing (z_{n}). If U’s positive information has length N, then U ⊩ “Beyond N (g_{n}) is apart from (x, y).”

Also, no open set forces (g_{n}) eventually to be ∗, because the closed sets in the negative information are finite. That is, given any open set O and natural number k, there is member of O with a non-∗ entry beyond slot k.

Hence (g_{n}) witnesses that X × Y is not an anti-Specker space.

All that remains to show is that X and Y are anti-Specker spaces. We will show this for X, the case for Y being symmetric.

To this end, suppose O ⊩ “(a_{n}) is a sequence through X ∪ {∗} eventually apart from each point in X.” For (z_{n}) ∈ O we must find a neighborhood of (z_{n}) forcing a place beyond which (a_{n}) is always ∗. First extend (i.e. shrink) O so the positive information α contains all of (z_{n})’s non-∗ entries. Then we claim we can extend again to force an integer K beyond which (i.e. for k > K) a_{k} is apart from each x_{n} in (z_{n})’s non-∗ entries, all the while keeping (z_{n}) in the open set. That is, for each α_{n} of the form ⟨I_{n}, J_{n}⟩, a_{k} is forced to be at least some fixed rational distance r_{n} away from the real approximated by I_{n}. To do this, iteratively extend the open set to have this property for each ⟨I_{n}, J_{n}⟩ individually.

Then extend again by shrinking I_{n} (to an interval we will still call I_{n}, recycling notation) so that I_{n} has length less than r_{n}. This forces a_{k} to be apart from the entire interval I_{n}, even not to be in some lengthening of I_{n} on both sides. We call such a lengthened interval a forbidden zone.

Finally, extend yet again to an open set U ∋ (z_{n}) in normal form, with positive information given by α of length N and negative information given by C.

The claim is that U ⊩ “For k > K a_{k} = ∗”. If not, for some fixed k > K and l let some extension V of U force “a_{k} = x_{l}”. Call V ’s positive information β. Notice that, by the construction above, l > N. That means we can change β_{l} without violating U’s positive information. Pick some v = (v_{n}) ∈ V. Let P be a path in ℝ^{2} starting at v_{l}, ending at some (x, y) with x is some forbidden zone, and avoiding C; this is possible, because C is just a finite rectangle. For each p ∈ P let v(p) be identical with v except that v_{l} is replaced by p. Notice that v(p) ∈ U, because by avoiding C we’re also not violating U’s negative information. So around each v(p) is an open subset of U forcing either that a_{k} is ∗ or that it’s not. Let P_{∗} be {p | some neighborhood of v(p) forces “a_{k} = ∗}

C I_{0} × J_{0} (x_{0}, y_{0}) I_{1} × J_{1} = I_{4} × J_{4} (x_{1}, y_{1}) = (x_{4}, y_{4}) I_{3} × J_{3} (x_{3}, y_{3}) forbidden zone forbidden zone (x, y) v_{ℓ}

Figure 2: The same open set as before, with forbidden zones and path P.

and P_{x} be {p | some neighborhood of v(p) forces “a_{k} ≠ ∗}. Since positive information is given by open sets, whatever some neighborhood of some v(p) forces, the same neighborhood will force the same thing for all v(q) where q is in some neighborhood of p. In other words, both P_{∗} and P_{x} are open. Since paths in ℝ^{2} are connected, one of those is empty and the other is P. Since v_{l} ∈ P_{x}, P_{x} = P. Recall that P ends at some (x, y) with x in a forbidden zone. This contradicts the choice of K, and so completes the proof.

3 RPT does not imply BD-N

At some point in this paper, it should be stated what the Riemann Permutation Theorem actually is.

Theorem 3.1 (Riemann) If every permutation of a series of real numbers converges, then the series converges absolutely.

For a constructive analysis of the issues involved with convergence of series, see [5, 6]. These include a proof that BD-N implies RPT, as well as that absolute convergence follows from merely having a bound on the partial sums of the absolute values, which we use implicitly below.

In [20] a topological model falsifying BD-N is presented, as well as a proof that, in that model, the anti-Specker spaces are closed under products. It is predictable that the proofs that other properties slightly weaker than BD-N hold in the same model would be very similar, and also true. To make the current paper somewhat self-contained we will describe the underlying topological space again; the argument afterwards that RPT holds should seem familiar to anyone familiar with the anti-Specker closure section from [20].

The points in T be the functions f from ω to ω with finite range, that is, enumerations of finite sets. A basic open set p is (either ∅ or) given by an unbounded sequence g_{p} of integers, with a designated integer stem(p), beyond which g_{p} is non-decreasing. f ∈ p if f(n) = g_{p}(n) for n < stem(p) and f(n) ≤ g_{p}(n) otherwise. Notice that p ∩ q is either empty (if g_{p} and g_{q} through their stems are incompatible) or is given by taking the larger of the two stems, the

\begin{matrix}ω \\ ω \end{matrix} ; g_{p} ; stem(p) ; …

Figure 3: An artist’s impression of an open set p.

function up to that stem from the condition with the larger stem, and the pointwise minimum beyond that. Hence these open sets do form a basis. It is sometimes easier to assume that g_{p}(stem(p)) ≥ max{g_{p}(i) | i < stem(p)}. The intuition is that once a certain value has been achieved there’s nothing to be gained anymore by trying to restrict future terms from being that big. It is not hard to see that that additional restriction does not change the topology. So whenever more convenient, a basic open set can be taken to be of this more restrictive form.

Theorem 3.2 T ⊩ RPT.

Proof: Suppose f ∈ p ⊩ “For every permutation σ the series (a_{σ(n)}) converges.” It suffices to find a neighborhood of f forcing an upper bound for Σ |a_{n}|. We assume as usual that p is basic open and that g_{p}(stem(p)) ≥ sup(rng(f)). So it suffices to extend p to r forcing a bound for Σ |a_{n}|, without altering the stem or the value g_{p}(stem(p)) (i.e. stem(p) = stem(r) and g_{p} = g_{r} at their common stem), as f will then be in r. We can also assume that each a_{n} is rational, as a_{n} could be replaced by a rational number (using Countable Choice, which holds in this model) sufficiently close that convergence will not be affected.

Definition 3.3 A finite sequence of integers σ of length at least stem(p) is compatible with p if for all i < stem(p) σ(i) = g_{p}(i) and for all i with stem(p) ≤ i < length(σ) σ(i) ≤ g_{p}(i). For σ compatible with p, p ↾ σ is the open set q ⊆ p such that stem(q) = length(σ), for i < stem(q) g_{q}(i) = σ(i), and otherwise g_{q}(i) = g_{p}(i).

The following lemma is analogous in statement and proof to lemma 3.3 from [20], the proof of which was an extrapolation of some lemmas from an earlier section, which themselves were just extensions of the basic lemma about this model. All of which is meant to explain why the proof will not be repeated here.

Lemma 3.4 There is an open set q ⊆ p, with stem(q) = stem(p) and g_{q}(stem(q)) = g_{p}(stem(p)), which determines the values of a_{n} in the following sense: for every n ∈ ℕ there is a length i_{n} (increasing as a function of n) such that, for all σ of length i_{n} compatible with q, q ↾ σ forces a (rational) value for a_{n}, say r_{σ}.

Let q be as in the lemma. The members of q naturally form a tree T r_{q}: the nodes are those finite sequences compatible with q, and the members of q are those paths through the tree with bounded range. At height j ≥ stem(q) of T r_{q}, the amount of splitting is g_{q}(j) + 1. The nodes at height i_{n} determine the value of a_{n}. We will have use for subsets of q the members of which have ranges that are uniformly bounded. (Such subsets are, of course, not open.) These subsets can be given as the set of paths through a subtree T r of T r_{q} with a fixed bound on the ranges of its nodes, as follows.

Definition 3.5 A tree T r ⊆ T r_{q} is bounded if there is a J such that for all σ ∈ T r and j < length(σ) σ(j) < J.

The following is the analogue of [20]’s lemma 3.5.

Lemma 3.6 Let T r ⊆ T r_{q} be bounded. Then there is a bound B in the sense that, for all σ ∈ T r of length some i_{n}, Σ_{m≤n} |r_{σ↾i_{m}}| ≤ B.

Proof: Say that τ ∈ T r is good if the conclusion of the lemma is satisfied for T r ↾ τ (i.e. those nodes in T r extending τ). Notice that if every immediate extension of τ is good then τ itself is good, by taking the maximum of the bounds witnessing the goodness of τ’s extensions. So if the root of T r is bad (i.e. not good) then there is a path f through T r consisting of all bad nodes. Because T r is bounded, f ∈ T.

Define the permutation σ as follows. At stage n, we have inductively a permutation σ_{n} of a natural number l_{n} (with l_{0} = 0). By the choice of f, there is an extension τ, with length some i_{k}, of f ↾ i_{l_{n}}, such that Σ_{l_{n}<m≤k} |r_{τ↾i_{m}}| is at least 2. That can be only if either the sum of the positive values of r_{τ↾i_{m}} is at least 1, or that of the negative such values is at least 1. Without loss of generality, suppose the former. Let σ_{n+1} extend σ_{n} by first listing all of the m’s such that r_{τ↾i_{m}} is positive, and then listing all of the other m’s which are at most k. As this σ_{n+1} is a permutation of {0, 1, ..., k}, the inductive construction can continue. Letting σ be ⋃_{n} σ_{n}, no neighborhood of f can force that Σa_{σ(n)} converges.

To complete the proof, let T r_{1} be the subtree of T r_{q} of all nodes with values less than or equal to I := g_{q}(stem(q)). Apply the lemma with T r_{1} for T r to get the least such upper bound B_{1}. Now let T r_{j} ⊆ T r_{q} extend T r_{1} by allowing nodes that may take on the value I + 1 at positions beyond j. The lemma applied to T r_{j} produces a least upper bound B_{j}. Notice that for j < k we have T r_{j} ⊇ T r_{k} ⊇ T r_{1}, and so B_{j} ≥ B_{k} ≥ B_{1}. Let B_{∞} be lim_{j} B_{j}.

We claim that B_{∞} = B_{1}. If not, then ϵ := B_{∞} − B_{1} > 0, and for all j there are nodes τ ∈ T r_{1} and ρ ∈ T r_{j} extending τ such that, summing over the i_{m}’s between the lengths of τ and ρ, Σ |r_{ρ↾i_{m}}| is as close to ϵ as you want. By a construction as in the previous lemma, a permutation σ could then be built with no condition forcing Σ_{n}a_{σ(n)} to converge. Hence B_{∞} = B_{1}. Choose j so that B_{j} is within 1/2 of B_{1}. Let T r_{2} be T r_{j} and B_{2} be B_{j}.

Continuing inductively, given T r_{s}, build T r_{s+1} which allows nodes to take on the value I + s past a certain point and has a lemma-induced least upper bound B_{s+1} no greater than 2^{−s} more than B_{s}. Let T r_{∞} be ⋃_{s} T r_{s}. T r_{∞} induces an open set which forces Σ_{n} |a_{n}| to be bounded by B_{1} + 1.

4 RPT may fail

We give present a topological model in which RPT is false. First we define the underlying space T, which not surprisingly will involve reference to permutations. By way of notation, for σ a permutation of ω, we think of σ(n) as the integer in the n^{th} slot. So applying σ to 0, 1, 2, ... would produce σ(0), σ(1), σ(2), .... Applying σ to (a_{n}) produces the sequence a_{σ(0)}, a_{σ(1)}, ..., for which we use the notation (a_{σ(n)}).

Definition 4.1 Let T be the set of sequences (a_{n}) which are eventually 0 and which sum to 0.

An open set O is given in part by a finite sequence I_{n}(n < N) of intervals from ℝ, thought of as approximations to an initial segment of (a_{n}); that is, in order for (a_{n}) to be in O, it is necessary that a_{n} ∈ I_{n}. Also, finitely many permutation σ are given. Each such σ is associated with finitely many pairs ϵ, M, with ϵ > 0 and M ∈ ℕ. For (a_{n}) to be in O, it must also be the case that the partial sums Σ_{n=0}^{m}a_{σ(n)} (m > M) are less than ϵ in absolute value. In words, after permuting (a_{n}) by σ, the series must have converged to within ϵ by M.

Theorem 4.2 T ⊩ ¬RPT.

Proof: The generic G induces the generic sequence of reals (g_{n}), with O ⊩ “g_{n} ∈ I_{n}.” Also, T ⊩ “(g_{n}) is total,” since, for every (a_{n}) ∈ T and k, the open set determined by any (I_{0}, ..., I_{k}), with a_{n} ∈ I_{n}, and no σ’s, forces “g_{k} is defined.” The generic sequence (g_{n}) will witness the failure of RPT.

First we want to see that for every ground model permutation σ Σg_{σ(n)} converges. Notice that for every (a_{n}) ∈ T and ϵ > 0 there an M such that the open set determined by associating ϵ and M to σ contains (a_{n}), for the simple reasons that Σa_{n} converges to 0 and that (a_{n}) is eventually 0: just choose M so large so that all non-0 entries of (a_{n}) have already occurred in a_{σ(n)} by the M^{th} entry there. It follows immediately that T ⊩ “Σg_{σ̂(n)} = 0.”

As for arbitrary permutations, suppose O ⊩ “σ is a permutation.” We claim that no extensions of O can force different values for any σ(n); if that is so, then O itself forces all of the values of σ(n). To see the claim, let (a_{n}) and (b_{n}) be two members of O. Consider the continuous family of sequences (c_{n})^{t} := t(b_{n}) + (1 − t)(a_{n}), 0 ≤ t ≤ 1. Notice that (c_{n})^{0} = (a_{n}), (c_{n})^{1} = (b_{n}), and for all t (c_{n})^{t} ∈ O, since the constraints imposed by O are linear. For any value of t_{0} of t, some neighborhood of (c_{n})^{t_{0}} forces a value for σ(n). Any such neighborhood forces the same value for all (c_{n})^{t} for t in a neighborhood of t_{0}; that is, those t’s that force any fixed value for σ(n) form an open set. Since [0,1] is connected, all (c_{n})^{t}’s must have neighborhoods forcing the same value for σ(n). Hence the values of σ(n) are all determined by O. As the forcing relation is definable in the ground model, these values form a ground model permutation. Since all permutations are equal locally to ground model permutations, by the previous paragraph, Σg_{σ(n)} converges for all σ.

It remains only to show that T ⊩ “(g_{n}) diverges absolutely.” Consider any (a_{n}) ∈ O. There is a K such that, for any σ which is a part of O’s definition, the partial sums beyond K of the permuted sequence are 0: for k > K Σ_{n=0}^{k}a_{σ(n)} = 0. (It suffices to take K = max{σ^{−1}(n)|a_{n} ≠ 0 and σ is constrained by O }.) Choose some i > σ”(K), and change a_{i} to be δ, where δ is less than all of the ϵ-constraints imposed by O. Iterate to find another safe spot j, and change a_{j} to be −δ. This can be iterated to get the sum of the absolute values to be as big as you want. Hence O does not force any bound on the sum of the absolute values.

5 “Partially Cauchy implies Cauchy” does not imply BD-N

Following a definition of Fred Richman (private notes), we say that a sequence of reals x_{n} is partially Cauchy if, for all increasing h, lim_{n} diam(x_{n}, x_{n+1}, ..., x_{h(n)}) = 0. Richman showed, among other things, that, under BD-N, every partially Cauchy sequence is Cauchy. In this section we show that BD-N is not necessary for this, in that the latter result does not imply BD-N. In the next section, we show that the result in question is not provable in basic set theory alone.

Let T be the space from [20], reviewed in section 3 above, the model over which falsifies BD-N. As in the other cases, we have:

Theorem 5.1 T ⊩ “Every partially Cauchy sequence is Cauchy.”

Proof: Suppose p ⊩ “(x_{n}) is partially Cauchy.” In a personal communication, Fred Richman studied several notions of Cauchyness, all akin to partiality, and showed essentially that any sequence which is Cauchy is any sense (partially, weakly, almost) is the sum of a Cauchy sequence (in as strong a sense as you like) and a rational sequence which is Cauchy in the same sense as the starting sequence. His proof uses Countable Choice, which is no problem here, as T ⊩ Dependent Choice, which implies Countable Choice, and is otherwise straightforward. The upshot of this is that we can assume that each x_{n} is rational.

For every f ∈ p we must find a neighborhood q of f forcing (x_{n}) to be Cauchy. So let T ⊩ ϵ > 0. It suffices to assume ϵ is rational, so we do not have to deal with conditions forcing ϵ to have an approximate value. We assume as usual that p is basic open and that g_{p}(stem(p)) ≥ sup(rng(f)). So it suffices to extend p to r forcing an appropriate value N for ϵ, without altering the stem or the value g_{p}(stem(p)) (i.e. stem(p) = stem(r) and g_{p}(stem(p)) = g_{r}(stem(r))), as f will then be in r.

As in section 3 above, we state without proof:

Lemma 5.2 There is an open set q ⊆ p, with stem(q) = stem(p) and g_{q}(stem(q)) = g_{p}(stem(p)), which determines the values of x_{n} in the following sense: for every n ∈ ℕ there is a length i_{n} (increasing as a function of n) such that, for all σ of length i_{n} compatible with q, q ↾ σ forces a (rational) value for x_{n}, say r_{σ}.

With terminology and notation as in section 3 above, we have the following analogue of lemma 3.6.

Lemma 5.3 Let T r ⊆ T r_{q} be bounded, and δ > 0 be rational. Then there is a natural number k such that, for all m, n ≥ k, m < n, and σ_{m} ⊆ σ_{n} of lengths i_{m} and i_{n} respectively, |x_{σ_{m}} − x_{σ_{n}}| < δ.

Proof: Say that τ ∈ T r is good if the conclusion of the lemma is satisfied for T r restricted to τ. Notice that if every immediate extension of τ is good then τ itself is good, by taking the maximum of the k’s witnessing the goodness of τ’s extensions. So if the root of T r is bad (i.e. not good) then there is a path f through T r consisting of all bad nodes. Because T r is bounded, f is a member of the topological space T.

Define the function h as follows. Given k, let m and n be as given by the badness of f ↾ k (i.e. there are nodes σ_{m} ⊆ σ_{n} in the tree beneath f ↾ k with |x_{σ_{m}} − x_{σ_{n}}| ≥ δ). Let h(k) be at least as big as that n (and, for k > 0, bigger than h(k − 1)). Then h witnesses that (x_{n}) is not partially Cauchy, as any neighborhood of f must contain all of T r restricted to some initial segment of f.

To complete the proof, let T r_{1} be the subtree of T r_{q} of all nodes with values less than or equal to I := g_{q}(stem(q)). Apply the lemma with T r_{1} for T r and ϵ/2 for δ. Let k_{1} be the integer produced by the lemma. Let T r_{2} ⊆ T r_{q} extend T r_{1} by allowing nodes that may take on the value I + 1 at positions beyond i_{k_{1}}. Again apply the lemma, with T r_{2} for T r and ϵ/4 for δ, to produce k_{2}, which can be taken to be larger than k_{1}. More generally, at stage s, let T r_{s} ⊆ T r_{q} extend T r_{s−1} by allowing the value I + s − 1 beyond i_{k_{s−1}}, and let k_{s} > k_{s−1} be the result of applying the lemma to T r_{s} and ϵ/2^{s}.

To finish the definition of r, we must just give g_{r}, and show that beyond N := k_{1} r forces the values of (x_{n}) to be within ϵ of one another. As motivation, consider x_{N} itself, as compared with x_{m} for some larger m (larger than N). If the value of x_{m} is determined by some node in T r_{1}, we’re golden – even better than golden, x_{m} being within ϵ/2 of x_{N}. But once we go into T r_{2}, all bets are off. Hence we want to restrict T r_{r} to equal T r_{1} at least for nodes up to length i_{k_{2}}. If m ≤ k_{2}, then x_{m} is determined by T r_{1}, and we’re done. For m > k_{2}, at least we can bound |x_{N} − x_{k_{2}}| by ϵ/2, and work on bounding |x_{k_{2}} − x_{m}| by ϵ/4, which would suffice. While working on the latter, we can now afford to be in the tree T r_{2}. By continuing to expand the tree in which we work in this fashion, we can guarantee that g_{r} be unbounded, while still remaining within ϵ of x_{N}.

So let g_{r} between i_{k_{s}} and i_{k_{s+1}} have the value I + s − 1. This makes g_{r} be unbounded, and forces the values of (x_{n}) beyond N to be within ϵ of one another, by the argument sketched in the previous paragraph.

6 Partially Cauchy may not imply Cauchy

As usual, in the coming topological model the generic will be a partially Cauchy sequence which is not Cauchy. We start by defining the underlying topological space.

Definition 6.1 Let T be the space of all Cauchy sequences (x_{n}). A basic open set is given by finitely many pieces of information. One is a finite sequence of intervals I_{n}(n < k). A sequence (x_{n}) satisfies the requirements I_{n}(n < k) if for all k < n x_{n} ∈ I_{n}. In addition, to each of finitely many functions h and rational numbers ϵ > 0 is associated a natural number n_{h,ϵ}. A sequence (x_{n}) satisfies that requirement if for all n ≥ n_{h,ϵ} diam(x_{n}, x_{n+1}, ..., x_{h(n)}) < ϵ. The basic open sets as given are closed under intersection, and so form a basis.

Theorem 6.2 T ⊩“Not every partially Cauchy sequence is Cauchy.”

Proof: The generic induces a sequence (g_{n}) of reals. For every (x_{n}) ∈ T, ground model function h from ℕ to itself, and rational ϵ > 0, there is a neighborhood O of (x_{n}) assigning a value to n_{h,ϵ}. Then O ⊩ “ if n ≥ n_{h,ϵ} then diam(g_{n}, g_{n+1}, ..., g_{h(n)}) < ϵ”. Furthermore, in this model, all functions from ℕ to itself are ground model functions, by the same argument as for permutations with respect to the RPT. Hence the generic sequence is partially Cauchy.

To see that the generic sequence is not itself Cauchy, let O be an open set and N an arbitrary natural number, which without loss of generality is less than k, the length of O’s sequence of intervals. We will show that O does not force that beyond N the values of the generic always stay within 1 of each other, which suffices.

To simplify on notation (and thinking), we can strengthen (i.e. shrink) O by reducing to one h (by taking the pointwise maximum of the finitely many h’s) and one ϵ (by taking the smallest). To be sure, this summary requirement does not capture all of the actual requirements present before this simplification, as there may have been demands made on intervals starting at n < n_{h,ϵ}. But those demands are only finite in number, and can be satisfied by choosing I_{n}(n < n_{h,ϵ}) to be sufficiently small.

Pick a sequence of values x_{n} of length j := max(n_{h,ϵ}, k) which is an initial segment of a member of O. Extend that finite sequence to have a value just under x_{j−1} + ϵ/2 at the places j through h(j). Extend again to have a value just under x_{h(j)} + ϵ/2 at the places h(j) + 1 through h(h(j) + 1). Extend again, by adding almost another ϵ/2 to the last value, from the next place, say s, until h(s). Continue this process for at least 2/ϵ + 1-many steps, at which point pick the Cauchy sequence which is constant from that point on. The upshot is, beyond N the sequence has increased by more than 1.

References

[1] Michael Beeson, “The nonderivability in intuitionistic formal systems of theorems on the continuity of effective operations,” Journal of Symbolic Logic, v. 40 (1975), p. 321-346 [2] Josef Berger and Douglas Bridges, “A Fan-theoretic equivalent of the an-

tithesis of Speckers Theorem,” Proc. Koninklijke Nederlandse Akad. Wetenschappen (Indag. Math., N.S.), v. 18 (2007), p. 195-202

[3] Josef Berger and Douglas Bridges, “The anti-Specker property, a Heine-Borel property, and uniform continuity,” Archive for Mathematical Logic, v. 46 (2008), p. 583-592

[4] Douglas Bridges, “Constructive notions of equicontinuity,” Archive for Mathematical Logic, v. 48 (2009), p. 437-448

[5] Josef Berger and Douglas Bridges, “Rearranging series constructively,” Journal of Universal Computer Science, v. 15 (2009), p. 3160-3168

[6] Josef Berger, Douglas Bridges, Hannes Diener and Helmut Schwichtenberg, “Constructive aspects of Riemann’s permutation theorem for series,” in preparation

[7] Josef Berger, Douglas Bridges, and Erik Palmgren, “Double sequences, almost Cauchyness, and BD-N,” to appear

[8] Douglas Bridges, “Uniform equicontinuity and the antithesis of Specker’s Theorem,” unpublished

[9] Douglas Bridges, “Inheriting the anti-Specker property”, preprint, University of Canterbury, NewZealand, 2009, submitted for publication

[10] Douglas Bridges, Hajime Ishihara, Peter Schuster, and Luminita Vita, “Strong continuity implies uniformly sequential continuity,” Archive for Mathematical Logic, v. 44 (2005), p. 887-895

[11] Robin J. Grayson, “Heyting-valued models for intuitionistic set theory,” in Applications of Sheaves, Lecture Notes in Mathematics, vol. 753 (eds. Fourman, Mulvey, Scott), Springer, Berlin Heidelberg New York, 1979, p. 402-414

[12] Robin J. Grayson, “Heyting-valued semantics,” in Logic Colloquium ’82, Studies in Logic and the Foundations of Mathematics, vol. 112 (eds. Lolli, Longo, Marcja) , North-Holland, Amsterdam New York Oxford, 1984, p. 181-208

[13] Hajime Ishihara, “Continuity and nondiscontinuity in constructive mathematics,” Journal of Symbolic Logic, v. 56 (1991), p. 1349-1354

[14] Hajime Ishihara, “Continuity properties in constructive mathematics,” Journal of Symbolic Logic, v. 57 (1992), p. 557-565

[15] Hajime Ishihara, “Sequential continuity in constructive mathematics,” in Combinatorics, Computability, and Logic (eds. Calude, Dinneen, and Sburlan), Springer, London, 2001, p. 5-12 [16] Hajime Ishihara and Peter Schuster, “A Continuity principle, a version

of Baire’s Theorem and a boundedness principle,” Journal of Symbolic Logic, v. 73 (2008), p. 1354-1360

[17] Hajime Ishihara and Satoru Yoshida, “A Constructive look at the completeness of D(R),” Journal of Symbolic Logic, v. 67 (2002), p. 1511-1519

[18] Peter Lietz, “From Constructive Mathematics to Computable Analysis via the Realizability Interpretation,” Ph.D. thesis, Technische Universität Darmstadt, 2004, http://www.mathematik.tu-darmstadt.de/ streicher/THESES/lietz.pdf.gz

[19] Robert Lubarsky, “Geometric Spaces with No Points,” Journal of Logic and Analysis, v. 2 No. 6 (2010), p. 1-10, http://logicandanalysis.org/, doi: 10.4115/jla2010.2.6

[20] Robert Lubarsky, “On the Failure of BD-N and BD, and an application to the anti-Specker Property,” Journal of Symbolic Logic, to appear