Year:

  1.  1
    Teachers, Learners, and Oracles.Achilles Beros & Colin de la Higuera - 2019 - Notre Dame Journal of Formal Logic 60 (1):13-26.
    We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2. Layered Posets and Kunen’s Universal Collapse.Sean Cox - 2019 - Notre Dame Journal of Formal Logic 60 (1):27-60.
    We develop the theory of layered posets and use the notion of layering to prove a new iteration theorem is κ-cc, as long as direct limits are used sufficiently often. This iteration theorem simplifies and generalizes the various chain condition arguments for universal Kunen iterations in the literature on saturated ideals, especially in situations where finite support iterations are not possible. We also provide two applications:1 For any n≥1, a wide variety of <ωn−1-closed, ωn+1-cc posets of size ωn+1 can consistently (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  2
    Abstraction Principles and the Classification of Second-Order Equivalence Relations.Sean C. Ebels-Duggan - 2019 - Notre Dame Journal of Formal Logic 60 (1):77-117.
    This article improves two existing theorems of interest to neologicist philosophers of mathematics. The first is a classification theorem due to Fine for equivalence relations between concepts definable in a well-behaved second-order logic. The improved theorem states that if an equivalence relation E is defined without nonlogical vocabulary, then the bicardinal slice of any equivalence class—those equinumerous elements of the equivalence class with equinumerous complements—can have one of only three profiles. The improvements to Fine’s theorem allow for an analysis of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  1
    Disjoint $N$ -Amalgamation and Pseudofinite Countably Categorical Theories.Alex Kruckman - 2019 - Notre Dame Journal of Formal Logic 60 (1):139-160.
    Disjoint n-amalgamation is a condition on a complete first-order theory specifying that certain locally consistent families of types are also globally consistent. In this article, we show that if a countably categorical theory T admits an expansion with disjoint n-amalgamation for all n, then T is pseudofinite. All theories which admit an expansion with disjoint n-amalgamation for all n are simple, but the method can be extended, using filtrations of Fraïssé classes, to show that certain nonsimple theories are pseudofinite. As (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5. Levels of Uniformity.Rutger Kuyper - 2019 - Notre Dame Journal of Formal Logic 60 (1):119-138.
    We introduce a hierarchy of degree structures between the Medvedev and Muchnik lattices which allow varying amounts of nonuniformity. We use these structures to introduce the notion of the uniformity of a Muchnik reduction, which expresses how uniform a reduction is. We study this notion for several well-known reductions from algorithmic randomness. Furthermore, since our new structures are Brouwer algebras, we study their propositional theories. Finally, we study if our new structures are elementarily equivalent to each other.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  1
    $\Pi ^{0}_{1}$ -Encodability and Omniscient Reductions.Benoit Monin & Ludovic Patey - 2019 - Notre Dame Journal of Formal Logic 60 (1):1-12.
    A set of integers A is computably encodable if every infinite set of integers has an infinite subset computing A. By a result of Solovay, the computably encodable sets are exactly the hyperarithmetic ones. In this article, we extend this notion of computable encodability to subsets of the Baire space, and we characterize the Π10-encodable compact sets as those which admit a nonempty Σ11-subset. Thanks to this equivalence, we prove that weak weak König’s lemma is not strongly computably reducible to (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  1
    Tame Topology Over Dp-Minimal Structures.Pierre Simon & Erik Walsberg - 2019 - Notre Dame Journal of Formal Logic 60 (1):61-76.
    In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is a good notion of dimension on definable sets, definable functions are almost everywhere continuous, and definable sets are finite unions of graphs of definable continuous “multivalued functions.” This generalizes known statements about weakly o-minimal, C-minimal, and P-minimal theories.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
 Previous issues
  
Next issues