On a Notion of Extensionality for Artifacts Lech Polkowski1 and Maria Semeniuk-Polkowska2 Polish-Japanese Institute of Information Technology1 . Koszykowa 86. 02008 Warszawa, Poland Chair of Formal Linguistics2 . Warsaw University. Browarna 8/12. 00956 Warszawa Poland emails: polkow@pjwstk.edu.pl; m.polkowska@uw.edu.pl 1 Abstract The notion of extensionality means in plain sense that properties of complex things can be expressed by means of their simple components, in particular, that two things are identical if and only if certain of their components or features are identical; e.g., the Leibniz Identitas Indiscernibilium Principle: two things are identical if each applicable to them operator yields the same result on either; or, extensionality for sets, viz., two sets are identiccal if and only if they consist of identical elements. In mereology, this property is expressed by the statement that two things are identical if their parts are the same. However, building a thing from parts may proceed in various ways and this unexpectedly yields various extensionality principles. Also, building a thing, may lead to things identical with respect to parts but distinct with respect, e.g., to usage. We address the question of extensionality for artifacts, i.e., things produced in some assembling or creative process and we formulate the extensionality principle for artifacts which takes into account the assembling process and requires for identity of two artifacts that assembling graphs for the two be isomorphic in a specified sense. 2 Mereology in a Nutshell The primitive notion of mereology due to Leśniewski, cf., Leśniewski [8], [9], [10], Srzednicki et al. [18], is a notion of a part; for an in–depth, autoritative review of mereology, consult Simons [17]; also, consult Casati–Varzi [7] for a treatment of mereology from the point of view of spatial reasoning. Given some things in a collection U , a relation of a part is a binary relation π on U which is required to be M1 Irreflexive: For each x ∈ U it is not true that π(x, x) M2 Transitive: For each triple x, y, z of things in U , if π(x, y) and π(y, z), then π(x, z) The relation of part induces the relation of an ingredient, ingr, due to Leśniewski [8] defined as ingr(x, y) ⇔ π(x, y) ∨ x = y (1) Clearly, Proposition 1. The relation of ingredient is a partial order on things. We formulate the third axiom with a help from the notion of an ingredient. M3 (Inference) For things x, y, the property I(x, y): The property O(x, y): For each thing t, if ingr(t, x), then there exist things w, z such that ingr(w, t), ingr(w, z), ingr(z, y) implies that ingr(x, y) The predicate of overlap, Ov in symbols, is defined by means of Ov(x, y) ⇔ ∃z.ingr(z, x) ∧ ingr(z, y) (2) Using the overlap predicate, one can write the property O(x, y) down in the form Ov(x, y) : For each t with ingr(t, x), there exists z such that ingr(z, y) and Ov(t, z) The notion of a mereological class follows, cf. [8]: for a non–vacuous property Φ of things, the class of Φ, denoted ClsΦ is defined by the conditions C1 If Φ(x), then ingr(x, ClsΦ) C2 If ingr(x, ClsΦ), then there exists z such that Φ(z) and Ov(x, z) In plain language, the class of Φ collects in an individual thing all objects satis- fying 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. Proposition 2. For each non–vacuous property Φ, the class ClsΦ is unique. Proof. Assuming that for some Φ there exist two distinct classes Y1 , Y2 , con- sider ingr(t, Y1 ). Then, by C2, and (2), there exists z such that Ov(t, z) and ingr(z, Y2 ). It follows by M3 that ingr(Y1 , Y2 ). By symmetry, ingr(Y2 , Y1 ) holds and Proposition 1(2) implies that Y1 = Y2 t u 3 Extensionality for things from Mereology point of view In Leśniewski Mereology, extensionality is derivable from the axioms in the form: (EP) (Extensionality Principle) For things x, y: x = y if and only if x and y have the same parts Clearly, only the implication from right to left may need a proof. Assume then that x and y have the same parts. The identity x = y follows from the Proposition 3. Each thing z is the class of all its ingredients. Indeed, each part of z is its ingredient (fulfilling C1) and for an ingredient w of z either w = z or π(w, z) in either case fulfilling obviously C2. It turns out that extensionality may be defined in some other ways: Varzi [20] considers two more principles of extensionality, viz., (UC) (Uniqueness of Composition) For things x, y: x =U y if and only if x and y are classes of the same things in a collection F (EC) (Extensionality of Composition) For things x, y: x =E y if and only if x and y are classes of the same collection P of pairwise disjoint things Varzi [20] gives a thorough analysis of those three principles, showing that they are not equivalent. This analysis may be recapitulated in a nutshell here for the benefit of the reader; first, both (EP) and (EC) are implied by (UC): assuming (UC) we admit (EP) by virtue of Proposition 3 and (EC) is a particular case of (UC). But, (EP) implies neither (EC) nor (UC): that both implications fail was shown in Varzi [20] (cf. Fig. 1) with a simple example of disjoint atoms a, b, c which induce d = Cls{a, b} and e = Cls{b, c} as well as x = Cls{d, c} and y = Cls{a, e}; we have x = Cls{a, b, c}, y = Cls{a, b, c}, (EP) holds as distinct things have distinct collections of parts and (UC) and (EC) fail because x and y are classes of the same disjoint atoms a, b, c. Existence of atoms is implied by the assumption of well–foundedness, cf., Aczel [1], Barwise and Moss [2]. (WFU) We say that the universe of things U is π–well–founded if and only if there is in U no decreasing π–sequence i.e. a sequence of things {xi : i ∈ N } such that π(xi+1 , xi ) for each i An atom in U is a thing x such that no y ∈ U satisfies π(y, x). It follows that being an atom in U is an absolute notion, not depending on the thing the atom is a part of. At(x) denotes the property of being an atom and a part of x. Under (WFU), the following hold. Proposition 4. (WFU) implies (1) each thing x in U contains an atom as an ingredient. (2) each thing x in U is the class of the property At(x). (3) (EC) implies (UC), i.e., (EC) and (UC) are equivalent under (WFU). For the proof, (1) is obvious; for (2), assume that, to the contrary, there is x in U which is not the class of At(x). By C2, there is an ingredient y of x disjoint (i.e. not overlapping) to each atom of x; but y has an atom as an ingredient and this atom is as well an atom of x, a contradiction. For (3) we may need a lemma which follows directly from the class definition C1, C2. LEMMA. If a thing x is the class of the property F and each W y in F is the class of the property P(y), then x is the class of the property y∈F P (y). We prove now (3). Assume that x, y are classes of things satisfying the prop- erty F. For each y in F , consider the property W At(y); by (2), y W= ClsAt(y) for y in F , henceWby LEMMA, x = Cls y∈F At(y) and y = Cls y∈F At(y). As the collection y∈F P (y) is pairwise disjoint, by (EC), x = y, satisfying (UC). In general, as shown in Varzi [20] (cf. Fig. 2 therein), (EC) implies neither (EP) nor (UC); clearly, the example is possible only in a non–well–founded universe. We have mentioned three types of extensionality immanent to composition of things from parts directly or via class forming. However, things are often composed of parts in systematic usage–oriented ways. Those things are called commonly artifacts (’made by art‘), or, artefacts. Things composed of the same parts may have very distinct forms and properties, e.g., a robot built of parts supplied as NXT 2.0 may be a walking one or a crawling one, see [13]. This fact is to be somehow recorded in the description of an artifact as a thing obtained in a creative process. 4 On the notion of an artifact The term artifact means, etymologically, a thing made by art, which covers a wide specter of things, from man–made things of everyday usage to abstract pieces of mathematical proofs, software modules, or concertos. All those distinct things are unified in a scheme dependent on some common ingredients in their making, cf., e.g., a concise discussion in SEP [16]. We cannot include here a discussion of vast literature on ontological, philosophical and technological aspects of this notion, we mention only a thorough analysis of ontological aspects of artifacts in Borgo and Vieu [4] in which authors propose also a scheme defining artifacts. It follows from discussion by many authors that important in analysis of artifacts are such aspects as: authorship, intended functionality, parthood relations. Analysis of artifacts is closely tied to design and assembly, cf., Boothroyd [5] and Boothroyd, Dewhurst and Knight [6] as well as Salustri [14] and Seibt [15]. A discussion of mereology with respect to its role in domain science and engineering and computer science can be found in Bjoerner [3] and Polkowski [12]. We thank the anonymous referee for turning our attention to a book by Zdzislaw Pawlak [11] in which the author develops a theory of manufacturing processes modeled on the mechanical assembly process of a thing from parts along a scheme adopted as a tree. Though no mereology is mentioned, yet the author defines parts of things as leaves of assembling trees (calling them details) for those things and derives basic mereological properties of parts in this setting. We attempt at a definition of an artifact as a thing obtained over a collection of things as a most complex thing in the sense of not being a part of any thing in the collection; to aspects of authorship (operator)and functionality, we add a temporal aspect. We propose a number of requirements governing the assembling process. We also regard a parallel process of design as an assembling process. 4.1 A definition of an artifact as a design or assembly product We single out: a category of operators P , a category of functionalities F , a lin- ear time T with the time origin 0; the process of artifact design/synthesis will be carried out by designers from the category D and assemblers from the cat- egory A. The domain of things is a category Things(D, A, P, F, π) of things endowed with a part relation π of which we do assume π–well–foundedness. The assignment operator S acts as a partial mapping on the Cartesian product D × A × T hings(D, A, P, F, π) with values in the category T ree of trees. For some things x in Things(D, A, P, F, π) and some pairs (d, a) ∈ D × A, the operator S assigns a unique tree S(d, a)(x) = T ree(d, a)(x) which is the design/synthesis tree for the pair (d, a) and the thing x. Its root node is rep- resenting the thing x designed by d, with assembly tools designed by a, and produced by some operators in P . Each node w of the tree T ree(d, a)(x) is the root of the tree of the form T ree(d, a)(y) for some thing y which does represent the design/assembling scheme for y. The replacement relation ∼ is defined on the category Things(D, A, P, F, π) by means of x ∼ y ⇔ ∃zπ(x, z) ∧ ∃z.π(y, z) ∧ [π(x, z) ⇔ π(y, z)] for each thing z (3) Classes of ∼ are categories of replaceable things. The category of x is denoted as Cat(x). From (3) it follows that x ∼ y implies that neither of x, y is a part of the other. We define a predicate πd,a on the domain of ∼; πd,a (y) means that the thing y is a part of some thing in the universe Things(D, A, P, F, π). The process of assembling will be formally described by means of the predi- cate Art(d, a, p, < x1 , ..., xk(y) >, y, f, t, T ree(d, a)(y)) with p in P , f in F , t in T , which reads an assembler a projects an assem- bly scheme according to the design d which yields from things x1 , ..., xk(y) the thing y of functionality f at the time t according to the scheme Tree(d,a)(y) with an operator p. The predicate Asmbl(x, i, y, p, f, t) reads the thing x is used in the position i in assembling the thing y of functionality f at some time t and with some operator p. We propose the following axioms of assembling. The tu- ple < d, a, p, < x1 , ..., xk(y) > y, f, t, T ree(d, a)(y) > is the signature of y when Art(d, a, p, < x1 , ..., xk(y) >, y, f, t, T ree(d, a)(y)) holds. Art0. For each thing x, each node of the tree T ree(d, a)(x) is labeled with a label of the form (d, a, p, < z1 , ..., zk(y) >, y, f, t, T ree(d, a)(y)) with T ree(d, a)(y) a subtree of T ree(d, a)(x), and t0 < t. Art 1. Art(p, < x1 , ..., xk(y) >, y, f, t, T ree(d, a)(y)) ∧ ∀i ≤ k(y).Art(pi , < z1 , ..., zk(xi ) >, xi , fi , ti , T ree(d, a)(xi )) ⇒ ∀i ≤ k(y).pi ⊂ p, f ⊂ fi , t0i < t . The relation p0 ⊂ p is meant as: if p’ is allowed to assemble a thing z then p is allowed to assemble z (a more complex operator has a wider scope); the relation f ⊂ f 0 means if y is usable in assembling z then xi is usable in assembling z (a less complex thing has a wider usage); the inequality ti < t means that less complex xi is assembled before y is assembled. Art 2. Asmbl(xi , i, y, p, f, t) ∧ Cat(xi ) = Cat(z) ⇒ Asmbl(z, i, y, p, f, t). Art 3. Art(p, < x1 , ..., xk(y) >, y, f, t, T ree(d, a)(y)) ∧ Cat(y) = Cat(y 0 ) ⇒ Art(p, < x1 , ..., xk(y) >, y 0 , f, t, T ree(y 0 )). Things of the same category are interchangeable. Art 4. Art(p, < x1 , ..., xk(y) >, y, f, t, T ree(d, a)(y)) ⇒ π(xi , y) for i ≤ k(y). Each thing is assembled from its parts. Art 5. π(y, x) ⇒ there exists a node w in T ree(d, a)(x) with the signature of the form (d, a, p, < z1 , ..., zk(w) >, w, T ree(d, a)(w)) such that Cat(w) = Cat(y). Each part of the thing x up to its category is to be used in the assembling of x at some appropriate step of the assembling process. Art 6. Each leaf of each tree of the form T ree(d, a)(.) is of the signature form (d, a, p, a, f, t, {a}) with a an atom. Initial assembling begins with elementary parts. Art 7. ∀i.Cat(xi ) = Cat(zi ) ∧ Art(p, < x1 , ..., xk(y) >, y, f, t, T ree(y)) ∧ Art(p , < z1 , ..., zk(y) >, y 0 , f 0 , t0 , T ree(y 0 )) 0 ∧πd,a (y) ∧ πd,a (y 0 ) ⇒ Cat(y) = Cat(y 0 ). Assembling factorizes through categories. Art 8. Formulas Art(d, a, p, < z1 , ..., zk(y) >, y, f, t, T ree(y)) and Art(d0 , a0 , p0 , < z1 , ..., zk(y0 ) >, y 0 , f 0 , t0 , T ree(y 0 )) are regarded as equivalent if and only if their signatures are identical, k(y) = k(y 0 ), Cat(zi ) = Cat(zi0 ) for i ≤ k(y), T ree(d, a)(y) and T ree(d, a)(y 0 ) are iso- morphic as unlabeled trees. The label Art(d, a, p, < z1 , ..., zk(y) >, y, f, t, T ree(y)) will be called the label at the node y. Art 9. Trees T ree(d, a)(x), T ree(d, a)(y) are identical if and only if they are isomorphic as unlabelled trees and signatures at all corresponding nodes of x and y are equivalent in the sense of Art 8. Art 10. ¬∃w, p, f, t, i.Asmbl(y, i, w, p, f, t) ⇒ y in ART IF ACT S(D, A, P, F, π). The category ART IF ACT S(D, A, P, F, π) consists of ’final‘ things. Art 11. (EA) (Extensionality for artifacts) Two things, in particular, arti- facts, x and y are identical if and only if trees T ree(d, a)(x), T ree(d, a)(y) are identical. Art 12. Each non–artifact thing may be used in synthesis of only one other thing. Corollary 1. y in ART IF ACT S ⇒ ¬∃z.π(y, z). We may construct the Ontology Graph GOG . Its vertex set VOG is the set of categories of things and the edge set EOG consists of all pairs (Cat(xi ), Cat(y)) for all cases Art(p, < x1 , ..., xk(y) >, y, f, t) which hold. From Art 1 - Art 12 it follows that GOG is a forest. Art 11 is the Extensionality for Artifacts Principle implying that two artifacts are identical if and only if their synthesis trees are isomorphic, i.e. they are com- posed of replaceable things under same designer, assembler, and operator, at the same time. Functionalities and timing are identical as well. Corollary 2. By Art4–6, Art8, Art12, for each artifact x, the tree T ree(d, a)(x) is uniquely determined by its atoms At(x) and x = ClsAt(x). We allow some modifications in definitions of properties (EP), (UC), (EC), viz., in those definitions, we replace the term ”parts” in (EP) with the phrase ”parts of the same category”, and in (UC), (EC) we replace phrases, respectively, ”things in a collection F”, ”pairwise disjoint things” with, respectively, phrases ”things of the same category in a collection F”, ” pairwise disjoint things of the same category”. Corollary 3. In our setting for artifacts, assuming the identity as defined by Art11, (EC), (UC) and (EP) in modified versions are equivalent. 5 Conclusion Artifacts have been defined here as things obtained in a process determined by postulates Art 0–Art 12 over a well–founded collection of things. Modified by factoring through the equivalence Cat identity postulates (EP), (EC), (UC), shown to be non–equivalent in general by Varzi, are shown to be equivalent when the identity is understood in the sense of Art 11. References 1. Aczel, P. (1988): Non–Well–Founded Sets. CSLI Publications. Stanford. 2. Barwise, J.; Moss, L. (1996): Vicious Circles: On the Mathematics of Non–Well– Founded Phenomena. CSLI Publications. Stanford. 3. Bjoerner, D. (2012–13): A role for mereology in domain science and engineering. In: Calosi, C.; Graziani, P. (eds.)(2012): Mereology and the Sciences, Springer Synthese Library, to appear. 4. Borgo, S.; Vieu, L.(2009): Artefacts in formal ontology. In: Meijers, A. (ed.): Hand- book of Philosophy of Technology and Engineering Sciences. Elsevier, pp. 273–308. 5. Boothroyd, G.(2005): Assembly Automation and Product Design (2nd ed.). Taylor and Francis, Boca Raton FL. 6. Boothroyd, G.; Dewhurst, P.; Knight, W.(2002): Product Design for Manufacture and Assembly (2nd ed.). Marcel Dekker, New York. 7. Casati, R.; Varzi, A. C.(1999): Parts and Places. MIT Press, Cambridge MA. 8. Leśniewski, S. (1916): Podstawy Ogólnej Teoryi Mnogości, I (Foundations of Gen- eral Set Theory, I, in Polish). Prace Polskiego Kola Naukowego w Moskwie, Sekcya Matematyczno–przyrodnicza, No. 2, Moscow. 9. Leśniewski, S. (1927–1931): O podstawach matematyki (On foundations of mathe- matics, in Polish). (1927) Przegla̧d Filozoficzny XXX, pp 164–206; (1928) Przegla̧d Filozoficzny XXXI, pp 261–291; (1929) Przegla̧d Filozoficzny XXXII, pp 60–101; (1930) Przegla̧d Filozoficzny XXXIII, pp 77–105 (1930); (1931) Przegla̧d Filo- zoficzny XXXIV, pp 142–170. 10. Leśniewski, S. (1982): On the foundations of mathematics. Topoi 2, pp 7–52. 11. Pawlak, Z. (1969): Mathematical Aspects of the Production Process (in Polish: Matematyczne Aspekty Procesu Produkcyjnego). The State Economic Publishers, Warszawa, Poland. 12. Polkowski, L. (2012–13): Mereology in engineering and computer science. In: Calosi, C.; Graziani, P. (eds.)(2012): Mereology and the Sciences, Springer Syn- these Library, to appear. 13. http://www.tuvie.com/wp-content/uploads/lego-mindstorms-nxt-2.0-robots4.jpg 14. Salustri, F. A.(2002): Mereotopology for product modelling.A new framework for product modelling based on logic. J. Design Res. 2. 15. Seibt, J.(2009): Forms of emergent interaction in general process theory. Synthese 1666, pp. 479–512. 16. SEP (Stanford Encyclopedia of Philosophy): Artifact; available http://plato. stan- ford. edu/entries/artifact 17. Simons, P. (1987): Parts: A Study in Ontology. Clarendon, Oxford. 18. Srzednicki, J., Surma, S. J., Barnett, D., Rickey, V. F. (eds.) (1992): Collected Works of Stanislaw Leśniewski. Kluwer, Dordrecht. 19. Thomasson, A.(2007): Artifacts and human concepts. In: Margolis, E.; Laurence, S. (eds.): Creations of the Mind: Theories of Artifacts and Their Representation. Oxford University Press, pp. 52–73. 20. Varzi, A. C. (2008): The extensionality of parthood and composition. The Philo- sophical Quarterly 58 pp. 108–133.