Undecidability of L(F_) and other lattices of r.e. substructures

DOI10.1016/0168-0072(86)90041-2MaRDI QIDQ1083446zbMATH OpenOpenAlexFDO

Authors Rodney G. Downey

Publication date 1986

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(86)90041-2

zbMATH Keywords

lattices of r.e. substructureslifting propertylocal exchange propertyr-maximal set

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)

Review text

This paper establishes the undecidability of \(L(F_{\infty})\). The result is established in a general setting along the lines of that of \textit{J. B. Remmel} [Ann. Math. Logic 18, 153-191 (1980; Zbl 0471.03037)]. It applies to the lattices of r.e. substructures of - for example - (all) Steinitz systems, free groups, Boolean algebras, and a wide class of modules over locally computable rings. The proof builds a special type of r-maximal set, and, using this, codes Boolean pairs into the relevant lattice. Related applications are discussed.

Recommendations

• Some undecidability results for lattices in recursion theory
• Some highly undecidable lattices
• An undecidability theorem for lattices over group rings
• More undecidable lattices of Steinitz exchange systems
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable

Cites work

• Decidable subspaces and recursively enumerable subspaces
• First-order theories of abstract dependence relations
• Hierarchies of Boolean algebras
• scientific article; zbMATH DE number 3878912 (Why is no real title available?)
• scientific article; zbMATH DE number 3809538 (Why is no real title available?)
• scientific article; zbMATH DE number 3914305 (Why is no real title available?)
• scientific article; zbMATH DE number 3704568 (Why is no real title available?)
• scientific article; zbMATH DE number 3747092 (Why is no real title available?)
• scientific article; zbMATH DE number 3478856 (Why is no real title available?)
• Maximal theories
• Recursion theory on algebraic structures with independent sets
• Recursion theory on fields and abstract dependence
• Recursively enumerable Boolean algebras
• Recursively enumerable sets and degrees
• Recursively enumerable vector spaces
• SOME REMARKS ON A THEOREM OF IRAJ KALANTARI CONCERNING CONVEXITY AND RECURSION THEORY
• The undecidability of the recursively enumerable degrees

Cited in

(12)

• The undecidability of the lattice of r. e. closed subsets of an effective topological space
• Undecidability of the theory of the lattice \(L^ 0_{sm}\)
• The undecidability of the elementary theory of lattices of all equational theories of large signature
• The Lattice of Computably Enumerable Vector Spaces
• Degree invariance in the \(\Pi ^{0}_{1}\) classes
• More undecidable lattices of Steinitz exchange systems
• Invariance in ℰ* and ℰ_{Π}
• scientific article; zbMATH DE number 3966058 (Why is no real title available?)
• Some highly undecidable lattices
• Correction to ``Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures
• Some undecidability results for lattices in recursion theory
• A class of \(\Sigma_{3}^{0}\) modular lattices embeddable as principal filters in \({\mathcal L}^*(V_\infty)\)

This page was built for publication: Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083446)