Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2025-01-03T17:35:44.230Z Has data issue: false hasContentIssue false
  • English
  • Français

The reducts of equality up to primitive positive interdefinability

Published online by Cambridge University Press:  12 March 2014

Manuel Bodirsky ,
Hubie Chen  and
Michael Pinsker
Manuel Bodirsky
Affiliation:
Laboratoire d'Informatique (LIX), CNRS UMR 7161, École Polytechnique, 91128 Palaiseau, France. E-mail: [email protected], URL: http://www.lix.polytechnique.fr/~bodirsky/
Hubie Chen
Affiliation:
Departament de Tecnologies de la Informació i Les Comunicacions, Universität Pompeu Fabra, Barcelona, Spain. E-mail: [email protected], URL: http://www.tecn.upf.es/~hchen/
Michael Pinsker
Affiliation:
Laboratoire de Mathématiques Nicolas Oresme, CNRS UMR 6139, Université de Caen, 14032 Caen Cedex, France. E-mail: [email protected], URL: http://dmg.tuwien.ac.at/pinsker/
Get access Rights & Permissions [Opens in a new window]

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

relational structurereductprimitive positive definitionlatticeinvariant relationGalois connectionlocal clonepermutations
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 4 , December 2010 , pp. 1249 - 1292
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
[Die05] Diestel, R., Graph theory, 3rd ed., Springer-Verlag, New York, 2005.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
[Sch89] Schöning, U., Logic for computer scientists, Springer, 1989.Google 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