20 found
Sort by:
  1. Alan Dow, Isaac Goldbring, Warren Goldfarb, Joseph Miller, Toniann Pitassi, Antonio Montalbán, Grigor Sargsyan, Sergei Starchenko & Moshe Vardi (2013). Madison, WI, USA March 31–April 3, 2012. Bulletin of Symbolic Logic 19 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Noam Greenberg, Antonio Montalbán & Theodore A. Slaman (2013). Relative to Any Non-Hyperarithmetic Set. Journal of Mathematical Logic 13 (1):1250007.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Antonio Montalbán (2013). A Fixed Point for the Jump Operator on Structures. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles McCoy & Antonio Montalbán (2012). Isomorphism Relations on Computable Structures. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Alberto Marcone, Antonio Montalbán & Richard A. Shore (2012). Computing Maximal Chains. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán (2011). Computability of Fraïssé Limits. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  7. Alberto Marcone & Antonio Montalbán (2011). The Veblen Functions for Computability Theorists. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  8. Antonio Montalbán (2011). Open Questions in Reverse Mathematics. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  9. Bakhadyr Khoussainov & Antonio Montalbán (2010). A Computable ℵ 0 -Categorical Structure Whose Theory Computes True Arithmetic. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Alberto Marcone & Antonio Montalbán (2009). On Fraïssé's Conjecture for Linear Orders of Finite Hausdorff Rank. Annals of Pure and Applied Logic 160 (3):355-367.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. 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). Conference on Computability, Complexity and Randomness. Bulletin of Symbolic Logic 14 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  12. Antonio Montalbán (2008). On the Π11‐Separation Principle. Mathematical Logic Quarterly 54 (6):563-578.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Jeremy Avigad, Sy Friedman, Akihiro Kanamori, Elisabeth Bouscaren, Philip Kremer, Claude Laflamme, Antonio Montalbán, Justin Moore & Helmut Schwichtenberg (2007). Montréal, Québec, Canada May 17–21, 2006. Bulletin of Symbolic Logic 13 (1).
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  14. Antonio Montalbán (2007). On the Equimorphism Types of Linear Orderings. Bulletin of Symbolic Logic 13 (1):71-99.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  15. Barbara F. Csima, Antonio Montalbán & Richard A. Shore (2006). Boolean Algebras, Tarski Invariants, and Index Sets. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Antonio Montalbán (2006). Equivalence Between Fraïssé's Conjecture and Jullien's Theorem. Annals of Pure and Applied Logic 139 (1):1-42.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Antonio Montalbán (2006). Indecomposable Linear Orderings and Hyperarithmetic Analysis. Journal of Mathematical Logic 6 (01):89-120.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Antonio Montalbán (2006). There is No Ordering on the Classes in the Generalized High/Low Hierarchies. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  19. Antonio Montalbán (2005). Up to Equimorphism, Hyperarithmetic Is Recursive. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  20. Antonio Montalbán (2003). Embedding Jump Upper Semilattices Into the Turing Degrees. Journal of Symbolic Logic 68 (3):989-1014.
    We prove that every countable jump upper semilattice can be embedded in D, where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, and D is the jusl of Turing degrees. As a corollary we get that the existential theory of $\langle D, \leq_{T}, \vee, '\rangle$ is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier free (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation