Mereotopologists generally come from either a point-set or algebraic topology perspective when developing boundary-based theories. Some involve dimensional aspects while others do not. Little work has studied whether the existing boundary characterizations convey the same meaning regardless of the mereotopology they build upon. To address this gap, we introduce a new mathematical theory that can be used as a unifying framework for boundaries in both multidimensional and nondimensional mereotopologies. With the proposed unifying framework, we are able to interpret both multidimensionaland nondimensional- based mereotoplogies.
To answer the questions posed by these two motivating scenarios, we need to closely examine the notion of boundary. Little study has successfully formalized the notion of crossing a boundary, inclusive of all dimensions. In the WSC sentence pair, the preposition “through"[5] indicates a movement that goes into at one side and out at another. Hence, we need to study crossing the boundary in terms of a three-dimensional region. On the other hand, the depiction of overlapped points, lines, and cycles in Kandinsky’s oil painting crosses both boundaries and dimensions. This brings our attention to the representation of boundaries across one and multiple dimensions.
The formalization of boundary has long been a topic of discussion in mereotopology. Boundary-agnostic theories have been excluded in this work for two reasons[3]. First, ignoring boundaries contradict the topological distinctions between open and closed entities. Next, in the absence of boundaries, an entity can be connected to its complement. The omission of boundary-less approaches leaves us with two directions for boundary-based approaches. Previous work has taken either a multi-dimensional or non-dimensional perspective. Smith’s mereotopology[6] ignores dimension. His axiomatization arises from point-set topology in which he uses the relation (, ), defined by a primitive relation (, ) (x is an interior part of y). He then takes the sum of all boundary points to form a complete set of boundary. The advocates for multidimensional characterizations come from an algebraic topology perspective; led by Gotts[7] and Galton[8], they take the boundary entity to be one dimension lower than the object it is attached to. Galton’s theory defines the notion of boundary as a primitive relation. Gott’s establishment in INCH Calculus is examined by Hahmann[9]. Hahmann’s mereotopology – CODI – is definably equivalent to the corrected INCH Calculus.
The various formalization regarding the notion of boundary best showcases disagreement behind characterizing spatial entities among mereotopologies. Few studies have focused on comparing and harmonizing diferent perspectives. The main problem we are solving is to ifnd a minimal theory to axiomatize the notion of dimension for elements of a mereology. We introduce the notion of a multimereology, which amalgamates a mereology with an incidence structure to partition partial orderings.
The paper is organized as follows. Section 2 introduces the root theories of multimereology. Inspired by the notion of topological manifolds, Section 3 is initiated from a combinatorial topology standpoint to examine the comprehensiveness of possible multimereology candidates against certain use cases. Section 4 showcases a successful application of our proposed multimereology to be logical equivalent to CODI, a multidimensional mereotopology. Section 5 returns to the motivating question of boundary classification and unification.
In designing an ontology, our objective is twofold – first, to prove that the models of the ontology are actually the intended models, and second, to demonstrate that the intended models do indeed formalize the ontological commitments. Our strategy is to first specify a class of mathematical structures and show that the ontology axiomatizes this class of structures (that is, there is a one-to-one correspondence between the class of models of the ontology and the class of mathematical structures). We then specify a representation theorem for this class of mathematical structures to demonstrate that it formalizes the ontological commitments. The primary benefit of this strategy is that it makes explicit the modular organization of the subtheories of the ontology, thereby highlighting how other ontologies are reused.
The first step is to specify the class of structures which capture the following intuitions and ontological commitments about multidimensional mereology:
3. There is a parthood relation that is specified on entities with the same dimension.
To formalize these semantic requirements for a multidimensional mereology, we introduce the notion of a multimereology as the amalgamation of a partial ordering with an incidence structure. Incidence structures are a generalization of geometry, first introduced by Gino Fano and later used by Hilbert in his axiomatization of Euclidean geometry.
Definition 1. A k-partite incidence structure is a tuple I = ⟨Ω1, ..., Ω, I⟩, where Ω1, ..., Ω are sets such that Ω ∩ Ω = ∅, ̸= and I ⊆ (⋃︀̸= Ω × Ω ).
Two elements of I that are related by I are called incident. The neighbourhood of an element is the set of elements which are incident with it: (x) = {y : ⟨x, y⟩ ∈ I}
Incidence structures are ideally suited to represent the dimensionality of diferent entities. In a tripartite incidence structure, points can be thought of as 0-dimensional, lines as 1-dimensional, and planes as 2-dimensional.
How is the incidence structure in a multimereology related to the partial ordering? The first approach to this question is to consider incidence to itself be a parthood relation, and enforce the transitivity of the incidence relation: Definition 2.
A tripartite incidence structure I = ⟨, , , I⟩ is transitive if
I ∘ I ⊆ I
At first glance, this might seem unusual since the incidence relation is symmetric; we therefore use the following notion from graph theory which allows us to associate a transitive symmetric incidence relation with a partial ordering: Definition 3. The comparability graph for a partial ordering Q = ⟨, ≤⟩ is a graph GQ = ⟨, E⟩ such that
(x, y) ∈ E ⇔ x ≤ y or y ≤ x
A second alternative approach is to start with the “global" partial ordering that applies to all entities, and then use the incidence structure to specify “local" partial orderings on the sets of points, lines, and planes. We therefore need to specify how the suborderings on each of these sets is related to the entire partial ordering.
Definition 4.
The upper set for x in a poset P, denoted by P(x), is The lower set for x in a poset P, denoted by P(x), is P(x) = {y : x ≤ y} P(x) = {y : y ≤ x}
With the aid of this terminology, we can impose the following conditions. The set of points forms a lower set in the partial ordering, so that all parts of points are points. The set of planes forms an upper set in the partial ordering, so that all elements that contain planes as parts are also planes. The set of lines forms an interval within the partial ordering. Alternatively, we can think of the incidence structure as partitioning the elements of the partial ordering into the disjoint classes of points, lines, and planes. Both of these perspectives will be used as the basis for the formalization.
Definition 5.
Q ⊕ I 1is a multimereology if 1The ⊕ symbol denotes the amalgamation of structures [10]. 1234 2345 2. I = ⟨, , , I⟩ such that I ∈ M__; 3. ⟨ ∪ ∪ , I⟩ ⊆
GQ; 4. if x ∈ , then Q(x) ⊆ ; 5. if x, y ∈ , then Q(x) ∩ Q[y] ⊆ ; 6. if x ∈ , then Q(x) ⊆ .
Examples of multimereologies can be seen in Figure 2. Figure 2(a) shows a mereology that has been partitioned into three disjoint sets containing equidimensional elements, while Figure 2(b) is the corresponding tripartite incidence structure. In this example, the element 34 is an equidimensional part of the element 345, and the element 2345 is an equidimensional part of the element 12345. On the other hand, since 345 is a line and 2345 is a plane in the incidence structure, they are related by incidence, even though in the “global" mereology they are related by parthood. 2.1.1. Representation Theorem Intuitively, each partitioning of a partial ordering corresponds to a unique multimereology, and each multimereology can be used to specify a partitioning of a partial ordering. This intuition forms the basis for the representation theorem for multimereologies. We begin by formalizing the idea of partitioning.
Definition 6. Suppose Q, P ∈ M_ such that Q = ⟨1, ≤⟩ , P = ⟨2, ⪯⟩ .
A mapping : Q → P is a poset homomorphism if x ≤
y ⇒ (x) ⪯ (y)
For poset homomorphism, we want to explicitly identify the equivalence class of elements of Q that all map to the same element of P: Definition 7. The idea is that all elements with the same dimension are in the same equivalence class. One of the semantic requirements for multimereologies is that there be a linear ordering on dimensions; if we consider the poset homomorphism to be the mapping from elements to their dimension, then we are particularly interested in the set of poset homomorphisms between partial orderings and finite linear orderings.
Theorem 1. Let (M_, 3) denote the set of all poset homomorphisms between partial orderings and the finite linear ordering with 3 elements.
There is a bijection: : (M_, 3) → M such that for any Q ∈ M_, ( ) = Q ⊕ I if : Q → 3 and
I(x) = ((Q[x] ∪ Q[x]) ∖ (x))
In other words, each multimereology corresponds to a poset homomorphism between a partial ordering and a linear ordering, and any poset homomorphism between a partial ordering and a linear ordering can be used to construct a multimereology.
In Figure 2(a), all elements of the partial ordering that are points in the incidence structure are
exactly the elements that are mapped to the minimum element of the linear ordering. Similarly,
all elements of the partial ordering that are planes in the incidence structure are exactly the
elements that are mapped to the maximum element of the linear ordering.
2.1.2. Axiomatization
can be found in Figure 2.1.2. The first three axioms are for partial orderings
(condition (
x ∈ Q[y]. 2. ⟨x, y⟩ ∈ inℳ if
x ∈ I[y]. 2Mod(.) denotes the class of models of the given ontology. 3M denotes a class of mathematical structures. 4ℳ is a specific model
∀ (, ) ∀, (, ) ∧ (, ) ⊃ ( = ) ∀, , (, ) ∧ (, ) ⊃ (, )
∀ (, ) ∀, (, ) ⊃ (, ) ∀, () ∧ () ∧ (, ) ⊃ ( = )
∀, () ∧ () ∧ (, ) ⊃ ( = ) ∀, () ∧ () ∧ (, ) ⊃ ( = ) ∀, , (, ) ∧ (, ) ⊃ (, ) ∀ (() ∨ () ∨ ()) ∀, ((, ) ⊃ ((, ) ∨ (, ))) ∀, ((() ∧ (, )) ⊃ ()) ∀, , ((() ∧ () ∧ (, ) ∧ (, )) ⊃ ()) ∀, ((() ∧ (, )) ⊃ ())
∀, ((, ) ≡ ((() ∧ () ∧ (, ))∨ (() ∧ () ∧ (, )) ∨ (() ∧ () ∧ (, ))))
x ∈ ⟨,≤⟩ [y] ∪ ⟨,≤⟩ [y] ∪ ⟨,≤⟩ [y].
Theorem 2 together with Theorem 1 show that we have characterized the models of up to isomorphism as the class of multimereologies. Moreover, we can easily see how multimereologies satisfy the semantic requirements. The incidence structure guarantees that elements are assigned a unique dimension and that the dimensions are linearly ordered. By partitioning the mereology into intervals of elements with the same dimension, we have both a parthood relation that is specified on entities with the same dimension., and a multidimensional parthood relation.
Although any partial ordering can be amalgamated with an incidence structure to construct a multimereology, two questions arise: 1. What is the appropriate partial ordering to represent the “global mereology"? 2. What criteria do we need to impose on the partitioning of the partial ordering into “local" equidimensional mereologies?
To answer these questions, we turn to the field of algebraic topology and the notion of topological manifold.
3
4 1
2 (a) 12 1
Mathematicians have long used the notion of manifold to formalize the topology of shape and space. Of key interest for this paper is that topological manifolds provide an explicit notion of dimension – an n-dimensional manifold is a topological space in which every point has a neighbourhood that is homeomorphic to R. In this section, we explore how diferent combinatorial structures for topological manifolds are related to multimereologies, and arrive at a suitable generalization of both that can serve as the basis for the framework that we seek to unify the nondimensional and multidimensional approaches to mereologies.
One combinatorial approach to the notion of manifold can be found in the notion of an abstract simplicial complex, which is a collection of finite sets that is closed under taking subsets: Definition 8. A family of sets Δ is called an abstract simplicial complex if, for every set X in Δ and every non-empty subset ⊆ , we have ∈ Δ.
An example of an abstract simplicial complex can be found in Figure 4(b). The dimension of an element in an abstract simplicial complex is equal to one less than the cardinality of the set corresponding to the element. Thus, the dimension of the element 23 is one and the dimension of the element 123 is two. A simplicial -complex is a simplicial complex in which the maximal dimension of an element in .
Interestingly, we can associate a mereology with any abstract simplicial complex. Recall that classical extensional mereology _ is the axiomatization of classical mereology together with the Strong Supplementation Principle5. Let 2_ be the extension of _ in which all models have rank 3 (i.e. all maximal chains in the model have cardinality 3).
Theorem 3. 2_ is logically synonymous [10] to _2 6. 5https://github.com/gruninger/colore/blob/master/ontologies/mereology/cem_mereology.clif 6https://github.com/gruninger/colore/blob/master/ontologies/tripartite_incidence/simplicial_2complex.clif
In other words, there is a one-one-correspondence between simplicial 2-complexes and models of 2_. In this sense, classical extensional mereology is the natural mereology for simplicial complexes. Nevertheless, even though we can associate a mereology with simplicial complexes, this approach falls short because it is trivial on equidimensional elements – no chain in the mereology contains elements with the same dimension. On the other hand, multimereologies allow models in which there is a nontrivial mereology on equidimensional elements.
An alternative approach to topological manifolds, from a combinatorial point of view, is the notion of a CW-complex, and we can ask how it can be related to mereologies. To start, we adopt Hatcher’s definition [11]: Definition 9.
CW complex is a space constructed in the following way: 1. Start with a discrete set 0, the 0-cell of . 2. Inductively, form the n-skeleton from − 1 by attaching n-cells via maps : − 1 → − 1. This means that is the quotient space of − 1 ⨆︀ under the identifications ∼ () for ∈ . The cell is the homeomorphic image of − . 3. = ⋃︀ with the weak topology: A set ⊂ is open (or closed) if ∩ is open (or closed) in for each .
A CW complex is constructed by induction via a cell attachment process. Simply put, each cell is attached to the existing one at its boundary in increasing order of dimensions. The connected graph in Figure 5(a) is the 1-skeleton of a CW complex. Figure 5(b) is the mereological representation corresponding to the construct of a CW complex. Since the 1-cells in the construction of a CW-complex are edges, the notion of “a path in a graph", like that of 123 in Figure 5(a), does not exist in the context of a CW complex. Nonetheless, in multimereology, we indeed want to diferentiate between an edge and a path. Even though a path is homeomorphic to an edge, we want to treat paths and edges as two separate entities that are of the same dimension.
In this sense, CW complexes sufer from the same drawback as simplicial complexes on non-trivially representing equidimensional elements. Even though we need a more general structure than CW complexes to formalize mereologies and dimensionality, we still obtain the key insight that each 1-complex is a connected graph. Therefore, the associated mereology should correspond to the connected induced subgraphs of the graph that is the 1-complex.
In the mereotopology _ [12], the sum of two elements exists if they are connected. A weaker mereotopology __ alllows connected elements that do not have sums, although elements for which sums do exist must be connected. In a model of _, there is one-to-one correspondence between elements in the mereology and connected induced 1245 1345 subgraphs of a connected graph, and the parthood relation is isomorphic to the containment ordering on the set of subgraphs.
Furthermore, many graph-theoretic properties are definable within the mereotopology. Paths in the graphs correspond to minimal upper bounds in the mereology and cycles in the graph correspond to triangles within the connection structure of the mereotopology. The identification of paths and cycles within an underlying graph is precisely the way in which we can use _ as the mereology within a multimereology that extends the structure of a CW-complex. Even though _ axiomatizes a mereology which is nondimensional, it is able to distinguish among elements which in the context of CW-complexes have diferent dimensions. On the other hand, _ also axiomatizes the mereology among elements with the same dimension, such as subpaths of paths and cycles which are subgraphs of 2-complexes.
Figure 6(a) showcases CISCO structure in representation of a 2-connected graph. We can non-trivially partition this given mereology into Figure 6(b). Element 124 is incident to 1234, and it is an equi-dimensional part of 1245.
An application of a multimereology based on can be seen in the Molecular Structure Ontology (MoSt) [13]. MoSt is an ontology to describe the shape of a molecule; it treats functional groups, that are composed of rings and chains, to be incident to skeletons, while
A further application of multimereology is that it can be used as the basis for evaluating other multidimensional mereotopologies. In particular, we can use multimereology to provide a verification of CODI [ 9]. Recall that the major benefit of CODI, compared to Gotts’ and Galton’s approaches, is its expressive power insofar as it generalizes relations between spatial entities up to finite dimensions within a single model. _ introduces three primitive relations for specifying a multidimensional mereotopology. The first two relations ( < (, ), (, )) specify the relative dimension of two elements; in particular, < (, ) is a linear ordering over dimensions. The third relation ((, )) is a parthood relation that applies to all elements regardless of their dimension such that the dimension of an element has a dimension greater than or equal to its parts.
To compare our axiomatization in with _, we want to find a common ground where the set of minimal and maximal dimensions allowed is the same for both sides. Since can only capture entities up to two-dimensional planes, we must restrict _ to two dimensions as well: Definition 10. 2__ is the following set of axioms: ∀, ((, ) ⊃ (< (, ) ∨ (, ))) ∃ ( ()) ∀ (¬ < , ) ∀, (< , ) ⊃ (¬ < (, )) ∀, , (< (, ) ∧ (< (, ) ∨ (, )) ⊃ (< (, )))
∀, (((, ) ∧ (, )) ⊃ ( = )) ∀, , (((, ) ∧ (, )) ⊃ ((, ))) ∀ ( () ∨ () ∨ ()) (16) (17) (18) (19) (20) (21) (22) (23) Theorem 4. 2__ is logically synonymous with .
By this Theorem, we know that there is a one-to-one correspondence between models of and models of 2__. Furthermore, because of Theorem 1, we know that all models of 2__ can be constructed by partitioning a partial ordering into intervals.
We want the weakest possible mereotopology in which the notions of boundary can be represented and unified. In this section, we demonstrate the capabilities of multimereologies in terms of representing diferent notions of boundary within the same theory.
We exploit the dual nature of the models of _ – on the one hand, models of are nondimensional mereologies, but because the elements of these mereologies correspond to connected subgraphs of a graph, they can also represent properties of graphs. The obvious place to start is to note that within graph theory there is a notion of the boundary of a subgraph [14]:
The boundary of the cycle 1234 in Figure 6 is {45}, while the boundary of the edge 12 in the same Figure is {23, 14}.
Inspired by algebraic topology [15], our interpretation of multidimensional notion of boundary exhibits the following two characteristics:
2. is said to be the boundary of if is a pendant element 7 of y. which can be axiomatized as Definition 13.
∀, ((, ) ≡ (, ) ∧ _(, ) ∧ (, )) (26) ∀, ((, ) ≡ ∃ , ((, ) ∧ (, ) ∧ (, ) ∧ (, ) ∧ ¬( = ))) (27) ∀, (_(, ) ≡ ((, ) ∧ ̸= ∧ ¬∃ ((, ) ∧ (, ) ∧ (, )) ∧ ̸= ∧ ̸= )) (28)
According to this multidimensional characterization of boundary, in the same Figure6(b), element 2 is not in the boundary of 123 because it is incident to more than one incomparable equi-dimensional parts. Contrarily, 1 and 3 are the boundary of 123 because it is incident to exactly one incomparable equi-dimensional part. In the same example in Figure5(a), the set of boundary that was generated based on graph-theory definition is diferent from that of a multidimensional based one. Note that even though multimereology successfully captures both non- and multi-dimensional approaches to boundary, the exact relationship that holds between these two approaches remains an open question. 7In graph theory, a pendant element is connected to exactly one neighboring element.
This work was motivated by the need to integrate diferent characterizations of boundary. From the Winograd Schema Challenge to Kandinsky’s painting, we saw that boundary is only of a special form to the dimension discrepancy founded by diferent mathematical theories, and borrowed by various mereotopologies. Instead of favoring one theory over the other, we established a common ground for non- and multi-dimensional approaches.
We started the discussion of unification by specifying ontological commitments that a multidimensional mereology must satisfy. We introduced the notion of multimereology, an amalgamation of a partial ordering and incidence structure that formalizes these commitments. A key result is that each partitioning of a partial ordering corresponds to a unique multimereology, and each multimereology specifies a partitioning of a partial ordering. This forms the basis of the representation theorem for the class of multimereologies with respect to the set of poset homomorphisms between partial orderings and finite linear orderings. Finally, we axiomatized the class of multimereologies up to isomorphism.
Coming up with root theories for multimereology left us with the problem of amalgamating an appropriate partial ordering with partitioning criteria. We therefore turned to the field of algebraic topology to find the “right" manifold that can characterize our notion of partitioning a partial ordering. We examined abstract simplicial complexes and regular CW complexes as two possibilities. Due to the sets of construction rules they impose on topological spaces, both CW and simplicial complexes fall short in representing non-trivial mereology within a single dimension. We proceeded to showcase the expressiveness of our multimereology by interpreting and representing other non- and multi-dimensional approaches.
So far, this work provided a middle ground to compare diferent notions of boundary. In the future, we plan to explore and extend what multimereology is capable of. This can be achieved in two directions. First, it would be useful to compose an exact theorem that captures the relationship between non- and multi-dimensional boundary. Next, if we could use multimereology to validate Smith’s and Hahmann’s mereotopologies, we would be one step closer to harmonizing this dimension disagreement. [5] Dictionary, Through definition & meaning, 2023. URL: https://www.merriam-webster.co m/dictionary/through. [6] B. Smith, Mereotopology: A theory of parts and boundaries, Data & Knowledge Engineering 20 (1996) 287–303. URL: https://www.sciencedirect.com/science/article/pii/S01690 23X96000158. doi:https://doi.org/10.1016/S0169-023X(96)00015-8, modeling Parts and Wholes. [7] N. M. GottsDivision, Formalizing commonsense topology : The inch calculus, 1996. [8] A. Galton, Taking dimension seriously in qualitative spatial reasoning, in: W. Wahlster (Ed.), 12th European Conference on Artificial Intelligence, Budapest, Hungary, August 11-16, 1996, Proceedings, John Wiley and Sons, Chichester, 1996, pp. 501–505. [9] T. Hahmann, M. Grüninger, Region-Based Theories of Space: Mereotopology and Beyond, 2012, pp. 1–62. doi:10.4018/978-1-61692-868-1.ch001. [10] B. Aameri, M. Grüninger, Reducible theories and amalgamations of models, ACM Transactions on Computational Logic 24 (2023) 1–24. doi:10.1145/3565364. [11] A. Hatcher, Algebraic Topology, Algebraic Topology, Cambridge University Press, 2002.
URL: https://books.google.ca/books?id=BjKs86kosqgC. [12] M. Grüninger, C. Chui, Y. Ru, J. Thai, A Mereology for Connected Structures, Frontiers in
Artificial Intelligence and Applications, 2020. doi: 10.3233/faia200670. [13] C. Chui, M. Grüninger, A molecular structure ontology for medicinal chemistry, in: R. Ferrario, W. Kuhn (Eds.), Formal Ontology in Information Systems - Proceedings of the 9th International Conference, FOIS 2016, Annecy, France, July 6-9, 2016, IOS Press, 2016, pp. 285–298. [14] A. Timar, Boundary-connectivity via graph theory, Proceedings of the American Mathematical Society 141 (2012) 475–480. [15] J. M. Lee, Homology, Graduate Texts in Mathematics, 2011, p. 339–380. doi:10.1007/97 8-1-4419-7940-7_13.