The main theorem of this article is that every countable model of set theory 〈M, ∈M〉, including every well-founded model, is isomorphic to a submodel of its own constructible universe 〈LM, ∈M〉 by means of an embedding j : M → LM. It follows from the proof that the countable models of set theory are linearly pre-ordered by embeddability: if 〈M, ∈M〉 and 〈N, ∈N〉 are countable models of set theory, then either M is isomorphic to a submodel of N (...) or conversely. Indeed, these models are pre-well-ordered by embeddability in order-type exactly ω1+ 1. Specifically, the countable well-founded models are ordered under embeddability exactly in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory M is universal for all countable well-founded binary relations of rank at most OrdM; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the proof method shows that if M is any nonstandard model of PA, then every countable model of set theory — in particular, every model of ZFC plus large cardinals — is isomorphic to a submodel of the hereditarily finite sets 〈 HFM, ∈M〉 of M. Indeed, 〈 HFM, ∈M〉 is universal for all countable acyclic binary relations. (shrink)

Let R be a real closed field. An integer part I for R is a discretely ordered subring such that for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r \in R}$$\end{document}, there exists an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${i \in I}$$\end{document} so that i ≤ r < i + 1. Mourgues and Ressayre (J Symb Logic 58:641–647, 1993) showed that every real closed field has an integer part. The procedure of Mourgues (...) and Ressayre appears to be quite complicated. We would like to know whether there is a simple procedure, yielding an integer part that is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document} —limit computable relative to R. We show that there is a maximal Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} which is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2(R)}$$\end{document}. However, this I may not be an integer part for R. By a result of Wilkie (Logic Colloquium ’77), any Z-ring can be extended to an integer part for some real closed field. Using Wilkie’s ideas, we produce a real closed field R with a Z-ring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I \subseteq R}$$\end{document} such that I does not extend to an integer part for R. For a computable real closed field, we do not know whether there must be an integer part in the class \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document}. We know that certain subclasses of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^0_2}$$\end{document} are not sufficient. We show that for each \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${n \in \omega}$$\end{document}, there is a computable real closed field with no n-c.e. integer part. In fact, there is a computable real closed field with no n-c.e. integer part for any n. (shrink)

Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels of the Borel hierarchy and there exist some locally finite ω-languages which (...) are Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet (Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1–2):85–105, 2001]. (shrink)

Local sentences were introduced by Ressayre in [6] who proved certain remarkable stretching theorems establishing the equivalence between the existence of finite models for these sentences and the existence of some infinite well ordered models. Two of these stretching theorems were only proved under certain large cardinal axioms but the question of their exact strength was left open in [4]. Here we solve this problem, using a combinatorial result of J. H. Schmerl [7]. In fact, we show that the (...) stretching principles are equivalent to the existence of n -Mahlo cardinals for appropriate integers n. This is done by proving first that for every integer n, there is a local sentence φn having well ordered models of order type τ, for every infinite ordinal τ > ω which is not an n -Mahlo cardinal. (shrink)