Decidable discriminator varieties from unary classes
Author:
Ross Willard
Journal:
Trans. Amer. Math. Soc. 336 (1993), 311333
MSC:
Primary 08A50; Secondary 03B25, 03C05, 08A60
MathSciNet review:
1085938
Fulltext 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 twoelement 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 firstorder theory of is decidable.
 [1]
S.
BulmanFleming and H.
Werner, Equational compactness in quasiprimal varieties,
Algebra Universalis 7 (1977), no. 1, 33–46. MR 0429694
(55 #2705)
 [2]
Stanley
Burris, Iterated discriminator varieties have undecidable
theories, Algebra Universalis 21 (1985), no. 1,
54–61. MR
835970 (87g:08018), http://dx.doi.org/10.1007/BF01187556
 [3]
Stanley
Burris and Ralph
McKenzie, Decidability and Boolean representations, Mem. Amer.
Math. Soc. 32 (1981), no. 246, viii+106. MR 617896
(83j:03024), http://dx.doi.org/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. MR 1136462
(93f:08006), http://dx.doi.org/10.2307/2275480
 [5]
Stanley
Burris and H.
P. Sankappanavar, A course in universal algebra, Graduate
Texts in Mathematics, vol. 78, SpringerVerlag, New YorkBerlin, 1981.
MR 648287
(83k:08001)
 [6]
Stanley
Burris and Heinrich
Werner, Sheaf constructions and their
elementary properties, Trans. Amer. Math.
Soc. 248 (1979), no. 2, 269–309. MR 522263
(82d:03049), http://dx.doi.org/10.1090/S00029947197905222638
 [7]
Stephen
D. Comer, Elementary properties of structures of sections,
Bol. Soc. Mat. Mexicana (2) 19 (1974), no. 2,
78–85. MR
0437333 (55 #10265)
 [8]
Stephen
D. Comer, Monadic algebras with finite degree, Algebra
Universalis 5 (1975), no. 3, 313–327. MR 0403965
(53 #7774)
 [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).
MR
0180490 (31 #4725)
 [10]
Ju.
L. Eršov, Elementary theories of Post varieties,
Algebra i Logika 6 (1967), no. 5, 7–15
(Russian). 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]
Joohee
Jeong, A decidable variety that is finitely undecidable, J.
Symbolic Logic 64 (1999), no. 2, 651–677. MR 1777777
(2002h:03078), http://dx.doi.org/10.2307/2586491
 [13]
Klaus
Keimel and Heinrich
Werner, Stone duality for varieties generated by quasiprimal
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. MR 0360411
(50 #12861)
 [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. MR 883644
(88e: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. MR 1033992
(92j:08001)
 [16]
Michael
O. Rabin, Decidability of secondorder theories
and automata on infinite trees., Trans. Amer.
Math. Soc. 141
(1969), 1–35. MR 0246760
(40 #30), http://dx.doi.org/10.1090/S00029947196902467601
 [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. 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.
A. Valeriote and R.
Willard, Discriminating varieties, Algebra Universalis
32 (1994), no. 2, 177–188. MR 1290157
(95m:08010), http://dx.doi.org/10.1007/BF01191537
 [21]
Volker
Weispfenning, A note on ℵ₀categorical
modelcompanions, Arch. Math. Logik Grundlag. 19
(1978/79), no. 12, 23–29. MR 514455
(80g:03032), http://dx.doi.org/10.1007/BF02011865
 [22]
H.
Werner, Varieties generated by quasiprimal algebras have decidable
theories, Contributions to universal algebra (Colloq., József
Attila Univ., Szeged, 1975) NorthHolland, Amsterdam, 1977,
pp. 555–575. Colloq. Math. Soc. János Bolyai, Vol. 17. MR 0480273
(58 #451)
 [23]
Ross
Willard, Decidable discriminator varieties with lattice
stalks, Algebra Universalis 31 (1994), no. 2,
177–195. MR 1259348
(95h:08009), http://dx.doi.org/10.1007/BF01236516
 [1]
 S. BulmanFleming and H. Werner, Equational compactness in quasiprimal varieties, Algebra Universalis 7 (1977), 3346. MR 0429694 (55:2705)
 [2]
 S. Burris, Iterated discriminator varieties have undecidable theories, Algebra Universalis 21 (1985), 5461. 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), 13551368. MR 1136462 (93f:08006)
 [5]
 S. Burris and H. P. Sankappanavar, A course in universal algebra, SpringerVerlag, 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), 269309. MR 522263 (82d:03049)
 [7]
 S. Comer, Elementary properties of structures of sections, Bol. Soc. Mat. Mexicana 19 (1974), 7885. MR 0437333 (55:10265)
 [8]
 , Monadic algebras with finite degree, Algebra Universalis 5 (1975), 315327. 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), 1738. MR 0180490 (31:4725)
 [10]
 , Elementary theory of Post varieties, Algebra i Logika 6 (1967), 715. MR 0231706 (38:34)
 [11]
 S. Feferman and R. L. Vaught, The first order properties of products of algebraic systems, Fund. Math. 47 (1959), 57103. 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. 5985. 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), 135. MR 0246760 (40:30)
 [17]
 M. Rubin, The theory of Boolean algebras with a distinguished subalgebra is undecidable, Ann. Sci. Univ. ClermontFerrand II Math., no. 60 (1976), 129134. 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 aleph0categorical model companions, Arch. Math. Logic 19 (1978), 2329. 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, NorthHolland, 1977, pp. 555575. 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:
http://dx.doi.org/10.1090/S00029947199310859388
PII:
S 00029947(1993)10859388
Article copyright:
© Copyright 1993
American Mathematical Society
