On the homogeneous countable Boolean contact algebra

Ivo Düntsch, Sanjiang Li

DOI: http://dx.doi.org/10.12775/LLP.2013.012


In a recent paper, we have shown that the class of Boolean contact algebras (BCAs) has the hereditary property, the joint embedding property and the amalgamation property. By Fraïssé’s theorem, this shows that there is a unique countable homogeneous BCA. This paper investigates this algebra and the relation algebra generated by its contact relation. We first show that the algebra can be partitioned into four sets {0}, {1}, K, and L, which are the only orbits of the group of base automorphisms of the algebra, and then show that the contact relation algebra of this algebra is finite, which is the first non-trivial extensional BCA we know which has this property.


pointless geometry; Boolean contact algebra; homogeneous structure; contact relation algebra, region connection calculus

Full Text:



Andréka, H., I. Düntsch, and I. Németi, “Binary relations and permutation groups”, Math. Logic Quarterly, 41 (1995): 197–216.

Birkhoff, G., Lattice Theory, vol. 25 of Am. Math. Soc. Colloquium Publications, 2nd edn., AMS, Providence, 1948.

Clarke, B.L., “A calculus of individuals based on ‘connection’”, Notre Dame Journal of Formal Logic, 22 (1981): 204–218.

de Laguna, T., “Point, line and surface as sets of solids”, The Journal of Philosophy, 19 (1922): 449–461.

Dimov, G., and D. Vakarelov, “Contact algebras and region-based theory of space: A proximity approach – I”, Fundamenta Informaticae, 74 (2006): 209 – 249.

Düntsch, I., and S. Li, “Extension properties of Boolean contact algebras”, in W. Kahl, and T.G. Griffin (eds.), Proceedings of RAMiCS 2012, vol. 7560 of “Lecture Notes in Computer Science”, Springer Verlag, Heidelberg, 2012, pp. 342–356.

Düntsch, I., G. Schmidt, and M. Winter, “A necessary relation algebra for mereotopology”, Studia Logica, 69 (2001): 381–409.

Düntsch, I., H. Wang, and S. McCloskey, “Relation algebras in qualitative spatial reasoning”, Fundamenta Informaticae, 39 (1999): 229–248.

Düntsch, I., and M. Winter, “Construction of Boolean contact algebras”, AI Communications, 13 (2004): 235–246.

Düntsch, I., and M. Winter, “The lattice of contact relations on a Boolean algebra”, in R. Berghammer, B. Möller, and G. Struth (eds.), Proceedings of the 10thInternational Conference on Relational Methods in Computer Science and the 5thInternational Workshop on Applications of Kleene Algebra, vol. 4988 of “Lecture Notes in Computer Science”, Springer Verlag, Heidelberg, 2008, pp. 99–109.

Galton, A., “The mereotopology of discrete space”, in C. Freksa, and D.M. Mark (eds.), Spatial Information Theory: Proceedings of the International Conference COSIT ’99, lncs, sv, 1999, pp. 251–266.

Gerla, G., “Pointless geometries”, in F. Buekenhout (ed.), Handbook of Incidence Geometry, chap. 18, Eslevier Science B.V., 1995, pp. 1015–1031.

Grzegorczyk, A., “Axiomatization of geometry without points”, Synthese, 12 (1960): 228–235.

Hodges, W., Model theory, Cambridge University Press, Cambridge, 1993.

Jónsson, B., “Maximal algebras of binary relations”, Contemporary Mathematics, 33 (1984): 299–307.

Jónsson, B., and A. Tarski, “Boolean algebras with operators I”, American Journal of Mathematics, 73 (1951): 891–939.

Jónsson, B., and A. Tarski, “Boolean algebras with operators II”, American Journal of Mathematics, 74 (1952): 127–162.

Koppelberg, S., I. Düntsch, and M. Winter, “Remarks on contact relations on Boolean algebras”, Algebra Universalis, 68 (2012), 3–4: 353–366.

Koppelberg, S., General Theory of Boolean Algebras, vol. 1 of Handbook of Boolean Algebras, North-Holland, 1989.

Li, S., and M. Ying, “Region connection calculus: Its models and composition table”, Artificial Intelligence, 145 (2003): 121–145.

Li, Y., S. Li, and M. Ying, “Relational reasoning in the region connection calculus”, 2003, http://arxiv.org/abs/cs.AI/0505041.

Macpherson, D., “A survey of homogeneous structures”, 2011. Retrieved September 20, 2011, from http://www1.maths.leeds.ac.uk/Pure/staff/macpherson/homog_final2.pdf.

Madarász, J., and T. Sayed Ahmed, “Amalgamation, interpolation and epimorphisms in alegraic logic”, in H. Andréka, M. Ferenczi, and I. Németi (eds.), Cylindric-like Algebras and Algebraic Logic, vol. 22 of “Bolay Society Mathematical Studies”, North-Holland, 2012.

Mormann, T., “Holes in the region connection calculus”, 2001. Preprint, Presented at RelMiCS 6, Oisterwijk, October 2001.

Nicod, J., “Geometry in a sensible world”, Doctoral thesis, Sorbonne, Paris 1924. English translation in Geometry and Induction, Routledge and Kegan Paul, 1969.

Randell, D.A., Z. Cui, and A.G. Cohn, “A spatial logic based on regions and connection”, in B. Nebel, W. Swartout, and C. Rich (eds.), Proc. 3rd Int Conf. Knowledge Representation and Reasoning, Morgan Kaufmann, 1992, pp. 165–176.

Stell, J., “Boolean connection algebras: A new approach to the region connection calculus”, Artificial Intelligence, 122 (2000): 111–136.

Tarski, A., “Les fondements de la géométrie du corps”, in Księga Pamiątkowa Pierwszego Polskiego Zjazdu Matematycznego, (1929), pp. 29–33 (summary of an address given to the First Polish Mathematical Congress, Lwów, 1927). English translationin J.H. Woodger (ed.), Logic, Semantics, Metamathematics, Clarendon Press, 1956.

Tarski, A., and S. Givant, A formalization of Set Theory without Variables, vol. 41 of “Colloquium Publications”, Amer. Math. Soc., Providence, 1987.

Whitehead, A.N., Process and Reality, MacMillan, New York, 1929.

ISSN: 1425-3305 (print version)

ISSN: 2300-9802 (electronic version)

Partnerzy platformy czasopism