5 found
  1.  64
    The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
    The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...)
    Direct download (8 more)  
    Export citation  
    Bookmark   9 citations  
  2.  50
    Partition theorems and computability theory.Joseph R. Mileti - 2005 - Bulletin of Symbolic Logic 11 (3):411-427.
    The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...)
    Direct download (11 more)  
    Export citation  
    Bookmark   8 citations  
  3.  37
    Reverse mathematics and Ramsey's property for trees.Jared Corduan, Marcia J. Groszek & Joseph R. Mileti - 2010 - Journal of Symbolic Logic 75 (3):945-954.
    We show, relative to the base theory RCA₀: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA₀. Ramsey's Theorem for singletons for the complete binary tree is stronger than $B\sum_{2}^{0}$ , hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers to questions, of Chubb, Hirst, and McNicholl [3].
    Direct download (6 more)  
    Export citation  
    Bookmark   5 citations  
  4.  19
    The Complexity of Primes in Computable Unique Factorization Domains.Damir D. Dzhafarov & Joseph R. Mileti - 2018 - Notre Dame Journal of Formal Logic 59 (2):139-156.
    In many simple integral domains, such as Z or Z[i], there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like Z[x] or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show (...)
    Direct download (3 more)  
    Export citation  
  5. Definition 1.1. 1. A tree is a subset T of< such that for all∈ T, if∈< and⊆, then∈ T. 2. If T is a tree and S⊆ T is also a tree, we say that S is a subtree of T. 3. A tree T is bounded if there exists h:→ such that for all∈ T. [REVIEW]Joseph R. Mileti - 2005 - Bulletin of Symbolic Logic 11 (3).