A taxonomy of composition operations Jan Westerhoff May 11, 2007 Abstract A set of parameters for classifying composition operations is introduced. These parameters determine whether a composition operation is 1) universal, 2) determinate, 3) whether there is a difference between possible and actual compositions, 4) whether there can be singleton compositions, 5) whether they give rise to a hierarchy, and 6) whether components of compositions can be repeated. Philosophical implications of these parameters, in particular in relation to set theory and mereology are discussed. 1 Introduction Composition operations are very widespread. Much of our human existence consists in combining things. We combine words into sentences and sentences into speeches, simple thoughts into complex thoughts, notes into melodies, we put together a menu from its ingredients, a brick wall from bricks, we combine people into groups or committees, we combine numbers by arithmetical operations, we form lists, sets, sequences, mereological sums... Unfortunately the status of composition operations is very unclear. This is not because questions pertaining to them are uninteresting or rarely discussed. ?, ? and ? are all dealing with some aspects of composition operations and address some of the most challenging questions in contemporary philosophy whilst doing so. The problem is rather that there is no unified framework for describing and comparing different composition operations. This paper sets out to come up with such a framework in the form of a set of six parameters which a composition operation may or may not obey. These parameters allow us to discuss and compare a wide range of composition operations. They also enable us to systematize the issues which are usually discussed in connection with composition operations, such as the 'principle of nominalism', the status of singletons, the possibility of creating hierarchical structures by iterated composition and the relation of composition operations with the abstract-concrete distinction. We will discuss each parameter in turn (section 3) and then show how a wide variety of composition operations can be classified by reference to them 1 (section 4). We conclude by adding some remarks on the relation between composition operations and categorizations (section 5). 2 Composition operations Composition operations are operations which make some thing out of other things. This is, of course, a bit too general. As Lewis correctly notes not just any operation that makes new things from old is a form of composition! There is no sense in which my parents are part of me, and no sense in which two numbers are part of their greatest common factor [. . .]1 We usually consider something to be a composition of some other objects if a) the objects are spatio-temporal parts of the new object and b) it is as least theoretically possible that the composition can be uniquely decomposed into the objects it was composed from. So a watch is a composition of its spatio-temporal parts, and in taking the watch apart we can retrieve all the original parts used in assembling it. A coffee with milk is composed of coffee and milk, the coffee and the milk are parts of the mixture and it is at least theoretically possible to take it apart molecule by molecule. There are, however, examples which me might want to regard as cases of composition which fail one of the two conditions. Take the relation between a number and its prime factors. This fails a) since numbers, not being in space or time, do not have spatio-temporal parts. But it satisfies b), since there is a unique decomposition of every number into its prime factors. Some sense can therefore be made of the prime numbers being actually 'in' a number, so that we might want to regard a number as composed of its prime factors. Other examples of composition operations fail the second condition. Suppose we compose the coffee with milk from two different cartons. It will then not even be theoretically possible to distinguish which molecule came from which carton, so that it is impossible to find a unique decomposition of the mixture into the three original objects (the coffee and the two samples of milk). For a less pedestrian example take mereological fusion of non-atomic objects. Different fusions can spatiotemporally coincide, and as a consequence we cannot even in principle determine whether e.g. the components fused in forming the whole that is the United Kingdom were England, Wales, and Scotland or all the counties of Great Britain. Fusions in general do not have unique decompositions. This is not an issue if we only fuse atoms, but whether some operation is a composition operation should, I think, only 1?, 38. 2 depend on facts about that operation, and not on the objects it operates on. (At the same time a) is obviously satisfied, since England, Wales, and Scotland are all spatio-temporal parts of Great Britain.) Considering these two cases we can now distinguish a narrow notion of composition, which includes only objects satisfying both a) and b), and a wide one, which will be adopted for our purposes and which also includes operations failing one of the two conditions, such as multiplication of primes or fusion of nonatomic objects. While this is perhaps not as sharp a distinction as we might have hoped, at least it manages to divide the composition operation from those 'which make new things from old' but should not be regarded as compositions. Let us note two things at this point. First of all we resist the (often nominalistically motivated) temptation of identifying composition operations tout court with operations obeying such principles as • compositions can only be made out of more than one thing, • different compositions cannot be made from the same thing, • compositions of compositions just give us the original composition again. Our idea is rather to start out with the minimalistic picture of compositions operations obeying either a) or b) or both and to regard such principles as the ones just given as parameters which a particular composition operation can satisfy. Secondly, as should by now be evident, there is more than just one composition operation. In particular mereology is regarded as a composition operation, but not as the only one (pace Lewis, who claims that 'mereology describes composition in full generality'2 The space of composition operations is more comprehensive than Lewis assumes. Restricting ourselves to mereology only obscures the universality and variety of composition operations. I do agree with Lewis, however, that the line must be drawn somewhere and that such operations like that of forming the greatest common factor should not be regarded as compositions. If we uphold our qualms regarding 'parthood' in the case of numbers it fails a), and, unlike in the prime number case b) is not satisfied either. Knowing that 5 is the greatest common factor of two numbers does not allow me to tell whether the numbers were 10 and 15 or 15 and 20. The same point holds for forming the sum of the digits of a number, and also for non-numerical operations such as drawing implications from propositions. Propositions do not have spatio-temporal parts, and it is obviously not the case that we can retrieve a set of propositions from 2?, 39. See also p. 37. 3 knowing one proposition it entails. I am not so sure about Lewis' second supposed non-example. We might regard the generation of children from parents as compositions if it was possible to clone parents from the child's DNA. As in the case of the prime numbers it would then make sense to claim that the parents are 'in' the child, although not in the familiar mereological sense of spatio-temporal parthood. 3 Parameters for composition operations In order to gain a more systematic picture of composition operations, let us introduce some notation. Let o be a polyadic composition operation on things a, b, c, . . . from some collection T .3 We will call the things put together to form a composition the components of that composition, so the components of the composition o(a, b, c) will be a, b, and c. For many composition operations we have to distinguish possible and actual compositions. The possible composition of some things is just the possible but not actual object which could be formed from them, while the actual composition is the actual object which results from actually putting together the things involved. To borrow an example of Fine's, an actual ham sandwich is the object resulting from putting together two slices of bread and one slice of ham in the appropriate way. The possible ham sandwich, however, is already there in my kitchen as long as the bread and the ham is, without requiring me to do anything with them. Let us now write o(a, b, c) to denote the possible composition of a, b, and c by o, and o!(a, b, c) for their actual composition. Thus if b1, b2 are the two slices of bread, h the slice of ham and o the appropriate sandwich-assembling operation, o(b1, b2, h) will denote the possible ham-sandwich and o!(b1, b2, h) the actual ham-sandwich. Let furthermore φ, ψ, . . . be collections of objects from T . We are now in a position to formulate six parameters which determine the behaviour of composition operations, depending on the way the parameters are set. 1. [range] A composition operation is universal if, for all φ, ψ, χ, if o(φ), o(ψ) exist, so will o(χ), where χ is a proper or improper subcollection of the union of φ and ψ. Else the composition operation is typed. 2. [determinacy] A composition operation is determinate if for any φ there is at most one o(φ). Else it is indeterminate. 3. [difficulty] A composition operation is easy if for all φ, o(φ) exists iff o!(φ) does. Else it is difficult. 3Our approach does not demand that the a, b, c, . . . are atomic relative to the composition operation, they might as well be composed from some other objects in turn. 4 4. [ornamentation] A composition operation is plain if for all φ, if card(φ) < 2, then o(φ) = φ. Else it is ornate. 5. [hierarchy] A composition operation is flat if for all φ, ψ, each o(o(φ), o(ψ)) is identical to some o(φ, ψ). Else it is hierarchical. 6. [diversity] A composition operation is diverse if for all objects a, b, . . ., o(a, b, . . .) = o(a, b, b, . . .). Else it is repetitive. These six parameters constitute conditions which individual composition operations can either satisfy or fail to satisfy. In the first can we will say that the parameter in question is 'on', in the second case it is 'off'. For example, a composition operation which is universal is taken to have the range parameter switched on, while it is switched off for a typed one. Let us now examine the individual parameters in greater detail. 3.1 range Roughly, range specifies whether any collection of objects can be composed using a particular composition operation, or, to put it differently, whether there is a possible composition for every collection of objects, which consists just of those objects composed by the composition operation. Set-theoretic composition is universal: for any collection of non-sets we choose to specify there is a set having exactly these as members. Composing words to form sentences, on the other hand, is not universal but typed: we cannot construct a grammatical sentence from any assortment of words. In fact the range parameter is slightly more complicated than the one we just described. This is because not all composition operations are applicable within all domains. For example it can be plausibly argued that mereological fusion is only applicable to spatio-temporal objects and thus for example not to numbers. But within its proper domain it applies unrestrictedly: for any two spatio-temporal objects there is their fusion. The more complicated form of the sum principle just ensures that we are dealing with a composition operation in its proper domain. Philosophical discussion of composition operations has concentrated almost exclusively on universal operations, such as set formation or mereological fusion.4 Typed composition operations, are, however, relatively widespread (in particular in theories of grammar) and of considerable philosophical interest. We will discuss some examples of these in section 5. 4?, 324 mentions the closely related case of complex forming composition operations: 'the sum exists just when all the constituent parts exist [. . .]. By contrast, a complex constituted of the same parts as the sum only exists if a further condition is fulfilled.' A plausible condition to impose here is that the different parts must fit together. 5 3.2 determinacy The determinacy parameter specifies whether the relation of collections and their compositions is functional or not, i.e. whether or not the same objects can be composed in different manners. Examples of both are straightforward: when collecting objects into a set or marbles into a bag there is only one way of doing this. When collecting objects into an ordered set or stacking them in a row on a shelf there are various ways of doing this and thus various possible compositions which can be the result of the composing. A reader familiar with the literature on nominalism will immediately be reminded of Nelson Goodman's 'principle of nominalism' which 'denies that two different entities can be made up of the same entities'.5 In fact nominalistically acceptable composition operations don't just have to be determinate, but also plain (composing an object on its own just gives us the object again), flat (repeated composition does not result in anything new) and diverse (objects may not occur repeatedly in compositions). Moreover, they will presumably have to be easy. Given Goodman's reluctance to accept different things made up of the same bits it is unlikely that he would stomach the distinction between actual and possible compositions which, after all, consist of the same objects (exactly the same ham and bread is in the actual and the possible ham sandwich). Thus Goodman's 'principle of nominalism' fixes five of the six parameters to the 'on' position. His composition operation of choice is, of course, mereological fusion, and this also has the range parameter switched on. But this is not necessitated by Goodman's discussion. The principle of nominalism would not contradict the existence of a composition operation which was just like fusion, but typed, so that not all collections of objects, but only those 'fitting together' in a previously defined way could be fused. Such an operation might be appealed to when discussing the composition of integral wholes.6 Integral wholes are objects which are in some suitable sense coherent, such as continuous lumps of matter, families or libraries, as opposed to arbitrary mereological sums and random assemblies of people and books.7 A typed version of mereological composition would only fuse such collections which would result in integral wholes (it would not fuse all material objects, but only those of the necessary spatio-temporal coherence). 3.3 difficulty In the case of difficult composition operations there is a difference between possible and actual compositions. Just having the ingredients for a ham sandwich (and thus a possible ham sandwich) in our kitchen does not yet get 5?, 158. 6See ?, 324–360. 7?, 330 defines this coherence as connectedness relative to a characteristic relation. 6 us an actual ham sandwich: we have to do some assembling first. Contrast this with the case of set formation. Set formation is not difficult but easy. Once the notion of a set has been defined there is a set of all the books in my room. But just defining 'linear arrangement on the shelf' does not result in there being a linear arrangement of all the books in my room on the shelf. I actually have to get up and put them there. It is not the case that a composition operation's being easy implies that either it or its components are abstract (in the sense of being located neither in space nor in time). This can easily be seen by considering the case of fusions. Fusions and their components are as concrete as arrangements of books on shelves and the books themselves (they are in space and time, can come into and go out of existence) but there is not difference between a possible and an actual fusion.8 Fusions come into existence just by fiat, in the same way in which sets do without the need of any further 'actualizing activity', as was required in the cases of putting together the ham sandwich or arranging books on the shelf. If a composition operation is difficult, however, this implies that the composition itself (though not necessarily all of its components) must be concrete. The activity necessary for transforming the merely possible composition into a fully-fledged actual one creates an object which is in space or time, or both. Difficult composition operations demand that we do something with the objects to be composed, either by interacting with physical objects in the ordinary manner (arranging them on a shelf, putting them into a bag) or by interacting with mental objects by performing certain mental operations with them (thinking of a collection of numbers one after another, computing their sum). For easy operations this doesn't have to be done, we don't even have to do something with them in our minds, as the Cantorian explication of set formation would have it.9 Neither me nor anybody else has to think of the set of objects in my room for it to be there. The introduction of the concept miraculously carries its existence with it, without demanding any further action on our part. The ham sandwich, the row of books, a sentence or a melody all exist in two forms, as mere possible compositions (which are abstract) and as actual compositions (which are concrete). This explains why there sometimes seem to be two answers when we inquire whether e.g. the composition operation which makes melodies from individual notes is easy or difficult. If we think of the notes independently of their physical realization on any instrument it is easy - possible and actual melodies coincide in the realm of musical abstracta that is the collection of all melodies. If we think of the notes as actual spatio-temporal events (performances of the notes) it is difficult, for 8At least if all the objects to be fused are actual. The problem of fusing mere possibilia will not be discussed here. 9Cantor famously defines a set as 'any collection into a whole S of definite and separate objects s of our intuition or our thought' (?, 85). 7 there is the world of difference between a merely possible melody and one which has been actualized. Note that not all the components of the result of an easy composition operation have to be concrete themselves, though the result has to be. Some, though not all, may be abstract. Consider the concrete object which is the tiling of a particular floor. It can be considered as the composition of some concrete objects (the tiles) and an abstract one (the pattern). In this sense concrete objects can have abstract components. 3.4 ornamentation The ornamentation parameter settles whether composing a single object results in anything new. The parameter specifies that a composition operation is plain just in case the following condition is fulfilled: if there are strictly fewer than two objects in a collection, the result of composing this collection is just the collection itself. Mereological fusion is an example of a plain composition operation. Fusing a collection with just one object in it gives us that very object again, while fusing nothing whatsoever leaves us with what we started with as well: nothing whatsoever.10 Set theory differs from this and is thus ornate. Applying set formation to a single object does not give us the single object again, but its singleton, and this, being a set, is different from the original object. Similarly forming a set of nothing whatsoever results in something, namely the empty set.11 In a way talk of the composition of collections with just a single object in them seems to be stretching language: after all the OED informs us that composing means 'to make by putting together parts or elements' (note the plural). In fact consideration of the ornamentation parameter allows us to distinguish two distinct senses of composition which are usually lumped together: compounding and collecting. Compounding operations are plain composition operations, and composition operations in the original sense: they only operate on more than one object. Collecting operations are ornate composition operations and can even function with only one object present. It is therefore tempting to regard them as operations which put objects in some sort of 'container' (in the widest possible sense of the word).12 The reason why they can produce something new out of a single object is because they add the 'container' to it, and thereby produce an object distinct from the old one. It seems that this distinction would help in clarifying the discussion 10Standard mereologies have no truck with the concept of an empty fusion. See ?, 13-14, ?, 10-11. 11For a discussion of the metaphysical oddities of the singletons and the empty set see ?, 1.5, chapter 2. 12Lewis (?, 42) calls this view of singletons the 'lasso hypothesis'. 8 of whether all composition operations have to be plain13 or whether there can also be ornate ones, such as the formation of committees14, where a committee with a single member is different from this member. Given that all the examples of ornate composition operations discussed so far satisfy one of the conditions on composition operations given above the dispute can be dissolved by accepting that there are composition operations which are compoundings (which are closest to the Lewisian claim that 'composition is the combining of many things into one' (?, 37)) and also those which are collectings. These latter can form a complex from just one object because they add something to it (the set-theoretic lasso, as it were). We might want to note at this point that there is at least one system of set theory which seems to consider set formation as plain rather than ornate. This is the system developed by Quine in (?, 31–33) which counts 'an individual, its unit class, the unit class of that unit class, and so on, as one and the same thing'. Thus if we take any collection containing a single individual a, according to Quine's theory a = {a}, so that set formation comes out as plain, rather than ornate. Our distinction of compounding and collecting operations would then run into difficulties, because set formation would not count as a collecting operation any more, a result which is unintuitive. But this problem is in fact illusory since Quine's theory does not satisfy o(φ) = φ unrestrictedly, but only when φ is a single individual. Quine does not identify entities and their singletons generally, but only individuals and their singletons.15 A further way of telling compounding from collecting operations is their attitude towards composing nothing whatsoever. In the case of compounding this makes no sense: if there is nothing, there is is nothing which could be produced by putting this nothing together. But for collecting operations the case is different. What justifies the existence of singleton collections (the conception of collecting things into a container) also justifies the existence of empty collections. In the same way as we can put one object in a bag we can put nothing in the bag and still end up with more than nothing, namely the empty bag. A badly planned art collection can end up containing only a single painting - it still remains an art collection16 and continues to be one if bad luck accompanies bad planning and the only picture it contains is stolen. It makes sense to speak of singleton or empty art collections because of the surroundings, the 'container' which make up an art collection in addition to the paintings: the exhibition hall, the frames, the catalogue, 13?, 38-39. 14As argued by ?, 144. 15'If y is a class of several members or of none, certainly y must be distinguished from its unit class, which has one member. [. . .] In general thus the distinction between classes and their unit classes is vital, and I continue to respect it. But the distinction between individuals and their unit classes serves no discoverable purpose [. . .].' ?, 32. 16This idea is due to Daniel Isaacson. See ?, 30. 9 the plans for further development and so on. 3.5 hierarchy The hierarchy parameter specifies whether iterated composition can result in objects which cannot be constructed by single compositions. For flat composition operations this is not the case. The history of constructing the composition cannot be found in the resulting object. The fusion of three objects a, b and c could have been composed in all sorts of ways: by fusing them all at once, by first fusing a and b, and then fusing c with the result, by first fusing a and c and then fusing b with the result, and so on. If the composition operation we employ is not fusion but set-formation, however, these three constructional histories will lead to three different sets, namely {a, b, c}, {{a, b}, c} and {{a, c}, b}. Hierarchical composition operations are important not just because they can 'spin extravagant realms of being out of just one single thing'17 but because they can be used to create many-layered hierarchical structures rather than one-layered flat ones. The existence of such a composition operation is essential for the expressive power of natural language. This is not often realized and in fact this consideration is curiously absent from Goodman's discussion of composition operations. Goodman discusses the case of ordered pairs and argues that pairs like < a, b > and < b, a > are distinct only to the extent to which they are descriptions of the same thing.18 But clearly this will not do in tackling the linguistic case. That Albert is taller than Becca and that Becca is taller than Albert are not different descriptions of the same fact, the facts they describe are even mutually exclusive. Composition operations forming sentences from their constituents cannot be flat, as for example syntactic concatenation is. Concatenating 'he chased away the man' and 'with the dog' and concatenating 'he chased away', 'the man', and 'with the dog' give exactly the same strings of syntactic items. The fact that this sentence has two meanings (depending on whether 'with the dog' is a qualification of the man or the means of chasing) must therefore be due to the fact that on another level (where the relevant composition operation is not concatenation but the composition of sentences from their constituents) there is the possibility of distinguishing these two different ways of composing the sentence (composing 'with the dog' first with 'the man' or first with 'he chased away'). The composition operation in play here is required to allow us to trace the compositional history of the item in question in the resulting object. As such it has to be hierarchical, rather 17?, 13. 18'Normally we do no more conclude that we describe different composite entities when we name two people in different order than we conclude that a house from top to bottom and the house from bottom to top are different entities [. . .]. In daily life a multiplicity of descriptions is no evidence for a corresponding multiplicity of things described.' (?, 164). 10 than flat. 3.6 Diversity This parameter specifies whether it makes a difference that some object appear repeatedly in the collection to be composed. For set formation this is not the case, the set formed from the object x twice over is just the same as that formed from x, namely {x}. But the tuples formed in such a way are different, namely < x, x > and < x >. Formation of ordered sets is therfore repetitive, not diverse. The same holds for the composition operation of multiplication; 2 * 3 is different from 2 * 2 * 3. One might think that there is a certain tension between a composition operation's being repetitive and its relating concrete objects. After all, do we not know that one of the identifying criteria of concreta is that they cannot be repeated in different spatial locations at the same time? This is correct, but the nature of repetition of concreta in compositions is different. Consider as a paradigm example the ordered set of cities I visited last year, it is < Vienna,London,Vienna >. I have been to Vienna twice and that is why Vienna (the city itself, not just the name or the concept of the city) occurs twice in the ordered set. Given that the set as an abstract object does not have a spatio-temporal location it can contain components (things it has been composed from) with such locations, without implying that they are repeated at different locations at the same time. So in the same way as concrete objects can have abstract components (as in the form/matter case discussed in section 3.3) abstract objects can have concrete components (for examples as members in the set-theoretic sense).19 We should note, however, that the above consideration implies that it is not possible to have a repetitive composition operation which puts together only concrete objects and is itself concrete, for the very reason that the only form of repetition of concrete objects in a concrete composition can be in the form of multiple spatial presence at the same time,20 and this is a property concrete objects do not have. Note finally that the impossibility of having a repetitive operation on concreta producing concreta does not imply that a repetitive composition operation could not be difficult. As we saw in section 3.3, being difficult only implies that the composition itself is concrete, but does not demand 19This point corresponds closely to Katz's point about 'composite objects' (?, 121, 141). He argues that the existence of objects such as impure sets implies that the division of things into homogeneously abstract and concrete things is not exhaustive. According to him we have to introduce a new category of heterogeneous composite objects which contain both abstract and concrete objects as constituents. 20Having multiple tokens of the same type will not help, since the tokens will all be spatio-temporally distinct objects and therefore cannot be repeated. The type itself, on the other hand, is abstract. 11 that all the components have to be concrete too (the tile/pattern example was supposed to demonstrate this). Repetitive composition operations are also essential in accounting for structural universals, i.e. universals involving other universals, such as 'being methane' involves the universal 'being a hydrogen atom'. ? argues vigorously against the existence of such universals. His main argument is that there is no good way of making sense of an operation which composes structural 'complex' universals from 'simple' ones. Amongst other things, this would have to be repetitive (since there are four hydrogen atoms in a methane molecule). Lewis claims this is incomprehensible: But what can it mean for something to have a part four times over? What are there four of? There are not four of the universal hydrogen, or of the universal bonded ; there is only one.21 If we get rid of the Lewisian equation of 'composition' with 'mereological fusion' the matter is not so obscure. If we talk in terms of the more general notion of constituents, ordered sets are a perfectly straightforward example of the multiple occurrence of objects. They do not have the same part several times over, but the same constituent repeatedly, which means that the same constituent was used several times over (if we are forgiven this temporal way of speaking) in putting together the composition, as for example an expression-types is used several times in the same sentence. Of course Lewis would not be happy with this, given that he denies set-theoretic composition to be composition at all.22 But first of all set-theoretic composition (which fails condition a) given in section 2) has as much right to be regarded as genuine composition as mereological fusion (which fails condition b)), and secondly we are not committed to assuming that structural universals are actually sets of simple ones. I personally do not think they are, though I do not have any conclusive argument for this. The important point is that all we would require is that the composition operation composing structural universals is repetitive, in the same way as composition of ordered sets is, and none of Lewis' arguments manage to show that such repetitive composition operation cannot exist. 4 The space of composition operations In order to see how the above parameters can help us systematize composition operations let us look at some examples which exemplify different settings of the six parameters. Here they are: 1. Collecting urelements together to form a set. 21?, 34. 22?, 37. 12 2. Collecting urelements together to form an ordered set. 3. Collecting urelements together to form an multiset.23 4. Collecting urelements together to form a sequence. 5. Forming the mereological fusion of some material objects. 6. Multiplying a collection of prime numbers. 7. Putting material objects into a bag 8. Aligning material objects in a spatial linear order, such as men in a row or books on a shelf. 9. Putting together expressions to form a sentence. 10. Stacking Lego blocks into one another. It is easy to see that all of these are composition operations in the sense described in section 2, i.e. the resulting compositions either contain the objects they are composed from as spatio-temporal parts or they can be uniquely decomposed into the original objects. How these operations reflect the different settings of our parameters can be best observed in the following table. Note that the second or 'negative' setting of each parameter is set in italics. operation range deter diffic ornam hierar div 1. set univ det easy orn hie dist 2. ms univ det easy orn hie rep 3. tuple univ ind easy orn hie dist 4. sequence univ ind easy orn hie rep 5. fusion univ det easy plain flat dist 6. prime univ det easy plain flat rep 7. linear univ ind diff plain flat dist 8. bag univ det diff orn hie dist 9. sentence typ ind easy orn hie rep 10. lego typ ind diff plain flat dist 23A brief note on terminology: Multisets (denoted by [ ]) are distinguished from sets ({ }) in that repetition but not the order of elements matters for their individuation. (For the formal details of multiset theory see ?.) Tuples (< >) with elements in different orders are distinct, but do not allow for elements to be repeated. Sequences (| |)are just like tuples but allow for repetitions. The following identities and non-identities may serve as a summary: {a, b} = {b, a} = {b, a, a} = {a, a, b} [a, b] = [b, a] 6= [b, a, a] = [a, a, b] < a, b > 6=< b, a >=< b, a, a > 6=< a, a, b > |a, b| 6= |b, a| 6= |b, a, a| 6= |a, a, b| 13 The justifications for most of the entries in this table should be straightforward. The setting of parameters allow us to group together different sets of composition operations. The first four operations are all hierarchical: they allow us to compose objects by iterated application which cannot be composed by single applications. Set formation is universal (any collection of objects can be composed into a set), determinate (there is always only one way of doing this), easy (there is no difference between actual and possible sets), ornate (singletons are different from their only members), and diverse (all the members of a set must be distinct). Multiset formation is just like set formation, apart from the setting of the last parameter: in multisets elements can occur repeatedly. Formation of tuples differs from multiset formation in the way the determinacy parameter is set: while there is only one way of composing a collection of objects into a multiset, there are generally different ways of composing them into a tuple. The diversity parameter for tuples is set in the same ways as for sets. Sequences again are like tuples but differ in the setting of the diversity parameter: as multisets are to sets, sequences are to tuples. Let us now consider the remaining four operations which are all universal: fusion, multiplying primes, linear arrangement and bagging. Fusion is the only operation which has all the parameters set in the first or 'positive' way. It is distinguished from set formation by being plain (fusing in object with itself does not result in anything new) and flat (we cannot construct a hierarchical structure with several levels by iterated fusing). Multiplying prime numbers is just like it, but does not demand that the elements composed must all be distinct: the diversity parameter is set the other way. Linear arrangement and bagging are the first two difficult operations we meet. Here actual and possible compositions come apart. The possible arrangement of objects in a row or their possible bagging are not the same as their actual arrangement or bagging. Our final two composition operations, sentence composition and Lego are typed. They do not apply to all objects across the board but only to certain specific collections which 'fit together', either into a grammatical sentence or into a Lego structure. They are also both indeterminate; it is generally possible to put them together in more than one way. As can easily be seen they differ regarding all other parameters. It is now obvious that there are 64 different ways in which the above six parameters can be set. Do all of these settings describe different composition operations, i.e. are all the different combinations of 'on' and 'off' settings consistent, and the six parameters thus all independent? It is straightforward to check that all the parameters are pairwise independent, so that every positive or negative setting of a parameter is consistent with the positive or negative setting of an arbitrary second one. Indeed the ten examples of composition operations given above provide us with sufficient material for producing examples of many of the pairwise combina14 tions to be considered. The only combination we might have initial doubts about is that of difficulty and repetitiveness. After all the two examples of difficult composition operations required some causal interaction with the objects composed (such as arranging them in a row or putting them into a bag) to bring about the composition. But then it might be argued that such a composition operation cannot also be repetitive: we cannot build a Lego structure, for example, using the same Lego block twice (we can use to tokens of the same block type, but this is a different thing). But as we saw at the end of section 3.6 this tension disappears once we consider that only the composition itself, not not all its components have to be concrete (so that repetition can be restricted to the abstract components of concrete objects). Of course the pairwise independence of the parameters does not yet give us full independence. After all it might be the case that, for example, the first three parameters being on required the fifth to be off. This would be consistent with pairwise consistency but implies that not all 64 possible settings of the parameters will describe composition operations. In order to rule out such a situation it is necessary to find examples of composition operations, one for each of the 64 settings. 5 Typed composition operations Typed compositions operations are an important and fundamental kind of composition. Moreover, they are operations which are not generally studied much as a class in their own right. Apart from the linguistic case and Lego we find them in chemistry (when composing atoms into molecules not all collections of atoms will fit: their valencies must be right too), in music (not all combinations of notes form a melody) and mathematics (in the case of functional composition: the range of the one function must be the domain of the other one). A less obvious example is composing constituents of states of affairs to form states of affairs (if they do not have the right logical form they will not fit, e.g. two individuals and a monadic property cannot together constitute a state of affairs). Composition operations of this sort allow us to type objects according to the way they can be stuck together with other objects to form a complex. In chemistry atoms can be sorted in this way, in linguistics categorial grammar uses exactly this procedure to define its grammatical categories. This is done by collecting objects together according to intersubstitutability criteria. Two objects will be taken to be in the same category if they can be intersubstituted in all complexes without destroying complexhood. Obviously this can only work if the range parameter is not set to universal, otherwise, whenever o(a, b), o(c, d) exist, so will o(a, c), o(b, d). The types or categories thus arrived at are functional categories. If o 15 is a typed composition operation on some objects a, b, c, . . . which compose compositions of sort C from them, an object x is said to belong to the functional category (a|C) if o(x, a) exists, so that (a|C) denotes the category of all the objects which combined with a yield a composition. If we assume that our objects are the words John, Mary, sleeps, walks, hits, and calls and o is sentence-forming composition (and the sort of composition C formed therefore that of an English sentence) we can divide them into three groups, c1 = {John,Mary}, c2 = {sleeps,walks} and c3 = {hits, calls}. These groups belong to the following functional categories: c1 : (c2|C), (c1|(c3|C)), c2 : (c1|C), c3 : (c1|(c1|C)), thus roughly corresponding to the traditional grammatical categories noun, intransitive and transitive verb.24 Categorizations on the basis of typed composition operations are important since they allow us to sort things like words, atoms or constituents of states of affairs without having to refer to any of their non-relational properties (that they name things or qualities of things, that they have a particular atomic weight, that they are individuals or properties). Such categorizations usually differ from those based on non-relational properties. The grammatical categories identified in categorial grammar are quite different from those usually listed in traditional grammar on the basis of semantic considerations. When categorizing constituents of states of affairs in this fashion it turns out that the resulting structure is too weak to establish a difference between those constituents which are usually regarded as individuals, and those regarded as properties.25 The interpretation of these results is debatable; while it is uncontroversial that the account of grammatical categories developed in categorial grammar is far superior to that of traditional grammar, the impossibility of retrieving the individual-predicate distinction in terms of functional categories can be taken in two ways. It could either be read as an indication that there 'really' is no distinction between individuals and properties since it cannot be formulated in terms of functional categories (in which case we have to explain where the apparent distinction comes from) or as showing that while the distinction is in fact there we need more than purely combinatorial information to discover it (in which case we have to show what exactly this 'something more' is). Which view we go for depends on whether we take the categorization of some set of objects as discovered by the study of the relevant composition operation, or as constituted by it. In the first case the functional categorization could just be wrong in delivering 24Real-life categorial grammar is of course much more sophisticated than this toy example suggests. Amongst other things it allows for different forms of concatenation (on the left and on the right), it has more than one primitive category (apart from our C ('sentence') usually that of a proper name), and it incorporates type-change rules which e.g. explain why John and Mary prima facie seem to belong to two different categories, while they are in fact both nouns. But taking these further complications into account would only distract from the general considerations about typed composition operations I want to raise. 25?. 16 a different categorization from the actual one, while this could not be so in the second case. The study of typed composition operations is therefore particularly interesting in contexts where we do not consider the categorization to have a life of its own, or where the only route to such a categorization is through the composition operation. We would clearly not want to make such assumptions in chemistry: there is more to being a particular element than its bonding behaviour, and there are other ways of finding out about them than considering just it. In grammar and ontology matters are not so clear, however. Why should a word-type or grammatical category a word belongs to be anything more than the reflection of that word's joining behaviour with other words? And why should an object-type or ontological category an object belongs to be anything more than the reflection of that object's joining behaviour with other objects? In these cases the typed composition operations which put together the objects in question are of fundamental importance for establishing a categorial structure on their components. ∗ References ∗I would like to thank Arif Ahmed and an anonymous referee for Logique et Analyse for their helpful comment on earlier versions of this paper.