Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Decidable discriminator varieties from unary classes


Author: Ross Willard
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] S. Bulman-Fleming and H. Werner, Equational compactness in quasiprimal varieties, Algebra Universalis 7 (1977), 33-46. MR 0429694 (55:2705)
  • [2] S. Burris, Iterated discriminator varieties have undecidable theories, Algebra Universalis 21 (1985), 54-61. MR 835970 (87g:08018)
  • [3] S. Burris and R. McKenzie, Decidability and Boolean representations, Mem. Amer. Math. Soc., vol. 246, 1981. MR 617896 (83j:03024)
  • [4] S. Burris, R. McKenzie, and M. Valeriote, Decidable discriminator varieties from unary varieties, J. Symbolic Logic 56 (1991), 1355-1368. MR 1136462 (93f:08006)
  • [5] S. Burris and H. P. Sankappanavar, A course in universal algebra, Springer-Verlag, New York, 1981. MR 648287 (83k:08001)
  • [6] S. Burris and H. Werner, Sheaf constructions and their elementary properties, Trans. Amer. Math. Soc. 248 (1979), 269-309. MR 522263 (82d:03049)
  • [7] S. Comer, Elementary properties of structures of sections, Bol. Soc. Mat. Mexicana 19 (1974), 78-85. MR 0437333 (55:10265)
  • [8] -, Monadic algebras with finite degree, Algebra Universalis 5 (1975), 315-327. MR 0403965 (53:7774)
  • [9] Yu. Ershov, Decidability of the elementary theory of relatively complemented lattices and of the theory of filters, Algebra i Logika 3 (1964), 17-38. MR 0180490 (31:4725)
  • [10] -, Elementary theory of Post varieties, Algebra i Logika 6 (1967), 7-15. MR 0231706 (38:34)
  • [11] S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57-103. MR 0108455 (21:7171)
  • [12] J. Jeong, A decidable variety that is not finitely decidable, J. Symbolic Logic (to appear). MR 1777777 (2002h:03078)
  • [13] K. Keimel and H. Werner, Stone duality for varieties generated by quasi primal algebras, Mem. Amer. Math. Soc., no. 148, 1974, pp. 59-85. MR 0360411 (50:12861)
  • [14] R. McKenzie, G. McNulty, and W. Taylor, Algebras, lattices, varieties, vol. I, Wadsworth & Brooks/Cole, Monterey, Calif., 1987. MR 883644 (88e:08001)
  • [15] R. McKenzie and M. Valeriote, The structure of decidable locally finite varieties, Birkhäuser, Boston, Mass., 1989. MR 1033992 (92j:08001)
  • [16] M. O. Rabin, Decidability of second order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1-35. MR 0246760 (40:30)
  • [17] M. Rubin, The theory of Boolean algebras with a distinguished subalgebra is undecidable, Ann. Sci. Univ. Clermont-Ferrand II Math., no. 60 (1976), 129-134. MR 0465835 (57:5721)
  • [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. Valeriote and R. Willard, Discriminating varieties, Algebra Universalis (to appear). MR 1290157 (95m:08010)
  • [21] V. Weispfennig, A note on aleph-0-categorical model companions, Arch. Math. Logic 19 (1978), 23-29. MR 514455 (80g:03032)
  • [22] H. Werner, Varieties generated by quasiprimal algebras have decidable theories, Contributions to Universal Algebra (B. Csákány and J. Schmidt, eds.), Math. Soc. János Bolyai, vol. 17, North-Holland, 1977, pp. 555-575. MR 0480273 (58:451)
  • [23] R. Willard, Decidable discriminator varieties with lattice stalks, Algebra Universalis (to appear). MR 1259348 (95h:08009)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 08A50, 03B25, 03C05, 08A60

Retrieve articles in all journals with MSC: 08A50, 03B25, 03C05, 08A60


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1993-1085938-8
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society