Granular Mereotopology: A First Sketch

Abstract

Mereotopology aims at a reconstruction of notions of set topology in mereological universa. Because of foundational di erences between set theory and mereology, most notably, the absence of points in the latter, the rendering of notions of topology in mereology faces serious di culties. On the other hand, some of those notions, e.g., the notion of a boundary, belong in the canon of the most important notions of mereotopology, because of applications in, e.g., geographic information systems. Rough mereology allows for a formal theory of knowledge granulation, and, granules may serve as approximations to open sets, hence, it is reasonable to explore the possibility of their usage in buildup of mereotopological constructs. This work is segmented into sections on mereology, rough mereology, granule theory, mereotopology.

-

(x; y) _ x = y: (1) Clearly, the relation of an ingredient is a partial order on things.

We formulate the third axiom of Standard Mereology which does involve the notion of an ingredient. Before it, we introduce a property of things. For things x; y, we let,

I(x; y): For each thing t such that ingr(t; x), there exist things w; z such that ingr(w; t); ingr(w; z); ingr(z; y)

Now, we can state an axiom.

M3 (Inference Rule) For each pair of things x; y, the property I(x; y) implies that ingr(x; y) The predicate of overlap, Ov in symbols, is de ned by means of Ov(x; y) , 9z:ingr(z; x) ^ ingr(z; y): (2) 1.1

The class operator

Aggregation of things into a composite thing is done in set theory by means of the union of sets operator. Its counterpart, and a generalization, in mereology, is the class operator. For a non{empty property of things, the class of , denoted Cls , is de ned by the conditions

C1 If (x), then ingr(x; Cls )

C2 If ingr(x; Cls ), then there exists z such that (z) and I(x; z) In plain language, the class of collects in an individual object all objects satisfying the property .

The existence of classes is guaranteed by an axiom.

M4 For each non{vacuous property there exists a class Cls The uniqueness of the class follows by M3.

In Fig. 1, we can discuss the class of white squares, the class of black squares, or, the class of occupied squares.

Example 1. 1. The strict inclusion on sets is a part relation. The corresponding ingredient relation is the inclusion . The overlap relation is the non{empty intersection. For a non{vacuous family F of sets, the class ClsF is the union S F ; 2. For reals in the interval [0; 1], the strict order < is a part relation and the corresponding ingredient relation is the weak order . Any two reals overlap; for a set F [0; 1], the class of F is supF .

The notion opposite to that of overlap is the notion of disjointness: its symbol is extr, and, for things x; y, extr(x; y) , it is not true that Ov(x; y): (3) The notion of a complement to an object, relative to another object, is rendered as a ternary predicate comp(x; y; z), [ 8 ], par. 14, Def. IX, to be read:`x is the complement to y relative to z', and it is de ned by means of the following requirements, 1. x = ClsEXT R(y; z); 2. ingr(y; z), where EXT R(y; z)(t) holds if and only if ingr(t; z) and extr(t; y).

This de nition implies that the notion of a complement is valid only when there exists an ingredient of z exterior to y.

The notion of a class has been extensively studied motivated by its fundamental importance for foundations of mathematics, logics and mereology, cf., e.g., Lewis [ 9 ].

For the property Ind(x) , ingr(x; x), one calls the class ClsInd, the universe, in symbols V ,cf.,[ 8 ], par. 12, Def. VII. The complement with respect to the universe of a thing serves as the complement in algebraic sense.

We let for an object x,

x = ClsEXT R(x; V ):

It follows that 1. 2.

( x) = x for each object x;

V does not exist.

In Fig. 1, the complement to the class of white squares is the class of black squares (we assume that classes of squares are ingredients of the chessboard as well). The operator x can be a candidate for the Boolean complement in a structure of a Boolean algebra within Mereology, constructed in [ 18 ], and anticipated in [ 17 ]; in this respect, cf., [ 5 ]. This algebra will be obviously rid of the null element, as the empty object is not allowed in Mereology , and the meet of two objects will be possible only when these objects overlap. Under this caveat, the construction of Boolean operators of join and meet proceeds as in [ 18 ].

We de ne the Boolean sum x + y by letting

x + y = Cls(t : ingr(t; x) _ ingr(t; y)):

In Fig. 2, we give an example of the sum which is the full moon as the sum of the two quarters: 4th and 1st ('halves`). (4) (5)

The product x y, cf., [ 18 ] is de ned in a parallel way,

If Ov(x; y) then x y = Cls(t : ingr(t; x) ^ ingr(t; y)): (6) Operators +; ; and the unit V introduce the structure of a complete Boolean algebra without the null element, cf., [ 18 ], [ 13 ].

An often invoked example of a mereological universe is the collection ROMn of regular open sets in the Euclidean space En; we recall that an open set A is regular open when

A = IntClA; (7) where Int; Cl are , respectively, the interior and the closure operators of topology, see, e.g., [ 10 ], Ch.2. In this universe, mereological notions are rendered as

Rough Mereology

Rough Mereology, cf., , [ 10 ], [ 11 ], [ 12 ], introduces the notion of a part to a degree, (x; y; r) read `x is a part in y to a degree of r' with requirements RM1 (x; y; 1) , ingr(x; y) RM2 (x; y; 1) ^ (z; x; r) )

(z; y; r) RM3 (x; y; r) ^ s r )

(x; y; s) where ingr is the ingredient relation in an a priori assumed Mereology. The relation called a rough inclusion in [ 11 ] can be induced in some ways from t{norms, for t{norms, see, e.g., [ 6 ], [ 10 ], Ch. 4. yields the rough inclusion x )t y = maxfr : t(x; r)

yg; t(x; y; r) , x )t y r: 2.2

Rough inclusions from archimedean t{norms

In the other case, for the t{norm of Lukasiewicz, or, the product t{norm, see, e.g., [ 10 ], Ch. 4, which admit representations, tL(x; y) = maxf0; x + y

1g; tP (x; y) = xy; with respectively, cf., [ 6 ], [ 10 ], Ch. 4, one de nes the rough inclusion tL(x; y) = gL(fL(x) + fL(y)); tP (x; y) = gP (fP (x) + fP (y)) gL(x) = 1 x = fL(x); gP (x) = exp( x); f (x) = lnx;

Rough inclusions from residua of continuous t{norms

In the rst case, for a continuous t{norm t, cf., e.g., [ 6 ], [ 10 ], Ch. 4, Ch. 6.2., the residual implication x )t y de ned as where a 4 b denotes the symmetric di erence of a; b, jaj is the cardinality of a, and, jjajj is the measure (area) of a.

L(x; y; r) , gL(jx P (x; y; r) , gP (jx yj) yj) r; r: sL(X; Y ) = g( jX 4 Y j ) = jX \ Y j ;

jXj jXj LG(X; Y ) = g( jjX 4 Y jj ) = jjX \ Y jj ;

jjXjj jjXjj The last formula can be transferred to the realm of nite sets, with g either gL or gP , as to the case of bounded measurable sets in En as (8) (9) (10) (11) (12) (13) (14) (15) (16) (17) 2.3

Transitivity of rough inclusions

An important property of rough inclusions is the transitivity property. For rough inclusions of the form t with t being L or P , as well as for rough inclusions of the form t this property has the form, see Polkowski [ 10 ], Props. 6.7, 6.16, In case of rough inclusions of the form t, it becomes, t(x; y; r) ^ t(y; z; s) )

t(x; z; t(r; s)): t(x; y; r) ^ t(y; z; s) ) t(x; z; t(r; s)): 3

Granules as weakly open sets in rough mereology

We begin our study of mereotopology in a rough mereological universe U with a given rough inclusion . In order to introduce topological structures, we rst introduce a mechanism of granulation in U . For a thing x in U and a real number r in the interval [0; 1], we de ne the granule g(x; r; ), about x of radius r, as (18) (19) (20) (21) (22) (23)

Granules can be characterized in terms of rough inclusions as follows, see Polkowski [ 10 ], Ch. 7, Props. 7.1, 7.2.

Proposition 1. For granules induced by rough inclusions of the form t as well as for granules induced by the rough inclusion M , we have for each pair x; y of things, ingr(y; g(x; r; )) if and only if (y; x; r).

For granules induced by rough inclusions cated, see Polkowski [ 10 ], 7.3. 3.1

Open sets

L, P , the situation is more compli

where g(x; r; ) is ClsM (x; r; ); M (x; r; )(y) , (y; x; r): The neighborhood system has properties of open sets, viz., see [ 10 ], Ch. 7, 1. If ingr(y; n(x; r; )), then 9s:ingr(n(y; s; ); n(x; r; )); 2. If s > r, then ingr(n(x; s; ); n(x; r; )); We apply the granules to de ne neighborhoods of things in U . To this end, we de ne a property N (x; r; ) by letting, The neighborhood n(x; r; ) of a thing x of radius r relative to is de ned as N (x; r; )(y) , 9s > r: (y; x; s):

n(x; r; ) is ClsN (x; r; ): 3. If ingr(y; n(x; r; )) and ingr(y; n(z; s; )), then

9q:ingr(n(z; sq; ); n(x; r; )) and ingr(n(z; q; ); n(y; s; )):

We de ne an open set as a collection of neighborhoods; the predicate open(F ) is therefore de ned as,

open(F ) , 8z:[z 2 F , z is n(x; r; ) f or some x; r ]: It is now possible to de ne open things as classes of open collections, Closed things are de ned as complements to open things, open(x) , 9F:open(F ) ^ x is ClsF:

closed(x) , open( x):

We may need as well the notion of a closed collection, as the complement to an open collection, closed(F ) , open( F ); (27) where, clearly, the complement F is the collection obtained by applying the mereological complement to each member of F . 4

Boundaries

The practical importance of boundaries stems from their role as separating regions among areas of interest like roads, rivers, elds, forests etc., and this causes the theoretical interest in them. The notion of a boundary has been studied in philosophy, mathematics, computer science by means of mereology. Mathematics resolved the problem of boundaries by topological notion of the boundary (frontier) BdX of a set X in a topological space (U; ) which was de ned as

BdX = ClX n IntX; i.e., any point x 2 U satis es

x 2 BdX , 8P:P open ^ x 2 P ) P \ X 6= ; 6= P \ (U n X): It is evident from this de nition that the notion of the boundary of X involves in the symmetrical way the complement:

BdX = Bd(U n X): It also follows that the notion of a boundary is of in nitesimal character as detecting whether x 2 BdX involves neighborhoods of x of arbitrarily small size. (24) (25) (26) (28) (29)

Philosophers noticed this duality of boundaries between things and their complements and went even further, in the extreme cases, assigning the boundary character to any thing by considering it as a potential boundary (the phenomenon of plerosis, e.g., a point in the open disc can be the end point of any radius from it to the perimeter of the disc, a fortiori, in the boundary of continuum many segments. Moreover, e.g., the perimeter of the planar disc, considered, e.g., in 3D space, can be the boundary of continuum many bubbles spanned on the perimeter , see [ 2 ], [ 3 ], [ 15 ]). 4.1

Mereoboundaries

Topological de nition of boundary led Smith [ 14 ] toward a scheme for de ning mereoboundaries. First, He proposes an axiomatic introduction of open sets as interior parts, IP in symbols. In this context, the notion of straddling, Str in symbols, is de ned as,

Str(x; y) , [8z:IP (x; z) ) Ov(z; y) ^ Ov(z; y)]: The notion of a boundary part is introduced in Smith [ 14 ] by means of an auxiliary predicate

B(x; y) , 8z:ingr(z; x) ) Str(z; y): Boundary Bd(y) of a thing y is de ned as (30) (31) (32)

Bdy(y) = Clsfx : B(x; y))g:

It is a straightforward task to verify that in the space ROMn of regular open sets, each set x is an interior set of each of its supersets and requirements for IP are ful lled, Str(x; y) is satis ed in case Ov(x; y) ^ Ov(x; y) and B(x; y) is satis ed for no x; y hence the boundary is not de ned being empty. The reason is a too liberal de nition of straddling, allowing mere ingredients of a given thing x. 4.2

Granular mereoboundaries

For this reason, we re{model the approach by Smith in [ 14 ] by allowing granular neighborhoods as open things, a fortiori interior parts, and by restricting interior parts to granular neighborhoods about the same thing. In detail, our approach presents itself as follows.

We say that a granular neighborhood n(x; r; ) granular straddles a thing y if and only if the following property GStr(x; r; y) holds,

GStr(x; r; y) , 8s 2 (r; 1):Ov(n(x; s; ); y) ^ Ov(n(x; s; ); y): (33) Let us observe that the notion of granular straddling is downward hereditary in the sense that

GStr(x; r; y) ^ s > r ) GStr(x; s; y): Also, it is manifest that this notion is upward hereditary, i.e.,

GStr(x; r; y) ) 8s < r:GStr(x; s; y): (35) With each granule g(x; r; ), we associate the collection GN (x; ) = fn(x; s; ) : s 2 (0; 1)g, which we call the x ultraf ilter base. We say that an x-ultra lter base GN (x; ) granular straddles a thing y if and only if there exists an s 2 (0; 1) such that GStr(x; s; ); y) holds. We denote this fact with the symbol B(x; y). We regard the collection GN (x; ) as a point at in nity and, according to the topological nature of boundary, we assign to the thing x such that the x-ultra lter base GN (x; ) granular straddles a thing y this point at in nity as the boundary point of y. Hence, we de ne the boundary of y, in symbols Bdy, as the collection of those points,

Boundaries de ned in this way are ingr upward

hereditary in the sense,

Bdy is fx : B(x; y)g: ingr(z; x) ^ B(z; y) ) B(x; y): (36) (37) The proof follows from de nitions by M3 and transitivity of the applied rough inclusion. In view of the correspondence between things and ultra lter bases, we may say that the thing x is a boundary point of the thing y in case the x{ultra lter base granular straddles y. This approach does satisfy philosophical postulates about boundary like 1. The boundary of a thing may not belong in the universe of considered things; in other words, the boundary is of di erent topological type then the thing; 2. in order to preserve the typology of the boundary one has to preserve its in nitesimal character; 3. the boundary of a thing may be a boundary of a plethora of other things , in particular, by necessity, it has to be the boundary of each complement to the thing.

Let us observe that the set{theoretic complement to Bdy is open as it is the collection, fz : 9s:ingr(n(z; s; ); y) _ ingr(n(z; s; ); y)g; (38) hence, Bdy is a closed collection for each thing y.

It is a straightforward task to check that in the space ROMn, for a regular open set A, the granular boundary is de ned by

B(Z; A) , ClZ \ A 6= ;: (39) 5

Conclusion

We admit an in nitesimal nature of boundaries along with the fact that their nature is distinct from the nature of things they bound, like it happens to closed nowhere dense boundaries of regular open sets, and we represent them by means of ultra lters constructed in the meta{space of collections of things. We have aimed at giving a de nition of boundary in purely mereological terms, without any resort to augmentations which are necessary for a more exact description, like geographic directions, notions of touching, contact, beacons, in a word many other than mereological primitive notions, see, e.g., [ 1 ], [ 7 ].

References

1. Aurnague , M. , Vieu , L. , Borillo , A. : Representation formelle des concepts spatiaux dans la langue . In: Denis, M. (ed.): Langage et Cognition Spatiale, Masson, Paris, pp 69 { 102 ( 1997 ).

2. Brentano , F. : The Theory of Categories . Nijho , The Hague ( 1981 ).

3. Chisholm , R.: Spatial continuity and the theory of part and whole. A Brentano study . Brentano Studien 4 , pp 11 { 23 ( 1992 {3).

4. Clarke , B. L.: A calculus of individuals based on connection . Notre Dame Journal of Formal Logic 22 ( 2 ), pp 204 { 218 ( 1981 ).

5. Clay , R.: Relation of Lesniewski's Mereology to Boolean Algebra . The Journal of Symbolic Logic 39 , pp 638 { 648 ( 1974 ).

6. Hajek , P. : Metamathematics of Fuzzy Logic. Kluwer, Dordrecht ( 1998 ).

7. Hayes , P. J.: The second naive physics manifesto . In: Hobbs, J. R. , Moore , R. C. (eds.): Formal Theories of the Common{Sense World , Ablex, Norwood, pp 1 { 36 ( 1985 ).

8. Lesniewski , S. : Podstawy Ogolnej Teoryi Mnogosci, I (Foundations of General Set Theory, I, in Polish) . Prace Polskiego Kola Naukowego w Moskwie , Sekcya Matematyczno{przyrodnicza (Trans . Polish Scienti c Circle in Moscow, Section of Mathematics and Natural Sciences) No. 2 , Moscow ( 1916 ) ; see also Lesniewski , S.: On the foundations of mathematics. Topoi 2 , pp 7{ 52 ( 1982 ) (translation by E. Luschei of the former ).

9. Lewis , D. : Parts of Classes. Blackwell, Oxford UK ( 1991 ).

10. Polkowski , L. : Approximate Reasoning by Parts . An Introduction to Rough Mereology. Springer Verlag, Berlin ( 2011 ).

11. Polkowski , L. , Skowron , A. : Rough mereology . In: Proceedings of ISMIS'94. Lecture Notes in Arti cial Intelligence 869 , Springer Verlag, Berlin, pp 85 { 94 ( 1994 ).

12. Polkowski , L. , Skowron , A. : Rough mereology: a new paradigm for approximate reasoning . International Journal of Approximate Reasoning 15 ( 4 ), pp 333 { 365 ( 1997 ).

13. Simons , P. : Parts . A Study in Ontology . Clarendon Press, Oxford UK ( 1987 , repr. 2003 ).

14. Smith , B. : Mereotopology: A theory of parts and boundaries . Data and Knowledge Engineering 20 , pp 287 { 303 ( 1996 ).

15. Smith , B. : Boundaries: An essay in mereotopology . In: Hahn, L . (ed.): The Philosophy of Roderick Chisholm . La Salle: Open Court, pp 534 { 561 ( 1997 ).

16. Sobocinski , B. : Studies in Lesniewski's Mereology . Yearbook for 1954-55 of the Polish Society of Art and Sciences Abroad V , pp 34 { 43 ( 1954 {5).

17. Tarski , A. : Les fondements de la geometrie des corps . Supplement to Annales de la Societe Polonaise de Mathematique 7, pp 29 { 33 ( 1929 ).

18. Tarski , A. : Zur Grundlegung der Booleschen Algebra. I. Fundamenta Mathematicae 24 , pp 177 { 198 ( 1935 ).