A Theory of Granular Partitions

In the present paper we present the basic formal theory of granular partitions, leaving for a later work the presentation of the theory of cell-labeling (and, more generally, of the cognitive aspects of partitions as we here understand them). Our formal theory has two orthogonal and independent parts: (A) a theory of the relations between cells, sub-cells, and the partitions in which they are contained; (B) a theory of the relations between partitions and objects in reality. The counterpart of (A) in a set-theoretic context would be the study of the relations among subsets of a single set; the counterpart of (B) would be the study of the relations between sets and their members. These set-theoretical counterparts of (A) and (B) are, be it noted, not independent. This is because the standard subset relation of set theory is itself defined in terms of the set-membership relation ($x$ is a subset of $y$ means: all the members of $x$ are members of $y$). In the context of partition theory, in contrast, the corresponding relations are defined independently of each other. Partition theory thus departs from the extensionalism of set theory (i.e. from the assumption that each set is defined exclusively by its members). A cell is defined by its position within a partition and by its relations to other cells, and it is this which gives rise to the relations treated of by theory (A). What objects in reality are located in a cell—the matter of theory (B)—is then a further question, which is answered, in different ways from case to case. Briefly, we can think of cells as being projected onto objects in something like the way in which flashlights are projected upon the objects which fall within their purview.

Consider the left part of Figure 1. Theory A governs the way we organize cells into nesting structures and the way we label cells. Theory B governs the way these cell-structures project onto reality indicated by the arrows connecting the left and the right parts of the Figure. Our strategy in what follows will be first of all to define a series of master conditions belonging to theory (A) and theory (B) respectively, and which—for the purposes of the present paper—all partitions will be assumed to satisfy. In later sections we will add further conditions, satisfied by some partitions but not by others.

Theory (A) is effectively a theory of well-formedness for partitions; it studies properties partitions have in virtue of the relations between and the operations performed upon the cells from out of which they are built, independently of any linkage to reality beyond. Cells in partitions may be nested one inside another in the way in which, for example, the species crow is nested inside the species bird, which in turn is nested inside the genus vertebrate in standard biological taxonomies. When one cell is nested inside another in this way we say that the former is a sub-cell of the latter. Note that the subcell relation can hold between two cells independently of whether there are any objects located in them (as for example in relation to the cells labeled ‘male dodos’ and ‘dodos’ in a classification of extinct animals).

We use $z,\; z\_1,\; z\_2,\; \backslash dots$ as variables ranging over cells and $A,\; A\_1,\; A\_2,\; \backslash dots$ as variables ranging over partitions ('cell' is 'Zelle', partition is 'Aufteilung' in German). We write $z\_1\; \backslash subseteq\_A\; z\_2$ in order to express the fact that $z\_1$ stands in a sub-cell relation to $z\_2$ within the partition $A$. (Where confusion will not result we will drop the explicit reference to the partition $A$ and write simply '$\backslash subseteq$'). We can then state the first of several master conditions on all partitions as follows:

MA1: The subcell relation $\backslash subseteq$ is reflexive, antisymmetric, and transitive.

This means that within every partition: each cell is a subcell of itself; if two cells are subcells of each other then they are identical; and if cell $z\_1$ is a sub-cell of $z\_2$ and $z\_2$ a sub-cell of $z\_3$, then $z\_1$ is in its turn a sub-cell of $z\_3$. We can think of the sub-cells of a cell within a given partition as special sorts of parts of the cell; they are those parts which are included within this same partition as cells in their own right.

We define a maximal cell of a partition $A$ as a cell satisfying:

Here '$Z(z,\; A)$' means that $z$ is a cell in the partition $A$. (Again: we shall normally omit the condition $Z(z,\; A)$ where confusion will not result.) We now demand as a further master condition that

MA2: Every partition has a unique maximal cell in the sense of DMax.

The motivation for MA2 is very simple: it turns on the fact that a partition with two maximal cells would either be in need of completion by some extra cell representing the result of combining these two maximal cells together into some larger whole; or it would not be one partition at all, but rather two separate partitions, each of which would need to be treated in its own right within the framework of our theory.

We also call the unique maximal cell of a partition its root, $r(A)$. The maximal cell of a partition is such that all the cells in the partition are included in it as subcells. MA2 implies that there are no partitions which are empty tout court in that they have no cells at all.

The transitivity of $\backslash subseteq$ generates a nestedness of cells inside a partition in the form of chains of cells satisfying $z\_1\; \backslash supset\; z\_2\; \backslash supset\; \backslash dots\; \backslash supset\; z\_n$, with $z\_1$ as root. We shall call the cells at the ends of such chains minimal cells or leaves, and define:

Another important aspect of a partition is then:

MA3: Each cell in a partition is connected to the root via a finite chain of immediate succeeding cells.

A cell $z\_2$ is the immediate successor of the cell $z\_1$ if and only if $z\_1\; \backslash subseteq\; z\_2$ and there does not exist a cell $z\_3$ such that $z\_1\; \backslash subset\; z\_3\; \backslash subset\; z\_2$ holds.

MA3 does not rule out the possibility that a given cell within a partition might have infinitely many immediate subcells (also called daughter cells). Enforcing finite chains thus leaves open the issue as to whether partitions themselves are finite.

If, in counting off the cars passing beneath you on the highway, your checklist includes one cell labeled red cars and another cell labeled Chevrolets, we will rightly feel that there is something amiss with your partition. One problem is that you will almost certainly be guilty of double counting. Another problem is that there is no natural relationship between these two cells, which seem rather to belong to distinct partitions. As a step towards rectifying such problems we shall insist that all partitions must satisfy a condition according to which every pair of distinct cells within a partition stand to each other either in the subcell relation or in the relation of disjointness. In other words:

MA4: If two cells within a partition overlap, then one is a subcell of the other.

Or in symbols:

(Here and in what follows initial universal quantifiers are taken as understood.) From MA3 and MA4 we can prove by a simple reductio that the chain connecting each cell of a partition to the root is unique.

The background to all our remarks in this paper is mereology. We take the relation $\backslash leq$ meaning ‘part of’ as primitive, and define the relation of overlap between two entities simply as the sharing of some common part. $\backslash leq$ is like $\backslash subseteq$ in being reflexive, anti-symmetric and transitive, but the two differ in the fact that $\backslash subseteq$ is a very special case of $\backslash leq$.

The subcells of a cell are also parts of the cell (just as, for David Lewis, 1991, each singleton is a part of all the sets in which it is included). What happens when we take the mereological products and sums of cells existing within a partition? In regard to the mereological product, $z\_1\; *\; z\_2$, of two cells matters are rather simple. This product exists only when the cells overlap mereologically, i.e. only when they have at least one subcell in common. This means that the mereological product or intersection of two cells, if it exists, is in every case just the smaller of the two cells.

In regard to the mereological sum of cells $z\_1\; +\; z\_2$, in contrast, it is a more difficult situation which confronts us. Given any pair of cells within a given partition, the corresponding mereological sum does indeed exist—simply in virtue of the fact that the axioms of mereology allow unrestricted sum-formation. (This is a trivial matter, for the mereologist: if you got the parts, whatever they are, then you got the whole.) But only in special cases will this mereological sum be itself a cell within the partition in question. This occurs for example when cells labeled ‘male rabbit’ and ‘female rabbit’ within a partition have as their sum the cell labeled ‘rabbit’. There is, in contrast, no cell in our standard biological partition of the animal kingdom labeled rabbits and jellyfish, and there is no cell in our standard geopolitical partition of the surface of the globe labeled Hong Kong and Algeria.

To make sense of these matters we need to distinguish the mereological sum of two cells from what we might call their partition-theoretic sum. We can define the former as just the result of taking the two cells together in our thoughts and treating the result as a whole. We can define the latter as follows. The partition-theoretic sum $z\_1\; \backslash cup\; z\_2$ of two cells in a partition is the smallest subcell within the partition containing both, $z\_1$ and $z\_2$, as subcells; i.e., it is the least upper bound of $z\_1$ and $z\_2$ with respect to $\backslash subseteq$. (By MA2 and MA4 we know that this is always defined and that it is unique.) This partition-theoretic sum is in general distinct from the mereological sum of the corresponding cells. (The partition-theoretic sum of the cells labeled rabbit and lion is the cell labeled mammal in our partition of the animal kingdom.) The best we can say in general is that $z\_1\; +\; z\_2$ is at least part of $z\_1\; \backslash cup\; z\_2$ (Smith, 1991). Note, on the other hand, that if we analogously define the partition-theoretic product, $z\; =\; z\_1\; \backslash cap\; z\_2$, of two cells within a given partition as the largest subcell shared in common by $z\_1$ and $z\_2$, i.e., as their greatest lower bound with respect to $\backslash subseteq$, then it turns out that this coincides with the mereological product already defined above.

Mereological sum and product apply to both cells and objects; partition-theoretic sum applies only to cells. Here we use the symbols for the two groups of relations as shown in Table 1:

When restricted to cells within a given partition $\backslash subseteq$ and $\backslash leq$ coincide, and so also do $\backslash cap$ and $*$. We can think of $\backslash subseteq$ as the result of restricting $\backslash leq$ to the natural units picked out by the partition in question. We can think of set theory as amounting to the abandonment of the idea that there is a distinction between natural units and arbitrary unions. Set theory, indeed, derives all its power from this abandonment.

Philosophers since Aristotle have recognized that the results of our sorting and classifying activities can be represented as those sorts of branching structures which mathematicians nowadays called trees. Trees are directed graphs without cycles. They consist of nodes or vertices and of directed edges that connect the nodes. That the edges are directed means that the vertices connected by an edge are related to each other in a way that is analogous to an ordered pair. Here we are interested specifically in rooted trees, which is to say: trees with a single topmost node to which all other vertices are connected, either directly or indirectly, via edges. In a rooted tree, every pair of vertices is connected by one and only one chain (or sequence of edges). We shall think of the directedness of an edge as proceeding down the tree from top to bottom (from ancestors to descendants). That a tree is without cycles means that, if we move along its edges, then we will always move down the tree and in such a way that, however far we travel, we will never return to the point from which we started.

The connection between partitions and trees will now be obvious: it is a simple matter to show that every finite partition can be represented as a rooted tree of finite depths and vice versa (Mark, 1978). To construct a tree from a finite partition we create a graph by mapping the cells $z\_i$ of the partition onto nodes $v\_i$ within the graph and by introducing a directed edge from vertex $v\_i$ to $v\_j$ if and only if the cell $z\_i$ has cell $z\_j$ as an immediate subcell. That this is always possible follows from the fact that the subcell relation is well defined (by MA1) and from the fact that chains of immediate cells are always finite (MA3). We can easily show also that the resulting graph is a rooted tree, which follows from MA2; that the graph structure is connected (from MA2), and acyclical (from MA4); and that there is a unique path between any two vertexes (from MA2, MA3 and MA4). The complementary reconstruction of a partition from its tree representation is no less trivial.

We can represent a partition not only as a tree but also as a simple sort of Venn diagram. In a Venn diagram partition cells are represented as topologically simple and regular regions of the plane. Our partitions are Venn diagrams within which regions do not intersect. (Conversely every array of non-intersecting, possibly nested regions in the plane can be transformed into a tree in such a way that each region is represented by a node in the tree, and each directed link in the tree represents an immediately contains relation between a corresponding pair of nested regions.) In the remainder we will often think of partitions as such planar maps (that is as Venn diagrams without overlapping), and the minimal cells correspond to the smallest regions within such diagrams.

Tree and Venn-diagram representations of granular partitions are not equivalent. To see this consider Figure 2. Even if we ignore the labeling it is obvious that the two Venn-diagrams represent two distinct partitions. The mammal-partition contains ‘empty space’ and the first-couple-partition is full in the sense that it does not contain ‘empty space’. This distinction, however, can not be made in terms of the corresponding tree representations. In order to represent it in the tree we needed consider labeled trees with nodes labeled full or not-full. We will discuss these issues in more detail in our section on fullness and cumulativeness of granular partitions.

Partitions are more than just systems of cells. They are constructed to serve as inventories or pictures or maps of specific portions of reality, and in this they are analogous to windows, or to the latticed grills purported to have been used by Renaissance artists as aids to the faithful representation of objects in reality (Smith, 2001b). They are analogous also to propositions (Elementarsätze) as described by Wittgenstein in the Tractatus (1961). A proposition, for Wittgenstein, is built out of simple signs (names) arranged in a certain order. Each name, Wittgenstein tells us, stands in a projective relation to a corresponding object in the world: it cannot fail to strike its target. If a proposition is true, then its simple signs stand to each other within the proposition as the corresponding objects stand to each other in the world. It is in this sense that a true atomic proposition is a picture, as Wittgenstein puts it, of a state of affairs in reality. That a proposition is a complex of names arranged in a certain order is in our present context equivalent to the thesis that a partition is a complex of cells arranged in a certain order.

A partition is a complex of cells in its projective relation to the world (compare Tractatus, 3.12). This relation may be effected either directly by the user of the partition—for example in looking through the cells of the grid and recording what objects are detected on the other side—or indirectly, with the help of proper names or other referring devices such as systems of coordinates or taxonomic labels.

For Wittgenstein it is guaranteed a priori for every name that there is some unique object onto which the name is projected. From the perspective of the theory of granular partitions, in contrast, projection may fail. That is, a partition may be such that—like the partition cataloguing Aztec gods—there are no objects for its cells to project onto. Works of fiction and also not yet realized plans may be conceived as involving partitions of this kind.

In this paper, however, we are interested primarily in partitions which do not project out into thin air in this way. We write '$P(z,\; o)$' as an abbreviation for: cell $z$ is projected onto object $o$. We can also, if the context requires it, write '$P\_A(z,\; o)$' to indicate that the projection of $z$ onto $o$ obtains in the context of partition $A$. In what follows we shall assume that a unique such projection is defined for each partition. In a more general theory we can weaken this assumption, for example by allowing projections to vary with time while the partition remains fixed (Smith and Brogaard, 2002a). Such variation of projection for a fixed partition is involved in all sampling activity. Consider, for example, what happens when we use a territorial grid of cells to map the presence of one or more birds of given species in given areas from one moment to the next.

If projection is successful, then the object upon which a cell is projected is located in that cell. The use of the term 'location' reflects the fact that one important inspiration of our work is the study of location relations in spatial contexts. One motivating example of a location relation within our theory is the relation between a spatial object such as a railway station and an icon on a map. Other motivating examples are of a non-spatial sort: they include the relation between an instance (Tibbles) and its kind (cat) or the relation between a customer and the corresponding record in a database. Indeed they include the relation between you and your name.

We can compare a partition with a rig of spotlights projecting down onto an orchestra during the performance of a symphony. Each cell of the partition corresponds to some spotlight in the rig. Some cells (spotlights) will project upon single players, others onto whole sections of the orchestra (string, wind, percussion, and so forth). One cell (spotlight) will project upon the orchestra as a whole. Note that the spotlights do not hereby create the objects which they cast into relief. When once the rig has been set, and the members of the orchestra have taken their places, then it will be an entirely objective matter which objects (individuals and groups of individuals) are located in which illuminated cells.

In what follows we make the simplifying assumption that objects are exactly located at their cells (that spotlights never partially illuminate single players or sections). Compare the way in which Wyoming is exactly located at the cell 'Wyoming' in the partition of the US into States or the way in which your brother Norse is exactly located at the cell 'Norse' in your partition (list) of your family members. In a more general theory we liberalize the location relation in such a way as to allow also for partial or rough location (Casati and Varzi, 1995; Bittner and Stell, 1998).

When projection succeeds, then location is what results. Projection and location thus correspond to the two directions of fit—from mind to world and from world to mind—between an assertion and the corresponding truthmaking portion of reality (Searle, 1983; Smith, 1999). Projection is like the relation which holds between your shopping list and the items which, if your shopping trip is successful, you will actually buy. Location is like the relation which obtains between the items you have bought and the new list your mother makes after your return, as she checks off those items which you have in fact succeeded in bringing back with you.

The formula '$L(o,\; z)$' abbreviates: object $o$ is located at cell $z$. (And again where this is required we can write '$L\_A(o,\; z)$' for: $o$ is located at $z$ in partition $A$.) Location presupposes projection: an object is never located in a cell unless the object has already been picked out as the target of the projection relation associated with the relevant partition. But successful projection—by which is meant the obtaining of the projection relation between a cell and an object—also presupposes location, so that where both $L$ and $P$ obtain they are simply the converse relations of each other. We have now reached the point where we can formulate the first of our master conditions on partitions from the perspective of theory (B):

(Successful) projection and (successful) location are simple converses of each other. (We formulate this principle as two separate conditions in order to leave room for a more general theory in which these two relations are teased apart.)

MB1 and MB2 tell us that a partition projects a given cell onto a given object if and only if that object is located in the corresponding cell. Very many partitions—from automobile component catalogues to our maps of states and nations—have this quality without further ado.

We shall call partitions which satisfy MB1 and MB2 transparent partitions, a notion which we can define in the obvious way as follows:

MB1 and MB2 jointly ensure that objects are actually located at the cells that project onto them. Notice however that a transparent partition, according to our definition, may still have empty cells. Such cells may for example be needed in the context of scientific partitions in order to leave room for what, on the side of the objects, may be discovered in the future. (Compare the cells labeled Ununnilium, Ununonium and Ununbium in the Periodic Table of the Elements.) Empty cells may similarly be needed to cover up for temporary lapses in memory. You are attempting to account for the people at your party last night. Your partition consists of six cells labeled: John, Mary, Phil, Chris, Sally, and anyone else (for people you might have forgotten). Assume that John, Mary, Phil, Chris and Sally is a complete listing of all the people at the party. Your anyone else cell is then empty.

An object $o$ is recognized by a partition if and only if the latter has a cell in which that object is located (Smith and Brogaard, 2002b). Intuitively, recognition is the partition-theoretic analogue of the standard set-membership relation. Partitions embody the selective focus of our mapping, classifying, and listing activities. To impose a partition on a given domain of reality is to foreground certain objects and features in that domain and trace over others. Note hereby that we trace over not only the objects which surround that which is foregrounded, as according to the usual understanding of the foreground/background structure; for we also trace over those parts of the foregrounded object which fall beneath the threshold of our concerns. Partitions are granular in virtue precisely of the fact that a partition can recognize an object without recognizing all its parts.

Partitions—think again of Venn diagrams—are designed to reflect the part-whole structure of reality through the fact that the cells in a partition are themselves such as to stand in relations of part to whole. Given the master conditions expressed within the framework of theory (A) above, partitions have at least the potential to reflect the mereological structure of the domain onto which they are projected. And in felicitous cases this potential is realized.

That we distinguish between the recognition (foregrounding, selection) of objects on the one hand and the reflection of mereological structure on the other hand is not an arbitrary matter. In Tractarian semantics we distinguish between projection and isomorphism. In set theory we distinguish, for any given set, between a domain of elements and the set-theoretic structure imposed on this domain. Just as it is possible to have sets consisting entirely of Urelemente (together with a minimal amount of set-theoretic packaging), so it is possible to have partitions built exclusively out of minimal cells (and one root cell). Such partitions amount, simply, to lists of the things that are recognized by their cells, with no mereological structure on the side of these objects being brought into account.

Figure 4(a) and 4(b) represent partitions consisting of two minimal cells $z\_1$ and $z\_2$ projecting onto objects $o\_1$ and $o\_2$. Case (a), a simple list, is unproblematic. Case (b) we shall also allow. This is in keeping with the notion that minimal cells are the (relative) atoms of our system, and we take this to mean that they should be neutral with regard to any mereological structure on the side of their objects. An example of type (b) would be a list of regions represented at a conference to discuss measures against terrorism, a conference including representatives from both Germany and Bavaria.

Cases like (c), in contrast, represents projections in which, intuitively, something has gone wrong. All three cases satisfy the master conditions we have laid down thus far, for the latter allow both for disjoint cells to be projected onto what is not disjoint (b) and also for disjoint objects to be located in cells which are not disjoint (c). Cases like (c) on the other hand seem to fly in the face of a fundamental principle underlying the practice of hierarchical classification, namely that objects recognized by species lower down in a hierarchical tree should be included as parts in whatever is recognized by the genera further up the tree. To exclude cases like (c) we shall impose a condition to the effect that mereological structure within a partition should not misrepresent the mereological relationships between the objects which the corresponding cells are projected onto. We first of all define the following relation of representation of mereological structure between pairs of cells:

If $z\_1$ is a subcell of $z\_2$ then any object recognized by $z\_1$ must be a part of any object recognized by $z\_2$. A partition is then mereologically structure-preserving if and only if each pair of cells within the partition satisfies DS1:

We can now impose a new master condition:

MB5: All partitions are mereologically structure-preserving in the sense of DS2.

Note that even MB5 is still very weak. Its effect is entirely negative, since it merely ensures that partitions do not misrepresent the mereological relationships between their objects. Partitions might still be entirely blind to (trace over) such relationships. Two minimal cells might project onto objects which stand to each other in any one of the possible mereological relations (identity, proper parthood, disjointness, overlap), and all pairs of cells are likewise neutral as to the mereological relations between the objects onto which they are projected provided only that they do not stand to each other in the subcell relation. This means that, given such cells, we are entitled to infer nothing at all about the mereological relations among the corresponding objects.

Consider, for example, a partition that contains cells, $z\_1$ and $z\_2$, that recognize John and his arm, respectively, so that $L(\backslash text\{John\},\; z\_1)$ and $L(\backslash text\{John\text{'}s\; arm\},\; z\_2)$. Then cell $z\_1$ need not be a proper subcell of the cell $z\_2$, for the partition may not know that the object located in $z\_2$ is properly designated as John's arm. Or consider a partition containing two cells that recognize, respectively, mammals and whales. Suppose that this is a partition constructed at a time when the status of whales as mammals was not yet recognized. The cell labeled whales is not, then, included as a subcell of the cell labeled mammals. But the partition can still satisfy our conditions laid down so far. This is so, for example, if the cell that recognizes whales is a subcell of the cell recognizing animals but not a subcell of any other subcell of the cell recognizing animals (Partition $A\_1$ in Figure 5). If the cell that recognizes whales were also a subcell of the cell that recognizes fish, for example, then the partition would misrepresent the mereological relationship between these two species and so violate MB5 (Partition $A\_2$ in Figure 5).

Partitions may trace over mereological relationships between the objects they recognize, but MB5 is strong enough to ensure that, if a partition tells us something about the mereological relationships on the side of the objects which it recognizes, then what it tells us is true. Notice that partition $A\_2$ still satisfies MB1–4.

Consider a domain of objects consisting of two regions, $x$ and $y$, that properly overlap in the region $v$, so that $x\; *\; y\; =\; v$ with and . Consider now a partition with cells $z\_1$ and $z\_2$ recognizing $x$ and $y$, respectively, so that $L(x,\; z\_1)$ and $L(y,\; z\_2)$. Assume further that $z\_1$ and $z\_2$ do not stand in any subcell relation to each other, i.e., their partition-theoretic intersection is empty. Only four possibilities regarding the representation of $v$ now remain: (1) our partition does not recognize $v$ at all; (2) it recognizes $v$ but traces over its mereological relationships to $x$ and $y$; (3) it recognizes $v$ through a subcell of $z\_1$ but it traces over the fact that $v$ could equally well be recognized by a subcell of $z\_2$; (4) it recognizes $v$ through a subcell of $z\_2$ but it traces over the fact that $v$ could equally well be recognized by a subcell of $z\_1$. The fifth possibility—of allowing sub-cells of both $z\_1$ and $z\_2$ to recognize $v$ is excluded by the tree structure of granular partitions.

Let $x$ and $y$ be two neighboring countries which disagree about the exact location of their common boundary and let $v$ be the disputed area. The inhabitants of country $x$ consider $v$ to be part of $x$, the inhabitants of country $y$ consider $v$ to be part of $y$. Possibility (1) then corresponds to the view of some third country at the other side of the globe who recognizes the countries $x$ and $y$ but does not care about their border dispute. (2) corresponds to the view of an observer who recognizes that there is a disputed area but who is neutral about the status of the disputed area. (3) corresponds to the view of country $x$ and (4) to that of country $y$.

Another example of case (2) is provided by Germany and Luxemburg, which overlap at their common border on the River Our. The river is part of both countries. Mapmakers normally have no facility to represent cases such as this, and so they either adopt the policy of not representing such common regions at all (the border is represented as a line which we are to imagine as being without thickness), or they recognize the region constituted by the river on the map but trace over its mereological properties. Larger-scale maps often embrace a third alternative, which is to misrepresent the relations between Germany and Luxemburg by drawing the boundary between the two countries as running down the center of the river.

That upon which a partition is projected is a certain domain of objects in reality (the term ‘domain’ being understood in the mereological sense). We shall conceive the domain of a partition as the mereological sum of the pertinent objects. It is, as it were, the total mass of stuff upon which the partition sets to work: thus it is stuff conceived as it is prior to any of the divisions or demarcations effected by the partition itself. The domains of partitions will comprehend not only individual objects and their constituents (atoms, molecules, limbs, organs), but also groups or populations of individuals (for example biological species and genera, battalions and divisions, archipelagos and diasporas) as well as their constituent parts or members. Domains can comprehend also extended regions (continua) of various types. Spatial partitions, for example maps of land use or soil type (Frank et al., 1997), are an important family of partitions with domains of this sort. There are also cases where partitions impose upon continuous domains a division into discrete units for example by creating temperature or frequency bands.

We are now able to specify what we mean by ‘domain of a partition.’ Our representation of partitions as trees and our condition on reflection of structure (MB5) ensure that all partitions trivially reflect the fact that the objects recognized by their cells are parts of some mereological sum. For MB5 is already strong enough to ensure that everything that is located at some cell of a partition is part of what is located at the corresponding root cell. If any cell pointed outside of what is located at the root cell it would misrepresent the mereological structure of the corresponding domain.

We can thus define the domain of a partition simply as the object (mereological whole) onto which its root cell is projected. By functionality of projection and location there can be only one such object.

We now demand as a further master condition that every partition has a non-empty domain in the sense of DD:

We then say that a partition represents its domain correctly if and only if MA1–5 and MB1–6 hold. Note that this condition of correctness is still rather easily satisfied. (It is achieved already in every simple list, provided only that the list involves no double counting and no ambiguous reference of the sort involved in the Oliver and Richard Cromwell case.)

If there is a single maximal object (the whole universe), then one correct representation thereof is provided by a partition consisting of just one cell labeled 'everything' (we might call this the Spinoza partition). A partition with just three cells: a root cell, labeled animals, and two subcells, labeled dogs and cats, represents its domain correctly; it just falls far short of a certain desirable completeness. Correct representations, as we see, can be highly partial.

A correct representation, as we see, is not necessarily a complete representation. Indeed, since partitions are cognitive devices, and cognition is not omniscient, it follows that no partition is such as to recognize all objects. There is no map of all the objects in the universe. The complexity of the universe is much greater than the complexity of any single cognitive artifact. This feature of partiality is captured already by our terminology of granular partitions. Partitions characteristically do not recognize the proper parts of the whole objects which they recognize; for example they do not recognize parts which fall beneath a certain size.

It is the cells of a partition which carry with them this feature of granularity. Because they function like singletons in set theory, they recognize only single whole units, the counterparts of set-theoretic elements or members. If a partition recognizes not only wholes but also one or more parts of such wholes, then this is because there are additional cells in the partition which do this recognizing job. Consider, for example, a partition that recognizes human beings and has cells that project onto John, Mary, and so forth. This partition does not recognize parts of human beings—such as John's arm or Mary's shoulder—unless we add extra cells for this purpose. Even if a partition recognizes both wholes and also some of their parts, it is not necessarily the case that it also reflects the mereological relationships between the two. Imagine we are forensic scientists examining photographs taken at a crime scene and that these photographs generate a partition with cells recognizing John, Mary, and an arm. It may then be the case that the state of our knowledge is such that the cell recognizing the arm is not a subcell of the cell recognizing either John or Mary. Or let the arm be Kashmir and let John and Mary be India and Pakistan, respectively.

In relation to this granularity of partitions, we can once more call in the aid of Wittgenstein:

In the proposition there must be exactly as many things distinguishable as there are in the state of affairs, which it represents. They must both possess the same logical (mathematical) multiplicity ... (4.04)

Wittgenstein himself takes care of the issue of granularity by insisting that the world is made up of discrete simples, and by insisting further that all partitions (for Wittgenstein: propositions) picture complexes of such simples. (A similar simplifying assumption is proposed by Galton, 1999.) This is a simplifying assumption, which our present theory of granular partitions will enable us to avoid. For the latter admits partitions of arbitrary granularity including partitions which reflect distinct cross-cuttings of the same domain of reality (Smith and Brogaard, 2002a). The theory of granular partitions enables us moreover to remain neutral as to the existence of any ultimate simples in reality from out of which all other objects would be constructed via summation. This is due to the fact that partitions are by definition top-down structures. The duality with trees puts special emphasis on this aspect: we trace down from the root until we reach a leaf. A leaf has no further parts within the partition to which it belongs. But it need not necessarily project upon something that itself has no parts. The fact that there are leaves simply indicates that a partition does not care about (traces over) what lies beneath a certain level of granularity on the side of its objects. An object located at a minimal cell is an atom only relative to the partition involved.

Partitions are cognitive devices which have the built-in capability to recognize objects and to reflect certain features of the latter's mereological structure and to ignore (trace over) other features of this structure. We can now see that they can perform this task of tracing over in two ways: (1) by tracing over mereological relations between the objects which they recognize; (2) by tracing over (which means failing to recognize) parts of those objects. (2) is (unless atomism is true) a variety of tracing over that must be manifested by every partition. A third type of tracing over arises in reflection of the fact that partitions (we leave to one side here the Spinoza partition) are partial in their focus. In foregrounding some regions of reality each partition thereby traces over everything that lies outside its domain.

Consider a simple biological partition of the animal kingdom including a cell projecting on the species dog (Canis familiaris). Our definition of the domain of a partition and our constraint on functionality of projection implies that, besides the species dog also your dog Fido, and also Fido's DNA-molecules, proteins, and atoms are parts of the domain of this partition. But the latter are of course not recognized by the partition itself. It is cases such as this which illustrate why mereology requires supplementation by a theory like the one presented here. Partition theory allows us to define a new, restricted notion of parthood that takes granularity into account (compare Degen et al., 2001). This restricted parthood relation is an analogue of partition-theoretic inclusion, but on the side of objects:

This means that $x$ is a part of $y$ relative to partition $A$ if and only if: $x$ is recognized by a subcell of a cell in $A$ which recognizes $y$. From this we can infer by MB5 that $x$ is a part of $y$ also in the unrestricted or absolute sense.

The usual common-sense (i.e., non-scientific) partition of the animal kingdom contains cells recognizing dogs and mammals, but no cells recognizing DNA molecules. Relative to this common-sense partition, DNA molecules are not parts of the animal kingdom in the sense defined by DRP, though they are of course parts of the animal kingdom in the usual, non-relativised sense of 'part'.

We required of partitions that they at least not misrepresent the mereological structure of the domain they recognize. This constraint is to be understood in such a way that it leaves room for the possibility that a partition is merely neutral about (traces over) some or all aspects of the mereological structure of its target domain. Taking this into account, we can order partitions according to the degree to which they actually do represent the mereological structure on the side of the objects onto which they are projected. At the maximum degree of structural fit we have those partitions which completely reflect the mereological relations holding between the objects which they recognize.

Such a partition satisfies a condition to the effect that if $o\_1$ is part of $o\_2$, and if both $o\_1$ and $o\_2$ are recognized by the partition, then the cell at which $o\_1$ is located is a subcell of the cell at which $o\_2$ is located. Such partitions satisfy the weak converse of MB5. Formally we can express this constraint on mereological structure (CM) as follows:

A partition satisfying CM is mereologically monotonic. This means that it recognizes all the restricted parthood relations obtaining in the pertinent domain of objects. A very simple example is given by a flat list (a partition having only minimal cells together with a root) projected one-for-one upon a collection of disjoint objects.

So far we have allowed partitions to contain empty cells, i.e., cells that do not project onto any object. We now consider partitions which satisfy the constraint that every cell recognizes some object:

We say that partitions that satisfy CC project completely. Notice that this condition is independent of the functional or relational character of projection and location. Of particular interest, however, are partitions that project completely and in such a way that projection is a total function (partitions which satisfy both MB3 and CC). An example is a map of the United States representing its constituent states. There are no no-man's lands within the territory projected by such a map and every cell projects uniquely onto just one state.

So far we have accepted that there may be objects in our target domain that are not located at any cell. This feature of partitions is sometimes not acceptable: governments want all their subjects to be located in some cell of their partition of taxable individuals. They want their partitions to satisfy a completeness constraint to the effect that every object in the domain is indeed recognized. In this case we say that location is complete. Alternatively we say that the partition exhausts its domain. Unfortunately, we cannot use

to capture the desired constraint. The tax authorities do not (as of this writing) want to tax the separate molecules of their subjects. Trivially, we have:

but this is much too weak, since it asserts only that every object within a given domain that is recognized by a partition is indeed recognized by that partition. It will in fact be necessary to formulate several restricted forms of exhaustiveness, each one of which will approximate in different ways to the (unrealizable) condition expressed in (*).

One such exhaustiveness condition might utilize a sortal predicate (schema) $\backslash varphi$ that singles out the kinds of objects our partition is supposed to recognize (for example, in the case of the partition of taxable individual human beings, rather than proper parts of human beings). We now demand that the partition $A$ recognize all of those objects in its domain which satisfy $\backslash varphi$:

Let $\backslash Delta$ be some domain and let $A$ be a partition such that $\backslash Delta\; =\; D(A)$. Since we can very simply use any predicate to define a partition over any domain – by setting

– we can also think of $CE\_\backslash varphi$ as asserting the completeness of one partition relative to another. Note that the idea underlying $CE\_\backslash varphi$ is closely related to the idea of granularity. Thus for some purposes we might find it useful to formulate condition $\backslash varphi$ as a restriction on object size.

The tax office probably does not care too much about empty cells in its partition, nor is it bothered too much by the idea of charging you twice. The main issue is to catch everything above a certain resolution at least once. This is the intuition behind constraints like $CE\_\backslash varphi$. If you are a law-abiding citizen, you will accept $CE\_\backslash varphi$ (where '$\backslash varphi$' stands for 'is a citizen'), but you will insist that the partition not locate you in two separate cells, i.e., that you are not charged twice. This means that you want the tax partition to satisfy $CE\_\backslash varphi$ and MB4. There might be a pedantic clerk in the tax office who does not rest until he has made sure that all empty cells have been removed. Partitions that will satisfy you, the government, and the clerk in the tax office must satisfy CC, $CE\_\backslash varphi$, and MB1–5. Projection and location are then total functions (relative to a selected predicate $\backslash phi$) and one is the inverse of the other. Under those circumstances projection and location are bijective functions. Notice that neither of the following holds:

Counterexamples are given in Figure 6 (a) and (b), respectively, where each depicted object is assumed to satisfy $\backslash phi$.

The following is the partition-theoretic equivalent of the unrestricted set-theoretic comprehension axiom. For each predicate $\backslash phi$ there is a partition $A(\backslash phi)$ whose location relation is defined as follows:

Under what conditions on $\backslash phi$ can this be allowed?

One type of restriction that is relevant to our purposes would allow $\backslash phi$ to be unrestricted but affirm additional restrictions on objects, for example in terms of spatial location. Thus we might define a family of spatial partitions $A(\backslash phi,\; r)$, where $r$ is some pre-designated spatial region, in such a way that

Something like this is in fact at work in the taxation partition (the tax office is interested in human beings bearing a special relation to a specific geographic location), as also in the partitions used by epidemiologists, ornithologists and others who are interested in (types of) objects at specific sites.

Partitions are natural cognitive devices, for example they are lists, maps, and so forth, used by human beings to serve various practical purposes. This means that partitions will normally be called upon to avoid certain sorts of redundancy. Here we distinguish what we shall call correspondence redundancy and structural redundancy. Necessarily empty cells (cells whose labels tell us ex ante that no objects can be located within them) represent one type of correspondence redundancy, which is excluded by condition CC.

Another type of correspondence redundancy we have addressed already in our discussion of the functionality of location. This occurs in a partition with two distinct cells whose labels would tell us, again ex ante, that they must necessarily project upon the very same object. Clearly, and most simply, a partition should not contain two distinct cells with identical labels.

The following case is not quite so trivial. Consider a partition with a cell labeled vertebrates which occurs as a subcell of the cell labeled chordates in our standard biological classification of the animal kingdom. Almost all chordates are in fact vertebrates. Suppose (for the sake of argument) that biologists were to discover that all chordates must be vertebrates. Then such a discovery would imply that, in order to avoid structural redundancy, they would need to collapse into one cell the two cells (of chordates and vertebrates) which at present occupy distinct levels within their zoological partitions.

A constraint designed to rule out such structural redundancy would be:

CR: A cell in a partition never has exactly one immediate descendant.

This rules out partition-theoretic analogues of the set theorist's $\backslash \{\backslash \{a\backslash \}\backslash \}$.

Consider a partition consisting of three cells, labeled people, Laura and George W. Or consider a partition with three cells labeled: mammals, cats and dogs. Both of these partitions are transparent, by our definition (DTr); but both are, again, such as to fall short of a certain sort of ideal completeness, which we can express by asserting that the mereological sum of the cells Laura and George W. (or of the cells cats and dogs) falls far short of the corresponding partition-theoretic sum.

If a collection of subsets of some given set forms a partition of this set in the standard mathematical sense, then these subsets are (1) mutually exhaustive and (2) pairwise disjoint. An analogue of condition (2) holds for minimal cells in our present framework, since minimal cells are always mereologically disjoint (they cannot, by definition, have subcells in common). Condition (1) however does not necessarily hold within the framework of partition theory. This is because, even where the partition-theoretic sum of minimal cells is identical to the root cell, the minimal cells still do not necessarily exhaust the partition as a whole. The mereological sum (+) of cells is, we will recall, in general smaller than their partition-theoretic sum ($\backslash cup$).

We call a cell full relative to its descendant cells within a given partition if these descendants are such that their mereological sum and their partition-theoretic sum coincide. Formally we define:

where $(+\_\{z\; \backslash subset\; z\_1\}\; z)$ and $(\backslash cup\_\{z\; \backslash subset\; z\_1\}\; z)$ symbolize respectively the operations of applying mereological and partition-theoretic sum for all proper subcells $z$ of the cell $z\_1$. Since we can easily prove that $(\backslash cup\_\{z\; \backslash subset\; z\_1\}\; z)\; =\; z\_1$, DFullcell could be reformulated as asserting that a cell is full if and only if it is identical to the mereological sum of its descendants:

DFullcell does not suffice to capture the intended notion of fullness for partitions however. To see the problem, consider the partition consisting of

top row: one maximal cell, labeled first couple
middle row: two intermediate cells, labeled George W. and Laura
bottom row: four minimal cells, labeled George W.'s left arm, George W.'s right leg,
Laura's left arm, Laura's right leg.

The cell in the top row satisfies DFullcell, i.e. it is full relative to the second row; but it is not full relative to all of its descendants, since the mereological sum of the cells George W.'s arm and George W.'s leg is not identical to the cell George W. (and analogously for Laura). The problem arises because if $x\; \backslash leq\; y$ then $x\; +\; y\; =\; y$ and if $x\; \backslash subseteq\; y$ then $x\; \backslash cup\; y\; =\; y$. From this it follows that only the immediate descendants of a given cell $z\_1$ contribute to its mereological and partition-theoretic sums.

This, however, tells us what we need to take into account in defining what it is for a cell to be full relative to all its descendant cells within a given partition $A$, namely that each of its constituent cells must be full relative to its immediate descendants. This yields:

Here minimal cells have been handled separately because they do not have subcells. One can see that, while Fullcell(first couple) holds in the mentioned partition, Fullcell*(first couple) does not, because the cells George W. and Laura are neither full nor minimal.

We can now define what it means for a partition to be full, as follows:

A partition is full if and only if all its non-minimal cells are full (or, equivalently, all its non-minimal cells are full*). Notice that full partitions might in principle contain empty cells, which may or may not have subcells. (Consider, for example, the cell dodo with subcells male dodo and female dodo.)

When a cell falls short of fullness, this means that, while the cell successfully projects onto some given domain, its subcells do not succeed in projecting onto the entirety of this domain. It is then as if there is some extra but invisible component in the cell, in addition to its subcells. We shall call this additional component ‘empty space’ (noting that the term ‘empty’ here has a quite different meaning from what it has in the phrase ‘empty cell’). Consider the partition depicted in Figure 2.

Here the empty space is that part of the cell mammals that is not occupied by cats and dogs. Notice that this empty space is a component of the cell mammals but it is not itself a cell nor is it made up of cells. Empty space is that part of a cell that is not covered by its subcells. The notion of empty space is then similar to the notion of hole in the sense of Casati and Varzi (1994). A hole requires an object which serves as its host. A hole is in every case a hole in something. In the same sense empty space requires a cell within which it can exist as empty space. As a hole is a concavity of a host object where no parts of this host object are to be found, so empty space is a zone within a cell where no subcells are to be found.

Empty space within a cell is like a hole also in the sense that there must be something that potentially fills it. In our case this means: more subcells. If all the empty space in a cell is filled, then the cell itself is full and the empty space has been eliminated. Empty space is inert in the sense that it does not project onto anything. Empty space is normally hidden to the user of the partition in which it exists, for otherwise this user would surely have constructed a fuller partition. In some cases however a user might deliberately accept empty space in order to have means to acknowledge the fact that something has been left out. Alternatively, the existence of empty space in a given partition might be brought to the attention of the user. We point in a certain direction and ask: What is there? The theory of empty space thereby serves as the starting-point for an ontology of questions (Schuhmann and Smith, 1987): empty space corresponds to a hole in our knowledge.

The presence or absence of empty space is a dimension of a granular partition that is skew to the dimension pertaining to the existence of empty cells. An empty cell is a cell that fails to project. Empty space is that which leaves room for the addition of new knowledge. It is a zone within a cell that is not (but given advances in knowledge, could be) occupied by further subcells. Notice, however, that there cannot be a partition that is full and yet consists entirely of empty cells. This is because by MB6 every partition projects onto some object.

Figure 2 (a) depicts a partition of the animal kingdom consisting of three cells, where $z\_3$ recognizes the animal kingdom as a whole, $z\_1$ recognizes dogs, and $z\_2$ recognizes cats. In terms of partition-theoretic union we have $z\_1\; \backslash cup\; z\_2\; =\; z\_3$, but clearly . New cells can be inserted into the partition if new species are discovered (e.g., the species indicated by $o\_3$).

Empty space from one point of view reflects the potential for adding new knowledge. From another point of view it can be seen as a matter of hidden knowledge. From this perspective it is as if we start from partitions which reflect the way God sees reality. Empty space then covers up what we humans do not yet know. The latter view was developed by Mislove et al. (1990) and resulted in the theory of partial sets. What we call empty space Mislove compares to packaging material. If we remove packaging material we potentially discover new things that were previously hidden from view. Our distinction between full and non-full partitions corresponds very closely to the distinction between ‘clear’ and ‘murky’ sets drawn in the theory of partial sets.

Since we have $Fullcell(z\_1)\; \backslash leftrightarrow\; (+\_\{z\; \backslash subset\; z\_1\}\; z)\; =\; z\_1$, we also have . Consequently we can define what it means for $x$ to be the empty space of the cell $z\_1$ as follows. We first of all define $x$ fills $z\_1$:

The empty space in $z\_1$ is then its smallest filler and we define that $x$ is the empty space in $z\_1$ if and only if $x$ fills the space not occupied by the subcells of $z\_1$ and $x$ is disjoint from all subcells of $z\_1$:

We note in passing that minimal cells, on the basis of the definitions above, are either empty (they do not project) or they are completely made up of empty space. (‘Minimal’ means: there is no further knowledge available, within a given partition, as concerns the objects onto which minimal cells are projected.)

$ES$ determines the empty space of a cell uniquely. To prove this, assume $ES(x,\; z)$ and $ES(y,\; z)$. For simplicity we use ‘$c$’ as an abbreviation for ‘$(+\_\{z\_1\; \backslash subset\; z\}\; z\_1)$’. We can then rewrite $ES(x,\; z)$ as: $x\; +\; c\; =\; z$ and $\backslash forall\; u\; :\; u\; +\; c\; =\; z\; \backslash rightarrow\; x\; \backslash leq\; u$, and rewrite $ES(y,\; z)$ as: $y\; +\; c\; =\; z$ and $\backslash forall\; v\; :\; v\; +\; c\; =\; z\; \backslash rightarrow\; y\; \backslash leq\; v$. Since $z\; =\; u\; +\; c\; =\; v\; +\; c\; =\; x\; +\; c\; =\; y\; +\; c$ we have for all $u,\; v$: if $v\; +\; c\; =\; u\; +\; c\; =\; x\; +\; c\; =\; y\; +\; c$ then $(x\; \backslash leq\; u\; \backslash text\{\; and\; \}\; y\; \backslash leq\; v)$. In particular this holds in the case of $\backslash forall\; u,\; v\; :\; u\; =\; v$. Now assume that $x\; \backslash neq\; y$. This means that for all $u$: if $u\; +\; c\; =\; x\; +\; c\; =\; y\; +\; c$ then or . Without loss of generality consider for all $u$: if $u\; +\; c\; =\; x\; +\; c\; =\; y\; +\; c$ then . Now without loss of generality consider for all $u$: if $u\; +\; c\; =\; x\; +\; c$ then . Since for all $u$: $u\; +\; c\; =\; x\; +\; c$ holds by assumption it in particular this holds for $u\; =\; x$. Consequently we have $\backslash exists\; u\; :\; u\; +\; c\; =\; x\; +\; c$ and $u\; =\; x$ and leading to a contradiction of the form $\backslash exists\; u,\; x\; :\; u\; =\; x$ and $u\; \backslash neq\; x$. Consequently we have $x\; =\; y$ as desired.

We can now define the notion of cumulativeness, which plays the same role in theory (B) which fullness plays in theory (A). The intuitive idea is as follows: a cell is cumulative relative to its immediate descendant cells if the mereological sum of the projections of these immediate descendants is identical to the projection of their partition-theoretic sum. For non-empty and non-minimal cells with at least two immediate descendants we define:

One can see that $p(\backslash cup\_\{z\; \backslash subset\; z\_1\}\; z)\; =\; p(z\_1)$ holds under the given conditions. Consequently:

Again, $Cu(z\_1)$ ensures that $z\_1$ is cumulative relative to its immediate descendants. In order to ensure cumulateness of a cell with respect to all its subcells, we define

A partition is cumulative if and only if all its cells are cumulative.

Another way of expressing this is as follows: a partition is cumulative if and only if it has a basis in objects (the objects projected by its minimal cells), and is then built up in stages in such a way that each non-minimal cell $z$ projects onto the mereological sum of the objects projected by $z$'s immediate descendants.

Recall that the notions of fullness and cumulateness are intended to characterize partitions that have no redundancies of the sort defined in CR. A cumulative partition $A$ is also exhaustive ($\backslash text\{CE\}\_\backslash varphi$) with $\backslash varphi\; =\; \backslash exists\; z\; :\; Z(z,\; A)$ and $P(z,\; o)$.

We can now distinguish four classes of partitions regarding their fullness and cumulateness:

Full and cumulative. Consider a list of the 50 US States, divided into two sub-lists: the contiguous 48, the non-contiguous 2. Here the objects towards which this partition is directed are the States themselves under the obvious 'Utah'–Utah projection relation.

Full and non-cumulative. Consider Figure 7 (a). This partition represents the belief of some child who thinks that cats and dogs are the only animals there are.

Non-full and cumulative. Consider Figure 7 (b). This partition represents the way a child sees the world who does not understand the concepts of the Northern and Southern hemisphere and who thinks that there are places on Earth that are neither in the Northern, nor in the Southern Hemisphere, nor overlapping both, but are rather in some secret and wonderful land that has not yet been discovered.

Non-full and non-cumulative. Consider Figure 7 (c). Imagine that you have a terrible hangover, and your accounting of the people at the party last night consists of a root with three subcells: you, John, and Mary. You know that you are missing somebody, but you cannot remember who.

We humans are often aware of the fact that our partitions are not full or not cumulative, or both. In the former case empty cells are often included into the cell structure in order to make explicit our awareness of these shortcomings. Consider, for example, the periodic table of the elements, which contains empty cells (labeled ununnilium, etc.), for elements not yet synthesized. Moreover the fact that the periodic table in its current form has a structure that can only accommodate a certain number of cells is not taken to imply that in reality there could not be elements whose discovery would require the table to be extended.