Switch to: References

Add citations

You must login to add citations.
  1. Effective weak and vague convergence of measures on the real line.Diego A. Rojas - 2023 - Archive for Mathematical Logic 63 (1):225-238.
    We expand our effective framework for weak convergence of measures on the real line by showing that effective convergence in the Prokhorov metric is equivalent to effective weak convergence. In addition, we establish a framework for the study of the effective theory of vague convergence of measures. We introduce a uniform notion and a non-uniform notion of vague convergence, and we show that both these notions are equivalent. However, limits under effective vague convergence may not be computable even when they (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The abstract type of the real numbers.Fernando Ferreira - 2021 - Archive for Mathematical Logic 60 (7):1005-1017.
    In finite type arithmetic, the real numbers are represented by rapidly converging Cauchy sequences of rational numbers. Ulrich Kohlenbach introduced abstract types for certain structures such as metric spaces, normed spaces, Hilbert spaces, etc. With these types, the elements of the spaces are given directly, not through the mediation of a representation. However, these abstract spaces presuppose the real numbers. In this paper, we show how to set up an abstract type for the real numbers. The appropriateness of our construction (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Weak computability and representation of reals.Xizhong Zheng & Robert Rettinger - 2004 - Mathematical Logic Quarterly 50 (4-5):431-442.
    The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Uniform Continuity Properties of Preference Relations.Douglas S. Bridges - 2008 - Notre Dame Journal of Formal Logic 49 (1):97-106.
    The anti-Specker property, a constructive version of sequential compactness, is used to prove constructively that a pointwise continuous, order-dense preference relation on a compact metric space is uniformly sequentially continuous. It is then shown that Ishihara's principle BD-ℕ implies that a uniformly sequentially continuous, order-dense preference relation on a separable metric space is uniformly continuous. Converses of these two theorems are also proved.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Gödel's functional interpretation and its use in current mathematics.Ulrich Kohlenbach - 2008 - Dialectica 62 (2):223–267.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Computable irrational numbers with representations of surprising complexity.Ivan Georgiev, Lars Kristiansen & Frank Stephan - 2021 - Annals of Pure and Applied Logic 172 (2):102893.
    Download  
     
    Export citation  
     
    Bookmark  
  • A note on the finitization of Abelian and Tauberian theorems.Thomas Powell - 2020 - Mathematical Logic Quarterly 66 (3):300-310.
    We present finitary formulations of two well known results concerning infinite series, namely Abel's theorem, which establishes that if a series converges to some limit then its Abel sum converges to the same limit, and Tauber's theorem, which presents a simple condition under which the converse holds. Our approach is inspired by proof theory, and in particular Gödel's functional interpretation, which we use to establish quantitative versions of both of these results.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Computability on Regular Subsets of Euclidean Space.Martin Ziegler - 2002 - Mathematical Logic Quarterly 48 (S1):157-181.
    For the computability of subsets of real numbers, several reasonable notions have been suggested in the literature. We compare these notions in a systematic way by relating them to pairs of ‘basic’ ones. They turn out to coincide for full-dimensional convex sets; but on the more general class of regular sets, they reveal rather interesting ‘weaker/stronger’ relations. This is in contrast to single real numbers and vectors where all ‘reasonable’ notions coincide.
    Download  
     
    Export citation  
     
    Bookmark  
  • H‐monotonically computable real numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
    Let h : ℕ → ℚ be a computable function. A real number x is called h-monotonically computable if there is a computable sequence of rational numbers which converges to x h-monotonically in the sense that h|x – xn| ≥ |x – xm| for all n andm > n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h : ℕ → ℚ, we show that the class h-MC coincides (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Representations of the real numbers and of the open subsets of the set of real numbers.Klaus Weihrauch & Christoph Kreitz - 1987 - Annals of Pure and Applied Logic 35 (C):247-260.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • When series of computable functions with varying domains are computable.Iraj Kalantari & Larry Welch - 2013 - Mathematical Logic Quarterly 59 (6):471-493.
    Download  
     
    Export citation  
     
    Bookmark  
  • Specker sequences revisited.Jakob G. Simonsen - 2005 - Mathematical Logic Quarterly 51 (5):532-540.
    Specker sequences are constructive, increasing, bounded sequences of rationals that do not converge to any constructive real. A sequence is said to be a strong Specker sequence if it is Specker and eventually bounded away from every constructive real. Within Bishop's constructive mathematics we investigate non-decreasing, bounded sequences of rationals that eventually avoid sets that are unions of sequences of intervals with rational endpoints. This yields surprisingly straightforward proofs of certain basic results fromconstructive mathematics. Within Russian constructivism, we show how (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • On local non‐compactness in recursive mathematics.Jakob G. Simonsen - 2006 - Mathematical Logic Quarterly 52 (4):323-330.
    A metric space is said to be locally non-compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non-compact iff it is without isolated points.The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a computable sequence (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Constructive notions of equicontinuity.Douglas S. Bridges - 2009 - Archive for Mathematical Logic 48 (5):437-448.
    In the informal setting of Bishop-style constructive reverse mathematics we discuss the connection between the antithesis of Specker’s theorem, Ishihara’s principle BD-N, and various types of equicontinuity. In particular, we prove that the implication from pointwise equicontinuity to uniform sequential equicontinuity is equivalent to the antithesis of Specker’s theorem; and that, for a family of functions on a separable metric space, the implication from uniform sequential equicontinuity to uniform equicontinuity is equivalent to BD-N.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • The anti-Specker property, a Heine–Borel property, and uniform continuity.Josef Berger & Douglas Bridges - 2008 - Archive for Mathematical Logic 46 (7-8):583-592.
    Working within Bishop’s constructive framework, we examine the connection between a weak version of the Heine–Borel property, a property antithetical to that in Specker’s theorem in recursive analysis, and the uniform continuity theorem for integer-valued functions. The paper is a contribution to the ongoing programme of constructive reverse mathematics.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Russian Text Ignored.P. Shanin - 1956 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 2 (1-4):27-36.
    Download  
     
    Export citation  
     
    Bookmark  
  • Monotonically Computable Real Numbers.Robert Rettinger, Xizhong Zheng, Romain Gengler & Burchard von Braunmühl - 2002 - Mathematical Logic Quarterly 48 (3):459-479.
    Area number x is called k-monotonically computable , for constant k > 0, if there is a computable sequence n ∈ ℕ of rational numbers which converges to x such that the convergence is k-monotonic in the sense that k · |x — xn| ≥ |x — xm| for any m > n and x is monotonically computable if it is k-mc for some k > 0. x is weakly computable if there is a computable sequence s ∈ ℕ of (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • A finitization of Littlewood's Tauberian theorem and an application in Tauberian remainder theory.Thomas Powell - 2023 - Annals of Pure and Applied Logic 174 (4):103231.
    Download  
     
    Export citation  
     
    Bookmark  
  • On a simple definition of computable function of a real variable‐with applications to functions of a complex variable.Marian Boykan Pour-El & Jerome Caldwell - 1975 - Mathematical Logic Quarterly 21 (1):1-19.
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • Resolution of the uniform lower bound problem in constructive analysis.Erik Palmgren - 2008 - Mathematical Logic Quarterly 54 (1):65-69.
    In a previous paper we constructed a full and faithful functor ℳ from the category of locally compact metric spaces to the category of formal topologies . Here we show that for a real-valued continuous function f, ℳ factors through the localic positive reals if, and only if, f has a uniform positive lower bound on each ball in the locally compact space. We work within the framework of Bishop constructive mathematics, where the latter notion is strictly stronger than point-wise (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • We Turing Machines Can’t Even Be Locally Ideal Bayesians.Beau Madison Mount - 2016 - Thought: A Journal of Philosophy 5 (4):285-290.
    Vann McGee has argued that, given certain background assumptions and an ought-implies-can thesis about norms of rationality, Bayesianism conflicts globally with computationalism due to the fact that Robinson arithmetic is essentially undecidable. I show how to sharpen McGee's result using an additional fact from recursion theory—the existence of a computable sequence of computable reals with an uncomputable limit. In conjunction with the countable additivity requirement on probabilities, such a sequence can be used to construct a specific proposition to which Bayesianism (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Constructive mathematics.Douglas Bridges - 2008 - Stanford Encyclopedia of Philosophy.
    Download  
     
    Export citation  
     
    Bookmark   33 citations  
  • On the progression of belief.Daxin Liu & Qihui Feng - 2023 - Artificial Intelligence 322 (C):103947.
    Download  
     
    Export citation  
     
    Bookmark  
  • Real numbers, continued fractions and complexity classes.Salah Labhalla & Henri Lombardi - 1990 - Annals of Pure and Applied Logic 50 (1):1-28.
    We study some representations of real numbers. We compare these representations, on the one hand from the viewpoint of recursive functionals, and of complexity on the other hand.The impossibility of obtaining some functions as recursive functionals is, in general, easy. This impossibility may often be explicited in terms of complexity: - existence of a sequence of low complexity whose image is not a recursive sequence, - existence of objects of low complexity but whose images have arbitrarily high time- complexity .Moreover, (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Gödel's Functional Interpretation and its Use in Current Mathematics.Ulrich Kohlenbach - 2008 - Dialectica 62 (2):223-267.
    Download  
     
    Export citation  
     
    Bookmark  
  • Fluctuations, effective learnability and metastability in analysis.Ulrich Kohlenbach & Pavol Safarik - 2014 - Annals of Pure and Applied Logic 165 (1):266-304.
    This paper discusses what kind of quantitative information one can extract under which circumstances from proofs of convergence statements in analysis. We show that from proofs using only a limited amount of the law-of-excluded-middle, one can extract functionals , where L is a learning procedure for a rate of convergence which succeeds after at most B-many mind changes. This -learnability provides quantitative information strictly in between a full rate of convergence and a rate of metastability in the sense of Tao (...)
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Approximation to measurable functions and its relation to probabilistic computation.Ker-I. Ko - 1986 - Annals of Pure and Applied Logic 30 (2):173-200.
    A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Recursive and nonextendible functions over the reals; filter foundation for recursive analysis.II.Iraj Kalantari & Lawrence Welch - 1999 - Annals of Pure and Applied Logic 98 (1-3):87-110.
    In this paper we continue our work of Kalantari and Welch . There we introduced machinery to produce a point-free approach to points and functions on topological spaces and found conditions for both which lend themselves to effectivization. While we studied recursive points in that paper, here, we present two useful classes of recursive functions on topological spaces, apply them to the reals, and find precise accounting for the nature of the properties of some examples that exist in the literature. (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • In Memoriam: Ernst Specker 1920–2011.Erwin Engeler - 2012 - Bulletin of Symbolic Logic 18 (3):413-417.
    Download  
     
    Export citation  
     
    Bookmark  
  • Zur Stetigkeit Berechenbarer Reeller Funktionen.Dieter Ilse - 1965 - Mathematical Logic Quarterly 11 (4):297-342.
    Download  
     
    Export citation  
     
    Bookmark  
  • Effective content of the calculus of variations I: Semi-continuity and the chattering lemma.Xiaolin Ge & Anil Nerode - 1996 - Annals of Pure and Applied Logic 78 (1-3):127-146.
    The content of existence theorems in the calculus of variations has been explored and an effective treatment of semi-continuity has been achieved. An algorithm has been developed which captures the natural algorithmic content of the notion of a semi-continuous function and this is used to obtain an effective version of the “chattering lemma” of control theory and ordinary differential equations. This lemma reveals the main computational content of the theory of relaxed optimal control.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Fifty years of the spectrum problem: survey and new results.Arnaud Durand, Neil D. Jones, Johann A. Makowsky & Malika More - 2012 - Bulletin of Symbolic Logic 18 (4):505-553.
    In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining to (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Reclassifying the antithesis of Specker’s theorem.Hannes Diener - 2012 - Archive for Mathematical Logic 51 (7-8):687-693.
    It is shown that a principle, which can be seen as a constructivised version of sequential compactness, is equivalent to a form of Brouwer’s fan theorem. The complexity of the latter depends on the geometry of the spaces involved in the former.
    Download  
     
    Export citation  
     
    Bookmark  
  • Primitive recursive real numbers.Qingliang Chen, Kaile Su & Xizhong Zheng - 2007 - Mathematical Logic Quarterly 53 (4‐5):365-380.
    In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure – Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if “computable” is replaced by “primitive recursive” , these definitions lead to a number of different concepts, which we (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Incompleteness, complexity, randomness and beyond.Cristian S. Calude - 2002 - Minds and Machines 12 (4):503-517.
    Gödel's Incompleteness Theorems have the same scientific status as Einstein's principle of relativity, Heisenberg's uncertainty principle, and Watson and Crick's double helix model of DNA. Our aim is to discuss some new faces of the incompleteness phenomenon unveiled by an information-theoretic approach to randomness and recent developments in quantum computing.
    Download  
     
    Export citation  
     
    Bookmark  
  • The anti-Specker property, positivity, and total boundedness.Douglas Bridges & Hannes Diener - 2010 - Mathematical Logic Quarterly 56 (4):434-441.
    Working within Bishop-style constructive mathematics, we examine some of the consequences of the anti-Specker property, known to be equivalent to a version of Brouwer's fan theorem. The work is a contribution to constructive reverse mathematics.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Reflections on function spaces.Douglas S. Bridges - 2012 - Annals of Pure and Applied Logic 163 (2):101-110.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Decidability and Specker sequences in intuitionistic mathematics.Mohammad Ardeshir & Rasoul Ramezanian - 2009 - Mathematical Logic Quarterly 55 (6):637-648.
    A bounded monotone sequence of reals without a limit is called a Specker sequence. In Russian constructive analysis, Church's Thesis permits the existence of a Specker sequence. In intuitionistic mathematics, Brouwer's Continuity Principle implies it is false that every bounded monotone sequence of real numbers has a limit. We claim that the existence of Specker sequences crucially depends on the properties of intuitionistic decidable sets. We propose a schema about intuitionistic decidability that asserts “there exists an intuitionistic enumerable set that (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations