Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures
type: Item
instance of: scholarly article
title: Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures
zbMATH Open document ID: 0604.03014
DOI: 10.1016/0168-0072(86)90041-2
published in: Annals of Pure and Applied Logic
publication date: 1986-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D45
zbMATH DE Number: 3974953
zbMATH Keywords: lifting property
zbMATH Keywords: local exchange property
zbMATH Keywords: lattices of r.e. substructures
zbMATH Keywords: r-maximal set
author: Rodney G. Downey
MaRDI profile type: Publication
full work available at URL: 0168-0072(86)90041-2
OpenAlex ID: W2047280602
cites work: Decidable subspaces and recursively enumerable subspaces
cites work: First-order theories of abstract dependence relations
cites work: Maximal theories
cites work: SOME REMARKS ON A THEOREM OF IRAJ KALANTARI CONCERNING CONVEXITY AND RECURSION THEORY
cites work: Hierarchies of Boolean algebras
cites work: The undecidability of the recursively enumerable degrees
cites work: Q3931263
cites work: Q3657979
cites work: Q4063426
cites work: Recursively enumerable vector spaces
cites work: Recursion theory on fields and abstract dependence
cites work: Q3343973
cites work: Q3690803
cites work: Q3897041
cites work: Recursively enumerable Boolean algebras
cites work: Recursion theory on algebraic structures with independent sets
cites work: Recursively enumerable sets and degrees
description: scientific article; zbMATH DE number 3974953