The undecidability of the lattice of r.e. closed subsets of an effective topological space

Annals of Pure and Applied Logic 35:193 (1987)
  Copy   BIBTEX

Abstract

The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n, is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using the method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Recursive constructions in topological spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Automorphisms of the lattice of recursively enumerable sets.Peter Cholak - 1995 - Providence, RI: American Mathematical Society.
Major subsets and the lattice of recursively enumerable sets.Michael Stob - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 107.
A conjunction in closure spaces.Andrzej W. Jankowski - 1984 - Studia Logica 43 (4):341 - 351.
Effective inseparability in a topological setting.Dieter Spreen - 1996 - Annals of Pure and Applied Logic 80 (3):257-275.
Decidable subspaces and recursively enumerable subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
Definable structures in the lattice of recursively enumerable sets.E. Herrmann - 1984 - Journal of Symbolic Logic 49 (4):1190-1197.
Topological aspects of the Medvedev lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
Simple and hyperhypersimple vector spaces.Allen Retzlaff - 1978 - Journal of Symbolic Logic 43 (2):260-269.

Analytics

Added to PP
2017-02-19

Downloads
3 (#1,519,925)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Recursive constructions in topological spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.
Simplicity in effective topology.Iraj Kalantari & Anne Leggett - 1982 - Journal of Symbolic Logic 47 (1):169-183.
A universal embedding property of the RETs.Anil Nerode & Alfred B. Manaster - 1970 - Journal of Symbolic Logic 35 (1):51-59.

Add more references