Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- Some results on ℝ-computable structures
- Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
- Computable structure theory using admissible recursion theory on ω1 using admissibility
- Local computability and uncountable structures
- Borel structures: a brief survey
- E-recursive intuitions
- Reverse mathematics, countable and uncountable: a computational approach
- Effective model theory: approach via σ-definability
- References
Borel structures: a brief survey
Published online by Cambridge University Press: 05 December 2013
Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- Some results on ℝ-computable structures
- Infinite time Turing machines and an application to the hierarchy of equivalence relations on the reals
- Computable structure theory using admissible recursion theory on ω1 using admissibility
- Local computability and uncountable structures
- Borel structures: a brief survey
- E-recursive intuitions
- Reverse mathematics, countable and uncountable: a computational approach
- Effective model theory: approach via σ-definability
- References
Summary
Abstract We survey some research aiming at a theory of effective structures of size the continuum. The main notion is the one of a Borel presentation, where the domain, equality and further relations and functions are Borel. We include the case of uncountable languages where the signature is Borel. We discuss the main open questions in the area.
§1. Introduction. When looking at structures of size the continuum from an effective viewpoint, the following definition is a natural generalization of ideas from computable model theory.
Definition 1.1. Let X be either 2ω, ωω or ℝ, and let C be a (complexity) class of relations on X. A C-presentation of a structure A is a tuple of relations S = (D, E, R1,…, Rn) such that
о All D, E, R1,…, Rn are in C;
о D ⊆ X and E is an equivalence relation on D (D is called the domain);
о R1, …, Rn are relations compatible with E.
S is a C-representation of A if A ≅ S/E. When E is the identity on D, we say that S is an injective C-presentation of A.
There are various possible choices for C. In this paper we concentrate on the case that C is the class of Borel relations. Given a topological space X as above, the σ-algebra of Borel sets is the smallest σ-algebra containing the open sets.
Information
- Type
- Chapter
- Information
- Effective Mathematics of the Uncountable , pp. 124 - 134Publisher: Cambridge University PressPrint publication year: 2013
References
[1] and . The Descriptive Set Theory of Polish Group Actions. Cambridge University Press, 1996.
[2] . On the logic of measure and category I. Manuscript, 1978.
[3] . Borel structures and mathematics. Manuscript, 1979.
[5] and . Counting equivalence classes for co-κ-Souslin equivalence relations. In Logic Colloquium '80 (Prague, 1980), (ed), volume 108 of Stud. Logic Foundations Math., 147–152. North-Holland, 1982.
[6] . Borel equivalence relations. In Handbook on Set Theory, Vol. 1, and (eds), Springer-Verlag, 2010.
[7] , , , and . From automatic structures to Borel structures. Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008), 431–441, 2008.
[10] . Models of Peano Arithmetic, volume 15 of Oxford Logic Guides. Oxford University Press, 1991.
[11] . Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, 1995.
[12] and . Models of arithmetic and closed ideals. J. Symbolic Logic, 47(4), 833–840. 1983.Google Scholar
[13] and . The Structure of Models of Peano Arithmetic. Oxford Logic Guides, vol. 50. Oxford University Press, 2006.
[14] . Algebra. Addison-Wesley, 1965.
[15] and . Classical Banach Spaces I. Springer, 1996.
[17] and . On the quasi-ordering of Borel linear orders under embeddability. J. Symbolic Logic, 55(2) 537–560, 1990.Google Scholar
[18] . Borel structures and measure and category logics. In Model-Theoretic Logics, and (eds), volume 8 of Perspect. Math. Logic, 579-596. Springer, 1985.
[19] . Borel structures for first-order and extended logics. In Harvey Friedman's Research on the Foundations of Mathematics, , , and (eds), volume 117 of Stud. Logic Found. Math., 161-178. North-Holland, 1985.
Accessibility standard: Unknown
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
Accessibility compliance for the PDF of this chapter is currently unknown and may be updated in the future.