Book contents
- Frontmatter
- Contents
- Preface
- Workshop and conference on logic, algebra, and arithmetic: Tehran, October 18–22, 2003
- Foreword
- Mathematical logic in Iran: A perspective
- Real closed fields and IP-sensitivity
- Categoricity and quantifier elimination for intuitionistic theories
- Primes and irreducibles in truncation integer parts of real closed fields
- On explicit definability in arithmetic
- From bounded arithmetic to second order arithmetic via automorphisms
- Local-global principles and approximation theorems
- Beatty sequences and the arithmetical hierarchy
- Specker's theorem, cluster points, and computable quantum functions
- Additive polynomials and their role in the model theory of valued fields
- Dense subfields of henselian fields, and integer parts
- A recursive nonstandard model for open induction with GCD property and cofinal primes
- Model theory of bounded arithmetic with applications to independence results
- Ibn-Sina's anticipation of the formulas of Buridan and Barcan
- Remarks on algebraic D-varieties and the model theory of differential fields
- A simple positive Robinson theory with LSTP ≠ STP
- Categories of theories and interpretations
- References
Specker's theorem, cluster points, and computable quantum functions
Published online by Cambridge University Press: 30 March 2017
Book contents
- Frontmatter
- Contents
- Preface
- Workshop and conference on logic, algebra, and arithmetic: Tehran, October 18–22, 2003
- Foreword
- Mathematical logic in Iran: A perspective
- Real closed fields and IP-sensitivity
- Categoricity and quantifier elimination for intuitionistic theories
- Primes and irreducibles in truncation integer parts of real closed fields
- On explicit definability in arithmetic
- From bounded arithmetic to second order arithmetic via automorphisms
- Local-global principles and approximation theorems
- Beatty sequences and the arithmetical hierarchy
- Specker's theorem, cluster points, and computable quantum functions
- Additive polynomials and their role in the model theory of valued fields
- Dense subfields of henselian fields, and integer parts
- A recursive nonstandard model for open induction with GCD property and cofinal primes
- Model theory of bounded arithmetic with applications to independence results
- Ibn-Sina's anticipation of the formulas of Buridan and Barcan
- Remarks on algebraic D-varieties and the model theory of differential fields
- A simple positive Robinson theory with LSTP ≠ STP
- Categories of theories and interpretations
- References
Summary
Abstract.The present paper continues the work we began in [KalWel95, KalWel96, KalWel03, KalWel05].
Specker [Spe49] proved existence of a computable sequence of computable reals whose limit is not a computable real by using a noncomputable c.e. (computably enumerable) set. He did this by requiring his sequence to evade every computable point as a limit.
We study similar and generalized results in our filter-based approach to computable analysis and computable topology. We strategically construct evading sequences of basic open sets to generalize Specker's work. An evading sequence is a sequence of basic open sets such that any sequence of points with one point chosen to lie in each basic open set has the same cluster points as any other such sequence. This set of cluster points is the set of Specker cluster points of the evading sequence. We devise two methods for obtaining evading sequences such that all the Specker cluster points lie in the spectrum of a given avoidance function. We then use these methods to construct evading sequenceswhere their cluster points can be of one or more types (computable, avoidable, or shadow) and of any possible cardinality for each type. Finally, we use the acquired machinery to reveal two facts of the fine structure of the lower semi-lattice of domains of computable quantum functions under the relation of ‘subset’. Specifically, we show that we cannot always interpolate a computable quantum function between two nested computable quantum functions by constructing a pair of nested computable quantum functions whose domains differ in exactly one point. In contrast, we show that any time two nested computable quantum functions exist whose domains differ by at least two points, we can interpolate another computable quantum function between them.
Introduction.There are three classical approaches to general topology : Fréchet's abstract spaces, Hausdorff's neighborhood classes andKuratowski's closure classes. The fundamental objects with which one works in all these approaches are points. But a point can be viewed as a limit of a sequence of other points or the sole member of an intersection of a nested sequence of open intervals. These approaches to points are often useful.
- Type
- Chapter
- Information
- Logic in Tehran , pp. 134 - 159Publisher: Cambridge University PressPrint publication year: 2006
References
[Abe80] , Computable Analysis, McGraw-Hill, New York, 1980.
[Bra96] , Recursive characterization of computable real-valued functions and relations,Theoretical Computer Science, vol. 162 (1996), pp. 45–77.Google Scholar
[Bra97] , Order-free recursion on the real numbers,Mathematical Logic Quarterly, vol. 43 (1997), pp. 216–234.Google Scholar
[BraKal98] and , A bibliography of recursive analysis and recursive topology,Handbook of Recursive Mathematics (, , , and , editors), Studies in Logic and the Foundations of Mathematics, vol. 138, Elsevier, Amsterdam, 1998, Volume 1, Recursive Model Theory, pp. 583–620.
[BW97] and , Computability on subsets of Euclidean space I: Closed and compact subsets,Theoretical Computer Science, vol. 219 (1999), pp. 65–93.Google Scholar
[Cei64a] , Three theorems on constructive functions,Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 72 (1964), pp. 537–543, Russian.
[Sha68] , , and , Peculiarities of Constructive Mathematical Analysis, Izdat. Mir, Moscow, 1968, Proc. Internat. Congr. Math. (Moscow, 1966), Russian.
[Cei62b] and , Singular coverings and properties of constructive functions connected with them, Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 67 (1962), pp. 458–502, Russian.Google Scholar
[Goo61] , Recursive Analysis, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1961.
[Grz55] , Computable functionals,Fundamenta Mathematicae, vol. 42 (1955), pp. 168–202.Google Scholar
[Grz57] , On the definitions of computable real continuous functions,Fundamenta Mathematicae, vol. 44 (1957), pp. 61–71.Google Scholar
[Her97a] , An effective Riemann mapping theorem,Theoretical Computer Science, vol. 219 (1999), pp. 225–265.Google Scholar
[Her97b] , A real number structure that is effectively categorical,Mathematical Logic Quarterly, vol. 45 (1999), no. 2, pp. 147–182.Google Scholar
[Kal82] , Major subsets in effective topology,Patras Logic Symposion (Patras, 1980), Studies in Logic and the Foundations of Mathematics, 109, North-Holland, Amsterdam- New York, 1982, pp. 77–94.
[KalWel95] and , Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I,Annals of Pure and Applied Logic, vol. 93 (1998), no. 1-3, pp. 125–151.Google Scholar
[KalWel96] and , Recursive and nonextendible functions over the reals; filter foundation for recursive analysis, II,Annals of Pure and Applied Logic, vol. 98 (1999), no. 1-3, pp. 87–110.Google Scholar
[KalWel03] and , A blend of methods of recursion theory and topology,Annals of Pure and Applied Logic, vol. 124 (2003), no. 1-3, pp. 141–178.Google Scholar
[KalWel05] and , A blend of methods of recursion theory and topology: a Π01 tree of shadow points, Archives for Mathematical Logic, vol. 43 (2004), pp. 991–1008.Google Scholar
[KL57] and , Ensembles récursivement mesurables et ensembles récursivement ouverts et fermés,Comptes Rendus Académie des Sciences Paris, vol. 245 (1957), pp. 1106–1109, French.
[KW84] and , A unified approach to constructive and recursive analysis,Computation and Proof Theory (, , , , and , editors), Lecture Notes in Mathematics, vol. 1104, Springer, Berlin, 1984, pp. 259–278.
[Kre87] and , , , , and , editors, Compactness in constructive analysis revisited,Annals of Pure and Applied Logic, vol. 36 (1987), pp. 29–38.Google Scholar
[Kus83] , A Class of Specker Sequences, Mathematical Logic, Mathematical Linguistics and Theory of Algorithms, Kalinin. Gos. Univ., Kalinin, 1983, Russian.
[Lac55] , Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles I,Comptes Rendus Académie des Sciences Paris, vol. 240 (1955), pp. 2478–2480, French.
[Lac55a] , Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles II,Comptes Rendus Académie des Sciences Paris, vol. 241 (1955), pp. 13–14, French.
[Lac55b] , Extension de la notion de fonction récursive aux fonctions d'une ou plusieurs variables réelles III,Comptes Rendus Académie des Sciences Paris, vol. 241 (1955), pp. 151–153, French.
[Lac57a] , Les ensembles récursivement ouverts ou fermés, et leurs applications á l'analyse récursive,Comptes Rendus Académie des Sciences Paris, vol. 245, 246 (1957), pp. 1040–1043, 28– 31, French.
[Lac58a] , Les ensembles récursivement ouverts ou fermés, et leurs applications a l'Analyse récursive,Comptes Rendus Académie des Sciences Paris, vol. 246 (1958), pp. 28–31, French.
[Mil02] , Π01 Classes in Computable Analysis and Topology, Ph.D. thesis, Cornell University, Ithaca NY, USA, 2002.
[Myh71] , A recursive function, defined on a compact interval and having a continuous derivative that is not recursive,The Michigan Mathematical Journal, vol. 18 (1971), pp. 97–98.Google Scholar
[Ore63a] , Aconstructive map of the square into itself, whichmoves every constructive point,Rossiıskaya Akademiya Nauk. Doklady Akademii Nauk, vol. 152 (1963), pp. 55–58.Google Scholar
[PR89] and , Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer, Berlin, 1989.
[Ric54] , Recursive real numbers,Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 784–791.Google Scholar
[Sch02] , Extended admissibility,Theoretical Computer Science, vol. 284 (2002), no. 2, pp. 519–538.Google Scholar
[Soa96] , Computability and Recursion,The Bulletin of Symbolic Logic, vol. 2 (1996), pp. 284–321.Google Scholar
[Spe49] , Nicht konstruktiv beweisbare Satze der Analysis, The Journal of Symbolic Logic, vol. 14 (1949), pp. 145–158, German.Google Scholar
[Spe59] , Der Satz vom Maximum in der rekursiven Analysis,Constructivity in Mathematics (, editor), North Holland, Amsterdam, 1959, Colloquium at Amsterdam, 1957, pp. 254–265.
[Tur36] , On computable numbers, with an application to the “Entscheidungsproblem”,Proceedings of the London Mathematical Society, vol. 42 (1936), no. 2, pp. 230–265.Google Scholar
[Tur37] , On computable numbers, with an application to the “Entscheidungsproblem”. A correction,Proceedings of the London Mathematical Society, vol. 43 (1937), no. 2, pp. 544–546.Google Scholar
[Sha62] , Constructive real numbers and constructive functional spaces,Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 67 (1962), pp. 15–294, Russian.
[WY96] and , Computability and metrics in a Fréchet space,Mathematica Japonica, vol. 43 (1996), no. 3, pp. 431–443.Google Scholar
[Wei93] , Computability on computable metric spaces,Theoretical Computer Science, vol. 113 (1993), pp. 191–210.Google Scholar
[Wei97b] , Computability on the probability measures on the Borel sets of the unit interval,Theoretical Computer Science, vol. 219 (1999), pp. 421–437.Google Scholar
[Wei00] , Computable Analysis, Springer, Berlin, 2000.
[MTY97] , , and , Effective properties of sets and functions in metric spaces with computability structure,Theoretical Computer Science, vol. 219 (1999), pp. 467–486.Google Scholar
[Zas62] , Some properties of constructive real numbers and constructive functions,Trudy Matematicheskogo Instituta Imeni V. A. Steklova, vol. 67 (1962), pp. 385–457, Russian.
- 1
- Cited by