The Undecidability of the Definability of Principal Subcongruences
classification
🧮 math.LO
cs.LO
keywords
algebraprincipalsubcongruencesdefinablefinitealgorithmconsequenceconstruct
read the original abstract
For each Turing machine T, we construct an algebra A'(T) such that the variety generated by A'(T) has definable principal subcongruences if and only if T halts, thus proving that the property of having definable principal subcongruences is undecidable for a finite algebra. A consequence of this is that there is no algorithm that takes as input a finite algebra a decides whether that algebra is finitely based.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.