On needed reals

Given a binary relationR, we call a subsetA of the range ofR R-adequate if for everyx in the domain there is someyεA such that (x, y)εR. Following Blass [4], we call a realη ”needed” forR if in everyR-adequate set we find an element from whichη is Turing computable. We show that every real needed for inclusion on the Lebesgue null sets,Cof(\(\mathcal{N}\)), is hyperarithmetic. Replacing “R-adequate” by “R-adequate with minimal cardinality” we get the related notion of being “weakly needed”. We show that it is consistent that the two notions do not coincide for the reaping relation. (They coincide in many models.) We show that not all hyperarithmetic reals are needed for the reaping relation. This answers some questions asked by Blass at the Oberwolfach conference in December 1999 and in [4].     

Relatively computably enumerable reals

A real X is defined to be relatively c.e. if there is a real Y such that X is c.e.(Y) and \({X \not\leq_T Y}\). A real X is relatively simple and above if there is a real Y < _T X such that X is c.e.(Y) and there is no infinite set \({Z \subseteq \overline{X}}\) such that Z is c.e.(Y). We prove that every nonempty \({\Pi^0_1}\) class contains a member which is not relatively c.e. and that every 1-generic real is relatively simple and above.     

The ring of Fermat reals

We give the definition of the ring of Fermat reals, a simple extension of the real field containing nilpotent infinitesimals. The construction takes inspiration from smooth infinitesimal analysis, but provides a powerful theory of actual infinitesimals without any need of a background in mathematical logic. In particular it is consistent with classical logic. We face the problem to decide if the product of powers of nilpotent infinitesimals is zero or not, the identity principle for polynomials, the characterization of invertible elements and some applications to Taylor's formulas.     

On the constructive Dedekind reals

In order to build the collection of Cauchy reals as a set in constructive set theory, the only power set-like principle needed is exponentiation. In contrast, the proof that the Dedekind reals form a set has seemed to require more than that. The main purpose here is to show that exponentiation alone does not suffice for the latter, by furnishing a Kripke model of constructive set theory, Constructive Zermelo–Fraenkel set theory with subset collection replaced by exponentiation, in which the Cauchy reals form a set while the Dedekind reals constitute a proper class.     

On cardinal collapsing with reals

We show that every uncountable regular cardinal can become {ie11-1} in a suitable Cohen extension by a real (set of integers) without destroying larger cardinals. The proof is analyzed to obtain results about the powers of Boolean algebras.     

Strongly dominating sets of reals

We analyze the structure of strongly dominating sets of reals introduced in Goldstern et al. (Proc Am Math Soc 123(5):1573–1581, 1995). We prove that for every ${\kappa < \mathfrak{b}}$ κ < b a ${\kappa}$ κ -Suslin set ${A\subseteq{}^\omega\omega}$ A ? ω ω is strongly dominating if and only if A has a Laver perfect subset. We also investigate the structure of the class l of Baire sets for the Laver category base and compare the σ-ideal of sets which are not strongly dominating with the Laver ideal l ⁰.     

On strongly jump traceable reals

In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is -complete.     

Schnorr trivial reals: a construction

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science     

The reals as full and balanced biframe

This paper is the first part of a two-part investigation. It introduces full and balanced biframes which capture useful properties of the reals viewed as a biframe (or bitopological space). The subsequent paper will apply these concepts to the study of completions of quasi-nearness biframes.We start with the smallest dense quotient for biframes. Next we discuss the reals as a biframe and introduce the key ideas of balanced, full and stable biframes. The crucial tool here is the frame pseudocomplement. We include a discussion of the relations between the newly introduced ideas and regularity. Order topology biframes are all regular, normal and balanced but not necessarily full. We consider the plane and various examples related to zero-dimensionality. We provide methods of transferring fullness and balancedness from domain to codomain and conversely under various kinds of maps.Of particular importance to our later study of completions is the idea of a biframe map whose right adjoint preserves the first and second parts of the biframe. We give a result providing sufficient conditions for a map to have a part-preserving right adjoint. We present an example of a dense onto map (which is in fact a compactification) between normal, regular biframes whose right adjoint is not part-preserving. The paper concludes with internal properties of full and balanced biframes showing the particularly close connection between the first and second parts and ends with a final visit to the biframe of reals.     

Perfect sets of random reals

We show that the existence of a perfect set of random reals over a modelM ofZFC does not imply the existence of a dominating real overM, thus answering a well-known open question (see [BJ 1] and [JS 2]). We also prove that (the product of two copies of the random algebra) neither adds a dominating real nor adds a perfect set of random reals (this answers a question that A. Miller asked during the logic year at MSRI). The first author would like to thank the MINERVA-foundation for supporting him. The second author would like to thank the Basic Research Foundation (the Israel Academy of Sciences and Humanities) for supporting him.     

Turing cones and set theory of the reals

We investigate Turing cones as sets of reals, and look at the relationship between Turing cones, measures, Baire category and special sets of reals, using these methods to show that Martin's proof of Turing Determinacy (every determined Turing closed set contains a Turing cone or is disjoint from one) does not work when you replace “determined” with “Blackwell determined”. This answers a question of Tony Martin. Received: 6 December 1999 / Revised version: 28 June 2000 Published online: 3 October 2001     

Pairwise sums in colourings of the reals

Suppose that we have a finite colouring of \(\mathbb R\). What sumset-type structures can we hope to find in some colour class? One of our aims is to show that there is such a colouring for which no uncountable set has all of its pairwise sums monochromatic. We also show that there is such a colouring such that there is no infinite set X with \(X+X\) (the pairwise sums from X, allowing repetition) monochromatic. These results assume CH. In the other direction, we show that if each colour class is measurable, or each colour class is Baire, then there is an infinite set X (and even an uncountable X, of size the reals) with \(X+X\) monochromatic. We also give versions for all of these results for k-wise sums in place of pairwise sums.     

Program extraction for 2-random reals

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} \, {\vdash} \, \forall{f}\, {\exists}{x} A_{qf}(f,x)}$ then one can extract from the proof a primitive recursive term t(f) such that ${A_{qf}(f,t(f))}$ . As a consequence, we obtain that ${{\textsf{WKL}_0}+ \Pi^0_1 - {\textsf{CP}} + 2-\textsf{RAN}}$ is ${\Pi^0_3}$ -conservative over ${\textsf{RCA}_0}$ .     

The distribution of ITRM-recognizable reals

Infinite Time Register Machines (ITRM's) are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. ,  and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM's in [3]. A real x is ITRM-recognizable iff there is an ITRM-program P   such that P^y$P^y$ stops with output 1 iff y=x$y=x$, and otherwise stops with output 0. In [3], it is shown that the recognizable reals are not contained in the ITRM-computable reals. Here, we investigate in detail how the ITRM  -recognizable reals are distributed along the canonical well-ordering _<L${<}_L$ of Gödel's constructible hierarchy L  . In particular, we prove that the recognizable reals have gaps in _<L${<}_L$, that there is no universal ITRM in terms of recognizability and consider a relativized notion of recognizability.     

No random reals in countable support iterations

We prove a preservation theorem for limit steps of countable support iterations of proper forcing notions whose particular cases are preservations of the following properties on limit steps: “no random reals are added”, “μ(Random(V))≠1”, “no dominating reals are added”, “Cohen(V) is not comeager”. Consequently, countable support iterations of σ-centered forcing notions do not add random reals. The work was supported by BRF of Israel Academy of Sciences and by grant GA SAV 365 of Slovak Academy of Sciences.     

Algorithms for proportional matrices in reals and integers

LetR be the set of nonnegative matrices whose row and column sums fall between specific limits and whose entries sum to some fixedh > 0. Closely related axiomatic approaches have been developed to ascribe meanings to the statements: the real matrixf R and the integer matrixa R are proportional to a given matrixp 0.These approaches are described, conditions under which proportional solutions exist are characterized, and algorithms are given for finding proportional solutions in each case.     

Riemann surfaces defined over the reals

The known (explicit) examples of Riemann surfaces not definable over their field of moduli are those with that field being a subfield of the reals but which cannot be defined over the reals. In this paper we provide explicit families of Riemann surfaces which are definable over the reals but cannot be defined over the field of moduli.     

Approximating reals by sums of rationals

We consider the question of approximating any real number α by sums of n rational numbers with denominators 1?q₁,q₂,…,qn?N. This leads to inquiries on approximating a real number by rational numbers with a prescribed number of prime factors in the denominator as well as by rational numbers with smooth denominator.     

The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].