Article contents
The reducts of equality up to primitive positive interdefinability
Published online by Cambridge University Press: 12 March 2014
Abstract
We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continuum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.
Keywords
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2010
References
REFERENCES
[BC07] Bodirsky, M. and Chen, H., Quantified equality constraints, LICS'07, 2007, pp. 203–212.Google Scholar
[BK08a] Bodirsky, M. and Kára, J., The complexity of equality constraint languages, Theory of Computing Systems, vol. 3 (2008), no. 2, pp. 136–158, A conference version of the paper appeared in the proceedings of the international Computer Science symposium in Russia (CSR'06).CrossRefGoogle Scholar
[BK08b] Bodirsky, M. and Kára, J., The complexity of temporal constraint satisfaction problems, Proceedings of STOC'08, 2008, pp. 29–38.CrossRefGoogle Scholar
[BN06] Bodirsky, M. and Nešetřil, J., Constraint satisfaction with countable homogeneous templates, Journal of Logic and Computation, vol. 16 (2006), no. 3, pp. 359–373.CrossRefGoogle Scholar
[BCRV04] Böhler, E., Creignou, N., Reith, S., and Vollmer, H., Playing with boolean blocks, part it. constraint satisfaction problems, ACM SIGACT-Newsletter, vol. 35 (2004), no. 1, pp. 22–35.Google Scholar
[Cam76] Cameron, P. J., Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, vol. 148 (1976), pp. 127–139.CrossRefGoogle Scholar
[Cam90] Cameron, P. J., Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, vol. 152, Cambridge University Press, Cambridge, 1990.CrossRefGoogle Scholar
[CD73] Crawley, P. and Dilworth, R. P., Algebraic theory of lattices, Prentice-Hall, 1973.Google Scholar
[Go1] Goldstern, M., Analytic clones, preprint available from http://arxiv.org/math.RA/0404214.Google Scholar
[GP08] Goldstern, M. and Pinsker, M., A survey of clones on infinite sets, Algebra Universalis, vol. 59 (2008), pp. 365–403.CrossRefGoogle Scholar
[GSS] Goldstern, M., Sági, S., and Shelah, S., Very many clones above the unary clone, preprint.Google Scholar
[GS05] Goldstern, M. and Shelah, S., Clones from creatures, Transactions of the American Mathematical Society, vol. 357 (2005), no. 9, pp. 3525–3551.CrossRefGoogle Scholar
[HR94] Haddad, L. and Rosenberg, I. G., Finite clones containing all permutations, Canadian Journal of Mathematics, vol. 46 (1994), no. 5, pp. 951–970.CrossRefGoogle Scholar
[Hei02] Heindorf, L., The maximal clones on countable sets that include all permutations, Algebra Universalis, vol. 48 (2002), pp. 209–222.CrossRefGoogle Scholar
[JZ08] Junker, M. and Ziegler, M., The 116 reducts of (ℚ, <, a), this Journal, vol. 73 (2008), no. 3, pp. 861–884.Google Scholar
[Kru72] Kruskal, J. B., The theory of well-quasi-ordering: A frequently discovered concept, Journal of Combinatorial Theory (A), vol. 13 (1972), pp. 297–305.CrossRefGoogle Scholar
[Lau06] Lau, D., Function algebras on finite sets, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2006.Google Scholar
[MP07] Machida, H. and Pinsker, M., The minimal clones above the permutations, Semigroup Forum, vol. 75 (2007), pp. 181–211.CrossRefGoogle Scholar
[Mil85] Milner, E. C., Basic wqo andbqo theory, Graphs and orders (Rival, I., editor), Reidel, Boston, MA, 1985, pp. 487–502.CrossRefGoogle Scholar
[Pin05a] Pinsker, M., Maximal clones on uncountable sets that include all permutations, Algebra Universalis, vol. 54 (2005), no. 2, pp. 129–148.CrossRefGoogle Scholar
[Pin05b] Pinsker, M., The number of unary clones containing the permutations on an infinite set, Acta Scientiarum Mathematicarum, vol. 71 (2005), pp. 461–467.Google Scholar
[Pin08] Pinsker, M., Sublattices of the lattice of local clones, Proceedings of the ROGICS'08 conference, 2008, pp. 80–87.Google Scholar
[Pin] Pinsker, M., More sublattices of the lattice of local clones, preprint available from http://dmg.tuwien.ac.at/pinsker/.Google Scholar
[PK79] Pöschel, R. and Kalužnin, L., Funktionen- und Relationenalgebren, VEB Deutscher Verlag der Wissenschaften, 1979.CrossRefGoogle Scholar
[Pos41] Post, E. L., The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies, vol. 5, Princeton University Press, 1941.Google Scholar
[Rs82] Rosenberg, I. G. and Schweigert, D., Locally maximal clones, Elektronische Informationsverarbeitung und Kybernetik, vol. 18 (1982), no. 7–8, pp. 389–401.Google Scholar
[Sch78] Schaefer, T. J., The complexity of satisfiability problems, Proceedings of STOC'78, 1978, pp. 216–226.CrossRefGoogle Scholar
[Sze86] Szendrei, Á., Clones in universal algebra, Les Presses de L'Université de Montréal, 1986.Google Scholar
[Tho91] Thomas, S., Reducts of the random graph, this Journal, vol. 56 (1991), no. 1, pp. 176–181.Google Scholar
- 25
- Cited by