Factor relations

In this post we will consider the different ways of comparing subsets of a partially ordered set. Let $(A,\subseteq)$ be a partially ordered set and $S,T$ be two different types of subsets of $A$. There are five types of relationship $\sqsubseteq$ between subsets $S,T$ of partial orders as described below:

• Ordinary precedence: $ \exists x \in S, y \in T : x \subseteq y$
• Strong ordinary precedence : $\forall x \in S : \exists y \in T : x \subseteq y$
• Upper ordinal precedence : $ \exists y \in T : \forall x \in S: x \subseteq y$
• Lower ordinal precedence : $ \exists x \in S : \forall y \in T : x \subseteq y$
• Strong ordinal precedence : $\forall x \in S, y \in T : x \subseteq y$

These five concepts clearly form a hierarchy with ordinary precedence being the most general case, and strong ordinal precedence being the most restricted. With such a variety of cases, it is not obvious at first what type of set comparison we want to work with.

The idea of a relation homomorphism lends a hint as to sort of relationship between sets we want to consider. Suppose that $(A,\subseteq)$ is a set $A$ with binary relation $\subseteq$ and that $P$ is a partition of the ground set $A$. Then there is a natural projection map $f : A \to P$. We want to form a relation on $P$ such that $f$ is a homomorphism using one of the five comparisons of sets. Then in general we need to use ordinary precedence.

To see this, notice that whenever have $S,T$ and we have $x \in S$ and $y \in T$ such that $x \subseteq y$ then in order for $f$ to be a relation homomorphism we must have $f(x) \subseteq f(y)$ in other words $S \sqsubseteq Y$. Therefore, in order for a projection map to always be a relation homomorphism we need to use ordinary precedence in general because the other types of relation may miss things. The other other types of projection are not always homomorphisms.

Proposition. Let $(A, \subseteq)$ be a partially ordered set and $P$ a partition of $A$. In order for the factor relation by ordinary precedence to be antisymmetric, then every set of $P$ must be convex.

Proof. Let $S$ be a non-convex subset of $A$ then there exists an element $x$ such that $s_1 \subseteq x \subseteq s_2$ for elements $s_1,s_2 \in S$. Let $T$ be the set containing $x$ in $P$. Then by $s_1 \subseteq x$ we have $S \subseteq T$ and by $x \subseteq s_2$ we have $T \subseteq S$. Therefore, $S,T$ are symmetrically related which is a contradiction. $\square$

This is a generalization of the fact that the equivalence classes of a lattice congruence are all convex. Lattice congruences produce quotient semilattices and ordinary predecendence produces factor relations. It would be interesting to see if the relational quotient agrees with the algebraic one.

Proposition. let $(L,\subseteq)$ be a lattice with congruence $C$. Then ordinary precedence on the congruence classes of $C$ and the lattice quotient $\frac{L}{C}$ coincide.

Proof. Let $f : L \to C$ be the map which takes any lattice element to its congruence class. Let $C_1, C_2$ be congruence classes such that $C_1 \subseteq C_2$ in the quotient lattice. Select arbitrary elements $x \in C_1$ and $y \in C_2$ then take $x \vee y$ then it is in $C_2$ and we have $x \in C_1$ and $x \vee y$ such that $x \subseteq x \vee y$ so that $C_1$ is an ordinary predecessor of $C_2$. Conversely, suppose that $C_1$ is an ordinary predecessor of $C_2$ then there exist $x \in C_1$ and $y \in C_2$ such that $x \subseteq y$. We clearly have that $x \vee y = y$ therefore, in the quotient lattice $C_1 \vee C_2 = C_2$ so $C_2$ is greater then $C_1$. $\square$

So the ordinary factor relation is sufficient to recover the order on a lattice congruence. Given a finite lattice, we also have upper ordinal precedence and lower ordinal precedence. We do not have strong ordinal precedence in all cases unless we are dealing with a total order, then of course strong ordinal precedence applies.

It is often use to quotient a lattice by a partition which doesn't necessarily form a congruence. For example, consider the simple example of the diamond partially ordered set $\{\emptyset,\{0\},\{1\},\{0,1\}\}$. Then we might want to form a partition by cardinality $\{ \{ \emptyset \}, \{ \{0\},\{1\} \}, \{ \{0,1\} \} \}$ these does not form a lattice congruence, but it does form a quotient partially ordered set which is the total order on cardinal numbers $\{0,1,2\}$.

Example 1. finite sets partitioned by cardinality produces the total order $\omega$

Example 2. finite multisets partitioned by signature produces the young's lattice $Y$

Example 3. subsets partitioned an automorphism group acting on sets produces the set orbit poset

Example 4. isomorphism types of algebraic structures can be ordered by subalgebras, quotients, or subquotients.

Example 5. finite abelian groups are determined up to isomorphism by a product of primary cyclic groups, then up to isomorphism a subalgebra is a reduction in the number of cyclic groups or in one of their exponents

Example 6. let $S$ be a finite set with cardinality $n$ then $Part(S)$ partitioned by set partition isomorphism type produces the refinement ordering of additive partitions of $n$