34 found
Order:
  1.  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   5 citations  
  2.  39
    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   13 citations  
  3.  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 (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  4.  6
    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  
  5.  10
    On the Equimorphism Types of Linear Orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  6.  34
    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   5 citations  
  7.  6
    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  
  8.  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  
  9.  12
    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   8 citations  
  10.  9
    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   5 citations  
  11.  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 (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  13
    Computable Structures in Generic Extensions.Julia Knight, Antonio Montalbán & Noah Schweber - 2016 - Journal of Symbolic Logic 81 (3):814-832.
  13.  8
    On the Π11‐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   3 citations  
  14.  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  
  15.  15
    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  
  16.  25
    Embedding and Coding Below a 1-Generic Degree.Noam Greenberg & Antonio Montalbán - 2003 - Notre Dame Journal of Formal Logic 44 (4):200-216.
  17.  34
    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   2 citations  
  18.  37
    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  
  19.  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   1 citation  
  20.  19
    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  
  21.  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.
  22.  8
    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  
  23.  9
    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  
  24.  26
    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 (8 more)  
     
    Export citation  
     
    Bookmark  
  25.  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.
  26.  19
    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).
  27.  11
    Undecidability of the Theories of Classes of Structures.Asher M. Kach & Antonio Montalbán - 2014 - Journal of Symbolic Logic 79 (4):1001-1019.
  28.  16
    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  
  29.  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  
  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.  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  
  32.  3
    Priority Arguments Via True Stages.Antonio Montalbán - 2014 - Journal of Symbolic Logic 79 (4):1315-1335.
  33.  2
    Classes of Structures with No Intermediate Isomorphism Problems.Antonio Montalbán - 2016 - Journal of Symbolic Logic 81 (1):127-150.
  34. Copyable Structures.Antonio Montalbán - 2009 - Journal of Symbolic Logic 78 (4):1199-1217.