36 found
Order:
  1.  44
    Open Questions in Reverse Mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
    We present a list of open questions in reverse mathematics, including some relevant background information for each question. We also mention some of the areas of reverse mathematics that are starting to be developed and where interesting open question may be found.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  2.  6
    Computable Functors and Effective Interpretability.Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller & Antonio Montalbán - 2017 - Journal of Symbolic Logic 82 (1):77-97.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  3.  39
    Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  4.  37
    Indecomposable Linear Orderings and Hyperarithmetic Analysis.Antonio Montalbán - 2006 - Journal of Mathematical Logic 6 (1):89-120.
    A statement of hyperarithmetic analysis is a sentence of second order arithmetic S such that for every Y⊆ω, the minimum ω-model containing Y of RCA0 + S is HYP, the ω-model consisting of the sets hyperarithmetic in Y. We provide an example of a mathematical theorem which is a statement of hyperarithmetic analysis. This statement, that we call INDEC, is due to Jullien [13]. To the author's knowledge, no other already published, purely mathematical statement has been found with this property (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  5.  10
    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   8 citations  
  6.  43
    Up to Equimorphism, Hyperarithmetic Is Recursive.Antonio Montalbán - 2005 - Journal of Symbolic Logic 70 (2):360 - 378.
    Two linear orderings are equimorphic if each can be embedded into the other. We prove that every hyperarithmetic linear ordering is equimorphic to a recursive one. On the way to our main result we prove that a linear ordering has Hausdorff rank less than $\omega _{1}^{\mathit{CK}}$ if and only if it is equimorphic to a recursive one. As a corollary of our proof we prove that, given a recursive ordinal α, the partial ordering of equimorphism types of linear orderings of (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  7.  14
    Equivalence Between Fraïssé’s Conjecture and Jullien’s Theorem.Antonio Montalbán - 2006 - Annals of Pure and Applied Logic 139 (1):1-42.
    We say that a linear ordering is extendible if every partial ordering that does not embed can be extended to a linear ordering which does not embed either. Jullien’s theorem is a complete classification of the countable extendible linear orderings. Fraïssé’s conjecture, which is actually a theorem, is the statement that says that the class of countable linear ordering, quasiordered by the relation of embeddability, contains no infinite descending chain and no infinite antichain. In this paper we study the strength (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  8.  10
    On the Equimorphism Types of Linear Orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
    §1. Introduction. A linear ordering embedsinto another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to beequimorphicif they can be embedded in each other. This is an equivalence relation, and we call the equivalence classesequimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also obtain results, as the (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  9.  7
    Jump Inversions of Algebraic Structures and Σ‐Definability.Marat Faizrahmanov, Asher Kach, Iskander Kalimullin, Antonio Montalbán & Vadim Puzarenko - 2019 - Mathematical Logic Quarterly 65 (1):37-45.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  7
    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 (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  11.  10
    Borel Functors and Infinitary Interpretations.Matthew Harrison-Trainor, Russell Miller & Antonio Montalbán - 2018 - Journal of Symbolic Logic 83 (4):1434-1456.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  39
    Fraïssé’s Conjecture in [Math]-Comprehension.Antonio Montalbán - 2017 - Journal of Mathematical Logic 17 (2):1750006.
    We prove Fraïssé’s conjecture within the system of Π11-comprehension. Furthermore, we prove that Fraïssé’s conjecture follows from the Δ20-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the Δ20-bqo-ness of 3 is a Π21-statement strictly weaker than Π11-comprehension.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  5
    Coding and Definability in Computable Structures.Antonio Montalbán - 2018 - Notre Dame Journal of Formal Logic 59 (3):285-306.
    These are the lecture notes from a 10-hour course that the author gave at the University of Notre Dame in September 2010. The objective of the course was to introduce some basic concepts in computable structure theory and develop the background needed to understand the author’s research on back-and-forth relations.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  14.  9
    On the Π1 1 -Separation Principle.Antonio Montalbán - 2008 - Mathematical Logic Quarterly 54 (6):563-578.
    We study the proof-theoretic strength of the Π11-separation axiom scheme, and we show that Π11-separation lies strictly in between the Δ11-comprehension and Σ11-choice axiom schemes over RCA0.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  15.  17
    Relative to Any Non-Hyperarithmetic Set.Noam Greenberg, Antonio Montalbán & Theodore A. Slaman - 2013 - Journal of Mathematical Logic 13 (1):1250007.
    We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  36
    Boolean Algebras, Tarski Invariants, and Index Sets.Barbara F. Csima, Antonio Montalbán & Richard A. Shore - 2006 - Notre Dame Journal of Formal Logic 47 (1):1-23.
    Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  17.  15
    Computable Structures in Generic Extensions.Julia Knight, Antonio Montalbán & Noah Schweber - 2016 - Journal of Symbolic Logic 81 (3):814-832.
  18.  26
    Embedding and Coding Below a 1-Generic Degree.Noam Greenberg & Antonio Montalbán - 2003 - Notre Dame Journal of Formal Logic 44 (4):200-216.
  19.  27
    Computability of Fraïssé Limits.Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (1):66 - 93.
    Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  3
    Priority Arguments Via True Stages.Antonio Montalbán - 2014 - Journal of Symbolic Logic 79 (4):1315-1335.
  21.  73
    There is No Ordering on the Classes in the Generalized High/Low Hierarchies.Antonio Montalbán - 2006 - Archive for Mathematical Logic 45 (2):215-231.
    We prove that the existential theory of the Turing degrees, in the language with Turing reduction, 0, and unary relations for the classes in the generalized high/low hierarchy, is decidable. We also show that every finite poset labeled with elements of (where is the partition of induced by the generalized high/low hierarchy) can be embedded in preserving the labels. Note that no condition is imposed on the labels.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  5
    A Fixed Point for the Jump Operator on Structures.Antonio Montalbán - 2013 - Journal of Symbolic Logic 78 (2):425-438.
    Assuming that $0^\#$ exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure $\mathcal A$ such that \[ \textit{Sp}({\mathcal A}) = \{{\bf x}'\colon {\bf x}\in \textit{Sp}({\mathcal A})\}, \] where $\textit{Sp}({\mathcal A})$ is the set of Turing degrees which compute a copy of $\mathcal A$. More interesting than the result itself is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full $n$th-order arithmetic for all $n$, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  23
    Generalized High Degrees Have the Complementation Property.Noam Greenberg, Antonio Montalbán & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (4):1200-1220.
  24.  4
    The Determined Property of Baire in Reverse Math.Eric P. Astor, Damir Dzhafarov, Antonio Montalbán, Reed Solomon & Linda Brown Westrick - 2020 - Journal of Symbolic Logic 85 (1):166-198.
    We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$, which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$. Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of an ω-model (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  19
    Montréal, Québec, Canada May 17–21, 2006.Jeremy Avigad, Sy Friedman, Akihiro Kanamori, Elisabeth Bouscaren, Philip Kremer, Claude Laflamme, Antonio Montalbán, Justin Moore & Helmut Schwichtenberg - 2007 - Bulletin of Symbolic Logic 13 (1).
    Direct download (2 more)  
    Translate
     
     
    Export citation  
     
    Bookmark  
  26.  18
    Conference on Computability, Complexity and Randomness.Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson - 2008 - Bulletin of Symbolic Logic 14 (4):548-549.
  27.  21
    Madison, WI, USA March 31–April 3, 2012.Alan Dow, Isaac Goldbring, Warren Goldfarb, Joseph Miller, Toniann Pitassi, Antonio Montalbán, Grigor Sargsyan, Sergei Starchenko & Moshe Vardi - 2013 - Bulletin of Symbolic Logic 19 (2).
  28.  5
    The Tree of Tuples of a Structure.Matthew Harrison-Trainor & Antonio Montalbán - forthcoming - Journal of Symbolic Logic:1-27.
  29.  11
    Undecidability of the Theories of Classes of Structures.Asher M. Kach & Antonio Montalbán - 2014 - Journal of Symbolic Logic 79 (4):1001-1019.
  30.  23
    A Computable ℵ 0 -Categorical Structure Whose Theory Computes True Arithmetic.Bakhadyr Khoussainov & Antonio Montalbán - 2010 - Journal of Symbolic Logic 75 (2):728-740.
    We construct a computable ℵ0-categorical structure whose first order theory is computably equivalent to the true first order theory of arithmetic.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  31.  27
    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 (7 more)  
     
    Export citation  
     
    Bookmark  
  32.  14
    Computable Polish Group Actions.Alexander Melnikov & Antonio Montalbán - 2018 - Journal of Symbolic Logic 83 (2):443-460.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  33.  2
    Classes of Structures with No Intermediate Isomorphism Problems.Antonio Montalbán - 2016 - Journal of Symbolic Logic 81 (1):127-150.
  34.  4
    Conservativity of Ultrafilters Over Subsystems of Second Order Arithmetic.Antonio Montalbán & Richard A. Shore - 2018 - Journal of Symbolic Logic 83 (2):740-765.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35. Copyable Structures.Antonio Montalbán - 2009 - Journal of Symbolic Logic 78 (4):1199-1217.
  36.  18
    On the Inevitability of the Consistency Operator.Antonio Montalbán & James Walsh - 2019 - Journal of Symbolic Logic 84 (1):205-225.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark