20 found
Order:
  1.  7
    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.  7
    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 (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  3. 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 (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  4.  12
    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.
  5.  10
    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 RCA 0 to ATR 0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR 0 over RCA 0.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  6.  3
    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 (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  7.  4
    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 (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  8.  9
    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 (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  9.  47
    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 (8 more)  
     
    Export citation  
     
    My bibliography  
  10.  9
    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-4):431-459.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  11.  3
    Addendum To: “The Bolzano–Weierstrass Theorem is the Jump of Weak Kőnig's Lemma” [Ann. Pure Appl. Logic 163 623–655].Vasco Brattka, Andrea Cettolo, Guido Gherardi, Alberto Marcone & Matthias Schröder - 2017 - Annals of Pure and Applied Logic 168 (8):1605-1608.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  12.  11
    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 (5 more)  
     
    Export citation  
     
    My bibliography  
  13.  7
    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 (4 more)  
     
    Export citation  
     
    My bibliography  
  14.  7
    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 (6 more)  
     
    Export citation  
     
    My bibliography  
  15.  6
    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 (3 more)  
     
    Export citation  
     
    My bibliography  
  16.  3
    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 (3 more)  
     
    Export citation  
     
    My bibliography  
  17.  3
    Review: Jeremy Avigad, Formalizing Forcing Arguments in Subsystems of Second-Order Arithmetic. [REVIEW]Alberto Marcone - 2001 - Bulletin of Symbolic Logic 7 (3):390-391.
  18.  4
    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 (6 more)  
     
    Export citation  
     
    My bibliography  
  19. Avigad Jeremy. 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.
  20. The Set of Better Quasi Orderings is ∏21.Alberto Marcone - 1995 - Mathematical Logic Quarterly 41 (3):373-383.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography