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 be a class of (universal) algebras of fixed type. denotes the class obtained by augmenting each member of by the ternary discriminator function if , while is the closure of under the formation of subalgebras, homomorphic images, and arbitrary Cartesian products. For example, the class of Boolean algebras is definitionally equivalent to where 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 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 of unary algebras of finite type for which the first-order theory of is decidable.

**[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)**

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