Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-11T14:02:19.400Z Has data issue: false hasContentIssue false

Borel structures: a brief survey

Published online by Cambridge University Press:  05 December 2013

By
Antonio Montalbán  and
André Nies
Edited by
Noam Greenberg ,
Denis Hirschfeldt ,
Joel David Hamkins  and
Russell Miller
Noam Greenberg
Affiliation:
Victoria University of Wellington
Denis Hirschfeldt
Affiliation:
University of Chicago
Joel David Hamkins
Affiliation:
College of Staten Island
Russell Miller
Affiliation:
Queens College, City University of New York
Get access

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.

Type
Chapter
Information
Effective Mathematics of the Uncountable , pp. 124 - 134
Publisher: Cambridge University Press
Print publication year: 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Howard, Becker and Alexander S., Kechris. The Descriptive Set Theory of Polish Group Actions. Cambridge University Press, 1996.
[2] Harvey, Friedman. On the logic of measure and category I. Manuscript, 1978.
[3] Harvey, Friedman. Borel structures and mathematics. Manuscript, 1979.
[4] Leo, Harrington, David, Marker, and Saharon, Shelah. Borel orderings. Trans. Amer. Math. Soc., 310(1), 293–302, 1988.Google Scholar
[5] Leo, Harrington and Saharon, Shelah. Counting equivalence classes for co-κ-Souslin equivalence relations. In Logic Colloquium '80 (Prague, 1980), D., van Dalen (ed), volume 108 of Stud. Logic Foundations Math., 147–152. North-Holland, 1982.
[6] Greg, Hjorth. Borel equivalence relations. In Handbook on Set Theory, Vol. 1, Matt, Foreman and Aki, Kanamori (eds), Springer-Verlag, 2010.
[7] G., Hjorth, Bakh, Khoussainov, Antonio, Montalbán, and André, Nies. From automatic structures to Borel structures. Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008), 431–441, 2008.
[8] Greg, Hjorth and André, Nies. Borel structures and Borel theories. J. Symbolic Logic 76 (2011), 461–476.Google Scholar
[9] Vladimir, Kanovei. When a partial Borel order is linearizable. Fund. Math., 155(3), 301–309, 1998.Google Scholar
[10] R., Kaye. Models of Peano Arithmetic, volume 15 of Oxford Logic Guides. Oxford University Press, 1991.
[11] Alexander S., Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, 1995.
[12] Julia, Knight and Mark, Nadel. Models of arithmetic and closed ideals. J. Symbolic Logic, 47(4), 833–840. 1983.Google Scholar
[13] R., Kossak and J.H., Schmerl. The Structure of Models of Peano Arithmetic. Oxford Logic Guides, vol. 50. Oxford University Press, 2006.
[14] S., Lang. Algebra. Addison-Wesley, 1965.
[15] J., Lindenstrauss and L., Tzafriri. Classical Banach Spaces I. Springer, 1996.
[16] Alain, Louveau. Two results on Borel orders. J. Symbolic Logic, 54(3) 865–874, 1989.Google Scholar
[17] Alain, Louveau and Jean, Saint-Raymond. On the quasi-ordering of Borel linear orders under embeddability. J. Symbolic Logic, 55(2) 537–560, 1990.Google Scholar
[18] C.I., Steinhorn. Borel structures and measure and category logics. In Model-Theoretic Logics, J., Barwise and S., Feferman (eds), volume 8 of Perspect. Math. Logic, 579-596. Springer, 1985.
[19] C.I., Steinhorn. Borel structures for first-order and extended logics. In Harvey Friedman's Research on the Foundations of Mathematics, L.A., Harrington, M.D., Morley, A., Scedrov and S.G., Simpson (eds), volume 117 of Stud. Logic Found. Math., 161-178. North-Holland, 1985.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×