Inclusion-exclusion principle for set partitions

Set theory is essentially an additive logic, while on the other hand partition theory is a multiplicative logic. Sets can be added together with respect to cardinality, and the difference from the sum can be determined by the intersection. This naturally leads one to wonder if a similar construct be introduced for set partitions to measure how far they are from being multiplicative. To deal with this, I introduced the idea of the sparsity of two set partitions.

Definition. Let $P$ and $Q$ be two set partitions, and let $P \times Q$ be their cartesian product. Then the sparsity of $P$ and $Q$ is the number of non-intersecting sets in $P \times Q$ defined by $|\{ (p,q) \in P \times Q : |p \cap q| = 0 \}|$

This naturally leads to a generalization of the inclusion-exclusion principle to set partitions. Instead of intersection measuring how far two sets are from being additive, the sparsity measures how far two set partitions are from being multiplicative.

Theorem. Let $P$ and $Q$ be two equivalence relations with a finite number of equivalence classes $|P|$ and $|Q|$ in each of them. Then the number of equivalence classes in their meet in the lattice of equivalence relations is the product of the number of equivalence classes in each of them minus the sparsity. In other words, \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] Proof. Let $P \times Q$ be the cartesian product of the sets of equivalence classes of $P$ and $Q$. Then we can partition $P \times Q$ into two classes $Z$ consisting of all pairs of equivalence classes with zero intersection and $N$ consisting of all pairs of equivalence classes without zero intersection. Since these two classes are non-intersecting, by the inclusion-exclusion principle for set partitions: \[ |P \times Q| = |N| + |Z| \] The cartesian product of two finite sets $A \times B$ can be partitioned into $|A|$ different equivalence classes all containing $|B|$ elements. By the inclusion-exclusion principle and the fact that each of these sets is disjoint, this can be expressed as a sum which by the definition of multiplication is equal to $|A| * |B|$. \[ |A \times B| = \sum_{n=1}^{|A|} |B| = |A|*|B| \] Using this formula, we can substitute $|P|*|Q|$ into the formula for the cardinality of $|P \times Q|$ where $P$ and $Q$ are the specifically sets of equivalence classes. This produces the new formula below. \[ |P|*|Q| = |N| + |Z| \] We are almost done with the proof now, except that we need to relate this decomposition of the product to the lattice operation $P \wedge Q$. In order to do that, we must construct $P \wedge Q$. If we express $P$ and $Q$ as equivalence relations, this is $P \cap Q$ and so $P \cap Q \subseteq P,Q$. If we take $P \cap Q$ and them break it down into equivalence classes, each equivalence classes $C$ of $P \cap Q$ is a subset of exactly one equivalence class in $P$ and $Q$ since $P$ and $Q$ are partitions, which produces a single member of $P \times Q$ consisting of two equivalence classes that contain $C$. These two equivalence classes that contain $C$ are members of $N$ which produce non-empty intersections and each equivalence class is distinct so they all define different members of $N$. Therefore, this defines a one to one mapping $f: P \wedge Q \to N$ which means that $|P \wedge Q|$ equals $|N|$ since one to one mappings preserve cardinality. Additionally, $|Z| = sparsity(p,q)$ by definition. \[ |N| = |P \wedge Q| \] \[ |Z| = sparsity(p,q) \] Finally, these two equivalent definitions can be substituted into the previous formula for $|P|*|Q|$ and $sparsity(p,q)$ can be subtracted from both sides to get the intended formula. \[ |P \wedge Q| = |P|*|Q| - sparsity(p,q) \] The two formulas compared:
We can now compare the two formulas used in additive logic and multiplicative logic side by side to get the analogy between the intersection of sets and the sparsity of partitions. \[ |A \cup B| = |A| + |B| - |A \cap B| \] \[ |A \wedge B| = |A| * |B| - sparsity(a,b) \] These are the fundamental formulas that relate logic and arithmetic. Partition logic can most accurately be defined as a higher form of set theory. While set lattices have $2^n$ members, the lattice of partitions has $2^{n-1}-1$ difference atoms. That is the atoms in partition logic are sort of like sets, in that they are bits of information. Bits of information then can be used to construct all pieces of information in the partition lattice. As this is the fundamental logic of information, its fair to say that partition logic is the natural logic of multiplication.

• Addition -> set theory
• Multiplication -> partition logic

Therefore, we can form certain partially ordered sets from which the addition and multiplication operations are abstracted from. Numbers are already a highly-abstract object, where as sets are much more concrete as specific examples of collections of objects emerge all the time. In the other direction, everyone is processing information and partition logic deals with concrete examples of that. For example, the bits of information in a computer can be represented as atoms in the partition lattice, and they can be combined to construct any piece of information.

Direct products:
As we have seen how partitions multiply together, we can now consider special cases of multiplicative partitions. One such special case is that of a direct product.

Definition. two set partitions $P$ and $Q$ are direct products of one another if they are multiplicative and the intersection of equivalence classes taken from $P$ and $Q$ all have cardinality one.

This can be used to describe a cartesian product used in set theory. In a cartesian product, the first and second equivalence relations are direct products of one another in the lattice of equivalence relations. On the same note, the direct product of two algebraic structures is defined by congruences that are direct products of one another.

References:
https://arxiv.org/abs/0902.1950