Undecidability of Brouwerian semilattices

DOI10.1007/BF01224033MaRDI QIDQ1821098zbMATH OpenFDO

Authors Katarzyna Idziak

Publication date 1986

Published in Algebra Universalis (Search for Journal in Brave)

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

zbMATH Keywords

finite Brouwerian semilatticesfinite graphsfinitely generated arithmetical varietyfirst order theory

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Varieties (08B99)

Review text

The author shows that the first order theory of finite Brouwerian semilattices of the variety generated by the algebra \(2^ 2\oplus 1\) is undecidable. She proves the theorem by interpreting finite graphs into finite Brouwerian semilattices from the variety. The result gives an example of a finitely generated arithmetical variety whose finite members have an undecidable first order theory. This answers in negative a question of \textit{S. Burris} and \textit{H. P. Sankappanavar} [A course of universal algebra (1981; Zbl 0478.08001)].

Recommendations

• scientific article; zbMATH DE number 4137743
• Undecidability of free pseudo-complemented semilattices
• No non-trivial quasivariety of BCK-algebras has decidable first order theory
• Undecidability of relatively free Hilbert algebras
• Undecidable Varieties of Semilattice—ordered Semigroups, of Boolean Algebras with Operators, and logics extending Lambek Calculus

Cites work

• Algebras Whose Congruence Lattices are Distributive.
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3222132 (Why is no real title available?)
• scientific article; zbMATH DE number 3304995 (Why is no real title available?)

Cited in

(12)

• Undecidability of free pseudo-complemented semilattices
• No non-trivial quasivariety of BCK-algebras has decidable first order theory
• The decision problem for finite algebras from arithmetical varieties with equationally definable principal congruences
• Reduced sub-powers and the decision problem for finite algebras in arithmetical varieties
• Varieties with decidable finite algebras. I: Linearity
• Bjarni Jónsson's contributions in algebra
• scientific article; zbMATH DE number 4137743 (Why is no real title available?)
• Decidability problem for finite Heyting algebras
• scientific article; zbMATH DE number 535104 (Why is no real title available?)
• Undecidable Varieties of Semilattice—ordered Semigroups, of Boolean Algebras with Operators, and logics extending Lambek Calculus
• Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
• Existentially closed Brouwerian semilattices

This page was built for publication: Undecidability of Brouwerian semilattices

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