Undecidable fragments of elementary theories

DOI10.1007/BF01190967zbMath0838.03035OpenAlexW1978292968MaRDI QIDQ1906521

André Nies

Publication date: 6 June 1996

Published in: Algebra Universalis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01190967

zbMATH Keywords

finite structuresheriditarily undecidable theories

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Model theory of finite structures (03C13) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45)

Related Items (19)

Classes of Ulm type and coding rank-homogeneous trees in other structures ⋮ UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS ⋮ The last question on recursively enumerable \(m\)-degrees ⋮ Preserving categoricity and complexity of relations ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ Quantifying over events in probability logic: an introduction ⋮ Classes of algebraic structures ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ CODING IN GRAPHS AND LINEAR ORDERINGS ⋮ Interpreting true arithmetic in the -enumeration degrees ⋮ The First Order Theories of the Medvedev and Muchnik Lattices ⋮ Computably enumerable sets and related issues ⋮ Separating Classes of Groups by First-Order Sentences ⋮ Fragments of the theory of the enumeration degrees ⋮ Complexity of the isomorphism problem for computable free projective planes of finite rank ⋮ The isomorphism problem for computable Abelian _p-groups of bounded length ⋮ The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable ⋮ The Π₃-theory of the -enumeration degrees is undecidable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidability and 1-types in the recursively enumerable degrees
• Classical recursion theory. The theory of functions and sets of natural numbers
• Lattice-theoretic decision problems in universal algebra
• Recursively enumerable many-one degrees
• Theory of equivalence relations
• Definability of models by means of existential formulas without identity
• Free Modular Lattices
• Finitely Presented Lattices
• On the Lattice of Recursively Enumerable Sets
• Undecidability and initial segments of the (r.e.) tt-degrees
• Finite inseparability of some theories of cylindrification algebras
• Initial Segments of Many-One Degrees

This page was built for publication: Undecidable fragments of elementary theories