Difference join of input/output relations

Given a function $f: A \to B$ we have seen how we can establish a logical input/output relationship using the lattice of set partitions, which establishes that for certain ordered pair of partitions $I$ and $O$ a mapping can be defined between the equivalence classes of $I$ and the equivalence classes of $O$. We will now see that the natural way of combining these input/output relations is defined by the meet operation in the lattice of equivalence relations.

Lemma. let $A$ and $B$ be sets and let $P_1 \times Q_1$ and $P_2 \times Q_2$ be set partitions of $A \times B$. Then $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1 \wedge P_2 \times Q_1 \wedge Q_2$.

Proof. define projection mappings to $P_1$ and $P_2$ on the first index and $Q_1$ and $Q_2$ on the second index. Then we can define a mapping to the ordered pair $(P_1, P_2)$ and this has $P_1 \wedge P_2$ as a kernel and a mapping to the ordered pair $(Q_1, Q_2)$ with $Q_1 \wedge Q_2$ as a kernel. Then mapping to both ordered pairs $((P_1,P_2),(Q_1,Q_2))$ produces a kernel of $P_1 \wedge P_2 \times Q_1 \wedge Q_2$. By swapping the inner elements of this function we can get $((P_1,Q_1),(P_2,Q_2))$ which is the ordered pair expression of $P_1 \times Q_1 \wedge P_2 \times Q_2 = P_1$. Since these two projection mappings have one-to-one mappings between one another they have isomorphic set partitions.

Corollary. $P^2 \wedge Q^2 = (P \wedge Q)^2$.

Proof. this can be immediately achieved by a simple change of variables.

Proving the main theorem:
Theorem. let $f: A \to B$ be a function and let $I_1 \to O_1$ and $I_2 \to O_2$, then $I_1 \wedge I_2 \to O_1 \wedge O_2$.

Proof. let $a =_{I_1 \wedge I_2} b$, then by the definition of intersection $a =_{I_1} b$ and $a =_{I_2} b$. Since $I_1 \to O_1$ by assumption, $f(a) =_{O_1} f(b)$ and likewise by $I_2 \to O_2$ we can infer $f(a) =_{O_2} f(b)$. Finally, by the definition of intersection of equivalence relations $f(a) =_{O_1 \wedge O_2} f(b)$.

Remarks. it makes perfect sense that given a collection of inputs you can get a collection of all their outputs. The interesting thing is that we can formally model this using the meet operation of the lattice of equivalence relations, which is the mathematical means of handling collections of information.

Constructing the congruence lattice:
Corollary. let $f : A^2 \to B$ and let $P,Q$ be congruence relations. Then their equality meet $P \wedge Q$ is a congruence.

Proof. congruence relations define mappings between equivalence classes from $P^2 \to P$ and from $Q^2 \to Q$. By the difference join of equivalence relations we can now get a mapping between equivalence classes $P^2 \wedge Q^2 \to P \wedge Q$. By the meet of cartesian products of partitions this is equal to $(P \wedge Q)^2 \to (P \wedge Q)$ which means that $P \wedge Q$ is a congruence.

Corollary. the set of congruences of an algebraic structure $A$ forms a lattice

Definition. the lattice of congruences of an algebraic structure $A$ will be denoted $Con(A)$.

Remarks. the lattice of congruences $Con(A)$ has more structure then the lattice of subalgebras $Sub(A)$ because it is a set of set systems rather then simply a set system. Therefore, it makes sense to consider $Sub(A)$ before moving on to $Con(A)$ which is potentially more complicated. Even then, $Con(A)$ has an intuitive basis in the idea of combining inputs and outputs as we have seen here.

Properties of lattices of congruences:
By the theorems that we have proven here we can immediately infer that the lattice of congruences $Con(A)$ is a lattice-ordered bounds-maintining meet subsemilattice of the lattice of equivalence relations on the ground set of an algebraic structure. As equivalence relations are intersection closed, this means that $Con(A)$ forms a Moore family as a set system just like $Sub(A)$.