Recent zbMATH articles in MSC 03F60
https://zbmath.org/atom/cc/03F60
2021-05-28T16:06:00+00:00
Werkzeug
Weihrauch-completeness for layerwise computability.
https://zbmath.org/1459.03069
2021-05-28T16:06:00+00:00
"Pauly, Arno"
https://zbmath.org/authors/?q=ai:pauly.arno-m
"FouchÃ©, Willem"
https://zbmath.org/authors/?q=ai:fouche.willem-louw
"Davie, George"
https://zbmath.org/authors/?q=ai:davie.george
Summary: We introduce the notion of being Weihrauch-complete for layerwise computability and provide several natural examples related to complex oscillations, the law of the iterated logarithm and Birkhoff's theorem. We also consider hitting time operators, which share the Weihrauch degree of the former examples but fail to be layerwise computable.
A bound for Dickson's lemma.
https://zbmath.org/1459.03092
2021-05-28T16:06:00+00:00
"Berger, Josef"
https://zbmath.org/authors/?q=ai:berger.josef
"Schwichtenberg, Helmut"
https://zbmath.org/authors/?q=ai:schwichtenberg.helmut
Summary: We consider a special case of Dickson's lemma: for any two functions \(f,g\) on the natural numbers there are two numbers \(i<j\) such that both \(f\) and \(g\) weakly increase on them, i.e., \(f_i\leq f_j\) and \(g_i \leq g_j\). By a combinatorial argument (due to the first author) a simple bound for such \(i,j\) is constructed. The combinatorics is based on the finite pigeon hole principle and results in a descent lemma. From the descent lemma one can prove Dickson's lemma, then guess what the bound might be, and verify it by an appropriate proof. We also extract (via realizability) a bound from (a formalization of) our proof of the descent lemma.
A density theorem for hierarchies of limit spaces over separable metric spaces.
https://zbmath.org/1459.03093
2021-05-28T16:06:00+00:00
"Petrakis, Iosif"
https://zbmath.org/authors/?q=ai:petrakis.iosif
Summary: In this paper, we show, almost constructively, a density theorem for hierarchies of limit spaces over separable metric spaces. Our proof is not fully constructive, since it relies on the constructively not acceptable fact that the limit relation induced by a metric space satisfies Urysohn's axiom for limit spaces. By adding the condition of strict positivity to Normann's notion of probabilistic projection we establish a relation between strictly positive general probabilistic selections on a sequential space and general approximation functions on a limit space. Showing that Normann's result, that a (general and strictly positive) probabilistic selection is definable on a separable metric space, admits a constructive proof, and based on the constructively shown in [the author, Ann. Pure Appl. Logic 167, No. 9, 737--752 (2016; Zbl 1432.03083)] Cartesian closure property of the category of limit spaces with general approximations, our quite effective density theorem follows. This work, which is a continuation of [loc. cit.], is within computability theory at higher types and Normann's Program of Internal Computability.
For the entire collection see [Zbl 1360.68012].