Switch to: References

Add citations

You must login to add citations.
  1. Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
    The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • A Nonstandard Counterpart of WWKL.Stephen G. Simpson & Keita Yokoyama - 2011 - Notre Dame Journal of Formal Logic 52 (3):229-243.
    In this paper, we introduce a system of nonstandard second-order arithmetic $\mathsf{ns}$-$\mathsf{WWKL_0}$ which consists of $\mathsf{ns}$-$\mathsf{BASIC}$ plus Loeb measure property. Then we show that $\mathsf{ns}$-$\mathsf{WWKL_0}$ is a conservative extension of $\mathsf{WWKL_0}$ and we do Reverse Mathematics for this system.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Refining the Taming of the Reverse Mathematics Zoo.Sam Sanders - 2018 - Notre Dame Journal of Formal Logic 59 (4):579-597.
    Reverse mathematics is a program in the foundations of mathematics. It provides an elegant classification in which the majority of theorems of ordinary mathematics fall into only five categories, based on the “big five” logical systems. Recently, a lot of effort has been directed toward finding exceptional theorems, that is, those which fall outside the big five. The so-called reverse mathematics zoo is a collection of such exceptional theorems. It was previously shown that a number of uniform versions of the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Set Existence Principles and Closure Conditions: Unravelling the Standard View of Reverse Mathematics.Benedict Eastaugh - 2019 - Philosophia Mathematica 27 (2):153-176.
    It is a striking fact from reverse mathematics that almost all theorems of countable and countably representable mathematics are equivalent to just five subsystems of second order arithmetic. The standard view is that the significance of these equivalences lies in the set existence principles that are necessary and sufficient to prove those theorems. In this article I analyse the role of set existence principles in reverse mathematics, and argue that they are best understood as closure conditions on the powerset of (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Comparing the Strength of Diagonally Nonrecursive Functions in the Absence of Induction.François G. Dorais, Jeffry L. Hirst & Paul Shafer - 2015 - Journal of Symbolic Logic 80 (4):1211-1235.
    We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • On Notions of Computability-Theoretic Reduction Between Π21 Principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.
    Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Randomness Notions and Reverse Mathematics.André Nies & Paul Shafer - 2020 - Journal of Symbolic Logic 85 (1):271-299.
    We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for each Z there is an X that is ${\cal R}$-random relative to Z. We show that the equivalence between 2-randomness and being infinitely often C-incompressible is provable in $RC{A_0}$. We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Separating Principles Below WKL0.Stephen Flood & Henry Towsner - 2016 - Mathematical Logic Quarterly 62 (6):507-529.
    No categories
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • Subsystems of Second-Order Arithmetic Between RCA0 and WKL0.Carl Mummert - 2008 - Archive for Mathematical Logic 47 (3):205-210.
    We study the Lindenbaum algebra ${\fancyscript{A}}$ (WKL o, RCA o) of sentences in the language of second-order arithmetic that imply RCA o and are provable from WKL o. We explore the relationship between ${\Sigma^1_1}$ sentences in ${\fancyscript{A}}$ (WKL o, RCA o) and ${\Pi^0_1}$ classes of subsets of ω. By applying a result of Binns and Simpson (Arch. Math. Logic 43(3), 399–414, 2004) about ${\Pi^0_1}$ classes, we give a specific embedding of the free distributive lattice with countably many generators into ${\fancyscript{A}}$ (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
    A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   27 citations  
  • Algorithmic Randomness, Reverse Mathematics, and the Dominated Convergence Theorem.Jeremy Avigad, Edward T. Dean & Jason Rute - 2012 - Annals of Pure and Applied Logic 163 (12):1854-1864.
    We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • The Dirac Delta Function in Two Settings of Reverse Mathematics.Sam Sanders & Keita Yokoyama - 2012 - Archive for Mathematical Logic 51 (1-2):99-121.
    The program of Reverse Mathematics (Simpson 2009) has provided us with the insight that most theorems of ordinary mathematics are either equivalent to one of a select few logical principles, or provable in a weak base theory. In this paper, we study the properties of the Dirac delta function (Dirac 1927; Schwartz 1951) in two settings of Reverse Mathematics. In particular, we consider the Dirac Delta Theorem, which formalizes the well-known property ${\int_\mathbb{R}f(x)\delta(x)\,dx=f(0)}$ of the Dirac delta function. We show that (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Program Extraction for 2-Random Reals.Alexander P. Kreuzer - 2013 - Archive for Mathematical Logic 52 (5-6):659-666.
    Let ${2-\textsf{RAN}}$ be the statement that for each real X a real 2-random relative to X exists. We apply program extraction techniques we developed in Kreuzer and Kohlenbach (J. Symb. Log. 77(3):853–895, 2012. doi:10.2178/jsl/1344862165), Kreuzer (Notre Dame J. Formal Log. 53(2):245–265, 2012. doi:10.1215/00294527-1715716) to this principle. Let ${{\textsf{WKL}_0^\omega}}$ be the finite type extension of ${\textsf{WKL}_0}$ . We obtain that one can extract primitive recursive realizers from proofs in ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN}}$ , i.e., if ${{\textsf{WKL}_0^\omega} + \Pi^0_1-{\textsf{CP}} + 2-\textsf{RAN} (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Mass Problems and Measure-Theoretic Regularity.Stephen G. Simpson - 2009 - Bulletin of Symbolic Logic 15 (4):385-409.
    A well known fact is that every Lebesgue measurable set is regular, i.e., it includes an F$_{\sigma}$ set of the same measure. We analyze this fact from a metamathematical or foundational standpoint. We study a family of Muchnik degrees corresponding to measure-theoretic regularity at all levels of the effective Borel hierarchy. We prove some new results concerning Nies's notion of LR-reducibility. We build some $\omega$-models of RCA$_0$which are relevant for the reverse mathematics of measure-theoretic regularity.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Uniform Almost Everywhere Domination.Peter Cholak, Noam Greenberg & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (3):1057 - 1072.
    We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Almost Everywhere Domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
    A Turing degree a is said to be almost everywhere dominating if, for almost all $X \in 2^{\omega}$ with respect to the "fair coin" probability measure on $2^{\omega}$ , and for all g: $\omega \rightarrow \omega$ Turing reducible to X, there exists f: $\omega \rightarrow \omega$ of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • 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   21 citations  
  • 10th Asian Logic Conference: Sponsored by the Association for Symbolic Logic.Toshiyasu Arai - 2009 - Bulletin of Symbolic Logic 15 (2):246-265.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • A Non-Standard Construction of Haar Measure and Weak König's Lemma.Kazuyuki Tanaka & Takeshi Yamazaki - 2000 - Journal of Symbolic Logic 65 (1):173-186.
    In this paper, we show within RCA 0 that weak Konig's lemma is necessary and sufficient to prove that any (separable) compact group has a Haar measure. Within WKL 0 , a Haar measure is constructed by a non-standard method based on a fact that every countable non-standard model of WKL 0 has a proper initial part isomorphic to itself [10].
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Located Sets and Reverse Mathematics.Mariagnese Giusto & Stephen G. Simpson - 2000 - Journal of Symbolic Logic 65 (3):1451-1480.
    Let X be a compact metric space. A closed set K $\subseteq$ X is located if the distance function d(x, K) exists as a continuous real-valued function on X; weakly located if the predicate d(x, K) $>$ r is Σ 0 1 allowing parameters. The purpose of this paper is to explore the concepts of located and weakly located subsets of a compact separable metric space in the context of subsystems of second order arithmetic such as RCA 0 , WKL (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  • A Study of Singular Points and Supports of Measures in Reverse Mathematics.Xiaokang Yu - 1996 - Annals of Pure and Applied Logic 79 (2):211-219.
    Arithmetical comprehension is proved to be equivalent to the enumerability of singular points of any measure on the Cantor space. It is provable in ACA0 that any perfect closed subset of [0, 1] is the support of some continuous positive linear functional on C[0, 1].
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Riesz Representation Theorem, Borel Measures and Subsystems of Second-Order Arithmetic.Xiaokang Yu - 1993 - Annals of Pure and Applied Logic 59 (1):65-78.
    Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability of Borel sets for (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • 1998 European Summer Meeting of the Association for Symbolic Logic.S. Buss - 1999 - Bulletin of Symbolic Logic 5 (1):59-153.
  • A Measure-Theoretic Proof of Turing Incomparability.Chris J. Conidis - 2010 - Annals of Pure and Applied Logic 162 (1):83-88.
    We prove that if is an ω-model of weak weak König’s lemma and , is incomputable, then there exists , such that A and B are Turing incomparable. This extends a recent result of Kučera and Slaman who proved that if is a Scott set and , Aω, is incomputable, then there exists , Bω, such that A and B are Turing incomparable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Reverse Mathematical Bounds for the Termination Theorem.Silvia Steila & Keita Yokoyama - 2016 - Annals of Pure and Applied Logic 167 (12):1213-1241.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Nonstandard Second-Order Arithmetic and Riemannʼs Mapping Theorem.Yoshihiro Horihata & Keita Yokoyama - 2014 - Annals of Pure and Applied Logic 165 (2):520-551.
    In this paper, we introduce systems of nonstandard second-order arithmetic which are conservative extensions of systems of second-order arithmetic. Within these systems, we do reverse mathematics for nonstandard analysis, and we can import techniques of nonstandard analysis into analysis in weak systems of second-order arithmetic. Then, we apply nonstandard techniques to a version of Riemannʼs mapping theorem, and show several different versions of Riemannʼs mapping theorem.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Separating Fragments of Wlem, Lpo, and Mp.Matt Hendtlass & Robert Lubarsky - 2016 - Journal of Symbolic Logic 81 (4):1315-1343.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Complex Analysis in Subsystems of Second Order Arithmetic.Keita Yokoyama - 2007 - Archive for Mathematical Logic 46 (1):15-35.
    This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the other hand, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations