Decidable discriminator varieties from unary classes
HTML articles powered by AMS MathViewer
- by Ross Willard PDF
- Trans. Amer. Math. Soc. 336 (1993), 311-333 Request permission
Abstract:
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 \ne y,t(x,x,z) = z)$, while $\vee ({\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 $\vee ({\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 $\vee ({\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 $\vee ({\mathcal {K}^t})$ is decidable.References
- S. Bulman-Fleming and H. Werner, Equational compactness in quasi-primal varieties, Algebra Universalis 7 (1977), no. 1, 33–46. MR 429694, DOI 10.1007/BF02485416
- Stanley Burris, Iterated discriminator varieties have undecidable theories, Algebra Universalis 21 (1985), no. 1, 54–61. MR 835970, DOI 10.1007/BF01187556
- Stanley Burris and Ralph McKenzie, Decidability and Boolean representations, Mem. Amer. Math. Soc. 32 (1981), no. 246, viii+106. MR 617896, DOI 10.1090/memo/0246
- Stanley Burris, Ralph McKenzie, and Matthew Valeriote, Decidable discriminator varieties from unary varieties, J. Symbolic Logic 56 (1991), no. 4, 1355–1368. MR 1136462, DOI 10.2307/2275480
- Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. MR 648287
- Stanley Burris and Heinrich Werner, Sheaf constructions and their elementary properties, Trans. Amer. Math. Soc. 248 (1979), no. 2, 269–309. MR 522263, DOI 10.1090/S0002-9947-1979-0522263-8
- Stephen D. Comer, Elementary properties of structures of sections, Bol. Soc. Mat. Mexicana (2) 19 (1974), no. 2, 78–85. MR 437333
- Stephen D. Comer, Monadic algebras with finite degree, Algebra Universalis 5 (1975), no. 3, 313–327. MR 403965, DOI 10.1007/BF02485264
- 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). MR 0180490
- Ju. L. Eršov, Elementary theories of Post varieties, Algebra i Logika 6 (1967), no. 5, 7–15 (Russian). MR 0231706
- S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57–103. MR 108455, DOI 10.4064/fm-47-1-57-103
- Joohee Jeong, A decidable variety that is finitely undecidable, J. Symbolic Logic 64 (1999), no. 2, 651–677. MR 1777777, DOI 10.2307/2586491
- Klaus Keimel and Heinrich Werner, Stone duality for varieties generated by quasi-primal algebras, Recent advances in the representation theory of rings and $C^{\ast }$-algebras by continuous sections (Sem., Tulane Univ., New Orleans, La., 1973), Mem. Amer. Math. Soc., No. 148, Amer. Math. Soc., Providence, R.I., 1974, pp. 59–85. MR 0360411
- 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. MR 883644
- Ralph McKenzie and Matthew Valeriote, The structure of decidable locally finite varieties, Progress in Mathematics, vol. 79, Birkhäuser Boston, Inc., Boston, MA, 1989. MR 1033992, DOI 10.1007/978-1-4612-4552-0
- Michael O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1–35. MR 246760, DOI 10.1090/S0002-9947-1969-0246760-1
- Matatyanu Rubin, The theory of Boolean algebras with a distinguished subalgebra is undecidable, Ann. Sci. Univ. Clermont No. 60 Math. 13 (1976), 129–134. MR 0465835 A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc. 55 (1949), 64. M. Valeriote, On decidable locally finite varieties, Ph.D. thesis, Univ. of California, Berkeley, 1986.
- M. A. Valeriote and R. Willard, Discriminating varieties, Algebra Universalis 32 (1994), no. 2, 177–188. MR 1290157, DOI 10.1007/BF01191537
- Volker Weispfenning, A note on $\aleph _{0}$-categorical model-companions, Arch. Math. Logik Grundlag. 19 (1978/79), no. 1-2, 23–29. MR 514455, DOI 10.1007/BF02011865
- H. Werner, Varieties generated by quasi-primal algebras have decidable theories, Contributions to universal algebra (Colloq., József Attila Univ., Szeged, 1975) Colloq. Math. Soc. János Bolyai, Vol. 17, North-Holland, Amsterdam, 1977, pp. 555–575. MR 0480273
- Ross Willard, Decidable discriminator varieties with lattice stalks, Algebra Universalis 31 (1994), no. 2, 177–195. MR 1259348, DOI 10.1007/BF01236516
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 336 (1993), 311-333
- MSC: Primary 08A50; Secondary 03B25, 03C05, 08A60
- DOI: https://doi.org/10.1090/S0002-9947-1993-1085938-8
- MathSciNet review: 1085938