×

A complete axiom system for polygonal mereotopology of the real plane. (English) Zbl 0921.03009

This paper proposes a calculus for mereotopological reasoning in which 2-dimensional spatial regions are treated as primitive entities.
The syntactical foundation is the (first-order) language \({\mathcal L}\) of Boolean algebras with a distinguished predicate \(c(x)\). Two formal models for the mereotopological language \({\mathcal L}\) are presented:
In an interpretation \({\mathcal R}\) for \({\mathcal L}\) the polygonal open subsets of the real plane \(\mathbb{R}^2\) serve as elements of the domains; and the predicate \(c(x)\) is read as “region \(x\) is connected”. (Function-symbols +, \(\cdot\) and \(-\) and constants 0 and 1 are given their meaning in terms of a Boolean algebra of polygons.)
Another interpretation \({\mathcal S}\) for \({\mathcal L}\) is based on the closed plane \(\mathbb{R}^2\cup \{\infty\}\), under the usual topology. This model \({\mathcal S}\) is isomorphic to \({\mathcal R}\).
The mereotopological calculus \({\mathcal C}\) is determined by a set of (eleven) axioms and rules of inference stated in the language \({\mathcal L}\).
The main part of this paper is to show that the axiom system \({\mathcal C}\) is sound and complete with respect to the given interpretations \({\mathcal R}\) and \({\mathcal S}\). These properties of the axiom system \({\mathcal C}\) are useful for theoretical aspects and for applications of the mereotopology. For such theoretical expositions see, among others, papers by B. L. Clarke [Note Dame J. Formal Logic 22, 204-218 (1981; Zbl 0438.03032) and ibid. 26, 61-75 (1985; Zbl 0597.03005)] and I. Pratt and O. Lemon [ibid. 38, 225-245 (1997; Zbl 0897.03014)] and relevant conference-reports.

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
54A99 Generalities in topology
68T27 Logic in artificial intelligence
51M99 Real and complex geometry
03C65 Models of other mathematical theories
Full Text: DOI

References:

[1] Asher, N. and Vieu, L.: Toward a geometry of common sense – A semantics and acomplete axiomatization of mereotopology, in Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), 1995, pp. 846–852.
[2] Biacino, L. and Gerla, G.: Connectionstructures: Grzegorczyk’s and Whitehead’s definition of point, Notre Dame J. Formal Logic 37(3) (1996), 431–439. · Zbl 0877.51006 · doi:10.1305/ndjfl/1039886519
[3] Bollobás, Béla: Graph Theory: An Introductory Course, Spinger-Verlag, New York, 1979. · Zbl 0688.05016
[4] Borgo, S., Guarino, N. and Masolo, C.: A pointless theory of space basedon strong connection and congruence, in L. C. Aiello, J. Doyle, and S. C. Shapiro (eds), Principles of Knowledge Representation and Reasoning: Proceedings of the Fifth International Conference (KR’ 96), Morgan Kaufmann, San Francisco, CA, 1996, pp. 220–229.
[5] Chang, C. C. and Keisler, H. J.: ModelTheory, 3rd edition, North-Holland, Amsterdam, 1990.
[6] Clarke, B. L.:A calculus ofindividuals based on ”connection”, Notre Dame J.Formal Logic 22(3) (1981), 204–218. · doi:10.1305/ndjfl/1093883455
[7] Clarke, B. L.: Individuals and points, Notre Dame J. Formal Logic 26(1) (1985), 61–75. · Zbl 0597.03005 · doi:10.1305/ndjfl/1093870761
[8] Gotts, N. M., Gooday, J. M. and Cohn, A. G.: A connection based approach to commonsense topological description and reasoning, Monist 79(1) (1996), 51–75.
[9] Johnstone, P. T.: Stone Spaces,Cambridge University Press, Cambridge, 1982. · Zbl 0499.54001
[10] Newman, M. H. A.: Elements of the Topology ofPlane Sets of Points, Cambridge University Press, Cambridge, 1964.
[11] Pratt, Ian and Lemon, Oliver: Ontologies for plane, polygonal mereotopology, Notre Dame J. Formal Logic 38(2) (1997), 225–245. · Zbl 0897.03014 · doi:10.1305/ndjfl/1039724888
[12] Randell, D. A., Cui, Z. and Cohn, A. G.: A spatial logic based on regions andconnection, in B. Nebel, C. Rich, and W. Swartout (eds), Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR’ 92), Morgan Kaufmann, Los Altos, CA, 1992, pp. 165–176.
[13] Tarski, Alfred: Foundations of the geometry of solids, in Logic, Semantics,and Metamathematics, Clarendon Press, Oxford, 1956, pp. 24–29.
[14] Whitehead, A. N.:Process and Reality, The MacMillan Company, New York, 1929. · JFM 55.0035.03
[15] Wilson, Robin J.:Introduction to Graph Theory, Longman, London, 1979. · Zbl 0458.05024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.