Logic of Division

Logical division is the operation that produces a hierarchy: a class, the genus, is split into subclasses, the species, on one characteristic, called the basis of division or, in the logic textbooks, the fundamentum divisionis. Jevons: “Logical division is the name of the process by which we distinguish the species of which a genus is composed. Thus we are said to divide the genus ‘book’ when we consider it as made up of the groups folio, quarto, octavo, duodecimo books, &c., and the size of the books is in this case the ground, basis, or principle of division”. A directory tree, a taxonomy and a class hierarchy are all products of repeated division, and the rules for doing it soundly were written down long before any of them existed. This page states the rules and then applies them to the two orders software/microsoft and microsoft/software, which turn out not to be mirror images: one is a hierarchy and the other is a grouping wearing a hierarchy’s clothes.

The rules#

Jevons gives three: “1. The constituent species must exclude each other. 2. The constituent species must be equal when added together to the genus. 3. The division must be founded upon one principle or basis.” Joseph’s 1916 Introduction to Logic adds that a division “must proceed at every stage, and so far as possible through all its stages, upon one principle”, and the ISKO Encyclopedia states the same four rules from Toohey (1918), the third of which is “Each process of division must have only one basis.” The rules are not decoration. Exclusivity is what makes a lookup deterministic — a thing has one place — and it follows from the single basis: Joseph, “The only security for their being mutually exclusive lies in their being formed upon one basis”.

Cross-division#

Breaking the third rule has a name. Joseph: “A division which proceeds on more than one fundamentum divisionis at once is called a cross-division; as if one were to divide soldier into artillery, cavalry, privates, and territorials. It is called a cross-division, because the grouping required by one basis cuts across that required by another; in distinguishing privates, for example, from other soldiers, we disregard the distinction of cavalry and artillery”. He rates the result: “A cross-division is worse than useless; for instead of assisting to an orderly arrangement of things in thought, it introduces confusion.” Jevons’s version is the book example: “It would be obviously absurd to divide books into folio, quarto, French, German and dictionaries, because these species overlap each other, and there may be French or German dictionaries which happen to be quarto or folio and belong to three different species at once.”

A directory whose siblings are microsoft/, spreadsheets/, adobe/ and operating-systems/ is exactly this. Excel belongs in two of them, so a reader has to guess which basis the filer applied at that level, and a checker has no way to tell a misfiling from a choice. The fix is not to pick the better facet; it is to pick one facet per level. Joseph also settles what happens at the next level. The basis may change between levels, but whatever basis is applied to one sibling must be applied to all: “if it is applied to one of these species it must equally be applied to the others.” A vendor-first tree therefore divides every vendor by kind, or none, and a kind-first tree divides every kind by vendor. Both trees have the same leaves — one per (vendor, kind) pair — and differ only in which facet is the internal node:

1
2
3
4
5
6

kind-first                         vendor-first
spreadsheets/                      microsoft/
  microsoft/  (Excel)                spreadsheets/       (Excel)
  google/     (Sheets)               operating-systems/  (Windows)
operating-systems/                 google/
  microsoft/  (Windows)              spreadsheets/       (Sheets)

Every product has one path in each tree, which is the exclusivity rule doing its job, and the reader who arrives with the other facet in mind is scattered, which is the cost described on the section page. What the diagram cannot show is that the two trees are not the same kind of object. That takes the next rule.

Genus and differentia#

A sound division does more than partition: each species is a kind of the genus, and the characteristic that distinguishes it — the differentia — is a form of some characteristic the genus already has. Aristotle’s example is feet: “we must not say, if we are to speak rightly, that of that which is endowed with feet one part has feathers and one is featherless (if we do this we do it through incapacity); we must divide it only into cloven-footed and not cloven; for these are differentiae in the foot; cloven-footedness is a form of footedness.” Porphyry, whose commentary fixed the vocabulary, defined the difference as “that by which species exceeds genus” and contrasted it with the accident, “that which is present and absent without the destruction of its subject” — a crow is black, but “we may possibly indeed conceive a white crow”.

Kwasnik states the modern consequence: “A true hierarchy has only one type of relationship between its super- and subclasses and this is the generic relationship, also known as species/differentia, or more colloquially as the is-a relationship.” A structure whose links are something else may still be a tree, but it is not a hierarchy in this sense, and Kwasnik keeps the word tree for exactly that case: “A tree divides and subdivides its classes based on specific rules for distinction just as in a hierarchy but does not assume the rules of inheritance.”

The thesaurus standards turn this into a test. ANSI/NISO Z39.19-2005 (from the National Information Standards Organization (NISO)) says of the generic relationship: “This type of relationship is often called ‘IsA.’ A simple way to apply the test for validity described above is to formulate the statement ‘[narrower term] is a [broader term].’” It then adds the all-and-some test — all cacti are succulent plants and some succulent plants are cacti, so cacti may sit under succulent plants; only some cacti are desert plants, so it may not sit under desert plants — and a constraint on what may be related at all: “both the broader and the narrower term should represent a thing, an action, a property, etc. For example: anatomy (a discipline) and central nervous system (a body part that can be an object of study of that discipline) represent different kinds of concepts; therefore, these terms cannot be related hierarchically”. The three admissible hierarchical relations are generic, instance and whole–part, which ISO 25964 codes as BTG, BTI and BTP.

Run the test on the two orders.

  • Microsoft software is a software. All Microsoft software is software; some software is Microsoft’s. Passes. The vendor is a differentia of the kind — Mills and Broughton’s “species-maker”, the same move as “Timber houses” — and the result is what Hedden calls a legitimate case for a second parent, since “Educational software is a kind of software … and Educational software is a kind of educational product”. Microsoft products would be a second genuine parent.
  • Microsoft software is a Microsoft. Fails. A company and a kind of product are “different kinds of concepts”. The relation between them is the one Z39.19 lists among the associative relations, not the hierarchical ones: its table has “Concept or Object / Origins” (beluga caviar RT Caspian Sea) and “Process / Agent” (hunting RT hunters), coded RT for related term.

The Library of Congress’s own record agrees. The subject heading Microsoft software has the broader term Computer software, not Microsoft Corporation. Wikipedia reaches the same place by another route: Category:Microsoft is the company’s eponymous category — “A category that covers exactly the same topic as an article” — and putting Category:Microsoft software under it makes the company a container for its products, which the guideline permits and the thesaurus standard would not. Brachman’s 1983 paper What IS-A Is and Isn’t is the classic statement that the single word hides many relations — it “cataloged” the common interpretations and proposed that “meanings might be a lot clearer if is-a were broken down into its semantic subcomponents” — and made by is one of the relations that gets smuggled in under it.

Rigidity#

There is a second test, from ontology engineering, that reaches the same verdict from a different direction. Guarino and Welty’s OntoClean method classifies properties by whether an instance can lose them. “A property is rigid if it is essential to all its possible instances; an instance of a rigid property cannot stop being an instance of that property in a different world.” Being human is rigid. “The property being a student is typically anti-rigid – every instance of student can cease to be such in a suitable state of affairs”. The constraint that follows is the one that matters here: “anti-rigid properties cannot subsume rigid properties. For example, the property being a student cannot subsume being a human if the former is anti-rigid and the latter is rigid. To see this, consider that, if p is an anti-rigid property, all its instances can cease to be such. This is certainly the case for student, since any student may cease being a student. However, no instance of human can cease to be a human, and if all humans are necessarily students (the meaning of subsumption), then no person could cease to be a student, creating therefore an inconsistency.”

Made by Microsoft is anti-rigid for a program. The evidence is in the category page: Category:Microsoft software contains Skype, LinkedIn software and Nuance software, each of which became Microsoft software by acquisition without becoming a different program. Spreadsheet is as rigid as a kind of software gets; a program that stopped being a spreadsheet would be a different program. By the OntoClean rule the vendor property cannot subsume the kind, so microsoft/spreadsheets is not a subsumption hierarchy, while spreadsheets/microsoft is. This application is ours, not Guarino and Welty’s, but it is a direct reading of their constraint.

What follows for a path#

Both orders satisfy the golden rule of classification — either is a consistent, predictable filing order — and the section page shows real systems living with each. Only one is a taxonomy. That matters when anything is inherited down the tree. What is true of all spreadsheets is true of Excel; what is true of Microsoft the company is not true of Excel. Kwasnik’s summary of why hierarchies are worth having is that they license inference: assess that “an animal is a kind of cat, which is a kind of mammal”, and “you can infer and predict” its properties. A vendor-first tree licenses no such inference, because its first link is not a kind-of link. It is a perfectly good index by origin, which is what a company’s directory of its products should be, and what a taxonomy of software should not.

Two practical rules fall out. Put the kind first when the tree is meant to be a taxonomy, and let the vendor in as a differentia at the level below. When the vendor genuinely has to be the first-cited facet — a per-vendor installation tree, a package namespace whose job is uniqueness — say so, and do not expect the tree to double as a classification. This wiki’s own placement rule, that the top level is for fields and not for named things, is the first of these applied to a site.

Sources#

  • Jevons, W. S., Elementary Lessons in Logic (Macmillan, 1870), Lesson XII, pp. 104–106 (full text)
  • Joseph, H. W. B., An Introduction to Logic, 2nd ed. (Clarendon Press, 1916), ch. V, pp. 117–121 (full text)
  • Frické, M., “Logical division”, ISKO Encyclopedia of Knowledge Organization, 2016 (the ISKO is the International Society for Knowledge Organization)
  • Aristotle, Metaphysics VII.12, trans. W. D. Ross (text); Porphyry, Isagoge, trans. O. F. Owen (text)
  • Kwasnik, B. H., “The Role of Classification in Knowledge Representation and Discovery”, Library Trends 48(1), 1999 (PDF)
  • ANSI/NISO Z39.19-2005 (R2010), Guidelines for the Construction, Format, and Management of Monolingual Controlled Vocabularies, §8.1 Table 1, §8.3, §8.4.2 (PDF)
  • ISO 25964 thesaurus ontology, broaderGeneric, broaderPartitive, broaderInstantial
  • Mills, J. and Broughton, V., Bliss Bibliographic Classification, 2nd ed., Introduction (1977), §5.734.6 (PDF)
  • Hedden, H., “Polyhierarchy in Taxonomies”, 2022
  • Brachman, R. J., “What IS-A Is and Isn’t: An Analysis of Taxonomic Links in Semantic Networks”, Computer 16(10), 1983, pp. 30–36 (IEEE; abstract)
  • Guarino, N. and Welty, C. A., “An Overview of OntoClean”, in Staab and Studer (eds), Handbook on Ontologies (Springer, 2004) (PDF)
  • Library of Congress authorities: Microsoft software; Wikipedia: Category:Microsoft software, Wikipedia:Categorization
Backward Citation Order Escapes From the Tree Forward