When citing, please refer to the published version.

This item was downloaded from IRIS Università di Bologna (https://cris.unibo.it/)

When citing, please refer to the published version.

This is the final peer-reviewed accepted manuscript of:

V. Brattka, A. Cettolo, G. Gherardi, A. Marcone and M. Schröder (2017) Addendum to “The Bolzano-Weierstrass Theorem is the jump of weak König’s Lemma”. Annals of Pure and Applied Logic, vol 168, no. 8, pp. 1605-1608, DOI:

10.1016/j.apal.2017.04.004

final published version is available online at: http://dx.doi.org/10.1016/j.apal.2017.04.004

Rights / License:

The terms and conditions for the reuse of this version of the manuscript are specified in the

publishing policy. For all terms of use and more information see the publisher's website.

Addendum to: “The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma” [Ann. Pure Appl. Logic 163 (6) (2012) 623–655]

Vasco Brattka^a,b,∗, Andrea Cettolo^c, Guido Gherardi^d, Alberto Marcone^c, Matthias Schröder^e

a DepartmentofMathematics&AppliedMathematics,UniversityofCapeTown,SouthAfrica

bFacultyofComputerScience,UniversitätderBundeswehrMünchen,Germany

cDipartimentodiScienzeMatematiche,InformaticheeFisiche,UniversitàdiUdine,Italy

dDipartimentodiFilosofiaeComunicazione,Universitàdi Bologna,Italy

eFachbereichMathematik,UniversitätDarmstadt,Germany

^{a b s t r a c t}

Thepurposeofthisaddendumistocloseagapintheproofof[1,Theorem 11.2], whichcharacterizesthecomputationalcontentoftheBolzano–WeierstraßTheorem forarbitrarycomputablemetricspaces.

In [1, Theorem 11.2] it is stated that BWTX≡sWK^_X holds for all computable metric spaces X. Here BWT_X denotestheBolzano–WeierstraßTheorem,K^_Xdenotesthejumpofcompactchoiceand≡sWstands for strong Weihrauchequivalence. Werefer the readerto [1]for the definitionof all notions thatare not definedhere.

WhilethereductionBWT_X≤sWK^_X was provedcorrectlyin[1], theproofprovidedfor K^_X≤sWBWT_X containsagapandisonlycorrectforthespecialcaseofcompactX as itstands.Thisfactwaspointedout byoneofus(M.Schröder)andisdue tothefactthatingeneraltheclosureofL⁻¹_X (K) isnotcompact.We closethisgap inthisaddendum.

WestartwithalemmathatshowsthatcompactsetsgiveninK₋^ (X) areeffectivelytotallyboundedina particularsense.ByO(X) wedenotetheset ofopensubsetsofX,representedascomplementsofelements

E-mailaddresses:[email protected](V. Brattka),[email protected](A. Cettolo),

[email protected](G. Gherardi),[email protected](A. Marcone),[email protected](M. Schröder).

of A−(X),i.e.,p isanameofanopenset U ifandonlyifitisaψ₋-nameoftheclosedsetX\ U.Wecall anopenballB(a,r) rational,ifa isapointofthedensesubsetofX (thatisusedtodefinethecomputable metricspaceX) andr≥ 0 is arationalnumber.

Lemma1.LetX beacomputable metricspace.ConsiderthemultivaluedfunctionF_X :⊆ K^₋(X)⇒ O(X)^N with dom(FX)={K ∈ K^₋(X): K = ∅} and suchthat, for each K = ∅, we have (Un)n ∈ FX(K) if and only if thefollowingconditionshold foreach n∈ N:

(1) Un isaunion offinitely manyrational openballsof radius≤ 2⁻ⁿ, (2) K ⊆ Un.

Then FX iscomputable.

Proof. Let X be acomputable metric space and let K ⊆ X bea nonempty compact set. Let pii be a κ^₋-nameofK.This meansthatp:= lim_i→∞p_i isaκ₋-nameforK and,inparticular,foreachn∈ N:

• pi(n) isanameforafinite setofrationalopenballsforeachi∈ N,

• thereexistsk ∈ N suchthatthefinite setof rationalballs givenbyp_k(n) coversK and p_k(n) = p_i(n) foralli≥ k.

Wealsohavethat{p(n): n∈ N} is asetofnamesofallfinitecoversofK by rationalopen balls.Wewant to build asequence ofopen sets (Un)n such that(1) and (2) hold.Wedescribe how to construct aname of ageneric open set U_n for n ∈ N.We start at stage 0 with U_n =∅. At eachstage s = m,i that the computation reaches, we focus on the balls B(a0,r0),. . . ,B(al,rl) given by pi(m) and we check whether r₀,. . . ,r_l ≤ 2⁻ⁿ.If this is nottrue,then we goto stage s+ 1. Otherwise,if thecondition ismet, we add these balls to the name of Un and we check whether pi(m) = pi+1(m). If this is the case we add again B(a0,r0),. . . ,B(al,rl) tothenameofUn.Werepeat thisoperationaslongaswefindthesameopenballs givenbyp_j(m) forj > i.Ifwefindp_i(m)= pj(m) forsomej > i,thenthecomputationgoestostages+ 1.

Weclaim that,for eachn,there existsastageinwhichthecomputationgoesonindefinitely.Consider, infact,{B(a0,r₀),. . . ,B(a_l,r_l)},afiniterationalcoverofK withr₀,. . . ,r_l≤ 2⁻ⁿ,whichexistsbyasimple argument using thecompactnessofK. Since pii is aκ^₋-name ofK,there exists aminimum m,i such that:

• pi(m) isanameforthecover{B(a0,r0),. . . ,B(al,rl)},

• p_i(m)= p_j(m) foreachj > i.

If thealgorithm reachesstage s= m,i, thenit isclearthatthecomputationgoes onindefinitelywithin this stage. Ifthe algorithm neverreaches stage s, then necessarilyit alreadystopped at apreviousstage.

Inboth casesourclaimistrue.

Finally, sincewebuiltthename ofU_n byadding onlyballsof radius≤ 2⁻ⁿ andsincethecomputation stabilizes atafinitestage,itisclearthatconditions(1)and(2)aremet. 2

WenotethateventhoughtheopensetsUn constructedinthepreviousproofarefiniteunionsofrational openballs,thealgorithmdoesnotprovideacorrespondingrationalcoverinafinitaryway.Itratherprovides aninfinitelistofrationalopenballsthatisguaranteedtocontainonlyfinitelymanydistinctrationalballs.

This is aweakform ofeffective totalboundedness and thebest onecan hopefor, given thatthe inputis representedbythejumpofκ₋.

Thefollowinglemma showsthatsequencesthatwechooseinrange(F_X) inaparticularway giveriseto totallyboundedsets.

Lemma2.LetX beametricspaceandletUn⊆ X beafiniteunionofballsofradius≤ 2⁻ⁿforeachn∈ N.

Let(x_n)_n beasequencein X withx_n∈n

i=0U_i.Then{xn: n∈ N} istotallybounded.

Proof. Weobtain{xn : n∈ N}⊆_∞

i=0



Ui∪_i−1

n=0B(xn, 2⁻ⁱ)

andthesetontheright-handsideisclearly totallybounded.Hencethesetontheleft-handsideistotallyboundedandso isitsclosure. 2

Wemention thatit iswell known thatasubsetof ametric spaceis totally boundedif and onlyif any sequenceinithasaCauchysubsequence[2,Exercise 4.3.A (a)].

Nowweusetheprevioustwolemmastocompletetheproofof[1,Theorem11.2].Withintheproofweuse thecanonicalcompletionX ofˆ acomputablemetricspace.Itisknownthatthiscompletionisacomputable metricspaceagainandthatthecanonicalembeddingX → ˆX isacomputableisometrythatpreserves the densesequence[3,Lemma 8.1.6]. Wewill identifyX withasubsetofX viaˆ thisembedding.

Theorem3([1,Theorem11.2]).BWT_X≡sWK^_X forallcomputablemetric spacesX.

Proof. ThereductionBWT_X≤sWK^_X hasbeenprovedin[1],sowefocusonthereductionK^_X≤sWBWT_X. Let(X,d,α) beacomputablemetricspaceandletK⊆ X beanonemptycompactsetgivenbyaκ^₋-name pii.WewanttocomputeapointofK usingBWT_X.Theideaistodefineasequence(x_n)_ninX,working withinthecompletionX ofˆ X andusingtheopensetsbuiltinLemma 1,suchthat{xn : n∈ N} iscompact inX.

Itis clearthatK isacompact subsetofX andˆ that pii canbe consideredasaκ^₋-nameforK in X.ˆ Weconsiderthemap

LXˆ : ˆX^N→ A^₋( ˆX), (xn)n → {x ∈ ˆX : x is a cluster point of (xn)n}.

By [1, Corollary 9.5] L⁻¹_ˆ

X is computable and hence L⁻¹_ˆ

X (K) yields asequence (zm)m inX whoseˆ cluster pointsareexactlytheelementsofK.

LetFXˆ bethe multivaluedfunctiondefinedinLemma 1.We cancompute asequence(Un)n ∈ FXˆ(K).

Since{zm: m∈ N} isnotcompact(andhencenotindom(BWT_X))ingeneral,werefineitrecursivelytoa sequence (yn)n using(Un)n inthe followingway: foreachn∈ N, yn := zmn forthefirst mn thatwefind with z_mn ∈ U0∩ · · · ∩ Un and suchthat m_i < m_n for alli < n. Notethat wecan alwaysfind such ay_n, sinceU0∩ · · · ∩ UncoversK whichisthesetofclusterpointsof(zm)m.Clearlyeverycluster pointof(yn)n

isalsoaclusterpointof(z_m)_m,henceitbelongstoK.

Recall now that (yn)n is asequence of points inX andˆ thatwe want asequence (xn)n inX in order to applyBWT_X. Wecompute(x_n)_n as follows: foreachn∈ N,x_n is thefirstelement thatwefind inthe densesubsetrange(α) suchthatd(xn,yn)< 2⁻ⁿandxn∈ U0∩ · · · ∩ Un,whered alsodenotestheextension ofthemetrictoX.ˆ BydensityofX inX suchˆ anxn alwaysexistsanditisclearthattheclusterpointsof (x_n)_n andthoseof(y_n)_n arethesameinX.ˆ

Now A := {xn : n∈ N} is totally bounded in X by Lemma 2 and hence every sequence in A has a Cauchy subsequence, which has alimit in X,ˆ since X isˆ complete.By construction of (x_n)_n thelimit of suchasubsequenceisinK andhenceinX.ThuseverysequenceinA hasasubsequencethatconvergesin X andhenceA iscompactinX.

Finally,wecanobtainanelementof K byapplyingBWTX to (xn)n. 2

References

[1]VascoBrattka,GuidoGherardi,AlbertoMarcone,TheBolzano–WeierstrasstheoremisthejumpofweakKőnig’slemma, Ann.PureAppl.Logic163(2012)623–655.

[2]RyszardEngelking,GeneralTopology,SigmaSer.PureMath.,vol. 6,Heldermann,Berlin,1989.

[3]KlausWeihrauch,ComputableAnalysis,Springer,Berlin,2000.