From propositional logic to subset logic to partition logic

From propositional logic to subset logic

This note outlines the following sequence of ideas. First, ordinary propositional logic is reinterpreted as the logic of subsets of a universe set U, with the propositional case being isomorphic to the special case of U = 1. Then the category-theoretic duality between subsets of a set and partitions on a set is used to broach the idea of a dual logic of partitions. At the end of the note, a link is given to my paper in the Review of Symbolic Logic which develops the logic of partitions from the basic ideas up through the correctness and completeness theorems for a tableau system of partition logic.

Largely due to the efforts of F. William Lawvere in category theory, there a “rethinking” of logic taking place. Lawvere’s best accessible restatement of logic is Appendix A: Logic as the Algebra of Parts in: Lawvere, F. William and Robert Rosebrugh 2003, Sets for Mathematics. Cambridge: Cambridge University Press.

For instance, what is the subject matter of the “propositional” part of mathematical logic since the notion of a “proposition” is far from being a precise mathematical concept? In Lawvere’s vision of “Logic as the Algebra of Parts,” a “part” is just Lawvere-speak for a “subobject.” For present purposes, we may restrict attention to the category of sets where “subobject” just means “subset.” Hence under this interpretation, the atomic variables in the formulas of “propositional” logic would be interpreted not as propositions but as subsets of some fixed (non-empty) universe set U. The “connectives” of this logic would be interpreted not as operations on propositions (such as “and” or “or”) but as operations on subsets (such as intersection or union).

The propositional calculus considers “Propositions” p, q, r,… combined under the operations “and”,”or”, “implies”, and “not”, often written as $p\land q$ , $p\lor q$ , $p\Rightarrow q$ , and $\lnot p$ . Alternatively, if P, Q, R,… are subsets of some fixed set U with elements u, each proposition p may be replaced by the proposition $u\in P$ for some subset $P\subset U$ ; the propositional connectives above then become operations on subsets; intersection $\land$ , union $\lor$ , implication ( $P\Rightarrow Q$ is $\lnot P\lor Q$ ), and complement of subsets. [Mac Lane, Saunders and Ieke Moerdijk 1992. Sheaves in Geometry and Logic: A First Introduction to Topos Theory. New York: Springer, p. 48]

A tautology of this subset logic would then be a formula such that, regardless of what subsets of U are assigned to the atomic variables, would always evaluate to the universe set U. We might call this a subset tautology.

One special case of the universe set U is 1, “the” singleton set with only two subsets, itself and the null set, which we could denote as 1 and 0. The subset operations on these two subsets could be defined by the usual “truth tables” for the “propositional connectives” where a “proposition” is mathematically modeled as a variable with the possible values 0 and 1 (for F and T). Then one arrives at the notion of a truth-table tautology, which is a formula that, regardless of the assignments of 0 or 1 to the atomic variables, would always evaluate to the value 1. Now, clearly any subset tautology is also a truth table tautology since U = 1 is only a special case for the universe set U. It is an interesting and philosophically “fateful” fact, that the converse is true. A formula that always evaluates to the universe set U = 1 in that very special case will evaluate to the universe set U for arbitrary non-empty U when arbitrary subsets of U are substituted for the atomic variables. Hence the distinct concepts of a subset tautology and a truth-table tautology turn out to be the same in the context of subsets of a universe set U.

The fact that “subset tautology = truth-table tautology” is philosophical fateful since it has allowed the very special case of U = 1, i.e., the propositional interpretation, to completely “take over” and crowd out the interpretation of subset logic and hence the very name of “propositional logic.” The 0-1 propositional interpretation is, to be sure, an extremely important special case for U, and a special case that suffices to delimit the valid formulas, but the broader concept of logic is subset logic, not just propositional logic.

The historical background

In Alonzo Church’s “Historical notes” on the “propositional calculus,” he noted that Boole actually developed the algebra of subsets.

The algebra of logic has its beginning in 1847, in the publications of Boole and De Morgan. This concerned itself at first with an algebra or calculus of classes, to which a similar algebra of relations was later added. Though it was foreshadowed in Boole’s treatment of “Secondary Propositions,” a true propositional calculus perhaps first appeared from this point of view in the work of Hugh MacColl, beginning in 1877. [Church, Alonzo 1956. Introduction to Mathematical Logic. Princeton: Princeton University Press, pp. 155-6]

In contrast, Frege used the propositional interpretation from the outset in his Begriffsschrift of 1879. Boole, on the other hand, noted that the propositional interpretation was essentially a special case.

But while the laws and processes of the method remain unchanged, the rule of interpretation must be adapted to new conditions. Instead of classes of things, we shall have to substitute propositions, and for the relations of classes and individuals, we shall have to consider the connexions of propositions or of events. [Boole, George 1854. An Investigation of the Laws of Thought on which are founded the Mathematical Theories of Logic and Probabilities. Cambridge: Macmillan and Co., p. 162]

Moreover Boole emphasized the fateful fact that for the purposes of valid calculations with what we now call “Boolean operations,” it suffices to take the values to be just 0 or 1.

We may in fact lay aside the logical interpretation of the symbols in the given equation; convert them into quantitative symbols, susceptible only of the values 0 and 1; perform upon them as such all the requisite processes of solution; and finally restore them to their logical interpretation. [Boole, Ibid., p. 70 (his italics)]

From the viewpoint of Lawvere’s “Logic as the Algebra of Parts,” Boole’s treatment of logic as the algebra of subsets (today called “Boolean algebra”), with the propositional interpretation being an important special case, is surprisingly modern.

From subset logic to partition logic

I have a vested interest in the broader interpretation of logic. If logic is restricted to the special case of propositions, then there is no notion of a “dual” of a proposition. But if logic is seen broadly as the algebra of subsets on a universe set then there is a natural notion of the dual of a subset or “part.” “The dual notion (obtained by reversing the arrows) of ‘part’ is the notion of partition.” [Lawvere and Rosebrugh, op. cit., p. 85] This has long been seen in the duality between the notions of subobject and quotient object throughout modern algebra (e.g., subgroup versus quotient group). In view of that duality, if logic is the logic of subsets, then the idea arises of a dual logic of partitions. For over a century there has been a rudimentary version of that dual logic for just the meet and join operations in the lattice of partitions on a universe set U studied in combinatorial theory and algebra. But now the implication operation as well as the other logical operations on partitions have been successfully defined so that the logic of partitions can be fully developed. My recent paper in the Review of Symbolic Logic : “The Logic of Partitions: Introduction to the Dual of the Logic of Subsets,” goes from basic concepts up through the correctness and completeness theorems for a tableau system of partition logic. My reprint of the paper can be downloaded from my website here.

From propositional logic to subset logic to partition logic