×

Decidable discriminator varieties from unary classes. (English) Zbl 0776.03013

Summary: Let \(\mathcal K\) be a class of (universal) algebras of fixed type. \({\mathcal K}^ t\) denotes the class obtained by augmenting each member of \(\mathcal K\) by the ternary discriminator function \((t(x,y,z)=x\) if \(x\neq y\), \(t(x,x,z)=z)\), while \(\bigvee({\mathcal K}^ t)\) is the closure of \({\mathcal K}^ t\) under the formation of subalgebras, homomorphic images, and arbitrary Cartesian products. For example, the class of Boolean algebras is definitionally equivalent to \(\bigvee({\mathcal K}^ t)\) where \({\mathcal K}\) consists of a two-element algebra whose only operations are the two constants. Any equationally defined class (that is, variety) of algebras which is equivalent to some \(\bigvee({\mathcal K}^ t)\) is known as a discriminator variety.
Building on recent work of S. Burris, R. McKenzie, and M. Valeriote, we characterize those locally finite universal classes, \(\mathcal K\) of unary algebras of finite type for which the first-order theory of \(\bigvee({\mathcal K}^ t)\) is decidable.

MSC:

03C05 Equational classes, universal algebra in model theory
03B25 Decidability of theories and sets of sentences
08A60 Unary algebras
Full Text: DOI

References:

[1] S. Bulman-Fleming and H. Werner, Equational compactness in quasi-primal varieties, Algebra Universalis 7 (1977), no. 1, 33 – 46. · Zbl 0367.08006 · doi:10.1007/BF02485416
[2] Stanley Burris, Iterated discriminator varieties have undecidable theories, Algebra Universalis 21 (1985), no. 1, 54 – 61. · Zbl 0593.08006 · doi:10.1007/BF01187556
[3] Stanley Burris and Ralph McKenzie, Decidability and Boolean representations, Mem. Amer. Math. Soc. 32 (1981), no. 246, viii+106. · Zbl 0483.03019 · doi:10.1090/memo/0246
[4] Stanley Burris, Ralph McKenzie, and Matthew Valeriote, Decidable discriminator varieties from unary varieties, J. Symbolic Logic 56 (1991), no. 4, 1355 – 1368. · Zbl 0747.08008 · doi:10.2307/2275480
[5] Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. · Zbl 0478.08001
[6] Stanley Burris and Heinrich Werner, Sheaf constructions and their elementary properties, Trans. Amer. Math. Soc. 248 (1979), no. 2, 269 – 309. · Zbl 0411.03022
[7] Stephen D. Comer, Elementary properties of structures of sections, Bol. Soc. Mat. Mexicana (2) 19 (1974), no. 2, 78 – 85. · Zbl 0338.02032
[8] Stephen D. Comer, Monadic algebras with finite degree, Algebra Universalis 5 (1975), no. 3, 313 – 327. · Zbl 0338.02033 · doi:10.1007/BF02485264
[9] Ju. L. Eršov, Decidability of the elementary theory of relatively complemented lattices and of the theory of filters, Algebra i Logika Sem. 3 (1964), no. 3, 17 – 38 (Russian). · Zbl 0199.03103
[10] Ju. L. Eršov, Elementary theories of Post varieties, Algebra i Logika 6 (1967), no. 5, 7 – 15 (Russian).
[11] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57 – 103. · Zbl 0088.24803
[12] Joohee Jeong, A decidable variety that is finitely undecidable, J. Symbolic Logic 64 (1999), no. 2, 651 – 677. · Zbl 0935.03017 · doi:10.2307/2586491
[13] Klaus Keimel and Heinrich Werner, Stone duality for varieties generated by quasi-primal algebras, Recent advances in the representation theory of rings and \?*-algebras by continuous sections (Sem., Tulane Univ., New Orleans, La., 1973), Amer. Math. Soc., Providence, R.I., 1974, pp. 59 – 85. Mem. Amer. Math. Soc., No. 148. · Zbl 0283.08001
[14] Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor, Algebras, lattices, varieties. Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1987. · Zbl 0611.08001
[15] Ralph McKenzie and Matthew Valeriote, The structure of decidable locally finite varieties, Progress in Mathematics, vol. 79, Birkhäuser Boston, Inc., Boston, MA, 1989. · Zbl 0702.08001
[16] Michael O. Rabin, Decidability of second-order theories and automata on infinite trees., Trans. Amer. Math. Soc. 141 (1969), 1 – 35. · Zbl 0221.02031
[17] Matatyanu Rubin, The theory of Boolean algebras with a distinguished subalgebra is undecidable, Ann. Sci. Univ. Clermont No. 60 Math. 13 (1976), 129 – 134. · Zbl 0354.02036
[18] A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc. 55 (1949), 64.
[19] M. Valeriote, On decidable locally finite varieties, Ph.D. thesis, Univ. of California, Berkeley, 1986.
[20] M. A. Valeriote and R. Willard, Discriminating varieties, Algebra Universalis 32 (1994), no. 2, 177 – 188. · Zbl 0814.08008 · doi:10.1007/BF01191537
[21] Volker Weispfenning, A note on ℵ\(_{0}\)-categorical model-companions, Arch. Math. Logik Grundlag. 19 (1978/79), no. 1-2, 23 – 29. · Zbl 0408.03024 · doi:10.1007/BF02011865
[22] H. Werner, Varieties generated by quasi-primal algebras have decidable theories, Contributions to universal algebra (Colloq., József Attila Univ., Szeged, 1975) North-Holland, Amsterdam, 1977, pp. 555 – 575. Colloq. Math. Soc. János Bolyai, Vol. 17.
[23] Ross Willard, Decidable discriminator varieties with lattice stalks, Algebra Universalis 31 (1994), no. 2, 177 – 195. · Zbl 0810.08005 · doi:10.1007/BF01236516
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.