The Logic of Partitions David Ellerman University of Ljubljana Slovenia Abstract This book is an introduction to the logic of partitions on a set as well as the quantum logic of partitions direct sum decompositions or DSDs on a vector space Partitions of a set are categorically dual to subsets of a set Thus the logic of partitions is in that sense the dual to the Boolean logic of subsets usually presented as the special case of propositional logic Since partitions can be seen as the inverse image partitions of random variables or numerical attributes without the actual values but retaining the information as to when the values are the same or di erent partition logic is the logic of random variables or numerical attributes abstracted from the actual values On the lattice of partitions of an arbitrary unstructured set there is a rich algebraic structure of dual operations of implication and co implication cid 150 resembling a non distributive version of Heyting and co Heyting algebras Subsets linearize to subspaces of a vector space and the usual quantum logic is the logic of the closed subspaces of the Hilbert spaces used in quantum mechanics QM Set partitions linearize to DSDs of a vector space so the logic of partitions linearizes to the logic of DSDs that can then be specialized to the Hilbert spaces of QM Since each diagonalizable linear operator e g the observables of QM on a vector operator determines a DSD of eigenspaces so the quantum logic of DSDs is the logic of observables abstracted from the actual eigenvalues Contents 1 The logical operations on set partitions 1 1 Introduction to partitions 1 1 1 The two mathematical logics of subsets and partitions 1 1 2 The duality of elements and distinctions 1 1 3 Partitions and equivalence relations 1 2 The join and meet operations on partitions 1 2 1 The set of blocks de cid 133 nitions of join and meet 1 2 2 The ditset de cid 133 nitions of join and meet 1 2 3 The graph theoretic de cid 133 nitions of join and meet 1 2 4 The complete Boolean subalgebra de cid 133 nitions of join and meet 1 2 5 The adjunctive characterizations of join and meet 1 3 1 Analogies with Heyting and bi Heyting algebras 1 3 2 The set of blocks de cid 133 nition of implication on partitions 1 3 3 The ditset de cid 133 nition of the partition implication 1 3 4 The graph theoretic de cid 133 nition of the partition implication 1 3 5 The adjunctive approach to the partition implication 1 4 Negation and other operations on partitions 1 4 1 Negation in partition logic 1 4 2 Relative negation in partition logic 1 4 3 The She er stroke not and or nand operation on partitions 1 3 The implication operation on partitions 2 2 2 4 4 6 6 7 8 10 10 11 11 12 13 14 15 17 17 18 20 1 1 4 4 The sixteen binary logical operations on partitions 1 4 5 The sixteen binary logical operations on equivalence relations 2 Partition tautologies 2 1 Subset truth table and partition tautologies 2 2 The cid 133 nite model property 2 3 Generating partition tautologies using the Boolean core B cid 25 1U 2 4 Some partition tautologies 2 5 Partition logic via the RST closure space U cid 2 U 2 5 1 The RST closure space U cid 2 U 2 5 2 The sixteen binary logical operations 2 5 3 The cid 25 orthogonal algebra A cid 25 cid 25 1U 3 The dual structure on the algebra of partitions 3 1 Co negation on partitions 3 2 Some tautologies for co negation 3 3 Di erence operation on partitions Relativizing co negation to cid 25 4 The quantum logic of vector space partitions 4 1 Linearization from sets to vector spaces 4 2 Direct Sum Decompositions 4 3 Compatibility of DSDs 4 4 Examples of compatibility incompatibility and conjugacy 4 5 The meet of DSDs and properties of re cid 133 nement 4 6 The partition lattice determined by a maximal DSD 4 7 Exploiting duality in between the logics of subspaces and DSDs 4 8 DSDs CSCOs and CSCDs 4 9 Some concluding thoughts 5 Appendix Counting direct sum decompositions of cid 133 nite vector spaces 5 1 Reviewing q analogs Again from sets to vector spaces 5 2 The direct formulas for counting partitions of cid 133 nite sets 5 3 The direct formulas for counting DSDs of cid 133 nite vector spaces 5 4 Counting DSDs with a block containing a designated vector v cid 3 5 5 Computing initial values for q 2 26 28 31 31 33 34 37 39 39 42 46 49 49 51 55 59 59 61 61 63 66 68 71 74 75 76 76 77 78 80 82 1 The logical operations on set partitions 1 1 Introduction to partitions 1 1 1 The two mathematical logics of subsets and partitions There are fundamentally two mathematical logics One the Boolean logic of subsets 7 usually presented today in the special case of propositional logic which has many sublogics and extensions the most important being the intuitionistic logic usually modeled by the open subsets of a topological space The other co fundamental mathematical logic is the topic of this book the logic of partitions We are using logic in a mathematical sense as being about basic mathematical objects subsets of a universe set or partitions on a universe set 1 Logic in this mathematical sense is not about propositions although as with any mathematical theory it involves propositions about the basic 1 We are not using the word logic for any syntactic axiom system using logical connectives but as a theory about certain fundamental mathematical notions Indeed today a Hilbert style axiom system for partition logic has yet to be developed 2 objects e g that an element is in a subset or that a distinction is made by a partition Moreover by taking the universe set to be the one element set 1 with two subsets and 1 there is a special case of subset logic namely propositional logic that can be interpreted as being about propositions with representing falsehood and 1 representing truth of subsets In the nineteenth century what is now called propositional logic was developed as the logic The algebra of logic has its beginning in 1847 in the publications of Boole and De Morgan This concerned itself at cid 133 rst with an algebra or calculus of classes to which a similar algebra of relations was later added Though it was foreshadowed in Boole cid 146 s treatment of Secondary Propositions a true propositional calculus perhaps cid 133 rst appeared from this point of view in the work of Hugh MacColl beginning in 1877 10 pp 155 56 Today the original subset version of propositional logic seems to be most often noted in the context of the category theoretic treatment The propositional calculus