×

The decidability of some classes of Stone algebras. (English) Zbl 1248.03016

Summary: Iterating the triple construction applied consecutively to \(n\) Boolean algebras, we introduce two finitely axiomatizable subclasses \({\mathbf {SA}^{\text{i}}_n}\) and \({\mathbf {SA}^{\text{s}}_n}\) of the class \(\mathbf {SA}_n\) of all Stone algebras of degree \(n\) with all the structure homomorphisms in their P-product representation injective or surjective, respectively. Then the class of all Post algebras of degree \(n\) is definitionally equivalent to the intersection \({\mathbf {SA}^{\text{i}}_n \cap \mathbf {SA}^{\text{s}}_n}\). We show that for each \(n \geqslant 2\) the class \({\mathbf {SA}^{\text{i}}_n}\) is hereditarily undecidable while \({\mathbf {SA}^{\text{s}}_n}\) is decidable. As a consequence we obtain several (un)decidability results for various axiomatic classes of Stone algebras: among them the decidability of the class of all Stone algebras of degree \(n\) which are dually pseudocomplemented and form a dual Stone algebra under the operation of dual pseudocomplement, and undecidability of the class of all Stone algebras with Boolean dense set. On the other hand, the class of all finite members in \(\mathbf {SA}_n\) is decidable.

MSC:

03B25 Decidability of theories and sets of sentences
06D15 Pseudocomplemented lattices
06D25 Post algebras (lattice-theoretic aspects)
06E15 Stone spaces (Boolean spaces) and related structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balbes R., Dwinger P.: Distributive Lattices. University of Missouri Press, Columbia, Miss. (1974)
[2] Burris, S.: Boolean constructions. In: Universal algebra and lattice theory (Puebla 1983) Lecture Notes in Mathematics vol. 1004, pp. 67–90. Springer-Verlag, Berlin (1983)
[3] Burris, S., McKenzie, R.: Decidability and Boolean Representations. Memoirs Amer. Math. Soc., vol. 32, no. 246, Providence, R. I. (1981) · Zbl 0483.03019
[4] Burris S., Sankappanavar H.P.: A Course in Universal Algebra. Sprinegr-Verlag, New York-Heidelberg-Berlin (1981) · Zbl 0478.08001
[5] Chang C.C., Keisler H.J.: Model Theory, 3rd edn. Elsevier, North-Holland Amsterdam (1990)
[6] Chen C.C., Grätzer G.: Stone lattices I. Construction theorems. Canad. J. Math. 21, 884–894 (1969) · Zbl 0184.03303 · doi:10.4153/CJM-1969-096-5
[7] Chen C.C., Grätzer G.: Stone lattices II. Structure theorems. Canad. J. Math. 21, 895–903 (1969) · Zbl 0184.03304 · doi:10.4153/CJM-1969-097-2
[8] Ershov, Yu. L.: Razreshimost’ elementarnoi teorii distributivnykh struktur s otnositel’nymi dopolneniami i teorii fil’trov (Decidability of the elementary theory of relatively complemented distributive lattices and of the theory of filters). Algebra i Logika 3, 17–38 (1964) (Russian)
[9] Ershov Yu. L.: Elementarnaya teoria mnogoobrazii Posta (Elementary theory of Post varieties). Algebra i Logika 6, 7–15 (1967) (Russian)
[10] Ershov, Yu. L.: Problemy razreshimosti i konstruktivnye modeli (Decidability problems and constructive models). Nauka, Moscow (1980) · Zbl 0495.03009
[11] Grätzer G.: General Lattice Theory, 2nd edn. Birkhäuser-Verlag, Basel-Boston-Berlin (2003) · Zbl 1152.06300
[12] Grzegorczyk A.: Undecidability of some topological theories. Fund. Math. 38, 137–152 (1951) · Zbl 0045.00301
[13] Idziak K., Idziak P.M.: Decidability problem for finite Heyting algebras. J. Symbolic Logic 53, 729–735 (1988) · Zbl 0664.06008 · doi:10.2307/2274568
[14] Katriňák T.: A new proof of the construction theorem for Stone algebras. Proc. Amer. Math. Soc. 40, 75–78 (1973) · Zbl 0266.06005 · doi:10.2307/2038636
[15] Katriňák T., Mitschke A.: Stonesche Verbände der Ordnung n und Postalgebren (Stone lattices of order n and Post algebras). Math. Ann. 199, 13–30 (1972) (German) · Zbl 0253.06009 · doi:10.1007/BF01419572
[16] Rabin, M. O.: A simple method for undecidability proofs. In: Bar-Hillel, Y. (ed.) Proc. of the International Congress for Logic (1964), pp. 58–68. North-Holland, Amsterdam (1965)
[17] Rabin M.O.: Decidability of second order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141, 1–35 (1969) · Zbl 0221.02031
[18] Rubin, M.: The theory of Boolean algebras with a distinguished subalgebra is undecidable. Ann. Sci. Univ. Clermont no. 60, Math. no. 13 pp. 129–134 (1976) · Zbl 0354.02036
[19] Tarski A.: Arithmetical classes and types of Boolean algebras. Bull. Amer. Math. Soc. 55, 64 (1949) · Zbl 0041.34502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.