Classification

One of the main topics of scientific research is classification. Classification is the operation of distributing objects into classes or groups—which are, in general, less numerous than them. It has a long history that has developed during four periods: (1) Antiquity, where its lineaments may be found in the writings of Plato and Aristotle; (2) The Classical Age, with natural scientists from Linnaeus to Lavoisier; (3) The 19th century, with the growth of chemistry and information science; and (4) the 20th century, with the arrival of mathematical models and computer science. Since that time, and from an extensional viewpoint, mathematics, specifically, the theory of orders and the theory of graphs or hypergraphs, has facilitated the precise study of strong and weak forms of order in the world, and the computation of all the possible partitions, chains of partitions, covers, hypergraphs or systems of classes that we can construct on a domain. With the development of computer science, Artificial Intelligence, and new kinds of languages such as oriented-objected languages, an intensional approach has completed the previous one. Ancient discussions between Aristotle and Plato, Ramus and Pascal, Jevons and Joseph found some kind of revival via object-oriented modeling and programming, most of objected oriented languages being concerned with hierarchies, or partial orders: these structures reflect in fact the relations between classes in those languages, which generally admit single or multiple inheritance. In spite of these advances, most of classifications are still based on the evaluation of resemblances between objects that constitute the empirical data. This one is almost always computed by the means of some notion of distance and of some algorithms of aggregation of classes. So all these classifications remain, for technical and epistemological reasons that are detailed below, very unstable ones. A real algebra of classifications, which could explain their properties and the relations existing between them, is lacking. Though the aim of a general theory of classifications is surely a wishful thought, some recent conjecture gives the hope that the existence of a metaclassification (or classification of all classification schemes) is possible.

Table of Contents

1. General Introduction: Classification Problems
2. A Brief History of Classifications
   1. From Antiquity to the Renaissance
   2. From Classical Age to Victorian Taxonomy
   3. The Beginning of Modernity
3. The Problem of Information Storage and Retrieval
4. Ranganathan and the PMEST Scheme
5. Order and Mathematical Models
   1. Extensional Structures
   2. A Glance at an Intensional Approach
6. The Idea of a General Theory of Classifications
7. References and Further Readings

1. General Introduction: Classification Problems

Classification problems are one of the basic topics of scientific research. For example, mathematics, physics, natural sciences, social sciences and, of course, library and information sciences all make use of taxonomies.  Classification is a very useful tool for ordering and organization. It has increased knowledge and helped to facilitate information retrieval.

Roughly speaking, ‘classification’ is the operation consisting of sharing, distributing or allocating objects in classes or groups which are, in general, less numerous than them. Commonly, classifications are defined on finite sets. However, if the objects are, for example, mathematical structures there can be infinite classifications. In this case, the previous requirement, of course, must be weakened: we may only want the (infinite) cardinal of the classification to be less than or equal to the (infinite) cardinal of the set of objects to be classified.  What we call ‘classification’ is also the result of this operation. We want, as much as it is possible, for this result be constant, namely, that the classification itself remains stable for a little transformation of data (of course, the sense of this requirement will have to become clearer). Various situations may happen: the classes may intersect or not, be finite or infinite, formal or fuzzy, hierarchically ordered or not, and so on.

The basic operation of grouping elements into classes, which simplifies the world, is a very powerful operation, but it also raises many questions. In particular, a number of philosophers, from Socrates to Diderot and even post-modern philosophers, criticized such an operation (see, for instance, Foucault 1967). Indeed, this operation has multiple profits.  First is the substitution of a rational and regular order in the chaotic and muddled multiplicities. Second is the reduction of the size of sets, so that, once we have constituted classes of equivalences, we can work with these classes and no more with the elements. Third, and finally, to make a partition of a set means locating in it a symmetry that  decreases the complexity of the problem and so simplifies the world. We can say with Dagognet (1984, 1990) than “less is more”: to compress the data really brings an intellectual gain.

Having outlined the main reasons for classifications, let us see how these classifications have developed and which forms they got throughout the course of time.

2. A Brief History of Classifications

The history of classifications (Dahlberg 1976) develops in four periods. From Plato and Aristotle to the 18th century, ancient classifications are hierarchical ones, they are finite and generally based on one single criterion. During the 18th century, some new classifications appear, which are multicriteria  – a domain can be co-divided in many ways, as Kant said in his Logic (see Kant 1988) – and indefinite or virtually infinite (Kant believed that we could endlessly subdivide the extension of a concept).  At the end of the 18th and at the beginning of the 19th century, with the chemical classifications of Lavoisier and then of Mendeleyev, one discovers combinatorial classifications or multiple crossed orders, like the chemical table of Elements, which correspond to a new concept of classification. In the 20th century, through the progress of mathematical order theory, factorial analysis of correspondence, and automatic classification, formal models begin to develop.

a. From Antiquity to the Renaissance

French commentator of Greek philosophers, R. Joly said that a typical trend of the Greek spirit was to reduce a multiple and complex reality into some categories which satisfy the reason, both by their restricted number and by the clear and precise sense that becomes attached to each of them. Indeed, Plato and Aristotle are among the great classifiers of these ancient times.

In all of Plato’s Dialogues, and especially in the latest ones (Parmenides, Sophist, Politicus, Philaebus), Plato obviously classified a lot of things (ways of life, political constitutions, pleasures, arts, jobs, kinds of knowledge, and so forth). Generally, for Plato, things were classified in relation with the distance that separates them from their archetypal forms, which yields some order (or pre-order) on them. Plato’s classifications are finite, hierarchical, dichotomous, and based on a single criterion. For example, in Gorgias (465c), a set of all practices is divided into two classes, the practices concerning the body and the practices concerning the soul, each of them being then divided into two others: gymnastics and medicine, on one hand, and legislation and justice, on the other hand. In the same way, in Republic (510a), the whole universe, viewed as the set of all real things, is divided into the visible world and the invisible world, each class being subdivided into images and objects or living beings on one hand, mathematical objects and ideas, on the other hand.

According to Plato, the rules of classifications are very simple. First, we have to make symmetric divisions in order to get well-balanced classes. For example, if we classify the peoples, we have to avoid setting the Greek in front of the other peoples, because one of the classes will be plethoric while the other one will have only one element (Politicus, 262a). Second, As a good cook who cuts an animal─this metaphor is in the Phaedrus−it is also necessary to choose the good joints or articulations. For example, in the field of numbers, it would be senseless to set 1000 in front of 999 other numbers. In contrast, the opposition even/odd or prime/not prime, is a real one. Thirds, in general, we must also avoid using negative determinations. For example, we have to avoid determinations like not-A because it is impossible that the non-being has sorts or species, these determinations block the development of thought.

Plato did not observe these wise rules, so incurring Aristotle’s criticisms. Against Plato’s theory, Aristotle argues that the method of division is not a powerful tool because it is non-conclusive. It does not make syllogisms (First Analytics, I, 31). In another text (Second Analytics, II,5), Aristotle insists on the contingency of the passage from a predicate to another one, that is, in the Platonic division, for every new attribute, we can wonder why it is such an attribute  oppose to another one. The differences introduced by dichotomies can be also purely negative and thus do not necessarily define a real being. Moreover, binary divisions presuppose that the number of the primitive species is a power of 2. In a division, a predicate can belong to different primitive species, for example “bipedalism” can apply to both birds and humans. But, according to Aristotle, the application of this term is not the same in both cases. Finally, the Platonic division confuses extensional and intensional views. It can identify the triangle, which is a kind, and one of its properties, for example, the equality of the sum of its angles in two right angles.

The previous questions get no answer in Plato’s theory. Aristotle rejected Plato’s method of division. But, Aristotle also rejected the Platonic doctrine of forms. According to Aristotle (Metaphysics, I, 9), Plato’s forms fail to explain how there could be permanence and order in the world. Far more, he argued, Plato’s theory of forms cannot explain anything at all in our material world. The properties that the forms have (according to Plato the forms are eternal, unchanging, transcendent, and so forth) are not compatible with material objects and the metaphor of participation or imitation breaks down in a number of cases. For instance, it is unclear what it mean for a white object to participate in, or to copy, the form of whiteness−that is, it is hard to understand the relationship between the form of whiteness and white objects themselves.

For all these reasons, Aristotle develops his own concepts, and his own logic of classifications. In the Topics (I, chap. 1), Aristotle introduces the notions of kind, species, property and a whole theory of basic predication that has subsequently developed in the work of Porphyry and Boece, respectively. This theory is based on the opposition between essence, all of the characters that define a thing, and accident, the qualities whose presence or absence does not modify the things essence. A commentator of the Aristotelian system, Porphyry (234-305), puts these distinctions to good use and tries to specify the hierarchy of the kinds and the species as defined by Aristotle. The famous Porphyrian Tree is the first abstract tree outlining these distinctions and illustrates the subordination existing between them (See Figure 1).

Figure 1: The Porphyrius Tree

In a passage of his Commentary on Aristotle’s Categories (2014) Porphyry asked good questions at the origin of a hotly-debated controversy over whether or not universals were physical or immaterial substances. That is, a contention over whether universals are separated from sensible things or if they are involved in them, finding their consistency therein. In opposition to the traditional views (Platonic and Aristotelian or scholastic realisms), other solutions appeared. For example, Nominalism (Roscelin, 11th c.) claimed that universals are but words and that nothing corresponds to them in the Nature, which knows only the singular. Against that was Conceptualism (Abélard, 12th cn. and Ockham, 14th cn.), the view that kinds exist as predicates of subjects that, themselves, are real. In the last centuries of Middle Ages and in the Renaissance, we find also great scholars who work on classification. In particular, Francis Bacon (1561-1626), whose work on the classification of knowledge that has inspired the great librarians of the 19th century. But, the logic of classifications, which remains, in this time, the Aristotelian logic, receives practically no new development until the 18th century.

b. From Classical Age to Victorian Taxonomy

In the Classical Age, taxonomy as a fully-fledged discipline began to develop for several reasons. One important reason emerges from the birth of natural science and the need to organize floras and faunas in connection with the growth of the human population on Earth, in the context of the beginning of agronomy (Dagognet, 1970). In this period, naturalists like Tournefort (1656-1708), Linnaeus (1707-1778), De Jussieu (1748-1836), Desfontaines (1750-1833) and Cuvier (1769-1832) tried to classify plants and animals all around the world.

When classifying things or beings, you must get a criterion or an index, in order to make classes and separate varieties inside the classes. Indeed, all those naturalists differ on the criteria of their classifications. For example, concerning the classification of plants, Tournefort chose corolla, while Linnaeus chose the sexual organs of the plant. Concerning the animals, the classification of Cuvier violates Aristotle’s recommendations, by compositing vertebrates and invertebrates which, by chance, are something real. At the end of the century, Kant summarizes, in his Logic (1800), the main part of the knowledge about classifications in this period, by specifying the definitions of a certain number of terms and operations that the naturalists of the time empirically use. Kant was only interested in the forms of the classifications. In his Logic he defines a logical division of a concept as “the division of all the possible contained in it”. The rules of this division are the following: 1) members of the division are mutually exclusive, 2) their union restores the sphere of the divided concept, 3) each member of the division can be itself divided (the division of such divided members is a subdivision).  (1) and (2) seem to indicate that Kant was approaching our concept of a partition. But (3) shows that he does not have the concept of a chain of partitions, since he does not see that a subdivision of the same level forms one and the same partition.

These problems were also discussed, during the 19th century in Anglo-Saxon countries, even after Darwin’s theory of evolution. One may think that Darwin’s belief in branching evolution was based upon his familiarity with the taxonomy of his day, from which he was very aware. There were great taxonomists in England in the Victorian age and some of them−for instance, the paleontologist H. Alleyne Nicholson, a specialist of British Stromatoporoids−were prodigious and wrote monographs still in force today (Woodward 1903). At approximately the same time, H. Agassiz (Agassiz 1957), a scholar in classification theory, wrote about taxonomic concepts like categories, divisions, forms, homologies, analogies, and so on. Among different taxonomic systems mentioned in his Essay on Classification, include the classical systems of Leeuckart, Vogt, Linnaeus, Cuvier, Lamarck, de Blainville, Burmeister, Owen, Ehrenberg, Milne-Edwards, von Siebold, Stannius, Oken, Fitzinger, MacLeay, von Baer, van Bencden, and van der Hoeven. In The Origin of Species, Darwin himself said that it was a

truly wonderful fact…that all animals and all plants throughout all time and space should be related to each other in group subordinate to group, in the manner which we everywhere behold−namely, varieties of the same species most closely related together, species of the same genus less closely and unequally related together, forming sections and sub-genera, species of distinct genera much less closely related, and genera related in different degrees, forming sub-families, families, orders, subclasses, and classes. (1859, 128)

But what he called the “principle of divergence”–namely, the fact that during the modification of the descendants of any one species and during the incessant struggle of all species to increase in numbers, the more diversified these descendants become, the better will be their chance of succeeding in the battle of life−was illustrated by his famous tree-like diagram sketched in 1837 in the notebook in which he first posited evolution. From this time, tree-like structures, that has been also of great use in chemistry and would be formalized at the end of the century by the mathematician Arthur Cayley, tended to replace classifications.

c. The Beginning of Modernity

A new kind of classifications appeared at the end of the 18th century, with the development of Chemistry, namely, combinatorial classifications or cross multiple orders. This kind of classifications is either the crossing of two or more divisions, or the crossing of two or more hierarchies of divisions. In such a structure, as Granger (1967) said,  “elements are distributed according to two or several dimensions, giving rise to a multiplication table”. In a combinatorial classification, the elements themselves are not necessarily distributed into classes. Only the components of these elements are classified. For Granger, this model refers to the Cartesian plane and to the ordinal principle on which it is based. The Cartesian plane, results from a will of ordering a certain distribution of points in the space, by ordering points in every row and then by ordering the rows themselves. The virtue of multiple orders is to place what is classified in the intersection of a line and a column. So, as Dagognet (1969) has shown, when an element is absent or there is an empty compartment, it can be defined by its surroundings. This is what happened in the Mendeleyev table. This table has two main advantages. First, the table is creative, so the mass of a chemical element can be calculated from those which surround it (see Figure 2), and hence, chemical elements, which did not exist in Nature but were synthesized only 30 years later in laboratories, have already been accounted for by Mendeleyev. Second, the classification is not a purely spatial picture of the world. The temporality, in particular the future, is already present in it.

Figure 2: The mass of an unknown element in the Mendeleyev Table

3. The Problem of Information Storage and Retrieval

At the end of the 19th century, the development of scientific research, which raised the question of information storage and retrieval, encouraged the constitution of voluminous librarian catalogues. This included the Dewey’s decimal classification, Otlet and La Fontaine’s universal decimal classification, and the Library of Congress classification. The aim of these kinds of classifications was to account for the whole of knowledge in the world. But, many problems arose from this attempt of library sciences to organize the whole knowledge. Three rules were commonly respected in more natural classifications: 1) Everything classified must appear in the catalogue (which must be, in principle, finite and complete), 2) there is no empty class, 3) nothing can belong to more than one class. Generally, these rules are not respected in library classifications. To face the extraordinary challenge of cataloguing knowledge growing indefinitely throughout the course of time, the big library classifications designed at the end of the 19th century adopted the principle of decimalization. This system was used because decimal numbers, used as numeral items, authorize indefinite extensions of classifications. Suppose you start with 10 main classes, from 0 to 9. If you add a zero to each number, you get the possibility of forming 100 classes (from 00 to 99) and if you go on, you can obtain 1000 classes (from 000 to 999). Then you can also put a comma or a point, and define items like: 150.234. After the point, the sequence of numbers is potentially infinite and you can go as far as is needed. Another difference is that library classifications can sometimes allow for vacant classes in their hierarchy, and also can, assume the inscription of classified subjects in several places. Vacant classes are used because a librarian must manage some place for new documents that are still temporarily unclassified. Multiple inscriptions are also used because readers, who sometimes do not know exactly what they are looking for, need to have a broad ranging accesses to knowledge. This made made way for the existence of entries like author, subject, time, place, and so forth. The previous requirement of decimalization is obvious in the Dewey Decimal Classification (DDC) proposed by Melvil Dewey in 1876 (Béthery 1982). This classification is made up of ten main classes or categories, each of them being divided into ten secondary classes or subcategories. These last ones contain in turn ten subdivisions. The partition of the ten main classes thus gives successively 100 divisions and 1000 sections.

DDC — main sections

• 000 – Computer Science, Information and General Works
• 100 – Philosophy and Psychology
• 200 – Religion
• 300 – Social Sciences
• 400 – Language
• 500 – Science (including Mathematics)
• 600 – Technology and Applied Science
• 700 – Arts and Recreation
• 800 – Literature
• 900 – History, Geography and Biography

In the same way, the Universal Decimal Classification (UDC) of Otlet and La Fontaine globally presents the same hierarchical organization, except in the fourth nodal class, which is left empty (thus, applying the previous principle of vacant classes).

As librarians have rapidly observed, one undesirable consequence of such decimal schemes is the increasing fragmentation of subjects as taxonomist’s work proceed. For example, the Dewey Classification, though having this useful advantage of being infinitely extendible, turns out rapidly to be a list or a nomenclature. This is also the case of the UDC of Otlet and La Fontaine, and of all the classifications of the same type. A first attempt to make up for such a disadvantage has consisted of allowing some junctions between categories in the classification. A second one is the possibility of using some tables (7 in the DDC) to aid in the search of a complex object, which may be located in different sites. For instance, a book of poetry, written by various poets from around the world, would appear in several classes, indexed thanks to the tables. In general, DDC used to combine elements from different parts of the structure, in order to construct a number representing the subject content. This one often combines 2 or more subject elements with linking numbers and geographical and temporal elements. The method consists of forming a new item rather than drawing upon a list containing each class and its meaning. For example, 330 (for Economics) + 9 (for Geographic Treatment) + 04 (for Europe) and the use of ‘/’ gives 330/94 (European Economy). Another example is the following: 973 (for United States) + 05 (division for periodicals) and the use of the point ‘.’ gives 973.05 (periodicals concerning the United States generally).

Other specific features occur in library classifications, which tend to make them very different from classical scientific taxonomies. One spectacular difference with hierarchical classifications in Zoology or Botany is, as we have already seen, that it is possible for subjects to appear in more than one class. For example, in DDC, a book on Mathematics could appear in the 372.7 section or in the 510 section, depending on if the book is a monograph instruction for teachers on how to teach mathematics, or a mathematics textbook for children. Another difference is a relative flexibility of library classifications.

Though there exist improvements, UDC and DDC, like most of the classifications constructed at the same time (see Bliss 1929) are based on a perception of knowledge and of the relationships between academic disciplines extant from 1890 to 1910. Moreover, though updated regularly, UDC and DDC, as decimal systems, are less hospitable to the addition of new subjects. These kinds of classification are based on fixed and historically dated categories. One may observe, for example, that none of the main concepts of our present library science (digital library, knowledge organization, automatic indexing, information retrieval, and so forth) were included in the index of the 2005 UDC edition, and that technical taxonomies generally require more complex features (Dobrowolski 1964).

4. Ranganathan and the PMEST Scheme

There have been many pursuits to solve the aforementioned librarian problems. Some of them are well known since the middle of the 20th century. In the course of the 20th century, new modes of indexing and original classification schedules appeared in library science with the Indian librarian Shiyali Ramamrita Ranganathan (1933, 2006) and his faceted classification – also called “Colon classification” (CC), because of its use of the colon to indicate relations between subjects in the former edition.

Ranganathan was at first a mathematician and knew little about the library. But he took charge of the Madras University Library, and was then deputed by his University to study Library Science in London. There, he attended the School of Librarianship in the University College and discovered, as he said later, the “charm of classifications”, and also its problems. He saw very quickly that Decimal Classifications did not give satisfaction to users. On the opposite, he had the vision of a meccano set, where, instead of having ready-made rigid toys, one can construct them with a few fundamental components. This made him think of a new kind of classification.

It appeared to Ranganathan that the new theory might be organized at the higher level in 5 fundamental categories (FC) called facets: Personality, Matter, Energy, Space and Time−in summary PMEST. In each isolate facet  a Compound Subject is deemed to be a manifestation of one (and only one) of one or other of the five fundamental categories. There is also subfacets, so that the facet scheme PMEST and the subfacets we may form from it, are then used to sort subclasses in the main classes of the classification.

The difference with previous classifications is in the way one defines ‘subfacets’. Rather than simply dividing the main classes into a series of subordinate classes, one subdivides each main class by particular characteristics into facets. Facets, labeled by Arabic numbers, are then combined to make subordinate classes as needed. For example, Literature may be divided by the characteristic of language into the facet of Language, including English, German, and French. It may also be divided by form, which yields the facet of Form, including poetry, drama and fiction. So CC contains both basic subjects and their facets, which contain isolates. A basic subject stands alone, for example: Literature in the subject English Literature, while an isolate, in contrast, is a term that modifies a basic subject, for example, the term ‘English’. Every isolate in every facet must be a manifestation of one of the five fundamental categories in the PMEST scheme.

The advantages of the CC are numerous. The first one is a greater flexibility in determining new subjects and subject numbers. A second is the concept of phases, which allows taxonomists to readily combine most of the main classes in a subject.  Consider for example a subject like Mathematics for biologist. In this case, single class number enumerative systems, as those predominating in US libraries, tend to force classifiers to choose either Mathematics or Biology as the main subject. However, CC supplies a specific notation to indicate this be-phased condition.

Indeed, some problems remain unsolved. In CC, facets, that is, small components of larger entities or units are similar to flat faces of a diamond which reflect the underlying symmetry of the crystal structure, so that the general structure of Ranganathan Classification, as that of a faceted classification in general, is a kind of permutohedron. In principle, all descriptions may be done, whatever the order of them. For example, if we have to classify a paper speaking about seasonal variations of the concentration of noradrenaline in the tissue of the rat, we must get the same access if we have the direct sequence: (1) Seasonal, variations, concentration, noradrenaline, tissue, rat, or the reversed one: (2) Rat, tissue, noradrenaline, concentration, variations, seasonal. In mathematical words, this means clearly that the underlying structure that makes this transformation possible must be a commutative group. But this is not always the case, and for some dihedral groups, this structure is even forbidden. Another potential worry is that the PMEST scheme, which certainly has some connections with Indian thought, is far from being universally accepted (see De Grolier 1962) and has not been very often implemented in libraries, even in India.

So, in spite of all the improvements they receive in the course of time, a lot of problems have been raised in front of library classifications. In particular, library classifications will be strongly questioned in the 20th century by the proliferating development of the knowledge. First, the ceaseless flux of new documents forbids a stiff topology for classifications. The problem, then, is to know how to construct evolutionary structures. Second, the successive orderings of the knowledge (groupings and revisions and not only ramifications) has called relational powerful and automated documentary languages. Classifications still remain necessary, because documentary languages cannot do everything. So the problem is still open. But, with the big development of mathematics in the last century, this general problem, which is the great problem of order, has to be investigated by the means of mathematical structures.

5. Order and Mathematical Models

First attempts to study orders in mathematics began to develop at the end of the 19th century with Peano, Dedekind and Cantor (especially with his theory of ordinals, which are linear ordered sets).  They go on with Peirce (1880) and Shröder (1890) and their works around the question of an algebra of logic. Then, in the first part of the 20th century, comes the notion of partial order with an article of MacNeille (1937) and the famous work of G. Birkhoff (1967) who introduced the notion of lattice, algebraically developed later in the great book of Rasiowa and Sikorski (1970). During the same period, mathematical models of hierarchical classifications, which have been investigated in the USA by Sokal and Sneath (1963, 1973) or, in England, by Jardine and Sibson (1971) were developed in France in the works of Barbut and Monjardet (1970), Lerman (1970, 1981), and Benzécri (1973). All these works supposed the big last century advances in mathematical order theory: especially the papers of Birkhoff (1935), Dubreil-Jacotin (1939), Ore (1942, 1943), Krasner (1953-1954) and Riordan (1958). The Belgian logician Leo Apostel (1963) and the Polish mathematicians Luszczewska-Romahnowa and Batog (1965a, 1965b) have also published important articles on the subject. The more and more important use of computers in the search of automatic classifications has also been, in those years, a reason for searchers to get interested in mathematical models.

As there are many forms of classifications in the world of knowledge (we can find them, as we have seen, in mathematics, natural sciences, library and information science, and so forth) there are also many possible mathematical models for classifications. We begin with the study of extensional structures.

a. Extensional Structures

In order to clarify the situation, we start with the weakest form of them and move to stronger forms. Mathematics allows us to begin with very few axioms, that usually define weak general structures, and afterwards, by adding new conditions, one can get other properties and stronger models. In our case, the weakest structure is just a hypergraph H = (X,P) in the sense of Berge (1970), with X a set of vertices and P a set of nonempty subsets called edges (See Figure 3).

Figure 3: A Hypergraph

In this case, the set of edges P does not necessarily cover the set X, and some nodes (vertex of degree zero), may have no link to some edge. Assume the following conditions:

(C0)    X ∈ P,

(C1)    For all x ∈ P, {x} ∈ P,

Accordingly, we have a system of classes (in the sense of Brucker-Barthélemy 2007).

Add now the following new conditions: for every P_i ∈ P:

(C2)      P_i ∩ P_j = Ø,

(C3)      ∪ P_i = X,

Then P is a partition of X and the P_i are the blocks of the partition P.

Let now P(X) be the set of partitions on a nonempty finite set X. We may define on P(X) a partial order relation ≤ (reflexive, antisymmetric and transitive) such that P(X), ≤) is a lattice in the sense of Birkhoff (1967), that is, a partial order where every pair of elements has the same least upper bound and the same greatest lower bound. Then, one can prove that all the chains (all the linearly ordered sequences of partitions) of this lattice are equivalent to hierarchical classifications. So, the set C(X) of all these chains is exactly the set of all hierarchical classifications on a set. This set C(X) has itself a mathematical structure: it is a semilattice for set intersection. This model allows us to get all the possible partitions of P(X) and all the possible chains of C(X) (See Figure 4).

Figure 4: The lattice of partitions of a 4-element set.

A first problem is that such partitions are very numerous. For |X| = 9, for example, there is already 21147 partitions. So, when we want to classify some domain of objects (plants, animals, books, and so forth), it is not very easy to examine what classification is the best one among, say, several thousands of them.

A second problem is that the world is not made of chains of partitions. If it were, of course, the game would be over. Everything could be inserted in some hierarchical classification. But, the real world has no reason to present itself as a hierarchical classification. In the real world, we have generally to deal with quite chaotic entities, complicated fuzzy classes and poor structured objects, all that form what we can call ‘rough data’. So when we want to get a clear order, we have to construct it,  such that it is extracted from the complicated data. For that, we have to compare objects, to know the degree to which they are similar, and to do so, we need of course a notion of ‘similarity’. In order to make empirical classifications we must evaluate the similarities or dissimilarities between elements to be classified. In the history of taxonomic science, Buffon (1749) and Adanson (1757) have tried to understand the meaning of this evaluation in the following way. First, they claim, we have to measure the distance between the objects by the means of some index, so that we can build classes. Afterwards, we have to measure the distance between classes themselves, so that we can group some classes into classes of classes, and so replace the initial set of objects with an ordered set of classes that is less numerous than them.

What old taxonomists were doing, only basis of observation, can now be carried out with the help of mathematics, using a modern notion of distance. Lerman (1970) and Benzécri (1973) showed that a hierarchical classification, that is, a chain of partitions, is nothing but a particular kind of distance or, a particular kind of dissimilarity (Van Cutsem 1994). It is an ultrametric distance, which gives tree representations (Barthélemy and Guénoche 1988) and also has the special property to correspond exactly with the chain, so that, when considering all the chains, the set of their corresponding distance matrices makes a semiring (R, +, ×) when we interpret the lattice operations min and max in an anusual but clever manner (+ for min, × for max) (Gondran 1976). Problems arise when the distance between the objects classified is not ultrametric. In such cases, we have to choose the closest ultrametric smaller than the given distance, and so, access to the best hierarchical classification we can get and which is the closest one to the data. However, this kind of approach leads, in general, to relatively unstable classifications.

Indeed, there are two kinds of instability for classifications. The first, Intrinsic instability,,is associated to the plurality of methods (distances, algorithms and so forth) that can be used to make the classifications of objects. The second is extrinsic instability, which is connected to the fact that our knowledge is changing with time, so the definitions of objects (or attributes of the objects) are evolving.

An answer to the question of intrinsic instability is a theorem of Lerman (1970) which says that if the number of attributes (or properties) possessed by the objects of a set X is constant, the associated quasi-order given by any natural metric is the same. But this result has two limits. First, when the sample variance of the number of attributes is a big one, of course, the stability is lost and second, if we classify the attributes, instead of classifying the objects, the reverse is not true.

For extrinsic instability the answers are more difficult to find. We may appeal to methods used in library decimal classifications (UDC, Dewey, and so forth), which make possible infinite ramified extensions, but these classifications, as we have seen, are apt to assume that higher levels are invariant and have also the disadvantage to be enumerative and to degenerate rapidly into simple lists. Also, pseudo-complemented structures (Hilman 1964) that admit some kinds of waiting boxes (or compartments) for indexing things that are not yet classified. We get as well structures whose transformations obey certain rules that have been fixed in advance. That is the case of Hopcroft 3-2 trees (Aho, Hopcroft, Ulmann 1983) for instance, or of structures close to these ones (Larson and Walden, 1979). In recent years, new models for making classifications came from conceptual formal analysis (Barwise and Seligman, 2003), computer science or views using non-classical logics in the domain of formal ontologies (Smith 1997, 2003). In computer science, for example, the concept of Abstract Data Type (ADT), related to the concept of Data Abstraction, important in object-oriented programming, may be viewed as a generalization of mathematical structures. An ADT is a mathematical model for data types, where a data type is defined by its behavior from the point of view of a user of the data. More formally, an ADT may be defined as a “class of objects whose logical behavior is defined by a set of values and a set of operations” (Dale-Walker 1996), which is strictly analogous to algebraic structures in mathematics. So, if we are not satisfied by a rough classification like the partition into collections, streams and iterators (support loops accessing data items) and relational data structures that capture relationships between data items, we must admit that ADT can also be regarded as a generalized approach of a number of algebraic structures, such as lattices, groups, and rings (Lidi 2004). Hence, classifications of ADT turn into classifications in algebraic specifications of ADT (Veglioni 1996). In this context, computer science adds nothing to mathematics and the problem is now that a classification of mathematical structures using, for instance, Category theory, as Pierce (1970) tried does not bring a sufficient answer because a category may exist while its objects are not necessarily constructible (Parrochia-Neuville 2013).

So, none of the previous approaches is very convincing for solving the basic problem, which always remains the same. We are lacking a general theory of classifications, which would only be able to study and, in the best case, solve some the main problems of classification.

b. A Glance at an Intensional Approach

Instead of making partitions by dividing a set of entities, so that the classes obtained in this way are extensional classes, as we saw in the previous section, we can instead proceed by associating a description to a set of entities. In this case, the classes are called intensional classes. Aristotle himself mixed the two points of view in his logic but Leibniz was the first to propose a purely intensional interpretation of classes. For a long time, that view was a minority and has never won unanimous support among the Ancient philosophers and logicians (as the numerous discussions between Aristotle and Plato, Ramus and Pascal, Jevons and Joseph demonstrate). However, the development of computer science brought this view back, since for declarative languages and particularly object-oriented languages, pure extensional classes or sets are rather uncommon. In this approach, the intension can be given either a priori, for example by a human actor from his knowledge of the domain, or a posteriori, when it is deduced from the analysis of a set of objects. In object-oriented modeling and programming, classes are traditionally defined a priori, with their extension mostly derived at running stage. This is usually done manually (intension being represented by logical predicates or tags), but techniques for a posteriori class discovery and organization also exist. In the context of programming languages, they deal with local class hierarchy modification by adding interclasses and use similarity-based clustering techniques or the Galois lattice approach (Wille 1996).

When there is an unrelated collection of sets, which is the case in artifact-based software classification, an issue is to compare and organize these sets simply by inclusion, or to apply conceptual clustering techniques. However, most of objected oriented languages are concerned with hierarchies, whose structure may be a tree, a lattice, or any partial order. The reason is that such structures reflect the variety of languages, some of them admitting multiple inheritance (C++, Eiffel), others only single inheritance (Smalltalk). Java has a special policy concerning this point: it admits two kinds of concepts, classes and interfaces, with single inheritance for classes and multiple inheritance for interfaces.

The viewpoint of Aristotle was the following: the division must be exhaustive, with parts mutually exclusive, and an indirect consequence of Aristotle’s principles is that only leaves of the hierarchy should have instances. Furthermore, the divisions must be based on a common concern whose modern name is the ‘discriminator’ in Unified Modeling Language (UML). But usual programming practices do not necessarily satisfy those principles. Multiple inheritance, for example, is contradictory with the assumption of mutually exclusive parts, and instances may in general be directly created from all (non-abstract) classes. Direct subclasses of a class can be derived according to different needs with different discriminators, but there is no evidence that this approach leads to relevant classifications. Objected oriented approaches, which transgress Aristotelian principles, are almost always practical storage modes but do not satisfy the main requisites of good classifications.

There are main principles that yield good classification, which are described in the intensional perspective. First–with Apostel [1963]– are some basic definitions.

From an intensional viewpoint, a division (or partition) is a closed formula F, which contains some assertion of the type (P ⊃ (Q₁ ∨ Q₂ ∨…∨ Q_n)). So, a classification is a sequence of implicative-disjunctive propositions which takes the following form: everything which has the property P has also one of the n properties Q₁ … Q_n. Everything which has the property Q_r  has also the property S, and so on (Apostel 1963, 188).

A division is essential if the individuals having the property P – and only this individual – may also have one of the properties Q_i. So, we can see that there are degrees in essentiality insofar as the number of individuals having the Q’s without having the P’s is greater or less. At every level, a classification may be probably or necessarily essential or exhaustive, or exclusive.

We call intensional weight w(P) of a property P,  the set of disjunctions implied by this property (with necessity, factuality or probability). Properties defining classes in the same level may have extremely variable intensional weights. The basis of a division is the constant relation R, if any, between the properties of two different classes of this division.

A basis of division is (partially or totally) exhausted in some level insofar as, for this level, we do not find, in any case, true disjunctive propositions that are implied by the properties of this level and whose terms are connected by this very relation R.

A division is said to follow another one immediately (or to be immediately subsequent) if, for all P properties of the first, and for all Q properties of the second that are disjunctively implied by the P’s, there exists no sequence of R properties disjunctively implied by the P’s and disjunctively implying the Q’s.

The form of a property defining a class is the logical form of this property (conjunction of properties, disjunction of properties, negation of properties, single property).

For Apostel, an optimal classification should satisfy the following requisites:

1. Every level needs a basis for division;
2. No new basis for division shall be introduced before the previous one is exhausted;
3. Every division is essential;
4. Intensional weights of classes in a given level are comparable and relations between intensional weights of subsequent division properties in the classification must be constant.
5. Properties used to define classes are conjunctive ones, and not negative ones.
6. From the intensional viewpoint, divisions must be immediately subsequent.

In real domains, these requirements, or some of them, fail to hold. Levels are often extensionally equivalent but intensionally, the basis of division, the intensional weight, and so forth may change or not.

A natural classification is such that the definition of the domain classified determines in one and the same way the choice of the criteria of classification. It means that the fundamental set may be divided such that the division in the first level of the classification is an essential and subsequent one.

Intensional and extensional classifications are intimately related. Gathering entities in sets to produce extensional classes implies tagging these entities by their membership to these classes. But, intensional classes, built according to these descriptions, have an extension, which may be different from the initial extensional classes. So, in fact, both perspectives are not totally isomorphic and from Peirce (Hulwitt 1997) to Quine (1969), and presently, the question of natural classes remains an open and somewhat controversial question.

6. The Idea of a General Theory of Classifications

The idea of a general theory of classifications is not new. Such a project has been anticipated by Kant’s logic at the end of the 18th century. Then it was followed by many attempts to classify sciences at the beginning of the 19th century (Kedrov 1977) and had been posed by Auguste Comte in his Cours de philosophie positive (Comte 1975) as a general theory based on the study of symmetries in nature. Comte was inspired by mathematician Gaspard Monge and his classification of surfaces in geometry. However, this remains, in the work of Comte, a wishful thought. In the same way, the French naturalist Augustin-Pyramus de Candolle, published in 1813 an Elementary Theory of Botany, a book in which he introduced the term ‘taxonomia’, used in this work for the first time (de Candolle 1813). De Candolle showed that Botany had to leave artificial methods for natural ones, in order to get a method independent from the nature of the objects. Unfortunately, nothing very concrete or precise followed his remarks. Moreover, the previous projects were only concerned with finite classifications, particularly, biological ones. A higher and more general view came into light around the 1960s with the Belgian logician Leo Apostel. Apostel (1963) wanted to write a concrete version of Set theory, and, in order to do that, needed axioms that allow him to include in the theory only the classes actually existing in the world. As such, Apostel was led to ask some questions about the well-known axioms of Zermelo-Fraenkel’s Set theory. He did not reject the whole ZF-axiomatics but however suspected axioms like the pairing axiom, the axiom of separation and the power set axiom. He also left optional the axiom of infinity and had rather a negative opinion about the axiom of choice. This project got a new revival with the recent book of Parrochia-Neuville (2013).

The hardships of solving the problem of instability of classifications provided motivation for a search for some clear composition laws to be defined on the set of classifications over a set and to a true algebra of classifications, if possible, which is very difficult because this algebra would have to be, in principle, commutative and non-associative. This search is all the more crucial that a recent theorem proved by Kleinberg (2002) shows that one cannot hope to find a classifying function which would be together scale invariant, rich enough and consistent. This result means that we cannot find empirical stable classifications by using traditional clustering methods.

In the past, some attempts have been made to formalize non-commutative parenthesized products: Comtet (1970) and Neuville, in the 1980s used the Lukasiewicz’s Reverse Polish Notation (RPN), named also Postfix Notation, whose advantage is not only to make brackets or parentheses superfluous, but also to perform calculations on trees in the required order. But, a general algebra of classifications on a set is not known, even if some new models−Loday’s dendriform algebras, for example, which work very well for trees (See Dzhumadil’daev-Löfwall 2002)−are good candidates. In any event, we are invited to look for it, for two reasons. First, the world is not completely chaotic and our knowledge is evolving according to some laws. Second, there exist quasi-invariant classifications in physics (elementary particle classification), chemistry (Mendeleyev table of Elements), crystallography (the 232 groups of crystallographic structures) among others. Most of these good classifications are based on some mathematical structures (Lie groups, discrete groups, and so forth.). To address questions concerning classification theory, and clarify the different domains of it, one may propose this final view (See Figure 6):

• When our mathematical tools apply only to sense data, we get phenomenal classifications (by clustering methods): these are generally quite unstable.
• When our mathematical tools deal with crystallographic or quantum structures, we get what we call, using a Kantian concept, noumenal classifications (for instance, by invariance of discrete groups or Lie Groups). These are generally more stables.
• When we search a general theory of classifications (including infinite ones), we are in the domain of pure mathematics. In this field, ordering and articulating the infinite set of classifications comes to construct the continuum.

Figure 6: Metaclassification

This problem is far from being solved because there are a lot of unstable theories (Shelah 1978, 1998). However, the recent work of Parrochia-Neuville (2013) assumes the conjecture that a metaclassification, that is, a classification of all mathematical schemes of classifications, does exist. The reason is that all these forms may be expressed as ellipsoids of an n-dimensional space (Jambu 1983) that must converge necessarily on a point, the index of the classification. If the real proof comes, this will give a theorem of existence of such a structure from which a number of important results could follow.

7. References and Further Readings

• Adanson, M. 1757. Histoire naturelle du Sénégal. Paris: Claude-Jean-Baptiste Bauche.
• Aho, A.V., Hopcroft, J.E, Ulmann, J.D. 1983. Data Structures and algorithms. Reading (Mass.): Addison-Wesley Publishing Company.
• Agassiz, L. 1962. Essay on Classification (1857), reprint. Cambridge: Harvard University Press.
• Apostel, L. 1963. Le problème formel des classifications empiriques. La Classification dans les Sciences. Gembloux: Duculot.
• Aristotle, 1984. The Complete Works. Princeton: Princeton University Press.
• Barbut M., Monjardet, B. 1970. Ordre et classifications, 2 vol. Paris: Hachette.
• Barthélemy, J.-P., A. Guénoche. 1988. Les arbres et les représentations des proximités. Paris: Masson.
• Barwise, J., Seligman, J. 2003. The logic of distributed systems. Cambridge: Cambridge University Press.
• Béthery, A. 1982. Abrégé de la classification décimale de Dewey. Paris: Cercle de la librairie.
• Bliss, H. E. 1929. The organization of knowledge and the system of the sciences. New York: H. Holt and Company.
• Benzécri, J.-P., et alii. 1973. L’analyse des données, 1, La taxinomie, 2 Correspondances. Paris: Dunod.
• Birkhoff, G. 1935. On the structure of abstract algebras. Proc. Camb. Philos. Soc. 31, 433-454.
• Birkhoff, G. 1967. Lattice theory (1940), 3rd ed. Providence: A.M.S.
• Brucker F., Barthélemy, J.-P. 2007. Eléments de Classification, aspects combinatoires et algorithmiques. Paris: Hermès-Lavoisier.
• Buffon, G. L. Leclerc de, 1749. Histoire naturelle générale et particulière (vol. 1). Paris: Imprimerie royale.
• Candolle (de), A. P. 1813. Théorie élémentaire de la Botanique ou exposition des principes de la classification naturelle et de l’art d’écrire et d’étudier les végétaux, first edition. Paris: Deterville.
• Comte, A. 1975. Philosophie Première, Cours de Philosophie Positive (1830), Leçons 1-45. Paris: Hermann.
• Comtet, L. 1970. Analyse combinatoire. Paris: P.U.F..
• Dagognet, F. 2002. Tableaux et Langages de la Chimie (1967). Seyssel: Champ Vallon.
• Dagognet, F. 1970. Le Catalogue de la Vie. Paris: P.U.F..
• Dagognet, F. 1984. Le Nombre et le lieu. Paris: Vrin.
• Dagognet, F. 1990. Corps réfléchis. Paris: Odile Jacob.
• Dahlberg, I., 1976. Classification theory, yesterday and today. International Classification 3 n°2, pp. 85-90.
• Dale, N., Walker, H. M. 1996. Abstract Data Types: Specifications, Implementations, and Applications. Lexington, Massachusetts: D.C. Heath and Company.
• Darwin, C.R., 1964. On the Origin of Species (1859), reprint. Cambridge: Harvard University Press.
• De Grolier, E. 1962. Etude sur les catégories générales applicables aux classifications documentaires, Unesco.
• Dobrowolski, Z. 1964. Etude sur la construction des systèmes de classification. Paris, Gauthier-Villars.
• Dubreil, P., Jacotin, M.-L. 1939. Théorie algébrique des relations d’équivalence. J. Math. 18, pp. 63-95.
• Dzhumadil’daev,A. et Löfwall, C. 2002. Trees, free right-symmetric algebras, free Novikov Algebras and Identities. Homology, homotopy and Applications, vol.(4(2), pp. 165-190.
• Foucault, M. 1967. Les Mots et les Choses. Paris: Gallimard.
• Gondran, M. 1976. La structure algébrique des classifications hiérarchiques. Annales de l’Insee, pp. 22-23.
• Granger, G.-G. 1980. Pensée formelle et Science de l’Homme (1967). Paris: Aubier-Montaigne.
• Hilman, D.J. 1965. Mathematical classification technics for non static document collections, with particular reference to the problem of revelance. Classification Research, Elsinore Conference Proceedings, Munksgaard, Copenhagen, pp. 177-209.
• Huchard, M., R. Godin, , A. Napoli, A. 2003. Objects and Classification. ECOOP 2000 Workshop reader, J. Malenfant, S. Moisan, A. Moreira (Eds), LNCS 1964. Berlin-Heidelberg-New York: Springer-Verlag, pp 123-137.
• Hulswit, M. 1997. Peirce’s Teleological Approach to Natural Classes. Transactions of the Charles S. Peirce Society, pp. 722-772.
• Jambu, M. 1983. Classification automatique pour l’analyse des données, 2 vol.. Paris: Dunod.
• Jardine N., Sibson, R. 1971. Numerical Taxonomy. New York: Wiley.
• Joly, R. 1956. Le thème philosophique des genres de vie dans l’Antiquité grecque. Bruxelles: Mémoires de l’Académie royale de Belgique, classe des Lettres et des Sciences mor. et pol., tome Ll, fasc. 3.
• Kant, E. 1988. Logic. New York: Dover Publications.
• Kedrov, B. 1977. La Classification des Sciences (vol. 2). Moscou: Editions du Progrès.
• Kleinberg, J. 2002. An impossibility theorem for Clustering. Advances in Neural Information Processing Systems (NIPS), 15, pp. 463-470.
• Krastner M. 1953-1954. Espaces ultramétriques et ultramatroïdes. Paris: Séminaire, Faculté des Sciences de Paris.
• Larson, J.A., Walden, W.E. 1979. Comparing insertion shemes used to update 3-2 trees. Information Systems, vol.4, pp. 127-136.
• Lerman, I.C. 1970. Les bases de la classification automatique. Paris: Gauthier-Villars.
• Lerman, I.C. 1981. Classification et analyse ordinale des données. Paris: Dunod.
• Lidi R., 2004. Abstract Algebra. Berlin-Heidelberg-New York: Springer-Verlag.
• Luszczewska-Romahnowa S., Batog T. 1965a. A generalized classification theory I. Stud. Log., tom XVI, pp. 53-70.
• Luszczewska-Romahnowa S., Batog T. 1965b. A generalized classification theory II. Stud. Log., tom XVII, pp. 7-30.
• MacNeille 1937. Partially ordered sets. Transaction Amer. Math. Soc., vol. 42, pp. 416-460.
• Ore O. 1942. Theory of equivalence relations. Duke Math. J. 9, pp. 573-627.
• Ore O. 1943. Some studies on closer relations. Duke Math. J. 10, pp. 761-785.
• Parrochia, D., Neuville, P. 2013. Towards a general theory of classifications. Bäsel: Birkhaüser.
• Peirce C. S. 1880. On the Algebra of Logic. American Journal of Mathematics 3, pp. 15-57.
• Pierce, R.S. 1970. Classification problems. Mathematical System theory, vol. 4, n°1, March, pp. 65-80.
• Plato, 1997. The Complete Works. Cambridge: Hacking publishing Company
• Porphyry, 2014. On Aristotle’s Categories. London, New York: Bloomsbury Publishing Plc.
• Quine, W.V.O. 1969. Ontological Relativity and Other Essays. New York: Columbia University Press.
• Ranganathan, S. R. 1933. Colon Classification. Madras: Madras Library Association.
• Ranganathan, S. R. 2006. Prolegomena to Library Classification (1937), Reprint. New Delhi: Ess Pub..
• Rasiowa H., Sikorski, R. 1970. The Mathematics of Metamathematics. Cracovia: Drukarnia Uniwersytetu Jagiellonskiego.
• Riordan, J. 1958. Introduction to combinatorial analysis. New York: Wiley.
• Roux, M. 1985. Algorithmes de classification. Paris: Masson.
• Shelah, S. 1988. Classification Theory (1978). Amsterdam: North Holland.
• Shröder, E. 1890. Vier Kombinatorische Probleme. Z. Math. Phys. 15, pp. 361-376.
• Smith, B. 1997. Boundaries: An Essay in Mereotopology. L. Hahn (ed.), The Philosophy of Roderick Chisholm. La Salle, Open Court: Library of Living Philosophers, pp. 534-561.
• Smith, B. 2003. Groups, sets and wholes. Revista di estetica, NS (P. Bozzi Festschrift), 24-3, 1209-130.
• Sokal R. R., Sneath, P.H. 1963. Principle of numerical taxonomy. San Francisco: W. H. Freeman.
• Sokal, R. R., and Sneath, P. H. 1973. Numerical Taxonomy, the principles and practice of numerical classifications. San Francisco: W. H. Freeman.
• Van Cutsem B. (ed.) 1994. Classification and dissimilarity analysis. New York-Berlin-Heidelberg: Springer Verlag.
• Veglioni, S. 1996. Classifications in Algebraic specifications of Abstract Data Types. CiteSeer^X
• Windsor, M. P. 2009. Taxonomy was the foundation of Darwin’s evolution. Taxon 58, 1, pp. 43-49.
• Wille, R. 1996. Restructuring lattice theory: an approach based on hierarchy of concepts. Rival, I (ed.) Ordered Sets. Boston: Reidel, pp. 445-470.
• Woodward, H. 1903. Memorial to Henry Alleyne Nicholson. M.D., D.Sc., F.R.S. Geological Magazine, 10, pp. 451-452.

 

Author Information

Daniel Parrochia
Email: daniel.parrochia@wanadoo.fr
Université Jean Moulin – Lyon III
France

Charles Sanders Peirce: Logic

Charles Sanders Peirce (1839-1914) was an accomplished scientist, philosopher, and mathematician, who considered himself primarily a logician. His contributions to the development of modern logic at the turn of the 20^th century were colossal, original and influential. Formal, or deductive, logic was just one of the branches in which he exercized his logical and analytical talent. His work developed upon Boole’s algebra of logic and De Morgan’s logic of relations. He worked on the algebra of relatives (1870-1885), the theory of quantification (1883-1885), graphical or diagrammatic logic (1896-1911), trivalent logic (1909), higher-order and modal logics. He also contributed significantly to the theory and methodology of induction, and discovered a third kind of reasoning, different from both deduction and induction, which he called abduction or retroduction, and which he identified with the logic of scientific discovery.

Philosophically, logic became for Peirce a broad discipline with internal divisions and external architectonic relations to other parts of scientific inquiry. Logic depends upon, or draws its principles from, mathematics, phaneroscopy (=phenomenology), and ethics, while metaphysics and psychology depend upon logic. One of the most important characters of Peirce’s late logical thought is that logic becomes coextensive with semeiotic (his preferred spelling), namely the theory of signs. Peirce divides logic, when conceived as semeiotic, into (i) speculative grammar, the preliminary analysis, definition, and classification of those signs that can be used by a scientific intelligence; (ii) critical logic, the study of the validity and justification of each kind of reasoning; and (iii) methodeutic or speculative rhetoric, the theory of methods. Peirce’s logical investigations cover all these three areas.

Table of Contents

1. Logic among the Sciences
2. Logic as Semeiotic
   1. Speculative Grammar
   2. Logical Critics
      1. From Three Types of Inference to Three Stages of Inquiry
      2. Abductive Logic
      3. Deductive Logic
      4. Inductive Logic
   3. Methodeutic
3. Peirce’s Logic in Historical Perspective
4. References and Further Reading

1. Logic among the Sciences

Peirce’s idea of logic is guided by finding the location of logic in the map of the sciences. Peirce’s mature classification of the sciences (CP 1.180-202, 1903; see Brent 1987), which is a “ladder-like scheme” (MS 328, p. 20, c. 1905), takes superordinate sciences to provide principles to subordinated sciences, forming a ladder of decreasing generality.

According to Peirce’s 1903 scheme, which he as late as 1911 considered a satisfactory account (MS 675), sciences are either sciences of discovery, sciences of review, or practical sciences. Logic is a science of discovery. The sciences of discovery are divided into mathematics, philosophy and idioscopy. Mathematics studies the necessary consequences of purely hypothetical states of things. Philosophy, by contrast, is a positive science, concerning matters of fact. Idioscopy embraces more special physical and psychical sciences, and depends upon philosophy. Philosophy in turn divides into phaneroscopy, normative sciences and metaphysics. Phaneroscopy is the investigation of what Peirce calls the phaneron: whatever is present to the mind in any way. The normative sciences (aesthetic, ethics, and logic) introduce dichotomies, in that they are, in general, the investigation of what ought and what ought not to be. Metaphysics gives an account of the universe in both its physical and psychical dimensions. Since every science draws its principles from the ones above it in the classification, logic must draw its principles from mathematics, phaneroscopy, aesthetics and ethics, while metaphysics, and a fortiori psychology, draw their principles from logic (EP 2, pp. 258-262, 1903).

In sharp contrast to the logicist hypothesis, Peirce did not believe that mathematics depends upon deductive logic. On the contrary, in a sense it is deductive logic that depends upon mathematics. For Peirce, mathematics is the practice of deduction, logic its description and analysis: Peirce’s father Benjamin Peirce had defined mathematics as the science which draws necessary conclusions (B. Peirce 1870, p. 1). Hence deductive logic for Charles became the science of drawing necessary conclusions (CP 4.239, 1902). Logic cannot furnish any justification of a piece of deductive reasoning: deduction in general is in the first place mathematically, rather than logically, valid. And deductive logic is at any rate only a part of logic: “logic is the theory of all reasoning, while mathematics is the practice of a particular kind of reasoning” (MS 78, p. 4; see Haack 1993 and Houser 1993). Logic rather draws its principles from phaneroscopy, as the latter analyzes the structure of appearance but does not pronounce upon the veracity of such appearance. Logic also draws its principles from the normative sciences of ethics and esthetics (Peirce’s preferred spelling), which precede normative logic in the ladder of generality. Ethics depends on esthetics because ethics draws from esthetics the principles involved in the idea of a summum bonum, the highest good. Since ethics is the science that distinguishes good from bad conduct, it must be concerned with deliberate, self-controlled, conduct, because only by deliberate conduct is it possible to say whether the conduct is good or bad. Logic treats of a special kind of deliberate conduct, thought, and distinguishes good from bad thinking, that is, valid from invalid reasoning. Since deliberate thought is a species of deliberate conduct, logic must draw its principles form ethics (CP 5.120-50; EP 2, pp. 196-207, 1903)

Of the sciences down the ladder of generality, metaphysics and psychology come out next. Peirce had learnt from Kant that metaphysical conceptions mirror those of formal logic. Peirce’s criticism ever since the 1860s had been that Kant’s table of categories was mistaken not because he based them upon formal logic but because the formal logic that Kant had used was itself poor and ultimately wrong (see NEM 4, p. 162, 1898). The only way to arrive at a good metaphysics is to begin with a good logical theory (EP 2, pp. 30-31, 1898). Psychology, too, depends upon logic. According to Peirce, different versions of logical psychologism characterized the logics of his time, especially in Germany. Logic for Peirce considers not what or how we in fact think but how we ought to think; logic is a normative, not a descriptive, science. The validity of an argument consists in the fact that its conclusion is true, always or for the most part, when its premises are true; it has nothing to do with reference to a mind. Logical necessity is a necessity of (non-empirical) facts, not a necessity of thinking. No appeal to psychology is thereby of any aid in logic. On the contrary, it is psychology that stands in the need of a science of logic (EP 2, pp. 242-257, 1903).

2. Logic as Semeiotic

In the 1890s (MS 595, 787), Peirce divided logic into three branches: speculative grammar (also called stechiology), logical critics (or just critics) and methodeutic (also called speculative rhetoric). The division echoes the three sciences of the medieval Trivium: grammar, dialectic and rhetoric.

Perhaps the most salient character of Peirce’s logic as a whole is that in his later works (MS L 75, 1902; MS 478, 1903; MS 693, 1904; MS 640, 1909) logic is identified with semeiotic, the science and philosophy of signs and representations. Already in his early works on the theory of inference Peirce had affirmed that logic is the branch of semeiotic that treats of one particular kind of representations, namely symbols, in their reference to their objects (W1, p. 309, 1865). By the beginning of the 20^th-century, he had shifted from the idea of “logic-within-semeiotic” to that of “logic-as-semeiotic.” He thus needed to distinguish between logic in the narrow sense, which he now calls logical critics, and logic in the wide sense; the latter is made coextensive with semeiotic. “Logic, in its general sense, is, as I believe I have shown, only another name for semiotic (σημειωτική), the quasi-necessary, or formal, doctrine of signs” (CP 2.227, c.1897; cf. Fisch 1986, pp. 338-341).

According to Peirce’s mature views, an enlargement of logic to cover all varieties of signs was a valuable methodological guidance to the building of an objective, anti-psychological and formal logical theory: “The study of the provisional table of the Divisions of Signs will, if I do not deceive myself, help a student to many a lesson in logic” (MS S 46, 1906; cf. MS 283, c. 1905; MS 675-676, 1911; MS 12, 1912). Therefore, his logic contains, as a proper part of it, a study of its own scope and expansions. In homage to Thomas of Erfurt’s grammatica speculativa, which at Peirce’s times was misattributed to Duns Scotus, Peirce names this part of logic “speculative grammar.”

a. Speculative Grammar

In the 1890s Peirce regarded speculative grammar as an analysis of the nature of assertion (MS 409-8, 1894; CP 3.432, 1896, MS 787, c. 1897). Starting with the Syllabus of his 1903 Lowell Lectures (A Syllabus of Certain Topics of Logic, MS 478, MS 540), speculative grammar becomes a classification of signs. In the Syllabus Peirce defines a Sign or Representamen as

the first Correlate of a triadic relation, the second Correlate being termed its Object, and the possible Third Correlate being termed its Interpretant, by which triadic relation the possible Interpretant is determined to be the first correlate of the same triadic relation to the same Object, and for some possible Interpretant. (MS 540, CP 2.242; EP 2, p. 290).

A sign for Peirce is something that represents an independent object and which thereby brings another sign, called interpretant, to represent that object as the sign does. According to a long tradition in the history of logic, Peirce declares that the principal classes of signs that logic is concerned with are terms, propositions, and arguments. But by 1903 these three elements become parts of a larger taxonomic scheme.

Since the Syllabus and until at least 1909 Peirce continued experimenting with principles and terminologies, without however settling on any definitive division. This section presents the main principles of the Syllabus classification.

Signs are divisible by three trichotomies; first, according as the sign in itself is a mere quality, is an actual existent, or is a general law; secondly, according as the relation of the sign to its Object consists in the sign’s having some character in itself, or in some existential relation to that Object, or in its relation to an Interpretant; thirdly, according as its Interpretant represents it as a sign of possibility, or as a sign of fact, or a sign of reason. (CP 2.243, 1903)

The first trichotomy considers signs as (i) tones, when taken in their material qualities (such as the blueness of the ink), as (ii) tokens (such as any instance of the word “the”), and as (iii) general types (such as the word “the”). The second trichotomy is the best known, namely that of (i) icons, or signs that bear similarity or resemblance to their objects, (ii) indices, which have factual connections to their objects, and (iii) symbols, which have rational connections to their objects. The third trichotomy divides signs into terms, propositions, and arguments: Through his work on the logic of relatives (see § 2.b.iii.), Peirce had come to consider the terms as (i) rhemas, which are unsaturated predicates with logical bonds or subject-positions, in some ways similar to Frege’s Begriff and Russell’s propositional function; (ii) propositions, which unify subject and predicate and thus assert, or as in the Syllabus are dicisigns, signs that tell, and (iii) arguments, which embody the ultimate perfection and end of signs as a representation of facts that are signs of other facts, such as the premises being the sign of the conclusion. [Peirce’s theory of the proposition is articulated and highly original and has been thoroughly investigated in Hilpinen 1982, 1992; Ferriani 1987; Chauviré 1994; Stjernfelt 2014.]

There are cross-divisions of these three trichotomies across speculative grammar. A term or rhema is a symbol which is represented by its interpretant as an icon of its object, while a proposition or dicisign is a symbol which is represented by its interpretant as an index of its object. Arguments themselves are considered as symbols that represent their conclusion in three different ways: iconically in abduction, indexically in deduction, and symbolically in induction. (In an early cross-division proposed in 1867 these last two were interchanged. See W2, p. 58). Other outcomes of the classifications consisted in further divisions of objects and interpretants into various subtypes. [For more on Peirce’s classifications, see Weiss & Burks 1945; Short 2007, chs. 7-9; and Burch 2011.]

Grammatical taxonomy shows that there are three kinds of arguments, each manifesting a different semiotic principle. But it is up to the second branch of logic, critics, to investigate the question of logical validity and justification of such arguments. The analysis of the conditions of validity of these three kinds of reasoning is a critical, not grammatical, question.

b. Logical Critics

i. From Three Types of Inference to Three Stages of Inquiry

Logical critics is the heart of Peirce’s logic. It cover what usually goes under the name of logic proper, that is, the investigation of inference and arguments. Many 19^th-century logicians (for example, John S. Mill, George Boole, John Venn and William Stanley Jevons) took the range of logic to include deductive as well as inductive logic. As appears from the classification, the remarkable novelty of Peirce’s logical critics is that it embraces three essentially distinct though not entirely unrelated types of inferences: deduction, induction, and abduction. Initially, Peirce had conceived deductive logic as the logic of mathematics, and inductive and abductive logic as the logic of science. Later in his life, however, he saw these as three different stages of inquiry rather than different kinds of inference employed in different areas of scientific inquiry.

Peirce had formulated a definite theory of logical leading principles early in the late 1860s. His argument is roughly as follows. In any inference, we pass from some fact to some other fact that follows logically from it. The former is the premise (for in cases where there is more than one they may be colligated or compounded into one copulative premise), the latter is the conclusion.

P
∴C

The conclusion follows from the premise logically, that is, according to some leading principle, L. As logic supposes inferences to be analyzed and criticized, as soon as the logician asks what is it that warrants the passing from such premise to the conclusion she is obliged to express the leading principle L in a proposition and to lay it down as an additional premise:

P
L
∴C

This gives what Peirce calls a complete argument, in opposition to incomplete, rhetorical or enthymematic arguments. This second argument has itself its own leading principle L₁, which may again be expressed in a proposition and laid down as a further premise:

P
L
L₁
∴C

When L₁ is not a substantially different leading principle than L, then L is said to be a logical leading principle. In Peirce’s words:

This second argument has certainly itself a leading principle, although it is a far more abstract one than the leading principle of the original argument. But you might ask, why not express this new leading principle as a premise, and so obtain a third argument having a leading principle still more abstract? If, however, you try the experiment, you will find that the third argument so obtained has no more abstract a leading principle than the second argument has. Its leading principle is indeed precisely the same as that of the second argument. This leading principle has therefore attained a maximum degree of abstractness; and a leading principle of maximum abstractness may be termed a logical principle. (NEM 4, p.175, 1898)

A logical leading principle is therefore a formal or logical proposition which, when explicitly stated, adds nothing to the premises of the inference which it governs. The central question of logical critics becomes that of determining different kinds of logical leading principles.

Peirce’s initial strategy to prove that there are three and only three irreducible kinds of reasoning was to use syllogism. He gave the demonstration that the second and the third figure are reducible to the first only through the employment of the very figure that is to be reduced. The principles involved in the three syllogistic figures cannot then be reduced to a combination of other, more primitive principles, as they invariably enter as parts into the reduction proof itself. From this Peirce drew the broader conclusion that the three figures of syllogism correspond to the three kinds of inference in general: deduction corresponds to the first figure, abduction to the second, and induction to the third:

In Peirce 1878 and Peirce 1883, abduction and induction are described as inversions of a deductive syllogism. If we call the major premise of a syllogism in the first figure Rule, its minor premise Case, and its conclusion Result, then abduction may be said to be the inference of a Case from a Result and a Rule, while induction may be said to be the inference of a Rule from a Case and a Result:

Later in 1903 Peirce had come to the conclusion that the three kinds of reasoning are in fact three stages in scientific research. First comes abduction, now often also called retroduction, by which a hypothesis or conjecture that explains some surprising fact is set forth. Then comes deduction, which traces the necessary consequences of the hypothesis. Lastly comes induction, which puts those consequences to test and generalizes its conclusions.

Any inquiry is for Peirce bound to follow this pattern: abduction–deduction–induction. Each kind of inference retains its validity and modus operandi and is logically irreducible to either of the others; yet all three of them are necessary in any complete process of inquiry. Of the three methods, Peirce took deduction to be the most secure and the least fertile, while abduction is the most fertile and the least secure.

All these three departments of critics epitomize the originality of Peirce’s contributions. The following sections deals with Peirce’s abductive, deductive, and inductive logics, respectively.

ii. Abductive Logic

The central question of abductive or retroductive logic is: is there a logic of scientific discovery? If yes, what are its justification and method?

Initially, Peirce described abduction as the inference of a Case from a Rule and a Result:

Hypothesis proceeds from Rule and Result to Case; it is the formula of the […] process by which a confused concatenation of predicates is brought into order under a synthetizing predicate. (Peirce 1883, p. 145)

Its general formula is this:

Result: S is M₁ M₂ M₃ M₄
Rule: P is M₁ M₂ M₃ M₄
Case: Therefore, S is P.

A certain number of surprising facts have been observed which call for explanation, and a single predicate embracing all of them is found which would explain them. When I notice that light manifests such-and-such complicated and surprising phenomena, and I know that ether waves exhibits those same phenomena, I conclude abductively that, if light were ether waves, it would be normal for it to manifest those phenomena. This offers rational ground for the hypothesis that light is ether waves.

In 1900, Peirce began viewing this description of abduction as inadequate. What he in 1883 had called hypothesis or abduction was actually induction about characters instead of things and is therefore better to be called qualitative induction (see § 2.b.iv): its leading principle is inductive and not abductive. Abduction is no longer constrained by the syllogistic framework. Most generally, it is the non-inductive process of forming an explanatory hypothesis. In Peirce’s words, abduction “is the only logical operation which introduces any new idea” (CP 5.172, 1903). Although abduction asserts its conclusions only conjecturally, it has a definite logical form. The following has become its standard, albeit not the ultimately satisfactory, description after Peirce’s pronouncement of it in the seventh of the Harvard Lectures of 1903:

The surprising fact, C, is observed;
But if A were true, C would be a matter of course,
Hence, there is reason to suspect that A is true. (CP 5.189, 1903)

This schema reveals why abduction is also called retroduction: it is reasoning that leads from a consequent of an admitted consequence to its antecedent.

Another description of the logical form of abduction is contained in a later, unpublished manuscript:

In the inquiry, all the possible significant circumstances of the surprising phenomenon are mustered and pondered, until a conjecture furnishes some possible Explanation of it, by which I mean a syllogism exhibiting the surprising fact as necessarily following from the circumstances of its occurrence together with the truth of the conjecture as premisses. (MS 843, p. 41, 1908)

The explaining syllogism is the inversion of the 1903 formula:

If A were true, C would be observable.
A is true.
Therefore, C is observable.

One more and hitherto unknown formulation of retroduction is found in an unpublished letter to Lady Welby:

[The] “interrogative mood” does not mean the mere idle entertainment of an idea. It means that it will be wise to go to some expense, dependent upon the advantage that would accrue from knowing that Any/Some S is M, provided that expense would render it safe to act on that assumption supposing it to be true. This is the kind of reasoning called reasoning from consequent to antecedent. For it is related to the Modus Tollens thus:

Instead of “interrogatory”, the mood of the conclusion might more accurately be called “investigand”, and be expressed as follows:

It is to be inquired whether A is not true.

The reasoning might be called “Reasoning from Surprise to Inquiry..” (Peirce to Welby, July 16, 1905, LoF, pp. 907-908)

The whole course of thought, consisting in noticing the surprising phenomenon, searching for pertinent circumstances, asking a question, forming a conjecture, remarking that the conjecture appears to explain the surprising phenomenon, and adopting the conjecture as plausible, constitutes the first, abductive stage of inquiry. Nonetheless, its crucial phase is that of forming the conjecture itself. This is often described by Peirce as an act of insight, or an instinct for guessing right, or what Galileo called il lume naturale. [That Peirce actually got the phrase from Galileo has sometimes been contested. But see the story by Victor Baker in Bellucci, Pietarinen & Stjernfelt (2014) on the “Myth of Galileo.” Baker refers to Jaime Nubiola’s finding of Peirce’s copy of Galileo’s Opere that had that phrase underlined in Peirce’s hand. That fifteen volumes edition was at least in 2012 still to be found at the Robbins Library at the Department of Philosophy, Harvard University.]

However, to pronounce reasoning to be instinctive would amount to excluding it from the realm of logic. For logic only considers reasoning, and reasoning is a deliberate act subject to self-control. According to Peirce, abduction is an inference type based upon a logical principle. In its most abstract shape, such logical principle gives abduction its justification, and the justification of abduction is the bottom question of logical critics (EP 2, p. 443, 1908).

According to Peirce, abduction “consists in studying the facts and devising a theory to explain them” (CP 5.145, 1903). Its only justifications are that “if we are ever to understand things at all, it must be in that way,” and that “its method is the only way in which there can be any hope of attaining a rational explanation” (CP 2.777, 1902). The only justification for a hypothesis is that it might explain the facts. But in general, an inference is valid if its leading principle is an instance of a logical principle which is conducive to the acquisition of new information. Therefore, the logical leading principle of all abductions is that nature, in general, is explainable. To suppose something inexplicable is contrary to the principles of logic: such supposition only has the appearance of an explanation conducive to the acquisition of new information, but to really suppose something inexplicable is to renounce knowledge.

That nature is explicable is therefore the primary abduction underlining all possible abductions. Human powers of insight may well be justified also inductively, that is, as testified by the history of science. But abduction’s primary justification is abductive rather than inductive: if we are to acquire new knowledge at all, sooner or later we must reason abductively. [See Bellucci & Pietarinen 2014; Burks 1946; Fann 1970; Kapitan 1992; Kapitan 1997; Paavola 2004 for further details on Peirce’s theory of abduction or retroduction, and Ma & Pietarinen 2015 for a dynamic logic approach to Peirce’s interrogative abduction.]

Of these three stages of reasoning, abduction is the most fertile but the least secure. For this reason, Peirce affirms that abduction is the principal kind of reasoning in which, after logical critics has pronounced it valid, it remains to be inquired whether and how it is advantageous. To carry out such tasks pertains to the third branch of logic, methodeutic, which is discussed in § 2.c below.

iii. Deductive Logic

The works of George Boole and Augustus De Morgan provided the essential backdrop for Peirce’s development of deductive logic. Also Benjamin Peirce’s Linear Associative Algebra (B. Peirce 1870) influenced his son’s early development of algebraic logic of relatives. Peirce’s dissatisfaction with how Boole represented syllogisms as algebraic equations led him to develop new algebraic approaches to logic, which he did by combining Boole’s calculus (Boole 1847, 1854) with De Morgan’s treatment of relations (De Morgan 1847, 1860).

Some of Peirce’s most important contributions to the development of modern logic are highlighted below.

1867: In the paper “An Improvement in Boole’s Calculus of Logic” published in the Proceedings of the American Academy of Arts and Sciences (Peirce 1867), Peirce subscribed all operation symbols with a comma to differentiate the logical from the arithmetical interpretation. He also made Boole’s union operator inclusive rather than exclusive (he was anticipated in this by Jevons 1864). Peirce became aware of the limitations of Boole’s algebraic logic, such as that it cannot express categorical propositions (Some X is Y), so it fails to properly represent quantification.

1870: Peirce’s development of De Morgan’s theory of relations is fully exposed in his paper “Description of a Notation for the Logic of Relatives, resulting from an Amplification of the Conceptions of Boole’s Calculus of Logic” (Peirce 1870), which was communicated to the American Academy of Arts and Sciences in January 1870. In this paper, Peirce combines De Morgan’s theory with Boole’s calculus. The result is a logical algebra equivalent in expressive power to first-order predicate logic without identity. Peirce’s paper introduces a number of original innovations. Among them is a new process of logical differentiation, explained in Welsh (2012, pp.166-180). Peirce also introduces the copula of inclusion, , later also termed the sign of illation and expressed in cursive form as . Inclusion is for Peirce a wider and logically simpler concept than that of equality. This difference marks another important departure from Boole’s mathematical algebra towards new types of logical algebras. Beginning with C. I. Lewis’s (1918) comments on Peirce’s algebra, the literature has discussed whether in this 1870 paper what Peirce calls relative terms are to be equated with relations (see Merrill 1997 for a summary and further references). It appears that in the very least they are what verbs and phrases express linguistically, such as lover of___, whatever is a lover of­____, or buyer of____for____from____. Here blanks stand for nouns that are required to complete the expressions. Beginning in 1882, Peirce comes to define relative terms as classes of ordered pairs ( later understood as being relations). He denotes such terms by rhemas with blanks for expressions standing for subjects, such as ­­____is a lover of____, whatever____is a lover of­____ and so forth. Of note is that the algebra of Peirce’s 1870 paper is able to express various forms of quantification although the term “quantifier” and its modern conception was to emerge only later in his works after the early 1880s.

1880a: The long paper “On the Algebra of Logic” (Peirce 1880a), which was published in the American Journal of Mathematics, introduces a number of further developments of which the following six are listed here:

(1) The copula, expressed as a binary relation between classes of propositions,  P_i  C_i , is now understood to express the notion of the semantic consequence, namely that “every state of things in which a proposition of the class P_i is true is a state of things in which the corresponding propositions of the class C_i are true” (W4, p. 166). The binary relation here is thus a truth-functional implication. Moreover, the remarks in his Logic Notebook published in W4 (p. 216) were written in the same year and appear to be the first instance presenting variables v and f to denote the truth values true and false.

(2) A dash over a symbol is used to denote a negative of the symbol. A dash over the sign of illation in P_i  C_i  indicates the class complement. Constants ∞ and 0 are taken to mean the values of the possible and the impossible. An important modal component which Peirce would develop later on is thus emerging in this work.

(3) The totality of all that is possible is according to Peirce the “universe of discourse, and may be very limited,” that is, limited to that which “actually occurs,” rendering “everything which does not occur” impossible (W4, p. 170). The important idea of working with variable and restricted domains makes a marked difference not only to Frege who is well-known to have his logic to quantify over the entire “logical thought”, but also to Schröder, who though also working on the algebra of logic had nonetheless rendered Peirce’s 1885 (see below) algebra of logic so as to quantify, in a Fregean fashion, what Peirce had later in 1903 remarked to be “the whole universe of logical possibility” (MS 478, pp. 163-4).

(4) A new operation on relatives, which Peirce termed transaddition (º) is then introduced (W4, p.204). Taking two relatives, such as being lover of___ (l) and being servant of___ (s), their relative product ls denotes whatever is lover of a servant of___. Their transaddition l º s denotes whatever is not a lover of everything but servants of___, that is, it denotes a complement of the complements of the relative product of the two terms l and s.

(5) The 1880 paper is also the first in which the idea of a relative sum, which is the complement of the transaddition and which Peirce in 1882 will denote by the dagger (†), is employed. For example, l † s reads lover of everything but servants of___. Hence this 1880 paper marks a decisive move towards a theory of quantification which will see its emergence in his 1883 Note B in the Studies in Logic (see below) and which comes to be completed in his 1885 “Algebra of Logic” paper (see below).

(6) The 1880 paper also suggests a mathematical theory of lattices for the treatment of the algebra of logic (W4, pp. 183-188).

Arthur Prior (1958, 1964) showed that Peirce’s 1880 paper provides a complete basis for propositional logic.

1880b: In an unpublished manuscript (MS 378, Peirce 1880b) entitled “A Boolian Algebra with One Constant”, which still in 1926 was tagged “to be discarded” at the Department of Philosophy at Harvard University, Peirce reduces the number of logical operations to one constant. He states that “this notation … uses the minimum number of different signs … shows for the first time the possibility of writing both universal and particular propositions with but one copula” (W4, p.221). Peirce’s notation was later termed the Sheffer stroke, and is also well-known as the NAND operation, in Peirce’s terms the operation by which “[t]wo propositions written in a pair are considered to be both denied” (W4, p.218). In the same manuscript, Peirce also discovers what is the expressive completeness of the NOR operation, indeed today rightly recognized as the Peirce arrow.

1881: “On the Logic of Number” (Peirce 1881), published in American Journal of Mathematics and read before the National Academy of Sciences, was noted by Gerrit Mannoury (1909, pp. 51, 78) to be the first successful axiomatization of natural numbers. Shields (1981/2012) has shown Peirce’s axiom system to be equivalent to the better-known systems of Dedekind (1888) and Peano (1889). Peirce’s paper formulates, presumably for the first time, the notions of partial and total linear orders, recursive definitions for arithmetical operations, and the general definition of cardinal numbers in terms of ordinals. The paper also provides a purely cardinal definition of a finite set (Dedekind-finite) by checking whether De Morgan’s syllogism of transposed quantity is valid. [The syllogism of transposed quantity is expressed in the following mode of inference: Every Texan kills a Texan; Nobody is killed by but one person; Hence, every Texan is killed by a Texan.] Peirce then derives in this paper the latter property of finiteness from the ordinal one. Doing the converse assumes the axiom of choice.

During 1881-2, Peirce edited a book, published in 1883 and entitled Studies in Logic by Members of the Johns Hopkins University (Peirce 1883). It contained significant graduate work by his students Benjamin I. Gilman, Christine Ladd(-Franklin), Allan Marquand and Oscar Howard Mitchell. Peirce contributed to the volume a paper “A Theory of Probable Inference”, together with Note A, “A Limited Universe of Marks”, and Note B, “The Logic of Relatives.” Some developments in Mitchell’s paper as well as in Note B are worth highlighting.

Mitchell’s “On a New Algebra of Logic” was hailed by his teacher as “one of the greatest contributions that the whole history of logic can show” (MS 492; LoF, p. 225). Peirce attributed to Mitchell two major discoveries: first, the invention of the basic form of proof transformation and second, the interpretation of quantifiers in multiple dimensions, one of which is time. The former is similar to the resolution rule in logic programming, and consists of a series of insertions (by adding to premises) and erasures (by elimination of consequents). In Peirce’s words, “the passage from a premiss or premisses … to a necessary conclusion in the manner to which is alone usually called necessary reasoning, can always be reached by adding to the stated antecedents and subtracting from stated consequents, being understood that if an antecedent be itself a conditional proposition, its antecedent is of the nature of a consequent” (MS 905; LoF, pp. 731-732). The latter discovery—universes in multiple dimensions—has its correlate in the idea of interpreted domains and in the modern notion of temporal logics and many-sorted quantification. It can also be seen as a development of new languages that take the role of indices in the quantifiers to be mappings from contexts to values in universes of discourse. Having in mind Mitchell’s pioneering idea of logical dimensions, Peirce goes on to mention that the study of Mitchell’s paper was for him necessary in order to break “ground in the gamma [modal logic] part of the subject” of existential graphs (MS 467; LoF, p. 332; see below). Years later, Peirce defines the term “dimension” in the Dictionary of Philosophy and Psychology by noting that it is

an element or respect of extension of a logical universe of such a nature that the same term which is individual in one such element of extension is not so in another. Thus, we may consider different persons as individual in one respect, while they may be divisible in respect to time, and in respect to different admissible hypothetical states of things, etc. This is to be widely distinguished from different universes, as, for example, of things and of characters, where any given individual belonging to one cannot belong to another. The conception of a multidimensional logical universe is one of the fecund conceptions which exact logic owes to O. H. Mitchell. Schröder, in his then second volume, where he is far below himself in many respects, pronounces this conception ‘untenable’. But a doctrine which has, as a matter of fact, been held by Mitchell, Peirce, and others, on apparently cogent grounds, without meeting any attempt at refutation in about twenty years, may be regarded as being, for the present, at any rate, tenable enough to be held. (DPP 2, p. 27)

Mitchell develops, for the first time, the idea and the notation for existential and universal quantifiers, and notices that it is by from alternations of these quantifiers that logic derives its expressive power. Peirce testifies in the same dictionary entry that placing Σ and Π in alternating orders “was probably first introduced by O. H. Mitchell in his epoch-making paper” (DPP 2, p. 650). However, being limited to monadic predicates, Mitchell’s language was deprived of some expressive power.

Having supervised and perused Mitchell’s paper, in Note B of the Studies in Logic, Peirce generalizes the groundwork Mitchell had laid on the theory of quantification. His theory of relatives adds indices as individual variables to the operators Σ and Π to denote individual objects. Relative products and relative sums are then defined as (lb)_ij = Σx(l)_ix(b)_xj and (l † b)_ij = Π_x {(l)_ix + (b)_xj}, thus becoming species of existential and universal quantification: the lover of a benefactor is “a particular combination, because it implies the existence of something loved by its relate and a benefactor of its correlate.” The lover of everything but benefactors is “universal, because it implies the non-existence of anything except what is either loved by its relate or a benefactor of its correlate” (Peirce 1883, p. 189). Peirce had already had the relative sum at his disposal and the idea of it expressing the non-existence of exceptions naturally led to its dual of the existential quantification. Towards the end of Note B Peirce writes something is a lover of something as Σ_i Σ_aj l_ij, everything is a lover of something as Π_i Σ_j l_ij, there is something which stands to something in the relation of loving everything except benefactors of it as Σ_i Σ_k Π_j (l_ij + b_jk), and so on. Taking α to denote accuser to___of___, ε excuser to___of___, and π preferrer to___of___, Π_i Σ_j Σ_k (α)_ijk (ε_jki + π_kij) means that “having taken any individual i whatever, it is always possible so to select two, j and k, that i is an accuser to j of k, and also is either excused by j to k or is something to which j is preferred by k” (Peirce 1883, p. 201). The phrasing Peirce uses here (such as “having taken any individual”, “it is always possible so to select”) is indicative of a new semantic treatment of quantifiers and sequences of quantifiers which he goes on to pursue further in later papers, and which in Hilpinen (1982), Hintikka (1996) and Pietarinen (2006) have shown to agree with game-theoretic semantics. Interestingly, Peirce’s examples are all stated in prenex normal form, which highlights the idea of sequences of dependent quantifiers. Peirce’s quantifiers bind variables ranging over interpreted domains. In this 1883 paper, he provides the basic inference rules, such as Σ_i Π_j   Π_j Σ_i, for manipulating the strings of quantifiers. The language is not inductively defined, it lacks notation for functions, and it uses neither constants nor an equality sign, but in other respects it coincides with that of first-order predicate calculus.

Alfred Tarski’s summary concerning Peirce’s contributions to the logical theory of relatives is illuminating:

[t]he title of creator of the theory of relations was reserved for C. S. Peirce. In several papers published between 1870 and 1882, he introduced and made precise all the fundamental concepts of the theory of relations and formulated and established its fundamental laws. Thus Peirce laid the foundation for the theory of relations as a deductive discipline; moreover he initiated the discussion of more profound problems in this domain. In particular, his investigations made it clear that a large part of the theory of relations can be presented as a calculus which is formally much like the calculus of classes developed by G. Boole and W. S. Jevons, but which greatly exceeds it in richness of expression and is therefore incomparably more interesting from the deductive point of view. (Tarski 1941, p. 73)

However, it is his 1885 theory of quantification that Peirce calculated to settle the problems of deductive logic and logical analysis in a way that decidedly brought him beyond the algebraic approach to the logic of relatives.

1885: Peirce’s logic of quantifiers comes to a full blossom in his paper, written in summer 1884, “On the Algebra of Logic: A Contribution to the Philosophy of Notation”, and published in the American Journal of Mathematics in the following year (Peirce 1885). This massive paper defies any condensed exposition; but in summary, it contains Peirce’s “five icons of algebra” as a system of natural deduction based on introduction and elimination rules. Peirce had repeatedly stated that his having supervised and examined Mitchell’s paper was essential in order to arrive at the idea of these two basic operations. There is an abundant use of truth-functional propositions and an anticipation of the truth-table method to test tautologies. One of the examples comes close to the tableaux method, later proposed by Evert Beth and Jaakko Hintikka, that spells out a systematic search for counter-models by deriving contradictions from the negations of the formula to be proved. In order “to find whether a formula is necessarily true,” he says, “substitute f and v for the letters and see whether it can be supposed false by any such assignment of values” (Peirce 1885, p. 224; Pietarinen 2006; Anellis 2012a).

When he moves on to the first-order (“first-intentional”) logic, Peirce seeks to devise a notation that is as iconic as possible, building on his semiotic insight that the more iconic a notation is, the better suited it would be for logical analysis. He starts by using “Σ for some, suggesting a sum, and Π for all, suggesting a product” (1885, p. 180). Once again, Peirce credits Mitchell, now for the method of separating the “quantifying part”—which he later termed the “Hopkinsian” to honour its place of discovery (MS 515, 1902)—from the pure Boolean expression: the latter refers to an individual by its use of indices (like pronouns in language) while the former states what that individual is. The quantifying operators are, however, “only similar to a sum and product,…because the individuals of the universe may be denumerable” (1885, p. 180). Peirce’s consideration illustrates similar lines of thought as those that prompted Löwenheim to formulate his famous 1915 theorem: if a first-order sentence has a model then it has also a countable model, or generally, models for sets of formulas being of some cardinality imply models of some other infinite cardinality (Badesa 2004). (Associating infinite products and sums with conjunctions and disjunctions was what Wittgenstein took to be his own biggest mistake in logic.) The 1885 paper continues introducing rules for quantifier manipulation, including “putting the Σs to the left, as far as possible” (1885, p. 182), which is a prelude to the idea of Skolem normal forms. One could say that it is the sequences of quantifiers, especially those of dependent quantifiers, that contribute to a linear logic notation as being maximally iconic, and that it is the prenex and Skolem normal forms that bring out maximal analyticity which logical icons exploit. The 1885 paper then presents many examples drawn from natural language to be analyzed logically with this new notation. The paper also extensively deals with issues having to do with the representation of mathematical notions such as one-to-one correspondence and identity in the second-intentional logic, developed in the third part of the paper, and in which variables range over relations. There is an early attempt at axiomatizing set theory as well as some profound philosophical consideration on the possibility of developing a “method for the discovery of methods in mathematics,” which is to be based on these new approaches that aim at formulating a general theory of deductive logic.

Thanks to the volumes that have appeared in the Chronological Edition of the Writings between 1982 and 2010, and which have covered Peirce’s work up to 1892, these earlier phases of Peirce’s deductive logic are now relatively well understood. But the research from that point on has been hampered by the unavailability of systematic editions concerning Peirce’s later logical writings. Yet the mid-1890s marks only the beginnings of a new and by far the most productive era in Peirce’s logical investigations, which were to last until the last months of his life. This situation has by no means been adequately reflected in the secondary literature.

Although Peirce would continue his investigations on the algebra of logic throughout his life, the algebraic element would no longer assume a central position in his overall oeuvre:

In 1895 Schröder published the third huge volume of his logic, which consisted mainly of a vast elaboration in detail of the logical algebra of my Note B. That I never considered that algebra to be a great masterpiece is sufficiently shown by my giving my exposition of it no other title than “Note B.” The perusal of Schröder’s book convinced me that the algebra was not what was wanted, and in the Monist for January 1897 I produced a system of graphs which I now term Entitative Graphs. I shortly after abandoned that and took up Existential Graphs” (MS 467; LoF, p. 332).

Although it was Schröder’s elaboration that was to influence the works of the early model theorists such as Löwenheim and Skolem (Brady 2000), it was Peirce’s and Mitchell’s works that germinated the concept of first-order statements being true-in-a model (Pietarinen 2006; Bellucci & Pietarinen 2015a). Moreover, Peirce’s incessant hunt for new logical notations and methods was much more ambitious and philosophical than his early algebraic investigations revealed.

What was to take the place of algebra were the ideas that emerged from diagrammatic, iconic and topological considerations on logical representation and reasoning. These considerations were at first prompted by logical analogues to algebraic invariants in chemistry first developed by Peirce’s John Hopkins colleague J. J. Sylvester (1878) and investigated in Kempe (1886). Peirce was initially fascinated by the analogy in which a chemical atom is like a relative “in having a definite number of loose ends or “unsaturated bonds”, corresponding to the blanks of the relative” (CP 3.469, 1897). But the continual search for better and better notations for the overall purposes of logical analysis would also reveal the reasons why Peirce had to overcome this analogy between logic and chemistry.

Peirce’s theory of Existential Graphs (EGs), first conceived in summer 1896 and developed in subsequent years (for example Peirce 1897, 1906), was in part motivated by his need to respond to the expressive insufficiency and lack of analytic power of the systems described in his Note B, which he later termed the algebra of dyadic (dual) relatives, and in the 1885 general (universal) algebra of logic. The analytic power comes from the idea of subsuming what the algebraic operations do when composing concepts under one mode of composition. This composition of concepts is effected in the theory of EGs by the device of ligatures. A ligature is a complex line, composed of what Peirce terms the lines of identities, which connects various parts and areas of the graphs: [See e.g. Zeman 1964; Roberts 1973; Shin 2002; Dipert 2006; Pietarinen 2005, 2006, 2011, 2015a.]

Fig. 1 

Fig. 2 

Fig. 3

The meaning of these lines is that the two or more descriptions apply to the same thing. For example, in Figure 2 there is a horizontal line attached to the predicate term “is obedient.” It means that “something exists which is obedient.” There is also another line which connects to the predicate term “is a catholic,” and that composition means that “something exists which is a catholic”, which is equivalent to the graph-instance in Figure 3. Since in Figure 1 these two lines are in fact connected by a continuous line, the graph-instance in Figure 1 means that “there exists a catholic which is obedient,” that is, “there exists an obedient catholic.” Ligatures, representing continuous connections composed of two or more lines of identities, stand for quantification, identity and predication, all in one go.

These EGs are drawn on a sheet of assertion that represents what the modeller knows or what mutually has been agreed upon to be the case by those who undertake the investigation of logic. The sheet thus represents the universe of discourse. The graph that is drawn on the sheet puts forth an assertion, true or false, that there is something in the universe to which it applies. This is the reason why Peirce terms these graphs existential. Drawing a circle around the graph, or alternatively, shading the area on which the graph-instance rests, means that nothing exists of the sort of description intended. In Figure 4, the assertion “something is a catholic” is denied by drawing an oval around it and thus severing that assertion from the sheet of assertion:

Fig. 4

The graph-instance depicted in Figure 4 thus means that “something exists that is not catholic.”

Peirce aimed at a diagrammatic syntax that would use a minimal number of logical signs but at the same time be maximally expressive and as analytic as possible. His ovals, for instance, have different notational functions: “The first office which the ovals fulfill is that of negation. […] The second office of the ovals is that of associating the conjunctions of terms. […] This is the office of parentheses in algebra” (MS 430, pp. 54-56, 1902). The ovals are thus not only the diagrammatic counterpart to negation but also serve to represent the compositionality of a graph-formula. He held (MS 430, 1902; MS 670, 1911) that a notation that does not separate the sign of truth-function from the representation of its scope is more analytic than some other notation, such as that of an ordinary “symbolic” language, where such a separation is needed to force a one-dimensional notation. The role of ovals as denials is in fact a derived function from more primitive considerations of inclusion and implication (Bellucci & Pietarinen 2015; MS 300, 1908).

As to expressivity, Peirce had already recognized that the notion of dependent quantification was essential in any system expressive enough to serve the purposes of logical analysis of any assertions. The nested system of ovals in EGs effectuate this in a natural way, much in contrast to algebras that resort to an explicit use of parentheses and other punctuation devices. For example, the graph in Figure 5 means that “Every Catholic adores some woman.” The graph in Figure 6 means that “Some woman is adored by every Catholic.” Peirce notes that the latter asserts more since it states that all Catholics adore the same woman, whereas the former allows different Catholics to adore different women.

Fig. 5        

Fig. 6  

The graph in Figure 7 means that “anything whatever is unloved by something that benefits it,” that is, “everything is benefitted by something or other that does not love it”:

Fig. 7

Lastly, Figure 8 provides an example of a very complex graph taken from MS 504 (1898):

 

Fig. 8

Peirce provided the meaning in natural language this way:

Every being unless he worships some being who does not create all beings either does not believe any being (unless it be not a woman) to be any mother of a creator of all beings or else he praises that woman to every being unless to a person whom he does not think he can induce to become anything unless it be a non-praiser of that woman to every being.

It is on the level of semantics where the power of dependent quantification comes to the fore. Peirce carried the semantics out in terms of defining the basics of what today is recognized as two-player zero-sum semantic games. For Peirce these games take place between the Graphist/Utterer and the Grapheus/Interpreter. [Sometimes, especially in Peirce’s model-building games, these roles split so that the Grapheus and the Interpreter are playing separate roles, see Pietarinen 2013.] Peirce’s semantic games were not limited to EGs; he applied the same idea also to interpret quantificational expressions and connectives in his general algebra of logic.

It speaks to the superiority of EGs over algebraic systems that in it deduction, following Mitchell’s work, is reduced to a minimum number of permissive operations. Peirce termed these operations illative rules of transformation, and in effect they consist only of two: insertions (permissions to draw a graph-instance on the sheet of assertion) and erasures (permissions to erase a graph-instance from the sheet). More precisely, the oddly enclosed areas of graphs (areas within an odd number of enclosures) permit inserting any graph on that area, while evenly enclosed areas permit erasing any graph from that area. A copy of a graph-instance is permitted to be pasted on that same area or any area deeper within the same nest of enclosures (the rule of iteration), and a copy thus iterated is permitted to be erased (the converse rule of deiteration). An interpretational corollary is that the double enclosure with no intervening graphs in the middle area can be inserted and erased at will.

A more detailed exposition of these illative rules of transformation would need to show their application to quantificational expressions, namely applying insertions and erasures to ligatures. A flavor of such proofs is given by inspecting the Figures 1, 2 and 3: an application of a permissible erasure on the line of identity in Figure 1 amounts to the graph-instance in Figure 2, and that another application of a permissible erasure on the upper part of the graph-instance in Figure 2 amounts to the graph-instance depicted in Figure 3. Thus what is represented in Figure 2 is a logical consequence of the graph-instance in Figure 1, and what is represented in Figure 3 is a logical consequence of the graph-instance given in Figure 2.

Roberts (1973) was the first to prove that these transformation rules, first given by Peirce in 1898, form a semantically complete system of deduction. Roberts did not mention, however, that Peirce had demonstrated their soundness in 1898 and again in 1903 and that he had argued for their completeness in terms of what he termed the “perfect archegetic rules of transformation” in the unpublished parts of the Syllabus for the Lowell Lectures that Peirce delivered in 1903.

The polarity of the outermost ends or portions of ligatures determines whether the quantification is existential (that end or portion resting on even/positive areas) or universal (if it rests on odd/negative area). Unlike in the Tarski-type semantics, but just as what happens in game-theoretic semantics, the preferred rule of interpretation of the graphs is what Peirce termed “endoporeutic”: one looks for the outermost portions of ligatures on the sheet of assertions first, assigns semantic values to that part, and then proceeds inwards into the areas enclosed with ovals. In non-modal contexts, ligatures are not well-formed graphs because they may cross the enclosures.

The diagrammatic nature of EGs consists in the iconic relationship between forms of relations exhibited in the diagrams and the real relations in the universe of discourse. Peirce was convinced that, since these graphical systems exploit a proper diagrammatic syntax, they—together with any of their extensions that would be introduced to cover modalities, non-declarative expressions, speech acts, and so forth—can express any assertion, however intricate. Guided by the precepts laid out by the diagrammatic forms of expression, and together with the simple illative permissions by which deductive inference proceeds, the conclusions from premises can be “read before one’s eyes”; these graphs present what Peirce believed is a “moving picture of the action of the mind in thought” (MS 298; LoF, p. 655; late 1906-1907).

If upon one lantern-slide there be shown the premisses of a theorem as expressed in these graphs and then upon other slides the successive results of the different transformations of those graphs; and if these slides in their proper order be successively exhibited, we should have in them a veritable moving picture of the mind in reasoning. (MS 905; LoF, p. 723; late 1907-1908)

The theory of EGs that uses only the notation of ovals and the spatial notion of juxtaposition of graphs is termed by Peirce the Alpha part of the EGs, and it corresponds to propositional logic. The extension of the alpha part with ligatures and rhemas (also termed spots by Peirce) gives rise to the Beta part, and it corresponds to fragments of first-order predicate calculus. What Peirce termed the Gamma part was a boutique of a number of developments, including various modalities such as metaphysical, epistemic and temporal modalities, as well as extensions of such graphs with ligatures. In Peirce’s writings, there are developments of graphical systems for higher-order logics and abstraction (Peirce’s “logic of potentials”), the logic of collections, and investigation of meta-logical expressions that use the language of graphs to talk about notions and properties of the graphs in that language (Peirce’s “graphs of graphs”). He mentions late in 1911 that the Delta part would also need to be added, most likely because of the ever-expanding systems that had been mushrooming in the Gamma part.

Peirce’s further contributions to deductive logic. While the development of the theory of the logic of existential graphs was his chief contribution, Peirce’s other contributions to the development of modern logic were numerous. In the Logic Notebook (1909) he defined a number of operations for three-valued logic and gave semantics for them in terms of defining truth-tables for such new connectives (Fisch & Turquette 1966). In these systems, which he called triadic logic, the third value is “the limit” between “true” and “not true,” and it applies to what Lane (1999) has identified as boundary-propositions: in Peirce’s terms, boundary-propositions have “a lower mode of being” which can “neither be determinately P, nor determinately not-P,” but are “at the limit between P and not P” (MS 399, p. 344r, 1909). Peirce defined several connectives to realize this idea in alternative ways, including four one-place connectives which were later reinvented as strong negation, two Post negations and the Tertium function, as well as six two-place connectives, including one that pertains to the logic of ordinary discourse.

Generally, Peirce divided deduction in two: on the one hand, deduction is either necessary or probable (deductive reasoning about probabilities), and on the other hand, deduction is either corollarial or theorematic. Corollarial deduction is reasoning “where it is only necessary to imagine any case in which the premisses are true in order to perceive immediately that the conclusion holds in that case.” Theorematic deduction “is deduction in which it is necessary to experiment in the imagination upon the image of the premiss in order from the result of such experiment to make corollarial deductions to the truth of the conclusion” (MS L 75, 1902). He considered the theorematic/corollarial distinction his first real discovery in the philosophy of mathematics. Theorematic deductions can be of different kinds and degrees of complexity, and he took the classification of various types of theorematic deductions to be of the utmost value in the theory of logic (MS 617; MS 201; Peirce 1908). Stjernfelt (2014) proposes a new classification of theorematic inferences. Hintikka (1980) has argued that reasoning is theorematic if it increases the number of layers of quantifiers, and that an argument is the more theorematic the more new individuals are used in it (see also Ketner 1985; Zeman 1986; Hoffmann 2010).

Zooming into some of the details of Peirce’s systems of logic, including those of diagrammatic logics, one finds a treasury of developments the meaning of which is only beginning to unravel over a century later (Bellucci, Pietarinen & Stjernfelt 2014). In 1886, Peirce suggested in a letter to his former student Allan Marquand, who had designed mechanical logic machines for syllogistic reasoning, that “it is by no means hopeless to expect to make a machine for really difficult problems. But you would have to proceed step by step. I think electricity would be the best thing to rely on” (L 269, Peirce to Marquand, 30 December, 1886; W5, p. 422). He then showed how switching circuits can be connected serially and in parallel, noting that these two configurations correspond to multiplication (algebraic sum as logical disjunction) and addition (algebraic product as logical conjunction) in logic. In addition to the idea of real logical machines running on electricity, Peirce was also very interested in the philosophical question of whether living intelligence is required in performing deductive reasoning, an issue of continuing relevance to A.I. and to the prospects of automatized theorem proving. In 1902 he developed two notational systems with sixteen binary connectives to map out all of the possible truth functions of the binary propositional calculus (Clark 1997; Zellweger 1997). According to Max Fisch, “No other logician compares with Peirce in attention to systems of notation and to sign-creation” (Fisch 1982, p. 132). Peirce’s work on these notational systems foresaw geometrical structures of logic, including spaces revealed by the study of the geometry of negation and other operators. Based on Peirce’s conceptual and sign-theoretic considerations, an apparatus for displaying and performing a complete set of the sixteen binary connectives in a two-valued propositional logic was patented in the U.S.A. in 1981 by Shea Zellweger.

Peirce also worked on early forms of topology (Havenel 2010), including studies on what might be recognized as rudimentary versions of homologies and knots, in his attempts to find pathways not only to logical issues but also to questions in philosophy of mathematics (Murphey 1961; Moore 2010).

Moreover, his diagrammatic systems of modal logic included suggestions for defining several types of multi-modal logics in terms of tinctures of areas of graphs. Tinctures enable logic to assert, among others, modalities including necessities and metaphysical possibilities, and so call for changes in the nature of how the corresponding logics behave, including the identification of individuals at the presence of multiple universes of discourses. He defined epistemic operators in terms of subjective possibilities, which, just as in contemporary epistemic logic, are epistemic possibilities defined as duals of knowledge operators. He analyzed the meaning of identities between actual and possible objects in quantified multi-modal logics. As an example, the two graphs given in Figures 9 and 10 that he presented in a 1906 draft of the Prolegomena paper (MS 292) illustrate the nature of the interplay between epistemic modalities and quantification.

Fig. 9

Fig. 10

The graph in Figure 9 is read “There is a man who is loved by one woman and loves a woman known by the Graphist to be another.” The reason is this. In the equivalent graph depicted in Figure 10 the woman who loves is denoted by the name A, and the woman who is loved is denoted by the name B. The shaded area is a tincture that refers to the modality of subjective possibility. Thus the graph in Figure 10 means that it is subjectively impossible, by which Peirce means that “it is contrary to what is known by the Graphist” (= the modeller of the graph), that A should be B. In other words, the woman who loves and the woman who is loved (whom the graph does not assert to be otherwise known to the Graphist) are known by the Graphist not to be the same person.

Peirce’s work highlights the philosophical significance of ideas that were rediscovered later and largely after the mid-twentieth century, though often in different clothes: in Peirce’s largely unpublished works one finds him addressing such topics as multi-modal logics and possible-worlds semantics, quantification into modal contexts, cross-world identities (in MS 490 he termed these special relations connecting objects in different possible worlds (for references, see Pietarinen 2005), cumulative and branching quantifiers (the latter being related to independence-friendly logic, see Pietarinen 2015b), as well as what later on became known as “Peirce’s Puzzle” (Dekker 2001; Hintikka 2011; Pietarinen 2015b), namely the question of the meaning of indefinites in conditional sentences, which Peirce himself analyzed in quantified modal extensions of EGs.

Far from merely anticipating later discoveries, thus, Peirce’s logic in general puts what later on came to be explored in the fields of philosophical logic, formal semantics and pragmatics, philosophy of logic, mathematics, mind and language, cognitive and computing sciences, and history and philosophy of science, into a systematic logico-semeiotic perspective. From time to time, his ideas even surpass stagnated contemporary discussions, especially in the philosophy of logic and mathematics. [See for example Bellucci, Pietarinen & Stjernfelt 2014; Lupher & Adajian 2015; Sowa 2006; Zalamea 2012a; Zalamea 2012b; PM. For further details on Peirce’s deductive logic, see the collection of Houser and others, eds. 1997. Hilpinen 2004 provides a useful overview.]

iv. Inductive Logic

In 1865 (W1, pp. 263-64) Peirce defines induction as inference from Case and Result to Rule. Its general form is:

Case: M₁ M₂ M₃ M₄  are S
Result: M₁ M₂ M₃ M₄  are P
Rule: Therefore, all S are P.

A certain number of objects (M₁ M₂ M₃ M₄ ), known to belong to a certain class (S), possess a certain character (P); therefore, it can be infered inductively that the whole class S possesses that character. I notice that neat, swine, sheep, and deer, which I know are cloven-hoofed, are herbivores. Therefore, I infer inductively that all cloven-hoofed animals are herbivores.

Later, Peirce came to divide induction into three principal kinds. Crude induction is the lowest form of induction, based upon the common practice of generalizing about future events on the ground of previous experience. For example, “No instance of a genuine power of clairvoyance has ever been established: So I presume there is no such thing”; “cancer is incurable, because every known case has proved to be so.” Its general form is “All observed As are B. Therefore, All As are B.” It is the weakest form of inductive reasoning in terms of security. Qualitative induction is the intermediate kind in terms of security. It is what Peirce had earlier called hypothetical reasoning or abduction. It consists in testing a hypothesis by sampling the possible predications that may be made on the basis of it (CP 7.216). Qualitative abduction is reasoning that tests hypotheses already formulated. It should not be confused with abduction, which is reasoning that originates new hypotheses. Quantitative induction is the highest form of induction in terms of security. It investigates the real probability that a member of a certain class will have a certain character. Its procedure consists in finding a representative sample of the class and noting the proportion of them that possess the character P. Then, the inference is drawn that the proportion holds for the whole class. Its logical form is

S₁ S₂ S₃ S₄ and so forth, are taken at random from the Ms.
The proportion p of S₁ S₂ S₃ S₄ is P.
Hence, probably and approximately, the same proportion p of the Ms are P.

The inversion of a quantitative induction gives us a statistical deduction, whose form is

The proportion p of the Ms are P.
S₁ S₂ S₃ S₄ and so forth, are taken at random from the Ms.
Hence, the proportion p of them is P.

Although crude, qualitative, and quantitative induction are different in kind, their justification is, according to Peirce, the same:

The validity of Induction consists in the fact it proceeds according to a method which though it may give provisional results that are incorrect will yet if steadily pursued, eventually correct any such error. […] all Induction possesses this kind of validity, and […] no Induction possesses any other kind that is more than a further determination of this kind. (MS 293, 1907)

The validity rests upon induction being self-corrective: in the long run induction is bound to lead us ever closer to the correct representation of reality. Its validity is therefore linked to esse in futuro, to the possibility of self-correction of the very method itself. Any actual induction that is performed may well be wrong or partly wrong, but it remains valid because its leading principle is valid, that is, is conducive to truth in the long run.

Peirce’s polemic target was a theory that would make the validity of induction rest upon some principles of uniformity or regularity in nature. According to Peirce, that was how John S. Mill and Philodemus of Gadara (ca.110–ca.30 B.C.E.) attempted, unsoundly, to justify induction. Of the several objections that Peirce raised from time to time against this way of justifying induction, one is worth reporting. Mill argues that a universe without any regularity is imaginable, and that in that universe inductions would be invalid. But the absence of uniformity, that is, the absence among certain objects S of the character P, is itself a uniformity. No universe is imaginable in which induction is not valid. According to Peirce, “even if nature were not uniform, induction would be sure to find it out, so long as inductive reasoning could be performed at all” (CP 2.775).

Cheng 1969, Goudge 1946, Merrill 1975 and Forster 1989 provide further details on Peirce’s inductive logic.

c. Methodeutic

The third branch of Peirce’s logic is methodeutic, which he also called speculative rhetoric. He defined it to be “the study of the proper way of arranging and conducting an inquiry” (MS 606, p. 17), depicting it as being “not so exact in its conclusions as is critical logic” (MS L 75, 1902) and as involving “certain psychological principles” (MS 633, 1909). But it nevertheless is a theoretical study and not an art. Methodeutic is based upon critics, and considers not what is admissible (logical validity) but what is advantageous (logical economy). It is a “theoretical study of advantages” (MS L 75, 1902).

Abduction is of special interest to methodeutic, because abduction is the only mode of inference that can initiate a scientific hypothesis. But being justifiable is not a sufficient property of good hypotheses:

Any hypothesis which explains the facts is justified critically. But among justifiable hypotheses we have to select that one which is suitable for being tested by experiment. (MS L 75, 1902)

Among critically equivalent hypotheses (that is, hypotheses that explain the facts), one should be able to select for testing those that are capable of experimental verification. [Being capable of experimental verification is in Peirce’s philosophy of science to be conceived in the wide sense, including mental experimentation and imaginative activities in our thoughts (Bellucci & Pietarinen 2015b). It is not the same thing as the empirical verification criterion of the positivists, which Peirce often criticized.] This is the core of Peirce’s philosophy of pragmati(ci)sm, which teaches that the whole meaning of a hypothesis is in its conceivable practical (that is, experienceable) effects; pragmaticism therefore is “nothing else than the question of the logic of abduction” (CP 5.196, 1903).

In turn, among “pragmatistically” equivalent hypotheses (that is, hypotheses that are capable of experimental verification) one should select those that in the sense of Peirce’s economy of research are the cheapest ones. His argument for the economic character of methodeutic is roughly as follows: the logical validity of abduction presupposes that nature be in principle explainable. This means that to discover is simply to expedite an event that would sooner or later occur. Therefore, the real service of a logic of abduction is of the nature of an economy. Economy itself depends on three factors: cost (of money, time, energy, thought), the value of the hypothesis itself, and its effects upon other projects and hypotheses (MS L 75, 1902; MS 690, CP 7.164-231, 1901).

Although primarily concerned with abduction, methodeutic also has an interest in deduction and induction. Theorematic deductions (see §2.b.iii) manifest peculiar logical steps that are abductive rather than deductive. In order to overcome the lack of critical instruments for the investigation of those steps, Peirce emphasizes the need to have an inventory and logical classification of valuable steps in the history of mathematics which would become part of a methodeutic of necessary reasoning (Peirce 1908, MS 200-201).

Peirce also considered the study of the properties of different logical and mathematical notations and symbolisms as belonging to the department of methodeutic. In this respect, he coined the maxim of the ethics of terminology and of notation:

The person who introduces a conception into science has both the right and the duty of prescribing a terminology and a notation for it; and his terminology and notation should be followed except so far as it may prove positively and seriously disadvantageous to the progress of science. If a slight modification is sufficient to remove the objection, a much greater one should be avoided. (MS 530, 1902)

Induction too has its methodological side. The methods of the three classes of inductions are all based on “samples,” and they all presuppose that the samples are representative of the class from which they are sampled: methodeutic should therefore teach methods of producing fair samplings. His own experimental work is exemplary in that it develops new statistical methods to ascertain that truly randomized samples are achieved and that fully blinded testing conditions are secured. He emphasizes the method of predesignation, which prescribes that the characters concerning which class is sampled are to be chosen beforehand so that the sampler would not be influenced by any agreement among the members of the sample (see Goudge 1946).

Other things Peirce considers to pertain to methodeutic include the principles of definition, the methods of classification in general, and the doctrine of the clearness of ideas.

Peirce’s logic, conceived as semeiotic, characterizes a broad philosophical, methodological and scientific area of investigation. Although the present article has exposed a number of developments in Peirce’s studies in deductive logic, the deductive part is only a fraction of the wider project of semeiotic, the theory and philosophy of signs, and the logic of science. From a contemporary perspective, deductive, formal, and mathematical logic may have become the mainstay of logic as such, but for Peirce other areas of logic, such as speculative grammar and the critics and methodeutic of abduction and induction, are at least as important as the deductive part of logic.

3. Peirce’s Logic in Historical Perspective

Peirce’s algebraic work in formal logic influenced Ernst Schröder (1841–1902), who drew heavily upon Peirce’s work in the three volumes of his Vorlesungen über die Algebra der Logik (Schröder 1890–1905). Peirce also successfully initiated a school in logic during his Johns Hopkins period (1879–1884), whose most evident manifestation is the richness and originality of the papers contained in the Studies in Logic (Peirce 1883). For the main part of his career, Peirce had been in contact and correspondence with the most prominent logicians, mathematicians and scientists of the time, and his works appeared in leading scientific journals and proceedings.

All these facts notwithstanding, the reception of Peirce’s deductive logic has been strangely erratic, even in the early days. Especially in his later period (1892–1914), Peirce worked virtually alone in an adverse environment and without much intellectual and material support. It is true that the recognition of his contributions has suffered from a long-term unavailability of his vast Nachlass of over 100,000 surviving pages of manuscripts and correspondence. In some cases at least, the explanation may be found in the unprecedented technical and mathematical standard and rigor characterizing his work. But what is certainly a chief reason behind the general neglect of Peirce’s logic is the rise, at the end of the 19^th century, of what has later been named the Frege-Russell tradition in logic.

The historiography of logic seems to have accepted the idea, initially promoted by Bertrand Russell and subsequently canonized by historian of logic Jean van Heijenoort (1912–1986), of a “Fregean revolution” in logic. In this narrative, modern mathematical logic (also deceptively called symbolic logic) has replaced traditional or Aristotelian logic. According to such a picture, the work of the “algebraists,” (including Boole, De Morgan, Peirce and Schröder) belongs to the pre-Fregean logical paradigm.

Anellis (2012b) identified seven features of such a “Fregean” revolution: (1) A propositional calculus with a truth-functional definition of connectives, especially the conditional. (2) Decomposition of propositions into function and argument instead of into subject and predicate. (3) A quantification theory, based on a system of axioms and inference rules. (4) Definitions of infinite sequence and natural number in terms of logical notions (that is the logicization of mathematics). (5) Presentation and clarification of the concept of a formal system. (6) Relevance and use of logic for philosophical investigations (especially for philosophy of language). (7) Separating singular propositions, such as “Socrates is mortal” from universal propositions such as “All Greeks are mortal.” All these characteristics, Anellis argued, can be found in Peirce’s work, which therefore falls within the parameters of van Heijenoort’s conception of the Fregean revolution and the definition of mathematical logic. One also needs to remember that there are many characteristics of Peirce’s logic and philosophy of logic, vitally important to his logical vision, that either add to, modify or reject those that have been taken to typify the Fregean tradition. What may be ill-named as a Fregean revolution is found in a different, and perhaps more penetrating and consequential shape in Peirce’s work.

Peirce and Frege discovered quantificational theory around the same time (1879–1883). Frege’s work was at the time largely ignored. Russell credited Frege a posteriori with having founded modern logic in the Begriffsschrift (Frege 1879). However, while Frege’s notation was hardly ever used, the Peirce-Schröder notation was largely adopted by others. The important results of Löwenheim and Skolem at the beginning of the 20^th century were presented in the Peirce-Schröder system without any trace of influence by Frege or Russell. Peano’s use of the existential and universal quantifiers derives from Schröder and Peirce, not from Frege. Unlike Frege, Peirce recognized the utmost importance of dependent quantifiers and experimented with that idea in various ways in the algebra of logic and in existential graphs, and proposed new systems and dimensions of quantification that involve independent quantification (MS 430). Peirce’s overall influence upon the development of modern logic was considerable though its nature and scope had remained ill-understood for a long time (Putnam 1982; Dipert 1995; Pietarinen 2015a).

Peirce’s philosophy of logic had no better fate. Aside from Josiah Royce and especially Lady Victoria Welby with whom Peirce corresponded on the logic of signs and semiotics during 1903-1910, Peirce’s radical idea of “logic as semeiotic” largely passed by unnoticed. In the 1930s Charles Morris took, misleadingly, Peirce’s trivium of speculative grammar, critics and methodeutic to correspond to the division of the study of language into syntax, semantics, and pragmatics (Morris 1938, pp. 21-22). Carnap (1942) adopted Morris’ trichotomy and made it popular. Peirce’s philosophy of signs has since been studied by semioticians, led by the pioneering explorations by Roman Jakobson and Umberto Eco (see Eco 1975; Jakobson 1977; Eco 1984). Other aspects of Peirce’s philosophy of logic, such as the distinction between corollarial and theorematic deduction, his ideas on diagrammatic reasoning, and the evolution of new logical notations and meanings, is gaining the interest, not only of logicians and historians of logic, but also of philosophers of science, cognitive scientists as well as many scholars, scientists, artists and practitioners looking for ways to overcome boundaries of narrow conceptions of logic, reasoning and representation, as well as the outdated 20^th-century scientific methodologies that have characterized their respective fields. [See for example the 2014 Peirce Centennial Conference at Lowell as well as the Applying Peirce Conference series at Helsinki in 2007 and 2014, which have brought together scholars and scientists interested in Peirce’s thought virtually on any field of science.]

From the perspectives of the history and philosophy of modern logic, it may not be entirely right to talk in strict terms about the two traditions in logic, namely those of the algebraic and the symbolic ones. On the one hand, Peirce’s line of work in the algebra of logic led to the invention of a spectrum of methods in the semantic and model-theoretic tradition while the logic that Schröder, for example, preferred was to quantify over the entire universe and was thus at bottom a universalist one, thereby sharing the same preference as Frege. On the other hand, Peirce’s continuous search for new notations for the purposes of logical analysis and representation made what others may have considered to be the subject of symbolic notations really the subject of diagrams and icons. Algebraic notations were for Peirce iconic and often even very graphically so. What mattered to him was to remain clear of the significations of logical signs. Logical signs were to be interpreted in proper contexts and according to the purposes of investigation at hand. Thus, Peirce’s philosophy of logic stands in stark contrast to purely formal, mathematical and proof-theoretic approaches to logic, which do not care so much for signification. Peirce should accordingly be counted in the pragmatic, rather than just the semantic, tradition in philosophy of logic and language (Pietarinen 2006; Tiercelin 1991).

The famous van Heijenoort–Hintikka distinction between “logic as calculus” and “logic as a universal medium” is nonetheless instructive here (van Heijenoort 1967; Hintikka 1997; Peckhaus 2004). According to the former view of logic as calculus, methods and languages are many, they are reinterpretable according to the context and purposes at hand, and they admit of many and varying universes as well as modal and intensional considerations. The latter, universalist position means, in contrast, that there is one logic to “rule them all,” and so our thought is bounded by what that logic can express. Peirce fits squarely into the former camp. Here again it is not that all who worked on the algebra of logic would be members of that same camp (Schröder is a counterexample), or that all of those who in the literature have been tagged as formalists would share the universalist presuppositions (David Hilbert may serve as another kind of a counterexample). It may be one of the lessons of Peirce’s pragmaticism and the methodological pluralism which he exercised in his logic that one does not fix in advance what may in the future be considered to fall within the scope of logic.

4. References and Further Reading

• Peirce’s works
• 1867. An Improvement in Boole’s Calculus of Logic. Proceedings of the American Academy of Arts and Sciences 7, pp. 249-261.
• 1870. Description of a Notation for the Logic of Relatives. Memoirs of the American Academy of Arts and Sciences 9, pp. 317-378.
• 1880a. On the Algebra of Logic.  American Journal of Mathematics 3, pp. 15–57.
• 1881. On the Logic of Number. American Journal of Mathematics 4, pp. 85-95.
• 1883 (ed.). Studies in Logic by Members of the Johns Hopkins University. Boston: Little, Brown, and Co. 1883.
• 1885. On the Algebra of Logic. A Contribution to the Philosophy of Notation. American Journal of Mathematics 7, pp. 197–202.
• 1897. The Logic of Relatives. The Monist 7, pp. 161–217.
• 1901-1902. Entries in Dictionary of Philosophy and Psychology, 3 vols, edited by Baldwin, James Mark. Cited as DPP followed by volume and page number.
• 1906. Prolegomena to an Apology for Pragmaticism. The Monist 16, pp. 492–546.
• 1908. Some Amazing Mazes. The Monist 18 (3), pp. 416-464.
• 1931–1966. The Collected Papers of Charles S. Peirce, 8 vols., ed. by Hartshorne, C, Weiss, P. and Burks, A. W. Cambridge: Harvard University Press. Cited as CP followed by volume and paragraph number.
• 1967. Manuscripts in the Houghton Library of Harvard University, as identified by Richard Robin, “Annotated Catalogue of the Papers of Charles S. Peirce,” Amherst: University of Massachusetts Press, 1967, and in “The Peirce Papers: A supplementary catalogue,” Transactions of the C. S. Peirce Society 7 (1971): 37–57. Cited as MS followed by manuscript number and, when available, page number.
• 1976. The New Elements of Mathematics by Charles S. Peirce, 4 vols., ed. by Eisele, C. The Hague: Mouton. Cited as NEM followed by volume and page number.
• 1982 – …. Writings of Charles S. Peirce: A Chronological Edition, 7 vols., ed. by. Moore, E. C., Kloesel, C. J. W. et al. Bloomington: Indiana University Press. Cited as W followed by volume and page number.
• 2010. Philosophy of Mathematics: Selected Writings, ed. by M. E. Moore, Bloomington and Indianapolis, IN: Indiana University Press. Cited as PM.
• 2015. Logic of the Future. Peirce’s Writings on Existential Graphs, ed. by A.-V. Pietarinen, Bloomington: Indiana University Press. Cited as LoF.
• Other works
• Anellis, I. 2012a. Peirce’s Truth-Functional Analysis and the Origin of the Truth Table. History and Philosophy of Logic 33, pp. 37–41.
• Anellis, I. 2012b. How Peircean was the ‘Fregean’ Revolution in Logic? arXiv:1201.0353.
• Badesa, C. 2004. The Birth of Model Theory: Löwenheim’s Theorem in the Frame of the Theory of Relatives, Princeton: Princeton University Press.
• Bellucci, F. & Pietarinen, A.-V. (2014). New Light on Peirce’s Concept of Retroduction and Scientific Reasoning, International Studies in the Philosophy of Science 28(2), pp. 1-21.
• Bellucci, F. & Pietarinen, A.-V. (2015). Existential Graphs as an Instrument of Logical Analysis. Part I: Alpha, to appear.
• Bellucci, F., Pietarinen, A.-V. & Stjernfelt, F. eds. 2014. Peirce: 5 Questions. VIP/Automatic Press.
• Boole, G. 1847. The Mathematical Analysis of Logic. Cambridge: Macmillan, Barclay, & Macmillan.
• Boole, G. 1854. An Investigation of the Laws of Thought. Cambridge: Walton & Maberly.
• Brady, G. 2000. From Peirce to Skolem. Amsterdam: Elsevier Science.
• Brent, B. 1987. Charles S. Peirce. Logic and the Classification of the Sciences, Kingston/Montreal: MacGill-Queen’s University Press
• Burch, R. W. 2011. Peirce’s 10, 28, and 66 Sign-Types: The Simplest Mathematics. Semiotica 184, pp. 93–98.
• Burks, A. W. 1946. Peirce’s Theory of Abduction. Philosophy of Science 13, pp. 301-306.
• Carnap, R. 1942. Introduction to Semantics, Cambridge, Mass: MIT Press.
• Chauviré, Ch. 1994. Logique et Grammaire Pure. Propositions, Sujets et Prédicats Chez Peirce. Histoire Epistémologie Langage 16, pp. 137–175.
• Cheng, C.-Y. 1969. Peirce’s and Lewis’s Theories of Induction, The Hague: Martinus Nijhoff.
• Clark, G. 1997. New Light on Peirce’s Iconic Notation for the Sixteen Binary Connectives. In Houser and others 1997, pp. 304-333.
• Dedekind, R. 1888. Was sind und was sollen die Zahlen. Braunschweig: Vieweg.
• Dekker, Paul 2001. Dynamics and Pragmatics of ‘Peirce’s Puzzle’, Journal of Semantics 18, pp. 211-241.
• De Morgan, A. 1847. Formal Logic. London: Taylor and Walton.
• De Morgan, A. 1860. On the Syllogism IV; and on the Logic of Relations. Transactions of the Cambridge Philosophical Society 10, pp. 331-358.
• Dipert, R. 1995. Peirce’s Underestimated Place in the History of Logic: A Response to Quine. In Ketner, K. L. ed. Peirce and Contemporary Thought. New York: Fordham University Press, pp. 32-58.
• Dipert, R. 2006. Peirce’s Deductive Logic: Its Development, Influence, and Philosophical Significance. In: Misak, C. (ed.). The Cambridge Companion to Peirce. Cambridge: Cambridge University Press, pp. 287-324.
• Eco, U. 1975. Trattato di semiotica generale. Milano: Bompiani.
• Eco, U. 1984. Semiotica e filosofia del linguaggio. Torino: Einaudi.
• Fann, K. T. 1970. Peirce’s Theory of Abduction. The Hague: Martinus Nijhoff.
• Ferriani, M. 1987. Peirce’s Analysis of the Proposition: Grammatical and Logical Aspects. In Ferriani, M. & Buzzetti, D. (eds.), Speculative grammar, universal grammar and philosophical analysis of language. Amsterdam: Benjamins, pp. 149-172.
• Fisch, M. H. 1982. The Range of Peirce’s Relevance, The Monist 65, pp. 123-141. Reprinted in Fisch 1986, pp. 422-448.
• Fisch, M. H. 1986. Peirce, Semeiotic and Pragmatism. Ed. by K. L. Ketner and C. J. W. Kloesel, Bloomington: Indiana University Press.
• Fisch, M. H. & Turquette, A. 1966. Peirce’s Triadic Logic. Transactions of the Charles S. Peirce Society 2, pp.71-85.
• Forster, P. 1989. Peirce on the Progress and Authority of Science. Transactions of the Charles S. Peirce Society 25, pp. 421–452.
• Frege, G. 1879. Begriffsschrift: eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle: Louis Nebert.
• Goudge, T. 1946. Peirce’s Treatment of Induction. Philosophy of Science 7, pp. 56-68.
• Haack, S. 1993. Peirce and Logicism: Notes Towards an Exposition. Transactions of the Charles S. Peirce Society 29, pp. 33–56.
• Havenel, J. 2010. Peirce’s Topological Concepts. In Moore 2010, pp. 283-322.
• Hilpinen, R. 1982. On C. S. Peirceʼs Theory of the Proposition: Peirce as a Precursor of Game-Theoretical Semantics. The Monist 65, pp. 182-188.
• Hilpinen, R. 1992. On Peirce’s Philosophical Logic: Propositions and Their Objects. Transactions of the Charles S. Peirce Society 28, pp. 467–488.
• Hilpinen, R. 2004. Peirce’s Logic, in Gabbay, D.M., and J. Woods. 2004. Handbook of the History of Logic. Vol. 3: The Rise of Modern Logic From Leibniz to Frege. Vol. 3. Amsterdam: Elsevier North-Holland, pp. 611-658.
• Hintikka, J. 1980. C. S. Peirce’s ‘First Real Discovery’ and Its Contemporary Relevance. Monist 63, pp. 304-315.
• Hintikka, J. 1996. The Place of C. S. Peirce in the History of Logical Theory. In J. Brunning, J. & Forster, P. eds. The Rule of Reason: The Philosophy of Charles Sanders Peirce, Toronto: University of Toronto Press, pp. 13–33.
• Hintikka, J. 1997. Lingua Universalis vs. Calculus Ratiocinator: An Ultimate Presupposition of Twentieth Century Philosophy. Dordrecht: Kluwer.
• Hintikka, J. 2011. What the bald man can tell us. In: Biletzky, A. (ed.) Hues of Philosophy: Essays in Memory of Ruth Manor. London: College Publications.
• Hoffmann, M. 2010. Theoric Transformations. Transactions of the Charles S. Peirce Society 46, pp. 570–590.
• Houser, N. 1993. On ‘Peirce and Logicism’: A Response to Haack. Transactions of the Charles S. Peirce Society 29, pp. 57–67.
• Houser, N., Roberts, D., Van Evra, J. eds. 1997. Studies in the Logic of Charles S. Peirce. Bloomington and Indianapolis: Indiana University Press.
• Jakobson, R. 1977. A Few Remarks on Peirce, Pathfinder in the Science of Language. MLN 92, pp. 1026–1032.
• Kapitan, T. 1992. Peirce and the Autonomy of Abductive Reasoning. Erkenntnis 37, pp. 1–26.
• Kapitan, T. 1997. Peirce and the Structure of Abductive Inference. In Houser and others eds. 1997, pp. 477-496.
• Kempe, A. B. 1886. A Memoir on the Theory of Mathematical Form. Philosophical Transactions of the Royal Society of London 177, pp. 1-70.
• Ketner, K. L. 1985. How Hintikka Misunderstood Peirce’s Account of Theorematic Reasoning. Transactions of the Charles S. Peirce Society 21, pp. 407–418.
• Lane, R. 1999. Peirce’s Triadic Logic Revisited. Transactions of the Charles S. Peirce Society 35, pp. 284–311.
• Lewis, C. I. 1918.  A Survey of Symbolic Logic. Berkeley: University of California Press.
• Lupher, T. and Adajian, T. eds. 2015. Philosophy of Logic: 5 Questions. Copenhagen: Automatic Press.
• Ma, Minghui & Pietarinen, A.-V. 2015. A dynamic approach to Peirce’s interrogative construal of abductive reasoning, IFCoLog Journal of Logics and their Applications, in press.
• Mannoury, G. 1909. Methodologisches und Philosophisches zur Elementar-Mathematik. Haarlem: P. Visser.
• Merrill, D. D. 1997. Relations and Quantification in Peirce’s Logic, 1870-1885. In Houser et. al. eds. 1997, pp. 158-172.
• Merrill, G. H. 1975. Peirce on Probability and Induction. Transactions of the Charles S. Peirce Society 11, pp. 90–109.
• Moore, M. ed. 2010. New Essays on Peirce’s Mathematical Philosophy. Chicago: Open Court.
• Morris, C.  W. 1938. Foundations of the Theory of Signs. In Morris, C. 1971. Writings on the General Theory of Signs. The Hague: Mouton.
• Murphey, M. G. 1961. The Development of Peirce’s Philosophy, Cambridge, Mass: Harvard University Press, 2^nd ed. 1993, Indianapolis: Hackett.
• Paavola, S. 2004. Abduction as a Logic and Methodology of Discovery: The Importance of Strategies. Foundations of Science 9, pp. 267–283.
• Peano, G. 1889. Arithmetices Principia. Nova Methodo Exposita. Torino: Bocca.
• Peckhaus, V. 2004. Calculus Ratiocinator vs. Characteristica Universalis? The Two Traditions in Logic, Revisited. History and Philosophy of Logic 25, pp. 3-14.
• Peirce, B. 1870. Linear Associative Algebra. Litographated ed., Washington D.C.
• Pietarinen, A.-V. 2005. Compositionality, Relevance and Peirce’s Logic of Existential Graphs. Axiomathes 15, pp. 513-540.
• Pietarinen, A.-V. 2006. Signs of Logic: Peircean Themes on the Philosophy of Language, Games and Communication. Dordrecht: Springer.
• Pietarinen, A.-V. 2011. Existential Graphs: What a Diagrammatic Logic of Cognition Might Look Like. History and Philosophy of Logic 32, pp. 265–281.
• Pietarinen, A.-V. 2013. Logical and Linguistic Games from Peirce to Grice to Hintikka (with comments by J. Hintikka). Teorema 33, pp. 121-136.
• Pietarinen, A.-V. 2015a. Exploring the Beta Quadrant. Synthese 192, pp. 941-970.
• Pietarinen, A.-V. ed. 2015b. Two Papers on Existential Graphs by Charles S. Peirce: 1. Recent Developments of Existential Graphs and their Consequences for Logic (MS 498, 499, 490, S-36, 1906), 2. Assurance through Reasoning (MS 669, 670, 1911). Synthese 192, pp. 881-922.
• Pietarinen, A.-V. & Bellucci, F. 2015a. Habits of Reasoning: On the Grammar and Critics of Logical Habits. In D. E. West & M. Anderson eds. Consensus on Peirce’s Concept of Habit: Before and Beyond Consciousness. Dordrecht: Springer.
• Pietarinen, A.-V. & Bellucci, F. 2015b. The Iconic Moment: Towards a Peircean Theory of Diagrammatic Imagination. In J. Redmond, A. N. Fernàndez, O. Pombo eds. Epistemology, Knowledge, and the Impact of Interaction, Dordrecht: Springer.
• Prior, A. N. 1958. Peirce’s Axioms for Propositional Calculus. The Journal of Symbolic Logic 23, pp. 135–136.
• Prior, A. N. 1964. The Algebra of the Copula. In Moore, E. & Robin, R. eds. Studies in the Philosophy of Charles Sanders Peirce. Amherst: The University of Massachusetts Press, pp. 79-94.
• Putnam, H. 1982. Peirce the Logician. Historia Mathematica 9, pp. 290-301.
• Roberts, D. D. 1973. The Existential Graphs of Charles S. Peirce. The Hague- Paris: Mouton.
• Schröder, E. 1890-1905. Vorlesungen über die Algebra der Logik, 3 vols. Leipzig: Teubner.
• Shields, P. 1981. Charles S. Peirce on the Logic of Number, 2^nd ed. Boston: Docent Press, 2012.
• Shin, S.-J. 2002. The Iconic Logic of Peirce’s Graphs. Cambridge, MA: MIT Press.
• Short, T. L. 2007. Peirce’s Theory of Signs. Cambridge: Cambridge University Press.
• Sowa, J. 2006. Peirce’s Contributions to the 21st Century, 14th International Conference on Conceptual Structures, Aalborg, Denmark, July 16-21, Lecture Notes in Computer Sceince, 4068, pp. 54-69.
• Stjernfelt, F. 2014. Natural Propositions. The Actuality of Peirce’s Doctrine of Dicisigns, Boston: Docent Press.
• Sylvester, J. J. 1878. On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics. American Journal of Mathematics 1, pp. 64-104.
• Tarski, A. 1941. On the Calculus of Relations. Journal of Symbolic Logic 6, pp. 73-89.
• Tiercelin, C. 1991. Peirce’s Semiotic Version of The Semantic Tradition in Formal Logic. In New Inquiries into Meaning and Truth, N. Cooper & P. Engel eds. Harverest Wheatsheaf: St. Martin’s Press, pp. 187–210.
• Van Heijenoort, J. 1967. Logic as Calculus and Logic as Language. Synthese 17, pp. 324–330.
• Walsh, A. 2012. Relations between Logic and Mathematics in the Work of Benjamin and Charles S. Peirce. Boston: Docent Press.
• Weiss, P. & Burks, A. 1945. Peirce’s Sixty-Six Signs. The Journal of Philosophy 42, pp. 383–388.
• Zalamea, F. 2012a. Synthetic Philosophy of Contemporary Mathematics, Urbanomic.
• Zalamea, F. 2012b. Peirce’s Logic of Continuity: A Mathematical and Conceptual Approach, Docent Press.
• Zellweger, S. 1997. Untapped Potential in Peirce’s Iconic Notation for the Sixteen Binary Connectives. In Houser and others eds. 1997, pp. 334-386.
• Zeman, J. 1964. The Graphical Logic of Charles S. Peirce, Ph.D. dissertation, University of Chicago.
• Zeman, J. 1986. Peirceʼs Philosophy of Logic. Transactions of the Charles S. Peirce Society 22, pp. 1-22.

 

Author Information

Francesco Bellucci
Email: bellucci.francesco@gmail.com
Tallinn University of Technology
Estonia

and

Ahti-Veikko Pietarinen
Email: ahti-veikko.pietarinen@ttu.ee
Tallinn University of Technology
Estonia

Adolf Lindenbaum (1904-1941)

Adolf Lindenbaum was a Polish mathematician and logician who worked in topology, set theory, metalogic, general metamathematics and the foundations of mathematics. He represented an attitude typical of the Polish Mathematical School, consisting of using all admissible methods, independently of whether they were finitary. For example, the axiom of choice was freely applied, but on the other hand, proofs omitting this axiom were welcomed. In set theory, Lindenbaum and Tarski posed an important conjecture that the generalized continuum hypothesis entails the axiom of choice. Among the most important metalogical and metamathematical results obtained by Lindenbaum are the following: every system of propositional calculus has an at most denumerably infinite normal matrix; the construction of the so–called Lindenbaum algebra; and the maximalization theorem.

Lindenbaum studied mathematics under Wacław Sierpiński, Stefan Mazurkiewicz and Kazimierz Kuratowski in Warsaw. As part of the Lvov–Warsaw School, formed by a powerful Polish group of analytic philosophers, Lindenbaum belonged to the Polish mathematical school and the Warsaw school of logic. He began his career as a topologist, and his doctoral dissertation, written under Sierpiński, was devoted to properties of point–sets. Then in the mid–1920s he switched to logic and joined the Warsaw School of Logic that was established by Jan Łukasiewicz and Stanisław Leśniewski after World War I. Lindenbaum was a close friend and collaborator of Alfred Tarski.

Table of Contents

1. Biography
2. A General Outline of Lindenbaum’s Scientific Career and His Views
3. Lindenbaum and Set Theory
4. Lindenbaum and Logical Calculi
5. Lindenbaum and General Metamathematics
6. Final Remarks
7. References and Further Reading

1. Biography

Adolf Lindenbaum was born in an assimilated (that is, polonized) rich Jewish family in Warsaw on June 12, 1904. He took his secondary education at M. Kreczmar’s Gymnasium in Warsaw from 1915 to 1922, and then he entered Warsaw University to study mathematics from 1922 to 1926. There his teachers included Kazimierz Kuratowski, Stefan Mazurkiewicz and Wacław Sierpiński in mathematics as well as Stanisław Leśniewski and Jan Łukasiewicz in logic. Lindenbaum also attended Alfred Tarski’s courses on cardinal numbers and elementary mathematics, Tadeusz Kotarbiński’s course in logic, and some classes in humanities. The latter included history of philosophy, Władysław Tatarkiewicz’s special class on Kant, Tatarkiewicz’s course on French art, a course in psychology by Władysław Witwicki, a course on linguistics by Karol Appel, a course on literature by Józef Ujejski, including his course on Adama Mickiewicz, the most important Polish national poet, and a course on the history and culture of Palestine by Moses Schorr.

Sierpiński supervised Lindenbaum’s Ph.D. dissertation entitled O Własnościach Mnogości Punktowych (On Properties of Point–Sets). The thesis was defended in 1928, and Lindenbaum received the title of Doctor of Philosophy. In 1934 he presented his Habilitation thesis, based on several published papers, to the Faculty of Mathematics and Natural Sciences at Warsaw University and obtained the degree of Docent (a person who could lecture). This resulted in his appointment as adjunct professor at the Philosophical Seminar at the same faculty. The Philosophical Seminar was an independent unit at the Faculty of Mathematics and Science directed for years by Łukasiewicz. It was the Logical Seminar. Lindenbaum lectured on various mathematical and logical topics from 1935 to 1939. His courses, for example, concerned the following topics: “On New Investigations into the Foundations of Mathematics and the Mathematical Foundations of other Disciplines”, “On Superposition of Functions” and “Selected Topics from Metrology and from the Theory of Functions”. He stood little chance of being promoted to an academic position higher than docent because of the anti–Semitic policy in Polish universities after 1935,  and his involvement in the communist movement, as well as the shortage of university positions at the time. He was also a tutor at the Scientific Circle of Jewish Students at Warsaw University, established after the exclusion (in the 1890s) of the Jews from general students’ associations existing in Poland.

Lindenbaum was a typical, good–looking bon vivant. He married a beautiful Jewish woman, Janina Hosiasson, who also was a logician and who successfully worked on induction and confirmation. She and Adolf became separated at the beginning of World War II (as Janina Hosiasson informed Alfred Tarski in one of her letters in early 1941, a letter that is in the Tarski Archive in U.C. Berkeley’s Bancroft Library).

Lindenbaum was a declared leftist. He belonged to the Polish Communist Party (KPP) until its dissolution by Stalin in 1938; He also was an activist in the intelligentsia circles. In 1936 Lindenbaum signed a petition demanding that Carl von Ossietzky, a journalist imprisoned by the Nazis, be awarded the Nobel Peace Prize, and he protested against the massacre of workers in Lvov in 1936. Mrs. Janina Kotarbiński, the wife of Tadeusz Kotarbiński who was a close friend of the Lindenbaums reported the following story:

It happened that I and Antoni Pański [also a philosopher – J. W] visited the Lindenbaums in their apartment. I noticed on Dolek’s [the diminutive of Adolf – J. W.] desk the Short Philosophical Dictionary [the dictionary written by Pavel Yudin and Mark Rozental and published in Russian in the Soviet Union at the beginning of the 1930s. The authors represented the Stalinist version of Marxism. The Short Philosophical Dictionary became a symbol of the orthodox Marxist ideology – J. W.]. The book was opened at the entry ‘Dialectical Contradiction’. I was surprised, and on our way back I asked Pański why Dolek, such a clever person, read such stupidities about the concept of contradiction. Pański answered that Dolek believed in every word of this book.

She added, however, that Lindenbaum had a considerable interest in philosophy without any kind of dogmatism. He was ready for an open discussion on any philosophical issue. Lindenbaum was strongly interested in literature and art, and was famous as a passionate climber.

After the outbreak of World War II, Lindenbaum immediately realized that for his own security he should escape before the German army would take Warsaw. His Jewish origin was probably not the only reason behind this decision. More importantly, it was obvious that the Germans possessed the lists of Polish communists and other critics of Hitler’s regime. Lindenbaum was particularly afraid of the consequences of the support he had given to Ossietzky, because such actions were strongly, even furiously, criticized in Germany. Although Lindenbaum could emigrate to the West or get a position in Moscow as a scientist, he decided to remain in Poland, because he had hope in the socialist future of the country. The Lindenbaums left Warsaw on September 6, 1939 and went to Vilna (presently Vilnius); this city, formerly in Poland, became the capital of Lithuania after September 17, 1939. Lithuania was an independent country in 1918–1939 with Kaunas as its capital; in 1939–1941 Lithuania was formally independent, but entirely dependent on the Soviet Union. It was occupied by Germany after its attack on the Soviet Union on June 22, 1941. Janina remained there, but Adolf moved to Bialystok, a city occupied by the Soviet Army after its invasion into Poland on September 17; he probably expected this part of Poland to become the center of the future Polish communist state. Lindenbaum was appointed as a docent in the Bialystok Pedagogical Institute established by the Soviet authorities, and he taught mathematics there. The German–Soviet War started on June 22, 1941, and the Germans soon came to Bialystok. The reasons why Lindenbaum did not leave the city are unknown. In September 1941, he was arrested by the Gestapo, transported to Vilnius, and killed in Ponary (the place of many massacres, particularly of the Jews in 1941–1944) near the Lithuanian capital. Janina Hossiasson–Lindenbaum was murdered in Vilnius in 1942. The more exact dates of the deaths of the Lindenbaums remain unknown.

See (Mostowski–Marczewski 1971), (Surma 1982), (Zygmunt–Purdy 2014) for more biographical data on Lindenbaum).

2. A General Outline of Lindenbaum’s Scientific Career and His Views

Lindenbaum began his scientific carrier as a topologist, but he soon converted to logic and the foundations of mathematics. He and Tarski (three years older) became friends in the early 1920s, and the latter influenced Lindenbaum in the direction of mathematical logic and the foundations of mathematics. Both shared not only scientific interests, but also a negative attitude to any version of religion, various leftist political ideas and a love of mountains and literature, but they were also very sensitive to their fate as secular Jews and their pretending to be assimilated and accepted by Polish society. Neither of them, however, was successful in the last respect. At the beginning of his scientific career, he was very active in the Student Mathematical Scientific Circle as well as in the Student Philosophical Circle, and he successfully promoted logic among his colleagues in both groups. In particular, he delivered several lectures on logical problems at the meetings of both circles. He was a mentor in logic to students in Warsaw. For instance, he wrote a section on logic in the Mathematical-Physical Study: Information Book for Newcomers published in 1926 in which he reported how logic was taught in Warsaw. It is a very interesting document which shows how powerful logic was in Warsaw in the mid–1920s. The revelation that the Principia Mathematica was recommended as a textbook for advanced students seems really shocking. Lindenbaum’s brilliant personality, charming style of life and powerful mathematical skills fascinated the Warsaw scientific community. Not surprisingly, he was commonly considered one of the most gifted Polish mathematicians of his generation. Tarski 1949, p. XII described Lindenbaum as “a man of unusual intelligence”. Mostowski once called Lindenbaum the most lucid mind in the foundations of mathematics. Legendary stories told by Lindenbaum’s friends and colleagues document many cases of theorems discovered by him but proved by someone else, as he had no time to complete his ideas. Yet the list of his scientific contributions is quite long; it comprises more than 40 papers, abstracts and reviews (see Surma 1982 for Lindenbaum’s bibliography), mostly published in German and French. Some of Lindenbaum’s papers were co–authored, in particular, by Tarski and Andrzej Mostowski. Lindenbaum and Tarski worked on the book Theorie der Eindeutigen Abbildungen. It was announced as volume 8 of the series “Mathematical Monograph” to be published in 1938. This information is given on the back cover of S. Sachs, The Theory of Integral, Monografie Matematyczne, Warszawa–Lwów 1937 (co–published by G. E. Stechert, New York). Sachs’ book appeared as volume 7 of this series. This suggests that the book by Lindenbaum and Tarski was near to being completed. Lindenbaum was also well–perceived on the international scale. Leading logicians and mathematicians, including Wilhelm Ackermann, Friedrich Bachmann, Abraham Fraenkel, Andrei Kolmogoroff and Arnold Schmidt, reviewed his writings.  Lindenbaum actively participated in the Polish Mathematical Congresses and in the International Congress of Scientific Philosophy held in Paris in 1935.

Lindenbaum belonged to three scientific schools. One affiliation was with the Polish Mathematical School with Sierpiński, Mazurkiewicz and Kuratowski as its leaders in Warsaw. The second affiliation was the Warsaw School of Logic (Łukasiewicz, Leśniewski, Tarski—the latter joined the top of the School in the 1920s; see Woleński 1995 for a general presentation of logic in Poland in the interwar period). The third affiliation was with the Lvov–Warsaw School (Kazimierz Twardowski and his disciples from Lvov, in particular, Łukasiewicz, Leśniewski and Kotarbiński).

The second affiliation is perhaps the most important. The Warsaw School of Logic was a “child” of mathematicians and philosophers. Łukasiewicz and Leśniewski, the main figures in this group were philosophers by training. Nevertheless, they became professors at the Faculty of Mathematics and Natural Science at Warsaw University and were active in the mathematical environment. Zygmunt Janiszewski, another founding father of the Polish Mathematical School, who died prematurely before Lindenbaum entered the university, developed the so–called Janiszewski program, a very ambitious plan of the development of mathematics in Poland that attributed crucial significance to logic and the foundations on mathematics. The Fundamenta Mathematicae, a journal established by Janiszewski and serving from its inception as an official scientific journal of the Polish Mathematical School, published many papers by logicians. It is noteworthy that Mazurkiewicz, Sierpiński, Leśniewski, and Łukasiewicz—two professional mathematicians and two logicians originating from philosophy—formed the Editorial Board of the Fundamenta. It was important for the subsequent stormy development of logic in Warsaw that the mathematical milieu accepted philosophers as professional teachers of students of mathematics.

This double heritage, philosophical as well as mathematical, determined the scientific ideology of Warsaw logicians. Perhaps one point should be mentioned here as particularly important in this context. Firstly, the Polish Mathematical School did not assume any specific philosophical standpoint concerning the nature of mathematics. Methodologically speaking, all fruitful mathematical methods, particularly coming from set theory, could be used in logical investigations, provided that they did not lead to contradictions. The last statement should be understood in the following way. Clearly, proofs of consistency are important and required, however even before Gödel’s second incompleteness theorem (roughly speaking, that the consistency of arithmetic cannot be proved in arithmetic itself) was announced, Polish mathematicians maintained that if it is empirically known that a theory of given concepts is contradiction–free, it can be faithfully used in mathematical investigations including logical research. As a consequence, the Polish Mathematics School did not subscribe to logicism, formalism or intuitionism, which were the main foundational currents in the philosophy of mathematics, even though they were widely regarded as such in 1900–1930. On the other hand, Polish logicians worked on many problems suggested by Russell, Hilbert and Brouwer, the main exponents of the mentioned schools. Moreover, sometimes a tension held between private, so to speak, philosophical views of some Polish logicians and their research practices. For instance, Tarski, influenced by Leśniewski’s and Kotarbiński’s nominalism, expressed explicit sympathy with this view, but on the other hand, he did not hesitate to use higher set theory and inaccessible cardinals in the foundations of mathematics.

There is practically nothing known about Lindenbaum’s philosophical views concerning mathematics. Clearly, his inclinations to dialectical materialism had no influence on his philosophy of mathematics and foundational views. In fact, he shared the general attitude of the Polish Mathematical School mentioned above. Lindenbaum published some papers directly related to general foundational problems (for example, Lindenbaum 1930, Lindenbaum 1931) in which he recommended the use of mathematics in logical investigations without any hesitation with respect to employing infinitary methods. He pointed out that such methods were present even in elementary arithmetic. For instance, he published reviews of works by Polish radical nominalists, such as Leon Chwistek and Władysław Hetper, but he entirely abstained from philosophical comments. Two papers—Lindenbaum 1936 and Lindenbaum–Tarski 1934–1935—should be particularly mentioned. The former paper is Lindenbaum’s contribution to the Paris Congress in 1935. It concerns the formal simplicity of concepts. Although Lindenbaum points out that this question arises in many fields, he does not offer any general definition of simplicity. Lindenbaum distinguishes seven relevant problems concerning simplicity (a) of systems of concepts (terms); (b) of propositions and their systems; (c) of inference rules; (d) of proofs; (e) of definitions and constructions; (f) of deductive theories; (g) of formal languages; but he addresses his further considerations to (a). The idea is that measuring the number of letters occurring in a given concept can tell us about the simplicity of the term. Lindenbaum follows Leśniewski in this respect. Two points are interesting. First, Lindenbaum assumes the simple theory of types.  This suggests that he preferred a more elementary construction if it is possible and adequate for a given problem. This attitude was also very popular among Warsaw mathematicians and logicians. Second, Lindenbaum observes, obviously under Tarski’s influence, that simplicity has not only a syntactic dimension (in Carnap’s sense), but it should also be considered semantically.

The paper Lindenbaum–Tarski 1934–1935 basically concerns some metamathematical problems about the limitations of means of expressions (expressive power, to use present terminology) in deductive theories. The authors claim that all relations between objects (individuals, classes, relations, and so forth) expressible by purely logical means remain invariant under an arbitrary one–one mapping of the “world” (that is, the collection of all individuals) onto itself. Moreover, this invariance is logically provable. This idea was more fully developed by Tarski in his paper on logical concepts (see Tarski 1986). In a sense, the understanding of logical concepts as invariant under all one–one mappings has affinities with the Erlangen Program (Tarski stressed this point) in the foundations of geometry formulated by Felix Klein. Lindenbaum and Tarski proved a general theorem justifying the intuitive explanation of understanding logical relations as invariant under one–one mappings. The consequences of this approach to logical concepts for philosophy of logic are far–reaching. In particular, the Lindenbaum–Tarski definition of logical concepts motivates the theorem that logic does not distinguish any extralogical concept (roughly speaking, what can be proved in logic about an extralogical item, for instance, an individual, can be proved about any other individual). Consequently, logical theorems are true in all possible worlds (models). Thus, the definition in question naturally leads to seeing logic as invariant with respect to any specific content.

Lindenbaum’s works that are related to logic and the foundations of mathematics concern set theory and logical calculi, including their metalogical properties. This article deals with general set theory in section 3, while sections 4 and 5 are devoted to logical matters Section 3 skips special topics, including those belonging to other mathematical fields; the borderline between general and special set theory is somehow arbitrary; also some of Lindenbaum’s results are mentioned without entering into formal details.

Lindenbaum’s results in set theory were achieved in an individual collaboration with other authors, particularly Tarski and Mostowski. In the 1920s and 1930s Łukasiewicz conducted a seminar in mathematical logic. Its participants were the group of young logicians including, in addition to Lindenbaum and Tarski, Stanisław Jaśkowski, Andrzej Mostowski, Jerzy Słupecki, Bolesław Sobociński and Mordechaj Wajsberg. This seminar soon became a factory of new results in mathematical logic. Its participants collaboratively worked on problems. Lindenbaum’s results about logical calculi, as Łukasiewicz explicitly says, were achieved at this seminar. Lindenbaum frequently stated theorems, usually without proofs. His most important results were mentioned by others; some of them are to be found in Łukasiewicz–Tarski 1930 (refered to in this article as Ł–T1930).

3. Lindenbaum and Set Theory

In 1926, Lindenbaum and Tarski published the joint paper “Communication sur les Recherches de la Théorie de Ensembles” (Lindenbaum–Tarski 1926; the abbreviation L–T1926 is used in further references). This paper is very compact. In 30 pages the authors announced many results in set theory and its applications, that were achieved by them within the “last few years.” More particularly, theorems and definitions concerned cardinal and ordinal numbers, the relations between them and the theory of one–one mappings. The results were stated without proofs. The authors noted that proofs and further developments would appear in the subsequent writings. (Perhaps the already mentioned monograph Theorie der Eindeutigen Abbildungen was intended as a continuation of L–T1926; several related results are contained in Tarski 1949; Lindenbaum is mentioned in the Preface to this book as a person particularly effective in conducting research on cardinal numbers.) The spirit of the Polish Mathematical School is evident in this paper. The purely mathematical text is interrupted by historical and methodological comments; Polish mathematicians considered (and they still do) such remarks as a very important feature of mathematical prose. Due to the role of the axiom of choice (AC) in set theory and its controversial nature, results obtained without use of this axiom are grouped in a section different from the sections containing the theorems based on AC. The paper lists 102 theorems or lemmas about cardinal numbers, 5 theorems or lemmas about properties of one–one mappings, 16 theorems or lemmas about order types, 4 theorems on the arithmetic of ordinal numbers, and 19 theorems or lemmas on point–sets. In many cases, the investigations by Lindenbaum and Tarski continue the earlier works and achievements by Cantor, Dedekind, Bernstein, Fraenkel, Hartogs, Korselt, König, Lebesgue, von Neumann, Russell and Whitehead, Schröder, Zermelo, Banach, Kuratowski, Leśniewski and Sierpiński. In a sense, L–T1926 can serve as a very important historical report on the state of the art in set theory and its foundational problems in the mid–1920s.

Perhaps the most important result (theorem 94) announced in L–T1926 concerns the generalized continuum hypothesis (GCH) and AC. Lindenbaum posed the problem of how AC (one of the main focuses of Polish Mathematical School) is related to Cantor’s hypothesis on alephs (the name of GCH used in L–T1926). Theorem 94 states that GCH entails AC. This result was proved by Sierpiński in 1947 (see Sierpiński 1965, pp. 43–44, Moore 1982, pp. 215–217 for a brief survey). The search for equivalents of AC became one of the Polish mathematical specialties de la maison. Lindenbaum (L–T1926, theorem 82(L)) claimed that AC is equivalent to the assertion that for arbitrary cardinal numbers m and n, m ≤* n or n ≤* m (the symbol ≤* expresses the relation between cardinal numbers m and n such that either m = 0 or every set of power n is the sum of m mutually disjoint non–empty sets). This theorem was finally proved by Sierpiński in 1949 (see Sierpiński 1965, p. 435–436).  L–T1926 also presents the material on the Cantor–Bernstein theorem (CBT; Lindenbaum and Tarski used the label “the Schröder–Bernstein theorem”), which says that for any cardinal numbers m, n, if m ≤ n and n ≤ m, then m = n (see Hinkis 2013 for a very detailed historical exposition). In particular, Lindenbaum proposed some equivalents of CBT also in the terms of order–types of one–one mappings. One of the equivalents of CBT is the following proposition: for any order–types α, β, γ, δ, if α = β + γ and γ = α + δ, then α = γ (via one–one mappings: if an well-ordered set X is similar to a segment of an ordered set B, and B is similar to a residue of A, then both sets A and B are similar). Another interesting result related to the Bernstein Division Theorem (BDT) says that for any natural number k and any cardinal numbers m, n, if km = kn, then m = n. L–T1926 claims that Lindenbaum proved BDT in its full generality and made that without AC. Yet there is a slight historical controversy concerning the scope of Bernstein’s original proof (see Hinkis, p. 139). [A ⇔ B]? Leaving this question aside, there is no doubt that L–T1926 played an important role in the development of the foundations of set theory.

Finally, consider the paper by Lindenbaum and Mostowski (Lindenbaum–Mostowski 1938) on the independence of AC from other axioms of Zermelo–Fraenkel set theory (ZF). Abraham Fraenkel claimed that he proved the independence of AC (in its standard version postulating the existence of a choice set for any family of non–empty and disjoint sets) and its two equivalents (every set can be ordered; if for every family of finite and mutually disjoint sets, a choice set exists, then there exists a choice set for every countable family of sets with mutually disjoint set as elements) from ZF. Lindenbaum and Mostowski remark that Fraenkel’s investigations, though of great value, cannot be regarded as fully successful “because a dangerous confusion of metamathematical and mathematical notions is inherent in it”. More specifically, Fraenkel’s notions of model and function are obscure. Lindenbaum and Mostowski propose to understand the concept of function in a semantic manner, that is, as determined by the formula “a set satisfies a propositional function”.  Moreover, they point out an error in Fraenkel’s proof consisting in his treatment of permutations. Lindenbaum and Mostowski propose a modification of Fraenkel’s construction in order to correct his proof. It is done by the improving axiomatization with respect to axioms of separation, replacement and infinity. This step allows for proving that also other equivalents of AC are not derivable in ZF. The authors observe that ZF remains (relatively) consistent if we add the axiom “there exists an infinite set having not–sets as elements”. Moreover, the results cannot be obtained in the system in which sets are admitted as the only elements. These results were later completed by Mostowski. The models of the improved ZF with Urelements (items not being sets) are called the Fraenkel–Mostowski models. Perhaps a particularly interesting feature of Lindenbaum–Mostowski 1938 consists in the conscious use of semantic methods in the metamathematics of set theory.

4. Lindenbaum and Logical Calculi

This section reviews Lindenbaum’s results in metalogic of propositional calculus.  They were announced at Łukasiewicz’s seminar in mathematical logic in 1926–1930. Łukasiewicz initiated a research program devoted to propositional (sentential) logic, classical as well as many–valued (the results are collected in Ł–T1930). The two main directions of investigations were executed by Łukasiewicz’s group. First, constructions of sentential logic as axiomatic systems were undertaken. Łukasiewicz and his students looked for independent and possibly economic axioms (economic in the sense of having the minimal number of axioms consisting of the shortest number of symbols). Second, Warsaw logicians—mostly Tarski—invented and systematized the basic metalogical tools for investigations of propositional calculus. Lindenbaum, contrary to the majority of the members of  Łukasiewicz seminar, had no interest in proposing new axiomatizations of logic. His activities belonged entirely to metalogic. More specifically, Lindenbaum contributed to the matrix method, that is, to investigating sentential logic via logical matrices. They are generalizations of the well–known truth–tables.

Abstractly speaking, (note that the level of abstraction is higher in Ł–T1930), a logical matrix is an ordered quadruple M = [U, U’, f, g] such that U and U’ are two arbitrary sets (in order to exclude trivial cases, both sets are assumed to be non–empty), U has at least two elements, U’ ⊂ U, f is a binary function, and g is a unary function. Both functions are defined for U and take values from U. The intended interpretation is as follows: U – the set of logical values, U’ ­– the set of designated logical values. In the case of two–valued logic (1 – truth, 0 – falsehood), U’ = {1, 0} and U’ = {0}. Assume that L is a language of sentential logic. If A ∈ L, then f(A), g(A) ∈ U. Intuitively speaking, f and g are valuation functions defined for formulas of L taking values from U; if language is not taken into account, M is an algebra of (logical or other) values.  Write v(A) for “v is a logical value of A in M”. The matrix M is normal provided that if v(A) ∈ U’ and v(B) ∈ U, then v(A, B) ∈ U. Roughly speaking, values of compound formulas always belong to U, independently of whether their constituents are valued by designated values or other (undesignated) values.  If A ∈ L and for every w, w(A) = 1, then A is a tautology in M (A is verified by M). We can consider g as the function corresponding to negation and f as the counterpart of implication. Thus, v(¬A) = 1, if v(A) = 0, v(¬A) = 0, if v(A) = 1; v(A ⇒ B) = 1, if v(A) = 0 or v(B) = 1, otherwise v(A ⇒ B) = 1. These equalities show that truth–tables for implication and negation are special cases of logical matrices in the abstract sense.

Lindenbaum established several important theorems connecting propositional calculi with logical matrices (they are listed in a different order than the theorems appear in Ł–T 1930; this paper contains no proofs). Let the symbol LOG_ℵ0 refer to a many–valued logic with a denumerably infinite set of logical values. Łukasiewicz defined matrices for such a system. Lindenbaum (theorem 16 in Ł–T 1930) established that LOG_ℵ0 can be characterized by a matrix in which U’ = {1}, functions f and g satisfy the conditions f(x, y) = min(1, 1 – x + y),  g(x) = 1 – x and U is an arbitrary infinite set of numbers which satisfies the condition 0 < x < 1 for any element of U and is closed under the operations f and g. Lindenbaum also proved (theorem 19 in Ł–T 1930) the following logico–arithmetical result (the converse of a result obtained earlier by Łukasiewicz): for 2 ≤ m ≤ ℵ₀ and 2 ≤ n ≤ ℵ₀, we have the equivalence LOG_m ⊆ LOG_n if and only if n – 1 is a divisor of m – 1. The next theorem established by Lindenbaum for n = 3 (Tarski generalized this result for any prime number) says if n is a prime number that there are only two systems L (the entire language) and LOG₂ which contain LOG₃ as a proper part. Lindenbaum also proved (Ł–T1930, theorem 23) that every logic LOG_n is axiomatizable for any 1 ≤ n < ℵ₀.

Although the above results are general, they were mainly directed as reporting facts on many–valued logic. Lindenbaum also obtained the results on arbitrary sentential calculi and their matrices. The definition of M (plus the definition of a sentential calculus as closed by the consequence operation) implies that the set of tautologies in a matrix, that is, LOG(M), provided that M is normal, is a system. Lindenbaum announced (theorem 3 in Ł–T 1930) that every sentential calculus has at most a denumerably infinite normal matrix. This theorem was proved by Jerzy Łoś (see Łoś 1949; this work contains the first systematic treatment of logical matrices). This last work originated from systematic investigations on matrix semantics for propositional calculi (see Wójcicki 1989 for an extensive report on this field of logical research; several important results are also described in Pogorzelski 1994). The following historical speculation can illustrate the importance of theorem 3. When Heyting formalized intuitionistic sentential logic (ISC) in 1930, the question of finding a normal matrix for this logic became important. Gödel showed (in 1932) that no finite matrix (he used the term “realization”) verifies all theorems of ISC. By Lindenbaum’s result (Gödel did not refer to it), there exists a denumerably infinite normal matrix ISC. Jaśkowski constructed it in 1936. He certainly must have known Ł–T 1930, but he did not refer to it. This story makes a nice example of how influences could interplay in looking for an adequate matrix for intuitionistic propositional logic; but we have no accessible evidence that Lindenbaum’s theorem actually inspired Jaśkowski.

5. Lindenbaum and General Metamathematics

Several of Lindenbaum’s contributions to general metamathematics are mentioned in Tarski 1956 (referred to as T1956 below). The two most important results achieved by Lindenbaum are his construction of the so–called Lindenbaum algebra (LIA) and the maximalization theorem LMT (frequently called the Lindenbaum Lemma). Lindenbaum observed that formulas can be the elements of logical matrices (see Surma 1967, Surma 1973, Surma 1982 for the reconstruction of Lindenbaum’s path to LIA). Then, he as well as other logicians (Łoś, for instance) generalized this idea for arbitrary languages. LIA is presented in this article for classical sentential calculus. Let L be a formal language with ¬, ∧, ∨, ⇒, ⇔ as connectives. Formulas as such, that is, variables and their well–formed strings do not constitute an algebra. The symbol [A] refers to the Lindenbaum class of formulas with respect to A. We further stipulate that B ∈ [A] if and only if ├ A ⇔ B (this step gives a congruence in L) and then define –[A] as [¬A], [A] ∩ [B]  as [A ∧ B], [A] ∪ [B]  as [A ∨ B], [A] ⊆ [B] as [A ⇒ B], and [A ⇔  B] as [A] = [B]. If we denote the set of classes of formulas produced by the defined congruence by the symbol L_[≈],  the structure < L_[≈], –, ∩, ∪, ⊆ , = > is a Boolean algebra of formulas, that is, LIA for sentential logic. An interesting feature of this construction is that building blocks for LIA come from language. This justifies the use of the same symbols for propositional connectives in the object language (the language of propositional calculus) and the metalanguage, (the language of LIA). Lindenbaum’s construction of algebras has important applications in algebraic proofs of metalogical theorems (see Surma 1967, Rasiowa–Sikorski 1970, Surma 1973, Rasiowa 1974, Surma 1982, Zygmunt–Pardy 2014), including the completeness theorem for classical logic as well as many non–classical systems.

There is a controversy concerning the origin of LIA. According to Surma 1967, p. 128 Lindenbaum presented his idea at the 1^st Polish Mathematical Congress in 1927. This fact, however, is only known from the Polish oral tradition. Significant information can be found in Rasiowa,–Sikorski 1970, 245–246, footnote 1. The first published mention was made by McKinsey with reference to Tarski’s oral communication in 1941. However, Tarski complained that the discovery of LIA should be credited to him (it is reported in the mentioned footnote in Rasiowa–Sikorski 1974).  Since Tarski’s historical claim concerning LIA is known, some authors used label “the Lindenbaum–Tarski algebra”.

MT is perhaps the most important result achieved by Lindenbaum. Its formulation is very simple: every consistent formal system has its maximal and consistent extension. The theorem was probably inspired by the concept of Post–completeness, well known in the Łukasiewicz’s group. This theorem is mentioned several times in T1956; its proof is to be found on pp. 98–100. An important feature of LMT consists in the fact that it is not intuitionistically  provable (although we know that maximal extensions exist, there is no general method of their construction) and it requires infinitistic methods (it is but weaker than AC; see below). T1956 points out many applications of LMT, for instance, that classical logic is the only consistent extension of intuitionistic logic (Tarski). The great career of LMT began after Henkin had used it in his proof of the completeness of first–order logic. This proof combines together LIA and the construction of maximal consistent sets of formulas. Henkin’s method became adapted for proving the completeness property of many logical systems. LMT is effectively equivalent to the Stone ultrafilter theorem. One can prove (see Surma  1968) that AC implies the Gödel–Malcev completeness theorem, and the latter entails LMT. The standard version of LMT works for countable languages (see Łoś 1955 for LMT for uncountable languages) and a compact consequence operation (omitting the property of compactness is not particularly significant). On the other hand, if LMT is strengthened by additional assumption concerning individual constants or by admitting uncountable languages, it becomes provably equivalent to AC (see also Gazzari 2014). These results help in placing LMT on the scale of infinitary methods in metamathematics.

The program of reverse mathematics (see Simpson 2009) gives a more general perspective in this respect. The symbol RCA₀ refers to Peano arithmetic minus the full induction scheme (it is restricted to ∑ zero–one formulas) plus the recursive comprehension scheme; it is a relatively weak subsystem of second–order arithmetic. LMT is equivalent over RCA₀ to the following propositions: weak König lemma, Gödel–Malcev completeness theorem, Gödel compactness theorem, completeness theorem for propositional logic for countable languages and the compactness theorem for propositional logic for countable languages. Since the weak König lemma is a rather mathematical (not metalogical) result, its equivalence with LMT exactly characterizes the mathematical content of the second. If LMT is associated with the consequence operation admitting the rule of substitution, we obtain the so–called relative Lindenbaum extensions (see Pogorzelski 1994, p. 318; this theorem was proved by Asser in 1959). Roughly speaking, if we take a consistent set X and a formula A such that A ∉ X, we have two consistent extensions of X, namely X ∪ {A} and X ∪ {¬A}. Clearly, by the standard LMT, there exist at least two different maximally consistent extensions. The problem how many such relative Lindenbaum sets are associated with a given consistent set X has no unique solution.

Here is a list of some other of Lindenbaum’s metamathematical results (see Tarski 1956, 32, 33, 36, 71, 297, 307, 338 for the technical details):

• the number of all deductive systems is equal to 2^ℵo;
• the number of all axiomatizable systems is equal to ℵ₀;
• the condition which must be satisfied in order for the sum of a deductive system to be a deductive system;
• structural type of a theory;
• theorems of degrees of completeness;
• atomic (atomistic, according to an older terminology) Boolean algebra.
• independence of primitive concepts in mathematical systems.

The last three results in the above list were achieved jointly by Lindenbaum and Tarski (see Tarski–Lindenbaum 1927), and other results inspired Tarski in his metamathematical investigations. Moreover, Tarski credited to Lindenbaum the pointing out the role of set–theoretical methods in metamathematical investigations (T1956, p. 75).

6. Final Remarks

Helena Rasiowa (in Rasiowa 1974, p. v) says that the introduction of the Lindenbaum–Tarski algebra became “one of the turning points in algebraic study of logic”. This tradition was continued,  systematized and conceptually unified by Tarski himself as well as by his American students, particularly J. C. C. McKinsey,  Bjarni Jónsson, Don Pigozzi as well as Polish logicians, notably Jerzy Łoś, Helena Rasiowa and Roman Sikorski.  Rasiowa–Sikorski 1970 can be considered as the opus magnum in this direction. A similar role should be attributed to LMT (not properly called the Lindenbaum Lemma, because its actual importance exceeds the fact of being an auxiliary device for proving other results) as a mark of mathematical content of tools used in metamathematics. Thus, Adolf Lindenbaum appears as one of the main masters in developing mathematics for metamathematics. His results on logical matrices opened a new stage in metalogical investigations concerning propositional calculus.

7. References and Further Reading

• Gazzari, R. 2014, “Direct Proofs of Lindenbaum Conditionals”, Logica Universalis 8, Issue 3–4, 321–343.
• Hinkis, A. 2013, Proofs of the Cantor-Bernstein Theorem. A Mathematical Excursion, Basel: Birkhäuser.
• Lindenbaum, A. 1930, “Remarques sur une question de la methode mathematique”, Fundamenta Mathematicae 15, 313–321.
• Lindenbaum, A. 1931, “Bemerkungen zu den vorhergehendem “Bemerkungen” des Herrn J. v. Neumann”, Fundamenta Mathematicae 17, 335–336.
• Lindenbaum, A. 1936, “Sur la simplicité formelle des notions”, in Actes du Congrès International de Philosophie Scientifique, VII Logique (Acutalités Scientifique et Industrieles 394), 29–38.
• Lindenbaum, A.–Mostowski, A. 1938, “Über die Unabhängigkeit des Auswahlaxioms und einiger seiner Folgerungen”, Comptes Renduz des Séances de la Société des Sciences et des Letters de Varsovie, Classe III, 31, 27–32; Eng. tr.  in A. Mostowski, Foundational Studies. Selected Works, Vol. II, Warszawa–Amsterdam: PWN–Polish Scientific Publishers – North–Holland Publishing Company, 70–74.
• Lindenbaum, A.–Tarski, A. 1926, „Communication sur la recherches de la théorie des ensembles”, Comptes Renduz des Séances de la Société des Sciences et des Letters de Varsovie, Classe III, 19, 299–330; repr. in A. Tarski, Collected Papers, vol. 1, 1921–1934, Basel: Birkhäuser 1986, 171–204.
• Lindenbaum, A.–Tarski, A. 1934–1935, “Über die Beschränktheit des Ausdrucksmittel deduktiver Theorien, Ergebnisse eines mathematischen Kolloqiums 7, 15–22; Eng. tr. in Tarski 1986, 384–392.
• Łoś, J. 1949, O matrycach logicznych (On Logical Matrices), Wrocław: Wrocławskie Towarzystwo Naukowe.
• Łoś, J. 1955, „The Algebraic Treatment of the Methodology of Elementary Deductive Systems”, Studia Logica 2, 151–212.
• Łukasiewicz, J.–Tarski, A. 1930, “Untersuchungen über den Aussgenkalkül”, Comptes Renduz des Séances de la Société des Sciences et des Letters de Varsovie, Classe III, 23, 30–50; Eng. tr. in Tarski 1956, 38–59.
• Marczewski, E.–Mostowski, A. 1971 “Lindenbaum Adolf (1904–1941)”, Polski Słownik Biograficzny 17, 364b–365b;
• Moore, G. H. 1982, Zermelo’s Axiom of Choice. Its Origins, Development, and Influence, Springer Verlag: New York – Heidelberg – Berlin.
• Pogorzelski, W. 1994, Notions and Theories of Elementary Formal Logic, Białystok: Warsaw University – Białystok Branch.
• Rasiowa, H. 1974, An Algebraic Approach to Non-Classical Logics, Amsterdam – Warszawa: PWN–Polish–Scientific Publishers – North–Holland Publishing Company.
• Rasiowa, H.–Sikorski, R. 1970, The Mathematics of Metamathematics, Warszawa: PWN– Polish Scientific Publishers.
• Sierpiński, W. 1965, Cardinal and Ordinal Numbers, Warszawa: PWN – Polish Scientific Publishers.
• Simpson, S. G. 2009, Subsystems of Second Order Arithmetic, Cambridge: Cambridge University Press.
• Surma, S. J. 1967, “History of Logical Applications of the Method of Lindenbaum’s Algebra”, Analele Univeritatii Bucurereşti – Acta Logica 10, 127–138.
• Surma, S. J. 1968, “Some Metamathematical Equivalents of the Axiom of Choice”, Prace z Logiki 3¸71–80.
• Surma, S. J. 1973, “The Concept of Lindenbaum Algebra and Its Genesis, in Studies in the History of Mathematical Logic, ed. by S. J. Surma, Ossolineum, Wrocław, 239–253.
• Surma, S. J. 1982, “On the Origins and Subsequent Applications of the Concept of Lindenbaum Algebra”, in Logic, Methodology and Philosophy of Science VI. Proceedings of the Sixth International Congress of Logic, Methodology and Philosophy of Science, Hannover 1979, ed. by L. J. Cohen, J. Łoś, H. Pfeiffer and K.–P. Podewski, Warszawa – Amsterdam: PWN Polish Scientific Publishers – North–Holland Publishing Company, 719–734.
• Tarski, A.–Lindenbaum, A. 1927, “Sur l’indépendance des notions primitives dans les systèmes mathématiques”, Annales de la Société Polonaise de Mathématique 7, 111–113.
• Tarski, A. 1949, Cardinal Algebras, New York: Oxford University Press.
• Tarski, A. 1956, Logic, Semantics, Metamathematics. Papers from 1923 to 1939, Oxford: Clarendon Press.
• Tarski, A. 1986, “What are Logical Notions?”, History and Philosophy of Logic 7, 143–154.
• Woleński, J. 1995, “Mathematical Logic in Poland 1900–1939: People, Institutions Circles, Institutions, Ideas”, Modern Logic V(4), 363–405; repr. in J. Woleński, Essays in the History of Logic and Logical Philosophy, Kraków: Jagiellonian University Press 1999, 59–84.
• Wójcicki, R. 1989, Theory of Logical Calculi. Basic Theory of Consequence Operations, Dordrecht: Kluwer Academic Publishers.
• Zygmunt, J.–Purdy, R. 2014, “Adolf Lindenbaum: Notes on His Life with Bibliography and Selected References”, Logica Universalis 8, Issue 3–4, 285–320.

 

Author Information

Jan Woleński
Email: wolenski@if.uj.edu.pl
University of Technology, Management and Information
Poland

Institution Theory

Institution theory is a very general mathematical study of formal logical systems—with emphasis on semantics—that is not committed to any particular concrete logical system. This is based upon a mathematical definition for the informal notion of logical system, called institution, which includes both syntax and semantics as well as the relationship between them. Because of its very high level of abstraction, this definition accommodates not only well-established logical systems but also very unconventional ones; and moreover it has served and it may serve as a template for defining new ones.

There is some criticism that the abstraction power of institutions is too much, allowing for examples that can hardly be recognised as logical systems. Institution theory is nevertheless part of the universal logic trend (Béziau, 2012) which approaches logic from a relativistic, non-substantialist perspective, that is quite different from the common reading of logic, both in philosophy and in the exact sciences. However, institution theory should not be regarded as opposed to the established tradition of logic since it includes it from a higher abstraction level. In fact the real difference may occur at the level of methodology, top-down (in the case of institution theory) versus bottom-up (in the case of conventional logic tradition). This means that, in institution theory, concepts come naturally as presumed features that a logical system might or might not exhibit, and they are defined at the most appropriate level of abstraction; hypotheses are kept as general as possible and introduced on an as-needed basis. These lead to a deeper understanding of logic phenomena that is not hindered by the largely irrelevant details of particular logical systems, but are guided by structurally-clean causality. In the exposition, after discussing the history of institution theory, its main concepts are presented. Then there is a discussion of the main contributions of institution theory, including a wide range from pure mathematical logic to applied computing science. A special point here is the institution-theoretic method for doing logic by translation, which means handling logical issues rather indirectly by transporting them across logical systems and solving them at the most appropriate place. After this some extensions of mainstream institution theory are presented briefly.

Table of Contents

1. History
   1. Origins
   2. Early Developments
   3. Later Developments
   4. Notes
2. The Concept of Institution
   1. Signatures
   2. Sentences
   3. Models
   4. Satisfaction
   5. Concrete Institutions
   6. Notes
3. Institution-independent Model Theory
   1. The Galois Connection between Syntax and Semantics
   2. Logical Connectors
   3. Quantifiers
   4. Diagrams
   5. Ultraproducts
   6. Interpolation and Definability
   7. Layered Completeness
   8. Notes
4. Logic by Translation
   1. Morphisms and Comorphisms
   2. Encodings
   3. Borrowing
   4. Notes
5. Contributions to Computing Science
   1. Structured Specifications
   2. Heterogeneous Specifications
   3. Ontologies
   4. Logic Programming
   5. Notes
6. Extensions
   1. Many-valued Truth
   2. Modalities
   3. Notes
7. References and Further Reading
   1. Primary Sources
   2. Secondary Sources
   3. Auxiliary Non-Institutional Sources

1. History

a. Origins

Institution theory was introduced by Joseph Goguen and Rod Burstall in the late seventies as a response to the explosion in the population of logical systems in use in formal specification theory and practice. Formal specification is a logic-based area of computer science that aims to support reliable system development through axiomatic formalisation of their structure and functionality. At the time (and now even more) there was a great diversity of specification formalisms, each of them supported by a particular underlying logical system. Hence the need for a uniform approach to specification theory capable to develop those part of the theory that are independent of the choice of a particular logical system, and thus are common to many specification formalisms. The key step was the definition of the concept of institution in (Goguen and Burstall, 1984) intended to capture formally the structural essence of logical systems beyond specific details. Since semantics plays the primary role in formal specification, institutions lean towards the semantics side of logic, known as model theory. This aspect has permanently constituted a source of criticism from the side of syntactic and proof oriented logicians and at the same time a source of celebration from the side of the semantics oriented ones.

The concept of institution has two theoretical sources. One is the abstract model theory of Barwise (1974), and the other is the category theory of Eilenberg and Mac Lane (1945); Mac Lane (1998). While the importance of the latter in traditional areas of mathematics remains controversial, it has gained a major status in theoretical computing science (see (Goguen, 1991)) and logic. Although mathematically institutions are categorical structures
their spirit is that of abstract model theory.

b. Early Developments

The first paper on institution theory (Goguen and Burstall, 1984) introduced the main concepts and in parallel illustrated them on the example of the capture of many-sorted equational logic as an institution, at the time being the most traditional and important specification logic. Among the basics of institution theory developed there were the Galois connection between syntax and semantics as well as various concepts and results related to the structuring of specifications and programs. The latter task has been carried much further in the influential work (Sannella and Tarlecki, 1988). Another important early development was the introduction in (Tarlecki, 1986b) of the treatment of classical connectives (conjunction, disjunction, negation, and so forth) and of quantifications in abstract institutions, and also of other logic concepts such as interpolation. That was a clear indication that institution theory may reach far beyond its original goal, that of providing a very general theoretical platform for formal specification. The work (Tarlecki, 1986c) was the first paper on institution theory that developed deep results having a logic (model theory) rather than a computing science flavour. In parallel with these developments the list of logical systems captured as institutions kept growing, with quite unconventional ones being added, a process fueled mainly by the increasing diversity of computing science logics. Very often the effort to formally capture particular logical systems as institutions has lead to (re)considerations, within the respective logical setups, of some basic logical concepts, such as variable, language (or vocabulary, signature), model, sentence, and so forth. Presenting logical systems as precise and coherent mathematical objects proves to be more than a simple exercise, it has lead to new understanding of some aspects of particular logical systems.

c. Later Developments

The work (Meseguer, 1989) extended the concept of institution, that has a pronounced semantic character, to include proof-theoretic concepts, thus opening the possibility to have a general institution-theoretic approach to logical calculi.

Although the conceptual infrastructure was already in place right from the beginning of institution theory, the first substantial institution-theoretic work in the direction of doing logic by translation is (Cerioli and Meseguer, 1997). Many other works in the same direction followed, most notably (Mossakowski et al., 2009), the winner of the contest of the 2nd World Congress in Universal Logic (Xi’an, China, 2007).

An important trend within institution theory is less motivated by computing science and more by model theory research. Several important model theory methods have been developed at the level of abstract institutions and a lot of very general and yet deep results have been developed. This has resulted in a very abstract form of model theory, often refereed to as institution-independent model theory or synonymously institutional model theory. The monograph (Diaconescu, 2008) provides a snapshot of this dynamic area. Many of the institution-independent model theory results constitute high generalisations of well known results from conventional concrete model theory and can be used for obtaining easily corresponding results in less conventional logical systems. The same can be said for model theoretic concepts. A lot of theoretical computer science has been developed within institution theory based on the principle that formal specification and declarative programming languages should be based rigorously upon an underlying concrete institution. Based upon a large body of institution-theoretic developments, two modern specification languages have been designed by following this principle: CafeOBJ in Japan (Diaconescu and Futatsugi, 1998) and CASL in Europe (Astesiano et al., 2002). Both developments (the latter via the Hets environment (Mossakowski, 2005)) acknowledged the importance of logically heterogeneous environments, where several logical systems instead of only one are used via appropriate translations between them. For this, institution theory was able to accommodate a construction from algebraic geometry due to the French mathematician Alexandre Grothendieck, and flatten any such heterogeneous environment to a single institution (Diaconescu, 2002; Mossakowski, 2002), with the benefit of avoiding the rather big eort of a redevelopment of concepts and results for the heterogeneous situation. Institution theory plays the core role in the OMG standard The Ontology, Integration and Interoperability (OntoIOp).

d. Notes

Although (Goguen and Burstall, 1984) may be considered as the first prominent publication from the now rather vast institution theory literature, the seminal reference of the area is considered (Goguen and Burstall, 1992). The large time gap between these two publications is due to a very slow editorial process. Some critics consider the term ‘institution’ as uninspired since it does not convey anything about the scientific or the philosophical meaning of the concept. Goguen said that they chose this name, somehow half joking, in response to the sectarianism that was taking over the specification community at the time. Around particular specification formalisms, people were building real social institutions consisting of dedicated conferences, publication forums, user groups, and so forth.

2. The Concept of Institution

An institution is a mathematical structure that can be regarded as a template for capturing mathematically logical systems. Many argue that this template is general enough to accomodate anything that may be called ‘logic’, or at least any logical system based on satisfaction between sentences and models of any kind. The concept of institution relies heavily upon category theory concepts, but in a rather elementary way. This means that most of institution theory does not involve sophisticated or advanced levels of category theory. An institution consists of four kinds of entities: signatures, sentences, models, and the satisfaction between models and sentences. All these are considered fully abstractly and axiomatically. This means the focus is on their external properties, how they relate to the other entities, rather than what they actually are or may be.

a. Signatures

When assuming a logical context the first thing to be done is to assume a collection of symbols as primitive building blocks for the syntactic constructs. In logic this is usually called language or vocabulary. In computing science this is usually called signature, and so is in institution theory. In a signature the symbols are also usually structured, and often this gets to rather complex structures. This is especially true in the context of many modern computing science logics. But institution theory encapsulates all such information and treats signatures as fully abstract entities. In addition to this, institution theory considers that in a logical system signatures may vary. This comes from the practice of formal specification where the signatures are defined locally. Hence in any institution we have a collection of signatures rather than only one signature. However, this is not taken as a discrete collection as institution theory also considers interpretations between signatures called morphisms of signatures; these are also considered fully abstractly. The only data is that any signature morphism has a source signature and a target signature ; this is denoted by employing the common mathematical notation of a function. Note that in concrete examples signature morphisms are not necessarily functions, they may be much more complex interpretations that preserve the respective structure of the signatures. Also given two signatures, in general nothing prevents the existence of more than one morphisms between them, or the non-existence of such morphisms.

In the case of concrete institutions, of examples, one has to define precisely what are the signatures and their morphisms. Let us consider the simple example of (the institution of) classical propositional logic, which we denote by . Here a signature is just a set , traditionally referred to as a set of ‘propositional variables’. It is important that , although arbitrary, is a fixed set. Another set gives another signature. And any function is a signature morphisms. Note that the Boolean connectors , , etc, although they contribute to the building of the propositional logic statements, are not part of the signatures.

The only property that institution theory considers for signatures and their morphisms is that when

   

and

   

there exists another signature morphism

   

called the composition of and . This composition should satisfy some associativity and identity laws, hence very compactly we say that in any institution the signatures and their morphisms form a category. In our example this is just the most standard category, the category of sets with functions as morphisms, with the composition being just the set theoretic composition , i.e.

   

b. Sentences

In any particular logical system once a language (signature) is assumed, we can have logical statements or sentences. The collection of sentences is dependent on the assumed language (signature). In institution theory this very basic principle is reflected by a designated function () that maps each signature to a set (of presumed sentences). At the abstract level one does not bother what this function is, it is considered fully abstractly. For each signature we just call the elements of as ‘-sentences’. However, the concrete institutions need to define these. For instance, given a signature (which is just a set), is the set of all formulæ built from by using the connectors and . If

   

then for example

   

Since semantically the other propositional logic connectors such as implication , disjunction , etc. can be expressed in terms of and , the latter two are enough to get all the expressivity power of propositional logic.

The signature morphisms reflect at the level of sentences as translation mappings. That is, for any signature morphism there exists a function

   

For abstract institutions is considered abstractly, but in concrete institutions we have to define it. Usually just replaces the symbols in -sentences according to . For example, given the only existing signature morphism

   

where is as above and then

   

. In other situations things are not that straightforward. For instance in many sorted quantified logics the translation of quantified sentences gets a little sophisticated due to the management of the first order variables (for example to make sure that a translated variable does not clash with an existing constant of the target signature). From our example we may note easily a very simple coherence property of the sentence translation: for any composition of signature morphisms we have that for each sentence ,

   

If we add also that the identity signature morphisms (i.e. those keeping everything as it is) always get mapped to identity functions then in category theory terminology we can just say that is a functor from the category of the signatures to the category of sets and functions. At the level of abstract institutions this property of the sentence translations is given as an axiom that characterises the sentence part of the general definition of institution.

c. Models

On the semantics shore, each signature can be interpreted as a collection of models. In general for each signature there can be several models (called -models), an aspect that gives model theory its relativistic character. For instance, the models of a signature are the valuations of the ‘propositional variables’ of to the truth values and , which is the same as the subsets of (by retaining only the elements of that are valuated to . Like with signatures and sentences, at the abstract level, that of the definition of the concept of institution, the models are also considered fully abstractly. Like for signatures, but unlike for sentences (of a given signature), we also consider morphisms between models. This yields the same kind of mathematical structure for the collection of the -models like in the case of , that of a category. Hence let denote the category of the -models and their morphisms. In the case of , has the particularity that given two models and there exists at most one morphism ; this happens only when (here we regard the -models as subsets of rather than valuations to ).

The fact that in general is defined as a category rather than set (like is), besides the morphisms aspect, has a rather subtle set-theoretic aspect. The -models may be so many that they may not constitute a set anymore. In examples this is closely related to the fact that there does not exists ‘the set of all sets’, which would be a violation of one of the axioms of formal set theory. However, this does not necessarily happen always, for example in the -models do form a set.

Another important difference between the syntax and semantics sides of the definition of institution occur at the level of the translations induced by the signature morphism. This phenomenon can be best understood when looking at concrete examples, such as . Given a signature morphism the corresponding translation mapping goes from to , opposite the direction the sentence translation goes. Namely, each -model gets reduced to the -model (here for convenience we regard -models as valuations rather than subsets). This is a very important feature of the semantics, called the contravariance of the reduction. The use of the name ‘reduction’ instead of ‘translation’ is in fact meant to convey this aspect. This terminological choice can be easily understood when considering to be an inclusion : as the valuation function, is just the restriction of to . Thus, at the general level, for any signature morphism there is a model reduct functor

   

By taking into account that and are categories rather than sets, is functor rather than function. The behaviour of the model reduct functors with respect to the composition of the signature morphisms is perfectly similar to what happens in the case of the sentence translations, of course modulo the contravariance aspect:

   

All these can be formulated compactly just by saying that is a contravariant functor from to the category of categories and functors.

d. Satisfaction

At the heart of the semantic concept of truth, promoted by Tarski (1944) and employed by institution theory, lies the satisfaction relation between models and sentences. For example, in given a signature , a -model and a -sentence , we may evaluate for the valuation as a truth value or by applying the well known truth table of classical propositional logic inductively on the structure of . Then we say that satisfies , written , if and only if the evaluation of in yields . Note that we speak about satisfaction only when the model and the sentence belong to the same signature.

Since in the definition of institutions signatures, sentences and models are fully abstract, the satisfaction of sentences by models is fully abstract too. Thus for each signature there is a satisfaction relation between -models and sentences, denoted . This is subject of an axiom known as the Satisfaction Condition whose meaning is often informally explained as the invariance of truth with respect to the change of notation: for each signature morphism , each -sentence and each -model ,

   

In concrete institutions one always has to define the satisfaction relation, commonly done by induction on the structure of the sentences (like in the case of . This principle, known as truth functionality, means that given a semantic context (model) the truth value of any compound sentence is determined from the truth values of its components. Truth functionality provides also the common method to establish the Satisfaction Condition in concrete institutions, by induction on the structure of the sentences. While in some cases this is an easy task ( is such an example) in other cases it can be highly non-trivial. Especially in the case of quantified logics the induction step corresponding the quantifications poses some technical problems, requiring some compositionality property for the models (see (Diaconescu, 2008)).

Our presentation of the mathematical definition of the concept of institution may be summarised as follows. An institution is a tuple where is a category, is a functor , is a contravariant functor , and for each signature , is a relation between -models and -sentences such that the Satisfaction Condition holds. Note that besides the Satisfaction Condition, the definition of institution includes other axioms encapsulated by the several categories and functors that are part of the definition.

e. Concrete Institutions

The institution theory literature (which includes part of the specification theory literature) contains countless examples of logical systems that have been formally captured as institutions. Among these there are first, second, higher order logics, logics with some form of partiality for the functions such as partial algebra and various dialects of order sorted algebras, non-classical logics such as intuitionistic ones, a wide diversity of modal logics, fuzzy and many valued logics, and so forth. All these institutions admit also many-sorted variants. Many examples of institutions arose on the basis of various combinations between other institutions. Several institutions related to programming look rather divorced from the common perception of what is a logical system, some of these being presented in (Sannella and Tarlecki, 2012).

f. Notes

The traditional style of doing logic has a rather global approach to signatures, they usually do not vary, and when they do this would be just extensions. By contrast, institution theory is genuinely multi signature oriented, with signature morphisms being a rather primitive concept. Moreover in concrete examples the institution-theoretic view is that these can be broader than extensions, they may rename and even collapse elements. This widening of the concept of signature morphism serves the purpose of specification theory but is also very convenient for abstraction. Having signature morphisms as a primitive concept is also crucial for the development of various important logic concepts at the abstract level, for example, quantification, interpolation, method of diagrams, saturated models, and so forth. Moreover, the generality of the concept of signature morphism in institution theory accommodates even first-order substitutions like in (Găină and Petria, 2010), or substitutions of propositional variables by compound propositions like in (Voutsadakis, 2002).

The Satisfaction Condition had appeared for the first time as an axiom in (Barwise, 1974), but in a much less abstract context than institution theory. Although in logic this appears as an indisputable property of logical systems, in computing science there was some criticism of being too strong and thus preventing some logical systems, albeit very marginal, from being institutions. More precisely, the critics of the Satisfaction Condition argued that the implication from the right to the left would be enough. Counter-criticism to this argues that in the absence of the full Satisfaction Condition as an equivalence, almost all general institution theory results both in model theory and in computing science become impossible. In defence of the Satisfaction Condition (Goguen, 1991) argues that those counterexamples arise due to some heavy incoherence between the respective concepts of signature morphism and satisfaction relation, that under a meaningful fix of the respective concept of signature morphism the Satisfaction Condition is rescued.

3. Institution-independent Model Theory

The institution-theoretic approach to model theory tends to be rather comprehensive, here we present some rudiments of it. This reading of this section may sometimes require some technical inclination from the side of the reader.

a. The Galois Connection between Syntax and Semantics

Given a signature in an institution we let

• for each , , and
• for each , .

These give what is called a Galois connection between the subsets of and those of operators allow also for the definition of semantic consequence: given any set of -sentences and any -sentence we say that is a semantic consequence of , written , when (that is every model that satisfies every sentence in satisfies too).

b. Logical Connectors

The semantics of the Boolean connectors can be formally defined in institutions also by using the operators. A -sentence is a conjunction of the -sentences and when . Or, is a negation of when . And similarly for disjunction, implication, etc. Note that, unlike their syntactic correspondents that are unique, the semantic conjunction, negation, implication, etc. are unique only up to semantic equivalence, which means that from this point of view sentences satisfied by the same models are indistinguishable. The definition of the Boolean connectors can be extended at the level of the whole institution: for example an institution has conjunctions when any two of its sentences have a conjunction, and so on.

c. Quantifiers

The institution theoretic treatment of quantifiers is semantic and relies crucially upon the concept of signature morphism essentially by assimilating valuations of variables with model expansions along the extension of the signature with the respective variables. While in concrete institutions one may discuss about valuations of variables into models as functions from to some underlying set theoretic carrier of , in the abstract setup this is not possible due to the lack of explicit set theoretic structures. However by assimilating the variables with the signature extensions obtained by adding them to the respective signatures, we may note that for any -model , there is a canonical one-to-one correspondence between the valuations and the -models such that their reducts to are just . This trick implies that variables can become part of the signatures, which breaks with the habit of traditional approaches to logic of keeping variables separated from the language (signature). The point of this separation is to avoid some clash between and the entities of . However this can be achieved differently without separating variables from the signatures, which anyway from the formal perspective poses several difficulties. The idea is very simple and comes from the practice of specification languages. One has just to qualify properly the variables by their signature context. For example a variable for a signature in the institution of many sorted first order logic would be a triple where is the name, the sort/type, and the signature of the variable. A signature becoming part of the data defining the variables prevents, by formal set theory reasons, any clash between and when adjoining to .

Hence at the level of abstract institutions a variable for a signature is just a signature morphism . Note that in the concrete situations variables-as-signature-morphisms support concepts of variables at the same level with the signatures, hence it is rather powerful. For example if the signature allows for higher order functions, then one can have variables for those. However often the intended variables are significantly more particular than what the respective concept of signature provides. This is one of the reasons why not any signature morphism can be considered as representing a variable. Another reason is that in concrete institutions the signature morphism representing variables are extensions, and moreover they are extensions with entities that have a proper qualification, as discussed above. A standard way to realize these restrictions abstractly is to have an abstract designated subclass of signature morphism as variables. Given in , a -sentence is a universal -quantification of a -sentence when for each -model , if and only if for all -models such that . Existential quantification is defined similarly. It is said that the institution has universal/existential -quantifications when any sentence as above has a universal/existential -quantification for any as above.

In logic in general and in model theory in particular it is well known that quantification by first-order variables has very good and desirable properties. This kind of quantification is captured at the abstract level by requiring that any signature morphism in is representable, which essentially means that there exists a -model such that there is a one-to-one correspondence between the -models with and the -model morphisms . The idea behind this is that in concrete situations valuations of variables can be represented by model morphisms from a ‘free model’ over the variables. In other words, when is a signature extension as discussed above, is the -model freely generated by , in standard actual situations being a term model over .

d. Diagrams

The method of diagrams is a widely pervasive method in model theory (see for example (Chang and Keisler, 1990)). Its institution-theoretic abstraction of Diaconescu (2004b) also plays an important role in many institution-independent model theory developments. In essence, the diagram of given a model represents a kind of comprehensive syntactic characterisation of . The institution-theoretic definition introduced in (Diaconescu, 2004b) axiomatises a category theoretic one-to-one correspondence between the model morphisms and the models satisfying an abstractly designated set of sentences . The signature of is not the signature of the model , instead there is an abstractly designated signature morphism

   

In the concrete examples in which the models have an underlying set theoretic structure, is usually the extension of with the elements of the underlying carrier of that are adjoined to as new constants.

The most typical examples come from classical first order model theory. Let be as described above, and let be the model that expands by interpreting the new constants by themselves. Then is the set of all atoms that are satisfied by . This corresponds to the case when the model morphisms are those that preserve the structure of the models, if we change the concept of model morphism then the diagram should change also. For example if we consider the elementary embeddings as model morphisms then is much larger, consisting of all first order sentences that are satisfied by . And so on. The narrower the class of model morphisms considered, the larger the corresponding diagrams.

The existence of institution-theoretic diagrams in concrete logical systems is a mark of coherence between the syntax (the kind of sentences involved) and the semantics (the concept of model morphism employed). For example non-hybrid modal logics lack diagrams because there is an unbalance between the syntax and the semantics (Kripke structures), in the sense that the syntax is too weak to express aspects of the semantics. On the other hand, the hybrid (modal) logics do have diagrams because they have more expressive power with respect to the Kripke frames.

e. Ultraproducts

The method of ultraproducts is a most important and remarkably powerful one in conventional model theory (Chang and Keisler, 1990). This has been realised at the abstract level of institution theory beginning with (Diaconescu, 2003), on the basis of the previously established concept of categorical ultraproduct (introduced perhaps first time in (Matthiessen, 1978)) and applied to the categories of models in institutions. This requires some familiarity with categorical limits and colimits. A filter on a set is a set of subsets of , such that when and when and . is an ultrafilter when in addition satisfies the property that for each , if and only if its complementary . Let us consider a family of -models in an institution and a filter on . For any let us denote the direct product of by . If has direct products then for any in there is a canonical projection

   

Then any colimit

   

of the diagram

   

is called an -product of . When is ultrafilter, -products are called ultraproducts. Due to the uniqueness up to isomorphisms of categorical direct products and of colimits it follows that -products are unique only up to isomorphisms too.

The foundation of the ultraproducts method in first-order model theory is constituted by a result in (Ło´s, 1955) which gives a ‘preservation’ property for the satisfaction by ultraproducts of models that is common to all sentences in first-order logic. This has been highly generalised in institution theory by decomposing it into a puzzle of general preservation results across connectors (Boolean, modalities) and quantifiers. Concrete instances of this result and of some of its extensions provide for free an ultraproducts method for a variety of logical systems, including unconventional ones for which such development was otherwise difficult to envisage.

A typical application of ultraproducts is the derivation of the compactness of the semantic consequence without having to resort to a proof system and a related completeness argument, which in general is technically very difficult. An institution is said to be compact when for each semantic consequence , where is a set of sentences and is a single sentence, there exists a finite set such that . In the presence of the preservation of the satisfaction relation under the ultraproduct construction of models, if in addition the institution has conjunctions and negations, we get the compactness of the institution. When adjoined to the institution-theoretic generalisation of the fundamental ultraproducts result of (Ło´s, 1955), this remarkably general property gives an abstract compactness result, which can be instantiated with little eort to a wide variety of concrete logical systems. The eciency of this path to compactness has become transparent for example in (Diaconescu and Stefaneas, 2007) in the case of a wide class of quantified modal systems.

f. Interpolation and Definability

Interpolation is an important property of logical systems which has a strikingly elementary formulation but which is usually very difficult to establish. Its common semantic version sounds like this:

given a -sentence and a -sentence , if then there exists a -sentence (called interpolant) such that and .

In other words, any semantic consequence is established by means of symbols that are common to both sentences. In institution theory interpolation is considered in a form that generalizes several aspects of its common formulation. First, the signature inclusions that appear implicitly in the formulation of interpolation are abstracted to arbitrary signature morphisms. Then the common formulation of interpolation corresponds to the situation when the institution comes with the signature morphisms restricted to inclusions only. However the generalisation of interpolation to arbitrary signature morphism allows in the concrete situations for consideration of signature morphisms that may rename or even collapse syntactic entities. While such extended form of interpolation may be unusual in conventional logic, it is used in specification theory. A second generalisation of the concept of interpolation replaces individual sentences by finite sets of sentences. While in logics that have conjunction (such as classical propositional, first-order logics, and so forth) this does not mean anything, it is very meaningful in logics lacking conjunctions, such as equational or Horn clause logics. In the latter ones interpolation may fail artificially due to unrealistic single sentence style formulation. These get us to the following definition of interpolation. A commuting square of signature morphisms like below

 
is an interpolation square when for any finite sets and such that

   

there exists a finite set

   

such that

   

and

   

Such commuting squares are meant to emulate the intersection-union of signatures from the common formulation of interpolation, with in the role of and in the role of . However in the common formulation of interpolation it is important that is the lowest signature above and . In the generalised formulation of interpolation this property appears as a category theoretic condition, that the commuting square is a pushout in the category of the signatures of the institution. But when considering interpolation as a property of the institution as a whole, it is in general not meaningful to look for interpolation in all pushout squares. This leads to another generalisation layer in the formulation of interpolation, which restricts abstractly the range of and to designated subclasses of signature morphisms. Thus, given and subclasses of signature morphisms, the institution has -interpolation when each pushout of a span of signature morphisms with and is an interpolation square.

Institution-theoretic interpolation has been established at the general level in relation to several different causes. One cause can be an axiomatizability property of the institution, like in (Diaconescu, 2004a). A typical example here is many sorted equational logic which has -interpolation with being the injective signature morphisms and being all signature morphisms. Another cause can be the Robinson consistency property, like in (Găină and Popescu, 2007). An instance of this is many sorted first order logic which has -interpolation when either of consists of signatures morphisms that are injective on the sorts. And yet another cause can be the existence of an adequate translation to an institution that has well established interpolation properties, like in (Diaconescu, 2012b).

Definability is one of the traditional important consequences of interpolation. The concept of definability has been approached in institution theory by Petria and Diaconescu (2006) in a rather similar way to interpolation, by abstracting the new (presumably definable) symbols for signatures to arbitrary abstract signature morphisms. The institution-theoretic study of definability in (Petria and Diaconescu, 2006) revealed that, besides interpolation, axiomatizability properties (considered in the generalised form introduced in (Diaconescu, 2004a)) may constitute a primary cause for definability.

g. Layered Completeness

The concept of institution can be enhanced with a proof theoretic structure (Meseguer, 1989) by adding for each signature an entailment relation between sets of -sentences and single -sentences subject to the following axioms:

• when ;
• If for each and then ; and
• For each signature morphism if then .

The entailment system is sound for the respective institution when implies and is complete when the reverse implication holds. These are institution-theoretic generalisations of the common concepts of soundness and completeness from logic and model theory. Soundness is an obligatory property that is also easy to establish in the concrete situations. Completeness is very desirable but hard to establish; completeness results are difficult ones.

The institution-theoretic approach to completeness results is a layered one based upon the observation that usually proof systems can usually be deconstructed into several layers that correspond to the structure of the sentences involved, and that completeness can be developed at each layer relative to the completeness at the previous one. This means that at each layer the respective entailment system is considered fully abstract, and hence the proof rules that build the next layer come in a form that is independent of the previous layers. The total completeness
result is thus obtained as a combination of smaller independent completeness results, each of them having the potential to be reused in other contexts.

For instance, let us consider the case of the completeness of Horn clause logic with equality, the fragment of first order logic with equality that restricts the sentences to those of the form , where is a finite conjunction of (equational and relational) atoms and is a single atom. This completeness can be decomposed into three layers. At the base layer we consider the institution that has as sentences only equational and relational atoms. For that we have a complete proof system defined by

• for each term ;
• for all terms ;
• for all terms ;
• for any function symbol of arity ; and
• for any relation symbol or arity .

At the next layer we add the sentences of the form where is a finite conjunctions of atoms and is a single atom and extend the proof system with the meta-rule

• if and only if .

The crucial point here is that this step does not depend upon the previous layer, meaning that information can be completely encapsulated, allowing the addition of implications over an arbitrary institution endowed with a complete entailment system. Then the completeness at the new layer is obtained. The final layer consists of adding the universal quantification to the sentences and a rule and a meta-rule to the proof system.

• for any substitution of variables with terms over the variables ; and
• if and only if .

This step can be also developed independently of the previous layer, over an institution endowed with a complete entailment system considered fully abstractly. This requires however an abstract treatment of substitutions. The completeness at the final upper layer is also obtained. By instantiating now the base layer to the one of the atoms in first-order logic with equality and the final layer to universal first-order quantification we get a complete proof system for Horn clause logic with equality. But all the compound completeness results can be also used separately on different instances of the abstract institutions, thus obtaining complete proof systems in various different logical systems. For example we can obtain a complete proof system for the universal fragment of first-order logic, that is, sentences of the form where is a quantifier-free sentence, just by replacing the mid layer above by the proof system of propositional logic.

h. Notes

The institution-theoretic concept of diagrams introduced by Diaconescu (2004b) is significantly simpler than a previously introduced one in (Tarlecki, 1986a,c). Since (Diaconescu, 2004b) this has been used rather intensively in many institution theory works.

The many-sorted first-order logic instance of the general interpolation result of (Găină and Popescu, 2007) represents an elegant solution by means of institution theory to a question about the limits of interpolation in many-sorted first-order logic that stayed as conjecture for several years. The layered completeness was introduced by Borzyszkowski (2002) within the context of the study of complete calculi for structured specifications. The example discussed here comes from Codescu and Găină (2008). Other works on layered completeness include (Găină and Petria, 2010) (two layers), (Găină et al., 2012) (four layers).

Other important model theory methods that have been developed at the level of abstract institutions include saturated models (Diaconescu and Petria, 2010), forcing (Găină and Petria, 2010), omitting types (Găină, 2014). These have lead to remarkable high generalisations of deep model theory results including downwards Löwenheim-Skolem in (Găină, 2014) and the Keisler-Shelah characterisation of first-order elementary equivalence as isomorphism under ultrapowers in (Diaconescu and Petria, 2010).

4. Logic by Translation

Institution theory is very well positioned with respect to the logic-by-translation paradigm because of its perspective on logical systems as mathematical objects/structures. Concepts of structure preserving mappings between institutions, when regarded as mathematical structures, constitute mathematical formalisations for translation concepts. The importance of this idea has been recognised right from the beginnings of institution theory.

a. Morphisms and Comorphisms

Institutions as mathematical structures invite several concepts of ‘morphisms’, or structure preserving mappings between institutions. All of them define three components, corresponding to the translations of the signatures, of the sentences, and of the models. Moreover in each case an axiom that represents an invariance property of the satisfaction relation with respect to these translations is imposed.

The original structure preserving mapping between institutions has been defined by Goguen and Burstall (1992), and called just morphism of institutions. Given institutions and a morphism consists of

• a functor translating -signatures to -signatures;
• for each -signature a sentence translation
• for each -signature a model translation/reduct

such that both and are natural transformations (this is a category theory notion, ‘naturality’ in this context meaning a coherence property of the component translations with respect to the signature morphisms) and such that the following Satisfaction/Translation Condition holds for each -model and each -sentence :

Institution morphisms have the flavour of ‘projecting’ from a more complex institution to a simpler one, like the following morphism from first-order to propositional logic. This maps any first-order logic signature to its set of sentences (each sentence being regarded as a propositional variable in a propositional logic signature), is just the first-order sentence , and being just the propositional logic model consisting of all -sentences that hold in .

By reversing the translation of the signatures we get the concept of comorphism of institutions which has the flavour of an ‘embedding’ of a simpler institution into a more complex one. A comorphism consists of

• a functor translating -signatures to -signatures;
• for each -signature a sentence translation ; and
• for each -signature a model translation/reduct .

such that both and are natural transformations and the following Satisfaction/Translation Condition holds for each -model and each -sentence :

   

The embedding of propositional logic into first-order logic can be captured as a comorphism that interprets any set of propositional variables as a first-order signature that has only relation symbols of arity zero; note that both  and are identities.

The level of preservation of institution-theoretic structure by morphisms and comorphisms is equal, so just from the viewpoint of institutions as mathematical structures one cannot say which of these is more adequate to play the role of morphisms for the category of institutions. This means that there can be at least two categories that have institutions as their objects, both of them equally legitimate from the perspective of structure. This constitutes a good example of the idea, prevalent in category theory, that a category is best described by its morphisms rather than its objects. The conceptual symmetry between institution morphisms and comorphisms got a formal explanation by Arrais and Fiadeiro (1996) where it is showed that a categorical adjunction between the categories of the signatures of two institutions and determine a canonical one-to-one correspondence between the morphisms and the comorphisms .

b. Encodings

Besides embeddings of simpler logics into more complex ones, the concept of comorphism supports also ‘encodings’ of more complex logics into simpler ones. Famous cases such as the translation of classical propositional logic into intuitionistic by Kolmogorov (1925) or the standard translation of modal logic into first-order logic by van Bentham (1988) can be presented as comorphisms. Most often the cost representing the difference in complexity is payed at the level of translation of the signatures, mapping signatures to theories in the target institution. This can be explained as a comorphism where denotes the canonically defined institution of -theories, that has as signatures the pairs where is an -signature and a set of -sentences. (Note that ‘theories’ here are mere sets of sentences rather than sets of sentences closed under some consequence relation as meant in some logical studies.) The comorphism are sometimes called theoroidal comorphisms. The two encodings mentioned above represent a notable exception, as they can be presented as plain rather than theoroidal comorphisms (Goguen and Ro¸su, 2002), in both cases the encoding cost being payed at the level of the translation of the sentences.

c. Borrowing

Comorphism-based encodings between institutions represent the main tool for the institution theoretic approach to the logic-by-translation paradigm. Suppose we want to establish a property in an institution but due to various reasons this is rather difficult. Then we can look for a suitable encoding such that the translation of along the encoding can be established in , and moreover such that we can reflect back to this conclusion in the form of . In this case we say that is ‘borrowed’ from along the encoding. This requires the respective encoding to satisfy some specific properties that are conducive for the borrowing process. The institution theory literature abounds of such examples, that include interpolation, definability, diagrams, saturated models, etc.

One especially important case is that of the borrowing of a consequence relation. Let be a consequence to be established. If it holds then by a simple argument relying upon the Satisfaction Condition of the comorphism we have that

   

holds too. If comes equipped with a complete proof system then

   

may be established by proof theoretic means. Now in order to get the conclusion back to we need a reflection property for the semantic consequence, which does not happen in general. However a standard way to ensure this is to check that the comorphism is conservative, which means that for any -model there exists a -model such that .

d. Notes

The importance of comorphisms and other types of structure preserving mappings between institutions has been understood gradually, with the paper (Goguen and Ro¸su, 2002) presenting a systematic comparative overview of the different notions of morphisms between institutions. That paper also fixed a lot of current terminology, including for example the term ‘comorphism’.

The work (Mossakowski et al., 2005) gave the institution-theoretic answer for the contest question of the 1st World Congress on Universal Logic (Montreux, Switzerland, 2005), namely what is the identity of a logic? The answer was that it is an equivalence class of institutions under equivalence of institutions. Briefly, the concept of equivalence of institutions proposed by Mossakowski et al. (2005) is a comorphisms (or alternatively a morphism) that consists of categorical equivalences at all levels.

The borrowing of a consequence relation is the foundation for formal verification by translation within the context of logic-based formal system specification. A specification based upon a source institution may have very good expressivity and readability but may lack adequate proof support. The solution is to shift the formal verification process across an encoding to an institution that is supported by good theorem proving tools, such as theorem provers, proof assistants, and so forth. Within the context of the heterogenous specification paradigm this has become a rather standard practice (Mossakowski, 2005), which is very economical since it makes good use of existing tools instead of building new ones.

5. Contributions to Computing Science

The contribution of institution theory to computing science is manifold, the most basic one being that it sets a standard style of developing new specification languages that requires at the beginning to define a logical system captured as institution and then develop all the language constructs solidly and rigorously backed by corresponding mathematical entities in the underlying institution.

a. Structured Specifications

Software systems tend to be very complex, and likewise their formal specifications. One key device for the management of this complexity is a structuring mechanism for specifications that allows to develop them in modular way. It has been noticed that structuring systems are largely, if not completely, independent of the logical systems underlying specification formalisms. Hence the idea to study the structuring of specifications and programs at a conceptual level that abstracts away the details of logical systems and instead exploits some of their compositionality properties. This has been the original motivation for institution theory.

Given an institution, considered abstractly, a structured specification is just a term formed by applying a specific fixed set of building operators to blocks consisting of finite set of sentences in the institutions (called basic, flat or unstructured specifications). Then by induction on the structure of a specification one may calculate its signature and its class of models . Seminal works such as (Sannella and Tarlecki, 1988) have proposed a core set of specification-building operators consisting of renaming (translations), sum, hiding (derivation) which can express most of the concrete structuring operations in the actual specification languages. Often an initial semantics operator is added in order to deal with initial semantics specification modules. A lot of results have been developed on this conceptual basis, providing an uniform and solid foundation for modular software development. A particularly remarkable one is the layered completeness result of Borzyszkowski (2002) that lifts a proof system (considered in the form of an abstract entailment system) from the base institution to structured specifications; under a set of general conditions expressed as properties of the base institution, the completeness of the former yields the completeness of the latter.

A later development by Diaconescu (2012a) proposes an even more abstract approach that avoids particular choices of sets of specification building operators. This abstracts the (structured) specifications as signatures in an abstract ‘upper level’ institution , the relationship to the base institution (representing the underlying logic) being axiomatised as a special kind of institution morphism, whose sentence translations are identities, and whose model translations/reducts are inclusions.

b. Heterogeneous Specifications

The increasing complexity of current systems has led to an understanding of the limitations of specification formalisms based upon single logical systems. Hence the emergence of the heterogeneous specification environments based on multiple logical systems. A standard view of such heterogeneous logical environments, actually realised by CafeOBJ (Diaconescu and Futatsugi, 1998) and Hets (Mossakowski, 2005), is as diagrams of institutions that are linked by comorphisms. However this raises the difficult question of how to lift specification theory to the heterogenous level. The answer comes from a category-theoretic construction that originated from algebraic geometry by Grothendieck (1963), and that can be replicated to institutions in order to ‘flatten’ a diagram of institutions to a single institution that retains all data provided by the respective diagram of institutions. This construction is known as the Grothendieck institution associated to the respective diagram. The main idea is to aggregate together all institutions of the diagrams into a big institution and label all the entities by their origin (node or edge in the diagram). This means that a signature of the Grothendieck institution is a pair where is a node in the diagram and is an signature in the institution at . A signature morphism in the Grothendieck institution is a pair where is an edge in the diagram and is a signature morphism in the institution at from the translation of across the institution comorphisms at to . The -sentences are just the -sentences (at ) and likewise the models, but the translations of both sentences and models across make use of the respective translations given by the comorphism at and the local translations corresponding to . The Grothendieck institution satisfaction relation is just of the institution at .

A series of properties required by specification theory have been gradually established for Grothendieck institutions. These results usually provide sets of sucient (and often necessary) conditions for lifting of institution-theoretic properties from the local level of the component institutions to the global level of the Grothendieck institution.

c. Ontologies

Computer science ontologies can be regarded as logic-based formal specifications. On the basis of this observation Goguen (2006) introduces the institution-theoretic trend in theory of ontologies which represents more or less a rephrasing of well established specification theory concepts and results in an ontology theoretic setup. This has brought several notable gains for ontologies, such as very well developed structuring technologies and the Grothendieck institution approach to logical heterogeneity (Kutz et al., 2010).

This line of development plays the core role in the OMG standard Ontology, Modeling and Specification Integration and Interoperability (OntoIOp).

d. Logic Programming

The Herbrand theorems as foundations of the logic-programming paradigm have been developed at the level of abstract institutions by Diaconescu (2004c). This has opened the possibility to develop logic programming over non-conventional logical structures, thus providing solid foundations for the combination of logic programming and other computing paradigms. Particularly important results in this line of developments are the Herbrand-based foundations for constraint solving (Diaconescu, 2008), which show that at the denotational level constraint solving is just an instance of plain (abstract) logic programming, and logic programming for services (Ţuţu and Fiadeiro, 2015b) that extends the original approach over a concept of generalized substitution system (Ţuţu and Fiadeiro, 2015a).

e. Notes

The work on the specification language Clear (Burstall and Goguen, 1980) was very influential and preceded the institution-theoretic structuring of specifications. Another particularly influential work in this area was (Diaconescu et al., 1993).

Grothendieck institutions, preceded by an attempt by Diaconescu (1998) to lift ‘by-hand’ specification theory concepts and results to the heterogeneous level, have been originally introduced by Diaconescu (2002) but in a slightly improper way using institution morphisms at the edges of the diagram representing the heterogeneous environment; that was soon corrected by Mossakowski (2002) to comorphisms.

The treatment of variables as signature extensions outlined in Sec. 3.c plays a key role in the institution-independent study of logic programming. It is an essential feature of the institutional approach to Herbrand theorems, one that has enabled the development of some of the most fundamental semantic concepts to logic programming, like query and solution, in arbitrary institutions. Despite such mild assumptions, the logic-programming semantics of services (Ţuţu and Fiadeiro, 2015b) does not fit into the framework proposed in (Diaconescu, 2004c). This has led to an upgrade of the original approach, to Herbrand theorems over a concept of generalized substitution system (Ţuţu and Fiadeiro, 2015a) that extends institutions by allowing for direct representations of variables and substitutions, much in the spirit of context institutions (Pawlowski, 1996). The connection between the substitution-system-based and the original institution-independent approach to logic programming was studied in depth in (Ţuţu and Fiadeiro, 2015c).

6. Extensions

While non-classical logics can be captured properly as institutions, some of their fine aspects may be beyond the conventional institution theory. For example, the institutions of many-valued logics handle the ternary aspect of the satisfaction relation by adjoining truth value to the sentences; in this way we get a binary satisfaction relation. While this works well with respect to most aspects of many-valued logics, it cannot handle graded (non-binary) consequences. The same with modal logics, the conventional concept of institution does not allow for a general semantics of modalities. These shortcomings have been overcome by extensions of the definition of institution towards non-classical aspects of logics.

a. Many-valued Truth

The many-valued extension of institution theory is very simple, just replace the binary truth values with any set of truth values. The satisfaction relation becomes a function

   

that for each sentence and model gives a truth value interpreted as a satisfaction degree. The Satisfaction Condition gets rephrased as

   

Very often it is necessary that comes as a partial order of some kind, such as lattice. In order to get a genuine many-valued implication one needs even more, that is a residuated lattice.

b. Modalities

The stratified institutions of Aiguier and Diaconescu (2007) refine institutions by considering models with states. Thus each model comes equipped with a designated set , and this is subject to several coherent conditions. In the case of Kripke models , gives the set of the possible worlds.

c. Notes

The idea to extend the definition of institution to many-valued truth arose at the beginning of institution theory (Mayoh, 1985) motivated by research in data base theory; this was already mentioned in (Goguen and Burstall, 1992). Later works on many-valued institutions include (Eklund and Helgesson, 2010; Diaconescu, 2013, 2014).

7. References and Further Reading

a. Primary Sources

• Răzvan Diaconescu. Institution-independent Model Theory. Birkhäuser, 2008.
• Joseph Goguen and Rod Burstall. Institutions: Abstract model theory for specification and programming. Journal of the Association for Computing Machinery, 39(1):95–146, 1992.
• Joseph Goguen and Grigore Ro¸su. Institution morphisms. Formal Aspects of Computing, 13:274–307, 2002.
• José Meseguer. General logics. In H.-D. Ebbinghaus et al., editors, Proceedings, Logic Colloquium, 1987, pages 275–329. North-Holland, 1989.
• Till Mossakowski, Joseph Goguen, Răzvan Diaconescu, and Andrzej Tarlecki. What is a logic? In Jean-Yves Béziau, editor, Logica Universalis, pages 113–133. Birkhäuser, 2005. 19
• Till Mossakowski, Răzvan Diaconescu, and Andrzej Tarlecki. What is a logic translation? Logica Universalis, 3(1):59–94, 2009.
• Donald Sannella and Andrzej Tarlecki. Foundations of Algebraic Specifications and Formal Software Development. Springer, 2012.

b. Secondary Sources

• Marc Aiguier and Răzvan Diaconescu. Stratified institutions and elementary homomorphisms. Information Processing Letters, 103(1):5–13, 2007. 01.
• Arrais and José L. Fiadeiro. Unifying theories in different institutions. In Magne Haveraaen, Olaf Owe, and Ole-Johan Dahl, editors, Recent Trends in Data Type Specification, volume 1130 of Lecture Notes in Computer Science, pages 81–101. Springer, 1996.
• Edigio Astesiano, Michel Bidoit, Hélène Kirchner, Berndt Krieg-Brückner, Peter Mosses, Don Sannella, and Andrzej Tarlecki. CASL: The common algebraic specification language. Theoretical Computer Science, 286(2):153–196, 2002.
• Tomasz Borzyszkowski. Logical systems for structured specifications. Theoretical Computer Science, 286(2):197–245, 2002.
• Rod Burstall and Joseph Goguen. The semantics of Clear, a specification language. In Dines Bjorner, editor, 1979 Copenhagen Winter School on Abstract Software Specification, volume 86 of Lecture Notes in Computer Science, pages 292–332. Springer, 1980.
• Maura Cerioli and José Meseguer. May I borrow your logic? (transporting logical structures along maps). Theoretical Computer Science, 173:311–347, 1997.
• Mihai Codescu and Daniel Găină. Birkhoff completeness in institutions. Logica Universalis, 2(2):277–309, 2008.
• Răzvan Diaconescu. Extra theory morphisms for institutions: logical semantics for multi-paradigm languages. Applied Categorical Structures, 6(4):427–453, 1998. A preliminary version appeared as JAIST Technical Report IS-RR-97-0032F in 1997.
• Răzvan Diaconescu. Grothendieck institutions. Applied Categorical Structures, 10(4):383–402, 2002. Preliminary version appeared as IMAR Preprint 2-2000, ISSN 250-3638, February 2000.
• Răzvan Diaconescu. Institution-independent ultraproducts. Fundamenta Informaticæ, 55(3-4):321–348, 2003.
• Răzvan Diaconescu. An institution-independent proof of Craig Interpolation Theorem. Studia Logica, 77(1):59–79, 2004a.
• Răzvan Diaconescu. Elementary diagrams in institutions. Journal of Logic and Computation, 14(5):651–674, 2004b.
• Răzvan Diaconescu. Herbrand theorems in arbitrary institutions. Information Processing Letters, 90:29–37, 2004c.
• Răzvan Diaconescu. An axiomatic approach to structuring specifications. Theoretical Computer Science, 433:20–42, 2012a.
• Răzvan Diaconescu. Borrowing interpolation. Journal of Logic and Computation, 22(3):561–586, 2012b.
• Răzvan Diaconescu. Institutional semantics for many-valued logics. Fuzzy Sets and Systems, 218:32–52, 2013.
• Răzvan Diaconescu. Graded consequence: an institution theoretic study. Soft Computing, 18(7):1247–1267, 2014.
• Răzvan Diaconescu and Kokichi Futatsugi. CafeOBJ Report: The Language, Proof Techniques, and Methodologies for Object-Oriented Algebraic Specification, volume 6 of AMAST Series in Computing. World Scientific, 1998.
• Răzvan Diaconescu and Marius Petria. Saturated models in institutions. Archive for Mathematical Logic, 49(6):693–723, 2010.
• Răzvan Diaconescu and Petros Stefaneas. Ultraproducts and possible worlds semantics in institutions. Theoretical Computer Science, 379(1):210–230, 2007.
• Răzvan Diaconescu, Joseph Goguen, and Petros Stefaneas. Logical support for modularisation. In Gerard Huet and Gordon Plotkin, editors, Logical Environments, pages 83–130. Cambridge, 1993. Proceedings of a Workshop held in Edinburgh, Scotland, May 1991. 20
• Patrick Eklund and Robert Helgesson. Monadic extensions of institutions. Fuzzy Sets and Systems, 161:2354–2368, 2010.
• Joseph Goguen. Types as theories. In George Michael Reed, Andrew William Roscoe, and Ralph F. Wachter, editors, Topology and Category Theory in Computer Science, pages 357–390. Oxford, 1991. Proceedings of a Conference held at Oxford, June 1989.
• Joseph Goguen. Data, schema, ontology and logic integration. Journal of IGPL, 13(6):685–715, 2006.
• Joseph Goguen and Rod Burstall. Introducing institutions. In Edward Clarke and Dexter Kozen, editors, Proceedings, Logics of Programming Workshop, volume 164 of Lecture Notes in Computer Science, pages 221–256. Springer, 1984.
• Daniel Găină. Forcing, downward Löwenheim-Skolem and omitting types theorems, institutionally. Logica Universalis, 8(3): 469–498, 2014.
• Daniel Găină and Marius Petria. Completeness by forcing. Journal of Logic and Computation, 20(6):1165–1186, 2010.
• Daniel Găină and Andrei Popescu. An institution-independent proof of Robinson consistency theorem. Studia Logica, 85(1): 41–73, 2007.
• Daniel Găină, Kokichi Futatsugi, and Kazuhiro Ogata. Constructor-based logics. J. of Universal Computer Science, 18 (2204–2233), 2012.
• Oliver Kutz, Till Mossakowski, and Dominik Lücke. Carnap, Goguen, and the hyperontologies – logical pluralism and heterogeneous structuring in ontology design. Logica Universalis, 4(2):255–333, 2010.
• Brian Mayoh. Galleries and institutions. Technical Report DAIMI PB-191, Aarhus University, 1985.
• Till Mossakowski. Comorphism-based Grothendieck logics. In K. Diks and W. Rytter, editors, Mathematical foundations of computer science, volume 2420 of Lecture Notes in Computer Science, pages 593–604. Springer, 2002.
• Till Mossakowski. Heterogeneous specification and the heterogeneous tool set. Habilitation thesis, University of Bremen, 2005.
• Wieslaw Pawlowski. Context institutions. In Magne Haveraaen, Olaf Owe, and Ole-Johan Dahl, editors, Recent Trends in Data Type Specification, volume 1130 of Lecture Notes in Computer Science, pages 436–457. Springer, 1996.
• Marius Petria and Răzvan Diaconescu. Abstract Beth definability in institutions. Journal of Symbolic Logic, 71(3):1002–1028, 2006.
• Donald Sannella and Andrzej Tarlecki. Specifications in an arbitrary institution. Information and Control, 76:165–210, 1988.
• Andrzej Tarlecki. On the existence of free models in abstract algebraic institutions. Theoretical Computer Science, 37:269–304, 1986a.
• Andrzej Tarlecki. Bits and pieces of the theory of institutions. In David Pitt, Samson Abramsky, Axel Poigné, and David Rydeheard, editors, Proceedings, Summer Workshop on Category Theory and Computer Programming, volume 240 of Lecture Notes in Computer Science, pages 334–360. Springer, 1986b.
• Andrzej Tarlecki. Quasi-varieties in abstract algebraic institutions. Journal of Computer and System Sciences, 33(3):333–360, 1986c.
• Ionuţ Ţuţu and José L. Fiadeiro. From conventional to institution-independent logic programming, 2015a.
• Ionuţ Ţuţu and José L. Fiadeiro. Service-oriented logic programming, 2015b.
• Ionuţ Ţuţu and José L. Fiadeiro. Revisiting the institutional approach to Herbrand’s theorem. In Algebra and Coalgebra in Computer Science, Leibniz International Proceedings in Informatics. Schloss Dagstuhl, 2015c.
• George Voutsadakis. Categorical abstract algebraic logic: Algebrizable institutions. Applied Categorical Structues, 10: 531–568, 2002.

c. Auxiliary Non-Institutional Sources

• Jon Barwise. Axioms for abstract model theory. Annals of Mathematical Logic, 7:221–265, 1974. 21
• Jean-Yves Béziau, editor. Universal Logic: an Anthology. Studies in Universal Logic. Springer Basel, 2012.
• Chen-Chung Chang and H. Jerome Keisler. Model Theory. North Holland, Amsterdam, 1990.
• Samuel Eilenberg and Saunders Mac Lane. General theory of natural equivalences. Transactions of the American Mathematical Society, 58:231–294, 1945.
• Joseph Goguen. A categorical manifesto. Mathematical Structures in Computer Science, 1(1):49–67, March 1991. Joseph Goguen. Programming Research Group Technical Monograph PRG–72, Oxford University, March 1989.
• Alexandre Grothendieck. Catégories fibrées et descente. In Revêtements étales et groupe fondamental, Séminaire de Géométrie Algébraique du Bois-Marie 1960/61, Exposé VI. Institut des Hautes Études Scientifiques, 1963. Reprinted in Lecture Notes in Mathematics, Volume 224, Springer, 1971, pages 145–94.
• Andrei N. Kolmogorov. On the principle of the excluded middle. Matematicheskii Sbornik, 32(646–667), 1925. (in Russian).
• Jerzy Ło´s. Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres. In Mathematical Interpretation of Formal Systems, pages 98–113. North-Holland, Amsterdam, 1955.
• Saunders Mac Lane. Categories for the Working Mathematician. Springer, second edition, 1998.
• Günter Matthiessen. Regular and strongly finitary structures over strongly algebroidal categories. Canadian Journal of Mathematics, 30:250–261, 1978.
• Alfred Tarski. The semantic conception of truth. Philos. Phenomenological Research, 4:13–47, 1944.
• Johan van Bentham. Modal Logic and Classical Logic. Humanities Press, 1988.

 

Author Information

Răzvan Diaconescu
Email: Razvan.Diaconescu@imar.ro
Simion Stoilow Institute of Mathematics of the Romanian Academy
Romania