×

Duality, non-standard elements, and dynamic properties of r.e. sets. (English) Zbl 1403.03066

Summary: We investigate the Priestley dual \((\mathcal{E}^\ast)^\star\) of the lattice \(\mathcal{E}^\ast\) of r.e. sets modulo finite sets. Connections with non-standard elements of r.e. sets in models of 1st order true arithmetic as well as with dynamic properties of r.e. sets are pointed out. Illustrations include the Harrington-Soare dynamic characterization of small subsets, a model-theoretic characterization of promptly simple sets, and relations between the inclusion ordering of prime filters on \(\mathcal{E}^\ast\) (a.k.a. points of \((\mathcal{E}^\ast)^\star\)) and the complexity of their index sets.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
03C62 Models of arithmetic and set theory
03H15 Nonstandard models of arithmetic
06D50 Lattices and duality
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alton, D. A., Iterated quotients of the lattice of recursively enumerable sets, Proc. Lond. Math. Soc. (3), 28, 1-12 (1974) · Zbl 0278.02035
[2] Bouacida, E.; Echi, O.; Picavet, G.; Salhi, E., An extension theorem for sober spaces and the Goldman topology, Int. J. Math. Math. Sci., 51, 3217-3239 (2003) · Zbl 1042.54003
[3] Cornish, W. H., On H. Priestley’s dual of the category of bounded distributive lattices, Математички весник. Нова сериjа, 12, 27, 329-332 (1975) · Zbl 0344.06007
[4] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), Cambridge University Press · Zbl 1002.06001
[5] Gaifman, H., A note on models and submodels of arithmetic, (Hodges, W., Conference in Mathematical Logic — London ’70 (1972), Springer-Verlag), 128-144 · Zbl 0255.02058
[6] Guaspari, D., Partially conservative extensions of arithmetic, Trans. Amer. Math. Soc., 254, 47-68 (1979) · Zbl 0417.03030
[7] Hájek, P., Completion closed algebras and models of Peano arithmetic, Comment. Math. Univ. Carolin., 22, 585-594 (1981) · Zbl 0499.03022
[8] Hájek, P., On a new notion of partial conservativity, (Richter, M. M.; Börger, E.; Oberschelp, W.; Schinzel, B.; Thomas, W., Computation and Proof Theory (1984), Springer-Verlag), 217-232 · Zbl 0587.03042
[9] Harrington, L.; Soare, R. I., Dynamic properties of computably enumerable sets, (Cooper, S. B.; Slaman, T. A.; Wainer, S. S., Computability, Enumerability, Unsolvability: Directions in Recursion Theory (1996), Cambridge University Press), 105-121 · Zbl 0846.03015
[10] Harrington, L.; Soare, R. I., Definable properties of the computably enumerable sets, Ann. Pure Appl. Logic, 94, 97-125 (1998) · Zbl 0928.03051
[11] Herrmann, E.; Kummer, M., Diagonals and \(D\)-maximal sets, J. Symbolic Logic, 59, 60-72 (1994) · Zbl 0799.03046
[12] Hirschfeld, J., Models of arithmetic and recursive functions, Israel J. Math., 20, 111-126 (1975) · Zbl 0311.02050
[13] Hirschfeld, J., Finite forcing and generic filters in arithmetic, (Saracino, D. H.; Weispfenning, V. B., Model Theory and Algebra: a Memorial Tribute to Abraham Robinson (1975), Springer-Verlag), 172-199 · Zbl 0317.02062
[14] Hirschfeld, J.; Wheeler, W. H., Forcing, Arithmetic, Division Rings (1975), Springer-Verlag · Zbl 0304.02024
[15] Jensen, D.; Ehrenfeucht, A., Some problem in elementary arithmetics, Fund. Math., 92, 223-245 (1976) · Zbl 0362.02049
[16] Kaye, R., Models of Peano Arithmetic (1991), Clarendon Press · Zbl 0744.03037
[17] Kirby, L. A.S., Initial segments of models of arithmetic (1977), Manchester University, Thesis · Zbl 0364.02032
[18] Kossak, R.; Schmerl, J. H., The Structure of Models of Peano Arithmetic (2006), Clarendon Press · Zbl 1101.03029
[19] Lachlan, A. H., The elementary theory of recursively enumerable sets, Duke Math. J., 35, 123-146 (1968) · Zbl 0281.02043
[20] Lachlan, A. H., On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc., 130, 1-37 (1968) · Zbl 0281.02042
[21] Lempp, S.; Nies, A.; Solomon, D. R., On the filter of computably enumerable supersets of an r-maximal set, Arch. Math. Logic, 40, 415-423 (2001) · Zbl 1030.03029
[22] Lerman, M.; Soare, R. I., A decidable fragment of the elementary theory of the lattice of recursively enumerable sets, Trans. Amer. Math. Soc., 257, 1-37 (1980) · Zbl 0439.03023
[23] Lindström, P., Aspects of Incompleteness (2003), Association for Symbolic Logic/A K Peters · Zbl 1036.03002
[24] Lindström, P., A theorem on partial conservativity in arithmetic, J. Symbolic Logic, 76, 341-347 (2011) · Zbl 1218.03033
[25] Lindström, P.; Shavrukov, V. Yu., The ∀∃ theory of Peano \(\Sigma_1\) sentences, J. Math. Log., 8, 251-280 (2008) · Zbl 1191.03005
[26] Maass, W., Recursively enumerable generic sets, J. Symbolic Logic, 47, 809-823 (1982) · Zbl 0498.03026
[27] Maass, W., Major subsets and automorphisms of recursively enumerable sets, (Nerode, A.; Shore, R. A., Recursion Theory (1985), American Mathematical Society), 21-32 · Zbl 0592.03029
[28] Maass, W.; Shore, R. A.; Stob, M., Splitting properties and jump classes, Israel J. Math., 39, 210-224 (1981) · Zbl 0469.03026
[29] Maass, W.; Stob, M., The intervals of the lattice of recursively enumerable sets determined by major subsets, Ann. Pure Appl. Logic, 24, 189-212 (1983) · Zbl 0538.03037
[30] Monteiro, A., L’arithmétique des filtres et les espaces topologiques I, Notas de Lógica Matemática, № 29 (1974), Instituto de Matemática, Universidad Nacional del Sur · Zbl 0318.06018
[31] Nerode, A., Some Stone spaces and recursion theory, Duke Math. J., 26, 397-406 (1959) · Zbl 0114.24702
[32] Поляков, Е.А.; Розинас, М.Г., Сводимости по перечислимости, Сибирский математический журнал. Сибирский математический журнал, Sib. Math. J., 18, 594-599 (1977), English translation: E.A. Polyakov, M.G. Rozinas, Enumeration reducibilities · Zbl 0409.03026
[33] Priestley, H. A., Ordered topological spaces and the representation of distributive lattices, Proc. Lond. Math. Soc. (3), 24, 507-530 (1972) · Zbl 0323.06011
[34] Schmerl, J. H., End extensions of models of arithmetic, Notre Dame J. Form. Log., 33, 216-219 (1992) · Zbl 0788.03049
[36] Selivanov, V., Fine hierarchies via Priestley duality, Ann. Pure Appl. Logic, 163, 1075-1107 (2012) · Zbl 1247.03094
[38] Shore, R. A., Determining automorphisms of the recursively enumerable sets, Proc. Amer. Math. Soc., 65, 318-325 (1977) · Zbl 0364.02023
[39] Simmons, H., The lattice of universal sentences modulo Peano arithmetic (1980), Institut de Mathématique pure et appliquée, Université catholique de Louvain, Séminaire de Mathématique pure, Rapport No. 93 · Zbl 0471.03023
[40] Smoryński, C., Recursively saturated nonstandard models of arithmetic, J. Symbolic Logic. J. Symbolic Logic, J. Symbolic Logic, 47, 493-494 (1982), Addendum · Zbl 0549.03059
[41] Smullyan, R. M., Theory of Formal Systems (1961), Princeton University Press · Zbl 0218.02030
[42] Soare, R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (1987), Springer-Verlag · Zbl 0623.03042
[43] Solovay, R. M., Injecting inconsistencies into models of PA, Ann. Pure Appl. Logic, 44, 101-132 (1989) · Zbl 0698.03040
[44] Steel, J., Descending sequences of degrees, J. Symbolic Logic, 40, 59-61 (1975) · Zbl 0349.02036
[45] Stob, M. J., The structure and elementary theory of the recursively enumerable sets (1979), The University of Chicago, Dissertation
[46] Wilkie, A., On models of arithmetic—answers to two problems raised by H. Gaifman, J. Symbolic Logic, 40, 41-47 (1975) · Zbl 0319.02050
[47] Wilkie, A. J., On the theories of end-extensions of models of arithmetic, (Lachlan, A.; Srebrny, M.; Zarach, A., Set Theory and Hierarchy Theory V (1977), Springer-Verlag), 305-310 · Zbl 0376.02043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.