23 found
Order:
  1.  59
    The Bolzano–Weierstrass Theorem is the jump of Weak Kőnig’s Lemma.Vasco Brattka, Guido Gherardi & Alberto Marcone - 2012 - Annals of Pure and Applied Logic 163 (6):623-655.
  2.  24
    Searching for an analogue of atr0 in the Weihrauch lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
    There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  33
    How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
    We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the class (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  4.  54
    The veblen functions for computability theorists.Alberto Marcone & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (2):575 - 602.
    We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) "If X is a well-ordering, then so is ε X ", and (2) "If X is a well-ordering, then so is φ(α, X)", where α is a fixed computable ordinal and φ represents the two-placed Veblen function. For the former statement, we show that ω iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ${\mathrm{A}\mathrm{C}\mathrm{A}}_{0}^{+}$ over RCA₀. To prove the (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  5.  49
    Reverse mathematics and the equivalence of definitions for well and better quasi-orders.Peter Cholak, Alberto Marcone & Reed Solomon - 2004 - Journal of Symbolic Logic 69 (3):683-712.
  6. The maximal linear extension theorem in second order arithmetic.Alberto Marcone & Richard A. Shore - 2011 - Archive for Mathematical Logic 50 (5-6):543-564.
    We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  7.  20
    On Fraïssé’s conjecture for linear orders of finite Hausdorff rank.Alberto Marcone & Antonio Montalbán - 2009 - Annals of Pure and Applied Logic 160 (3):355-367.
    We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ2, the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in +“φ2 is well-ordered” and, over , implies +“φ2 is well-ordered”.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  8.  20
    The open and clopen Ramsey theorems in the Weihrauch lattice.Alberto Marcone & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (1):316-351.
    We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  23
    Linear extensions of partial orders and reverse mathematics.Emanuele Frittaion & Alberto Marcone - 2012 - Mathematical Logic Quarterly 58 (6):417-423.
    We introduce the notion of τ-like partial order, where τ is one of the linear order types ω, ω*, ω + ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form “any τ-like partial order has a τ-like linear extension” and “any τ-like partial order is embeddable into τ” . Working in the framework of reverse mathematics, we show that these (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  18
    Linear orders: When embeddability and epimorphism agree.Riccardo Camerlo, Raphaël Carroy & Alberto Marcone - 2019 - Journal of Mathematical Logic 19 (1):1950003.
    When a linear order has an order preserving surjection onto each of its suborders, we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is a [Formula: see text]-complete set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  19
    Reverse mathematics and initial intervals.Emanuele Frittaion & Alberto Marcone - 2014 - Annals of Pure and Applied Logic 165 (3):858-879.
    In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  12.  41
    Lebesgue numbers and Atsuji spaces in subsystems of second-order arithmetic.Mariagnese Giusto & Alberto Marcone - 1998 - Archive for Mathematical Logic 37 (5-6):343-362.
    We study Lebesgue and Atsuji spaces within subsystems of second order arithmetic. The former spaces are those such that every open covering has a Lebesgue number, while the latter are those such that every continuous function defined on them is uniformly continuous. The main results we obtain are the following: the statement “every compact space is Lebesgue” is equivalent to $\hbox{\sf WKL}_0$ ; the statements “every perfect Lebesgue space is compact” and “every perfect Atsuji space is compact” are equivalent to (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  13.  37
    Reverse mathematics, well-quasi-orders, and Noetherian spaces.Emanuele Frittaion, Matthew Hendtlass, Alberto Marcone, Paul Shafer & Jeroen Van der Meeren - 2016 - Archive for Mathematical Logic 55 (3):431-459.
    A quasi-order Q induces two natural quasi-orders on $${\mathcal{P}(Q)}$$, but if Q is a well-quasi-order, then these quasi-orders need not necessarily be well-quasi-orders. Nevertheless, Goubault-Larrecq (Proceedings of the 22nd Annual IEEE Symposium 4 on Logic in Computer Science (LICS’07), pp. 453–462, 2007) showed that moving from a well-quasi-order Q to the quasi-orders on $${\mathcal{P}(Q)}$$ preserves well-quasi-orderedness in a topological sense. Specifically, Goubault-Larrecq proved that the upper topologies of the induced quasi-orders on $${\mathcal{P}(Q)}$$ are Noetherian, which means that they contain no (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  24
    Borel quasi-orderings in subsystems of second-order arithmetic.Alberto Marcone - 1991 - Annals of Pure and Applied Logic 54 (3):265-291.
    We study the provability in subsystems of second-order arithmetic of two theorems of Harrington and Shelah [6] about Borel quasi-orderings of the reals. These theorems turn out to be provable in ATR0, thus giving further evidence to the observation that ATR0 is the minimal subsystem of second-order arithmetic in which significant portion of descriptive set theory can be developed. As in [6] considering the lightface versions of the theorems will be instrumental in their proof and the main techniques employed will (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  15.  70
    The complexity of continuous embeddability between dendrites.Alberto Marcone & Christian Rosendal - 2004 - Journal of Symbolic Logic 69 (3):663-673.
    We show that the quasi-order of continuous embeddability between finitely branching dendrites (a natural class of fairly simple compacta) is $\Sigma_1^1$ -complete. We also show that embeddability between countable linear orders with infinitely many colors is $\Sigma_1^1$ -complete.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  28
    (Extra)Ordinary Equivalences with the Ascending/Descending Sequence Principle.Marta Fiori-Carones, Alberto Marcone, Paul Shafer & Giovanni Soldà - 2024 - Journal of Symbolic Logic 89 (1):262-307.
    We analyze the axiomatic strength of the following theorem due to Rival and Sands [28] in the style of reverse mathematics. Every infinite partial order P of finite width contains an infinite chain C such that every element of P is either comparable with no element of C or with infinitely many elements of C. Our main results are the following. The Rival–Sands theorem for infinite partial orders of arbitrary finite width is equivalent to $\mathsf {I}\Sigma ^0_{2} + \mathsf {ADS}$ (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  37
    Interval Orders and Reverse Mathematics.Alberto Marcone - 2007 - Notre Dame Journal of Formal Logic 48 (3):425-448.
    We study the reverse mathematics of interval orders. We establish the logical strength of the implications among various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain 2 \oplus 2. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  18.  31
    Coloring linear orders with Rado's partial order.Riccardo Camerlo & Alberto Marcone - 2007 - Mathematical Logic Quarterly 53 (3):301-305.
    Let ⪯R be the preorder of embeddability between countable linear orders colored with elements of Rado's partial order . We show that ⪯R has fairly high complexity with respect to Borel reducibility , although its exact classification remains open.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  23
    Polish metric spaces with fixed distance set.Riccardo Camerlo, Alberto Marcone & Luca Motto Ros - 2020 - Annals of Pure and Applied Logic 171 (10):102832.
    We study Polish spaces for which a set of possible distances $A \subseteq R^+$ is fixed in advance. We determine, depending on the properties of A, the complexity of the collection of all Polish metric spaces with distances in A, obtaining also example of sets in some Wadge classes where not many natural examples are known. Moreover we describe the properties that A must have in order that all Polish spaces with distances in that set belong to a given class, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  49
    Computing maximal chains.Alberto Marcone, Antonio Montalbán & Richard A. Shore - 2012 - Archive for Mathematical Logic 51 (5-6):651-660.
    In (Fund Math 60:175–186 1967), Wolk proved that every well partial order (wpo) has a maximal chain; that is a chain of maximal order type. (Note that all chains in a wpo are well-ordered.) We prove that such maximal chain cannot be found computably, not even hyperarithmetically: No hyperarithmetic set can compute maximal chains in all computable wpos. However, we prove that almost every set, in the sense of category, can compute maximal chains in all computable wpos. Wolk’s original result (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  21.  27
    The Set of Better Quasi Orderings is ∏21.Alberto Marcone - 1995 - Mathematical Logic Quarterly 41 (3):373-383.
    In this paper we give a proof of the II12-completeness of the set of countable better quasi orderings . This result was conjectured by Clote in [2] and proved by the author in his Ph.d. thesis [6] . Here we prove it using Simpson's definition of better quasi ordering and as little bqo theory as possible.
    Direct download  
     
    Export citation  
     
    Bookmark  
  22.  26
    Addendum to: “The Bolzano–Weierstrass theorem is the jump of weak Kőnig's lemma” [Ann. Pure Appl. Logic 163 (6) (2012) 623–655]. [REVIEW]Vasco Brattka, Andrea Cettolo, Guido Gherardi, Alberto Marcone & Matthias Schröder - 2017 - Annals of Pure and Applied Logic 168 (8):1605-1608.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  23.  26
    (1 other version)Jeremy Avigad. Formalizing forcing arguments in subsystems of second-order arithmetic. Annals of pure and applied logic, vol. 82 , pp. 165–191. [REVIEW]Alberto Marcone - 2001 - Bulletin of Symbolic Logic 7 (3):390-391.