Partition Lattice

June 13, 2024 11 minute read

0. ReferencesPermalink

https://staff.fnwi.uva.nl/d.j.n.vaneijck2/software/demo_s5/EREL.pdf

https://www.ellerman.org/book-draft-the-logic-of-partitions/

1. CoverPermalink

Definition: Given a set $A$ , a cover of $A$ , denoted by $κ = {A_{1}, A_{2}, \dots, A_{n}}$ , is a family of subsets of $A$ (i.e. $\forall A_{i} \subseteq A$ ), which satisfies:

$\emptyset \notin κ$
- I.e. $\forall A_{i} \neq \emptyset$
$⋃ κ = A$

Cover $\Rightarrow$ Similarity RelationPermalink

If $κ$ is a cover of $A$ , then the relation $R \subseteq A \times A$ given by

R = {(x, y) \in A \times A ∣ \exists A_{i} \in κ such that x \in A_{i} and y \in A_{i}}

is a similarity relation.

Cover $\Leftarrow$ Similarity RelationPermalink

If $R$ is a similarity relation on $A$ , given an element $a \in A$ , the similarity class of $a$ is defined as $[a]_{R} = {a^{'} \in A ∣ a^{'} R a}$ .

Then the family of subsets of $A$ , denoted by $κ$ , given by

κ = {[a]_{R} ∣ a \in A}

is a cover of $A$ .

Fusion vs Fission (in Haskell)Permalink

fusion 和 fission 首先是核物理的术语：

fusion: 核聚变
fission: 核裂变

Haskell 中用来形容对 cover 的变形，非常形象地说明了变形的方向：

the fusion of a cover $⟹$ the finest coarsening of the cover that turns it into a partition
- 等价于 cover 的 transitive closure. See Closure (Math) ▪️ Closures of Relations
the fission of a cover $⟹$ the coarsest refinement of the cover that turns it into a partition

2. PartitionPermalink

Definition: Given a set $A$ , a partition of $A$ , denoted by $π = {A_{1}, A_{2}, \dots, A_{n}}$ , is a family of subsets of $A$ (i.e. $\forall A_{i} \subseteq A$ ), which satisfies:

$π$ is a cover of $A$
$\forall A_{i}, A_{j} \in π$ , $A_{i} \neq A_{j} ⟹ A_{i} \cap A_{j} = \emptyset$
- We call elements of $π$ pairwise disjoint or mutually exclusive
- Furthermore, $⋂ π = \emptyset$

Definition: The elements of $π$ are called the blocks, parts, or cells, of the partition.

Partition $\Rightarrow$ Equivalence RelationPermalink

If $π = {A_{1}, A_{2}, \dots, A_{n}}$ is a partition on set $A$ , the relation $R$ induced by the partition $π$ , given by

\forall x, y \in A, x R y ⟺ \exists A_{i} \in π such that x \in A_{i} and y \in A_{i}

is an equivalence relation.

Partition $\Leftarrow$ Equivalence RelationPermalink

Similarly, if $R$ is an equivalence relation on $A$ , given an element $a \in A$ , the equivalence class of $a$ is defined as $[a]_{R} = {a^{'} \in A ∣ a^{'} R a}$ .

E.g. If $x =_{2} y ⟺ x = y (\mod 2)$ (where $x, y \in N$ ), then equivalence relation $=_{2}$ split $N$ into 2 equivalence classes, odd numbers and even numbers.

If $R$ is an equivalence relation on any non-empty set $A$ , then the distinct set of equivalence classes of $R$ , given by

π = {[a]_{R} ∣ a \in A}

forms a partition on $A$ .

Element $a \in A$ 的 equivalence class 一定是 partition $π$ 的某个 block，i.e. $\exists A_{k} \in π$ such that $[a]_{R} = A_{k}$

Partition $⟺$ Equivalence Relation，这也就是说 set $A$ 上的 equivalence relation $R$ 和对应的 partition $π$ 是等价的，所以也有教材写成 $π = A / R$ .

A set equipped with an equivalence relation or a partition is sometimes called a setoid, typically in type theory and proof theory.

IndexPermalink

Definition: We define the index of equivalence relation $R$ , denoted by $# (R)$ , as the number of equivalence classes of $R$ .

Definition: We define the index of partition $π$ , as the number of blocks in $π$ , i.e. $| π |$

3. Closure PropertiesPermalink

Closure under Union: ✅ Similarities (Covers) ❌ Equivalences (Partitions)Permalink

以下我们把 similarity relation 简称为 similarity，把 equivalence relation 简称为 equivalence。

在 cover 和 partition 上定义 “集合的 union 操作 $\cup$ “ 并不很直观，所以我们转去 relation 上定义 union 操作，毕竟 relation 本质就是 $(x, y)$ pairs 的集合。

假设有 relation $R_{1}, R_{2}$ ，那么 $R_{1} \cup R_{2} = {(x, y) ∣ (x, y) \in R_{1} or (x, y) \in R_{2}}$

Proposition 1:

If $R_{1}, R_{2}$ are similarities on $A$ , then $R_{1} \cup R_{2}$ is also a similarity on $A$
- I.e. similarities are closed under union
If $R_{1}, R_{2}$ are equivalences on $A$ , then $R_{1} \cup R_{2}$ is also a similarity on $A$
If $R_{1}, R_{2}$ are equivalences on $A$ , then $R_{1} \cup R_{2}$ is not necessarily an equivalence on $A$
- I.e. equivalences are NOT closed under union

Proof: (1) Since $R_{1}$ and $R_{2}$ are both reflexive, then $R_{1} \cup R_{2}$ must also be reflexive. Formally, construct $I = {(x, x) ∣ x \in A}$ , then $I \subseteq R_{1}$ and $I \subseteq R_{2}$ , thus $I \subseteq R_{1} \cup R_{2}$ .

Since $R_{1}$ and $R_{2}$ are both symmetric, then $R_{1} \cup R_{2}$ must also be symmetric. Formally, consider $(x, y) \in R_{1} \cup R_{2}$ .

If $(x, y) \in R_{1}$ , then $(y, x) \in R_{1}$ by symmetry;
If $(x, y) \in R_{2}$ , then $(y, x) \in R_{2}$ by symmetry.

Either case we have $(y, x) \in R_{1} \cup R_{2}$ .

Therefore $R_{1} \cup R_{2}$ is reflexive and symmetric, qualified as a similarity.

(2) Obviously, following (1)

(3) Counter example:

\begin{aligned} R_{1} & = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} \\ R_{2} & = {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)} \\ R_{1} \cup R_{2} & = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3)} \end{aligned}

Since $(3, 2)$ and $(2, 1)$ are $\in R_{1} \cup R_{2}$ , but $(3, 1) \notin R_{1} \cup R_{2}$ , then $R_{1} \cup R_{2}$ is not transitive, thus not an equivalence. $◼$

这意味着我们可以通过 ”similarities 的 union“ 去定义 ”cover 的 union“，只是这两个 union 不是同样的定义。我们用 $\cup$ 表示 “集合的 union”，用 $⋎$ 表示 “cover 的 union”。于是有：

κ_{1} ⋎ κ_{2} = {[a]_{R_{1} \cup R_{2}} ∣ a \in A}

但对 partitions 而言， $π_{1} ⋎ π_{2}$ 不一定是 partition，但一定是 cover

Closure under Intersection: ✅ Similarities (Covers) ✅ Equivalences (Partitions)Permalink

假设有 relation $R_{1}, R_{2}$ ，那么 $R_{1} \cap R_{2} = {(x, y) ∣ (x, y) \in R_{1} and (x, y) \in R_{2}}$

Proposition 2:

Similarities are closed under intersection
Equivalences are closed under intersection

Proof: (1) Similar to (2)

(2) Suppose $R_{1}, R_{2}$ are equivalences.

Since $R_{1}$ and $R_{2}$ are both reflexive, then $R_{1} \cap R_{2}$ must also be reflexive. (Follow the idea in the proof of Proposition 1)

Since $R_{1}$ and $R_{2}$ are both symmetric, then $R_{1} \cap R_{2}$ must also be symmetric. (Follow the idea in the proof of Proposition 1)

Since $R_{1}$ and $R_{2}$ are both transitive, then $R_{1} \cap R_{2}$ must also be transitive. Consider $(x, y) \in R_{1} \cap R_{2}$ , and $(y, z) \in R_{1} \cap R_{2}$ , then:

$(x, y) \in R_{1}$
$(y, z) \in R_{1}$
$(x, y) \in R_{2}$
$(y, z) \in R_{2}$

Since $R_{1}$ is transitive, $(x, z) \in R_{1}$ stands (bullet $1$ and $2$ ); since $R_{2}$ is transitive, $(x, z) \in R_{2}$ stands (bullet $3$ and $4$ ). Therefore $(x, z) \in R_{1} \cap R_{2}$ , thus $R_{1} \cap R_{2}$ is transitive.

Therefore $R_{1} \cap R_{2}$ is reflexive, symmetric, and transitive, qualified as an equivalence. $◼$

这意味着我们可以通过 ”similarities/equivalences 的 intersection“ 去定义 ”cover/partition 的 intersection“，只是这两个 intersection 不是同样的定义。我们用 $\cap$ 表示 “集合的 intersection”，用 $⋏$ 表示 “cover/partition 的 intersection”。于是有：

\begin{aligned} κ_{1} ⋏ κ_{2} & = {[a]_{R_{1} \cap R_{2}} ∣ a \in A} \\ π_{1} ⋏ π_{2} & = {[a]_{R_{1} \cap R_{2}} ∣ a \in A} \end{aligned}

但我们其实还有另一种定义 $π_{1} ⋏ π_{2}$ 的方法，非常巧妙 (或者巧合？)：

π_{1} ⋏ π_{2} = {X_{i} \cap Y_{j} ∣ X_{i} \in π_{1}, Y_{j} \in π_{2}, X_{i} \cap Y_{j} \neq \emptyset}

我们可以看个例子：

$A = {1, 2, 3, 4}$
$π_{1} = {{1}, {2, 3}, {4}}$
$π_{2} = {{1, 2}, {3}, {4}}$
$R_{1} = {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)}$
$R_{2} = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}$
$π_{1} ⋏ π_{2} = {{1}, {2}, {3}, {4}}$
$R_{1} \cap R_{2} = {(1, 1), (2, 2), (3, 3), (4, 4)}$

4. Partition LatticePermalink

构建 Lattice 的思路Permalink

假设 $Π_{n} = {π_{1}, π_{2}, \dots, π_{B_{n}}}$ 为集合 $[n] = {1, 2, \dots, n}$ 上所有的 partition。

$| Π_{n} | = B_{k}$ 这个值被称为 Bell Number，它还蛮复杂的，有需要时再研究。

我们已知的情报有：

可以取 $⊥ = {{1}, {2}, \dots, {n}}$
- i.e. the finest partition
可以取 $⊤ = {[n]} = {{1, 2, \dots, n}}$
- i.e. the coarsest partition
可以定义 partition 的 meet $π_{1} \land π_{2} = π_{1} ⋏ π_{2}$
- see Closure under Intersection

所以即使暂时没有 join 的定义，根据 Order-Theoretic Definition of Lattices (Poset == Lattice) > 更精炼的定义的 Proposition 1，我们也可以确认 $Π_{n}$ 是一个 lattice。

注意我们这里的思路：

开局一个 partition 的集合 $Π = {π_{1}, π_{2}, \dots, π_{n}}$ ，注意它是 finite 的
若我们能定义一个 meet operation $\land : Π \times Π \to Π$ ，那么就能定义出一个 relation $\leq$ such that $π_{1} \leq π_{2} ⟺ π_{1} \land π_{2} = π_{1}$
若 relation $\leq$ 是 partial order，那么 $(Π, \leq)$ 就是个 poset
根据 Order-Theoretic Definition of Lattices (Poset == Lattice) > 更精炼的定义的 Definition 1，既然 $(Π, \leq)$ 是个 finite poset，那么它 $(Π, \land, ⊤)$ 就是个 meet-semilattice
再根据 Order-Theoretic Definition of Lattices (Poset == Lattice) > 更精炼的定义的 Proposition 1, $(Π, \land, ⊤, ⊥)$ 也可以升级为 lattice

开拓思路：因为 partition 本质是个 equivalence，所以 partition lattice 本质也是个 equivalence lattice?

meet 的两种定义Permalink

给定 partition lattice $Π$ ，我们定义 $\land := ⋏$ ，而 $⋏ : Π \times Π \to Π$ 的定义有两种：

\begin{aligned} (1) & π_{1} ⋏ π_{2} & = {[a]_{R_{1} \cap R_{2}} ∣ a \in A} \\ (2) & π_{1} ⋏ π_{2} & = {X_{i} \cap Y_{j} ∣ X_{i} \in π_{1}, Y_{j} \in π_{2}, X_{i} \cap Y_{j} \neq \emptyset} \end{aligned}

“finer-than” relation $\leq$ 的两种释义Permalink

给定 partition lattice $Π$ ，我们可以定义一个 “finer-than” 的 partial order $\leq$ ：

π_{1} \leq π_{2} ⟺ π_{1} \land π_{2} = π_{1}

若 $π_{1} \leq π_{2}$ , 我们称:

$π_{1}$ is finer than $π_{2}$
$π_{2}$ is coarser than $π_{1}$

同时根据 meet 的第二个定义，当 $π_{1} \leq π_{2}, i.e. π_{1} \land π_{2} = π_{1}$ 时，有：

\forall X_{i} \in π_{1}, \forall Y_{j} \in π_{2}, X_{i} \cap Y_{j} \neq \emptyset ⟹ X_{i} \cap Y_{j} = X_{i}

所以 $\leq$ 也可以定义为：

π_{1} \leq π_{2} ⟺ \forall X_{i} \in π_{1}, \exists Y_{j} \in π_{2} such that X_{i} \subseteq Y_{j}

又因为 partition 的 pairwise disjoint 的特性，我们可以确定 $\forall Y_{j} \in π_{2}$ is a union of one or more $X_{i} \in π_{1}$ ，这也意味着，index 方面有 $| π_{1} | \geq | π_{2} |$ .

我们再回头看 meet 的第一个定义，当 $π_{1} \leq π_{2}, i.e. π_{1} \land π_{2} = π_{1}$ 时，我们可以推出：

\forall a \in A, [a]_{R_{1} \cap R_{2}} = [a]_{R_{1}}

它也意味着：

R_{1} \cap R_{2} = R_{1} ⟹ R_{1} \subseteq R_{2}

所以在 relation cardinality 方面有 $| R_{1} | \leq | R_{2} |$

$\leq$ 是 partial order，证明可以参考后面 join 的定义

词义 overloading 警告！Given a partition $π$ , we can adjust it in opposite directions:

“to make $π$ coarser (than itself/before)”
- 这个动作我们称为 “to coarsen $π$ ”
- 这个 procedure 我们称为 “the coarsening of $π$ ”
- 最后得到一个新 partition $ψ$ 满足 $π \leq ψ$ ，这个结果 $ψ$ 我们也称 “a coarsening of $π$ ”
“to make $π$ finer (than itself/before)”
- 这个动作我们称为 “to refine $π$ ”
- 这个 procedure 我们称为 “the refining/refinement of $π$ ”
- 最后得到一个新 partition $ψ$ 满足 $ψ \leq π$ ，这个结果 $ψ$ 我们称 “a refinement of $π$ ”

总结下规律：

Refining:
- 使得 $π$ 往 $⊥ = {{1}, {2}, \dots, {n}}$ 靠拢
- 使得 $| π | ↑$ ，意味着 equivalence class 更细碎
- 使得 $| R | ↓$ ，意味着 equivalence 的要求更严苛 (只有特定的几个元素才有 equivalence 关系)
Coarsening:
- 使得 $π$ 往 $⊤ = {{1, 2, \dots, n}}$ 靠拢
- 使得 $| π | ↓$ ，意味着 equivalence class 更融合
- 使得 $| R | ↑$ ，意味着 equivalence 的要求更水 (大多数元素都可以有 equivalence 关系)

Closure of $R$ 一定是对 $π$ 的 coarsening。假定 $R$ 的某个 closure 是 $R^{+}$ ，且 $R^{+}$ 对应的 partition 是 $π^{+}$ 。因为 $R \subseteq R^{+}$ ，所以 $| R | \leq | R^{+} |$ ，对应 $π \leq π^{+}$ ，所以说是对 $π$ 的 coarsening

join 的定义Permalink

我们已知 $π_{1} ⋎ π_{2}$ 不一定是 partition (但一定是 cover)，所以一定是不能定义 $\lor := ⋎$ 的，它连 $\lor : Π \times Π \to Π$ 这个最基础的要求都达不到。

但如果我们能取 $π_{1} ⋎ π_{2}$ 背后的 relation $R_{1} \cup R_{2}$ 的 transitive closure，i.e. 把 $R_{1} \cup R_{2}$ 升级为一个 equivalence，i.e. 把 $π_{1} ⋎ π_{2}$ 升级为一个 partition，那么这第一步的 $\lor : Π \times Π \to Π$ 就成功了。后续只要能证明 $\lor$ 引出的 $\leq$ 是 partial order，那么一切都会好起来的。

我们先定义几个符号：

Given a partition $π = {A_{1}, \dots, A_{n}}$ on $A$ , define $R (π) = {(x, y) \in A \times A ∣ \exists A_{i} \in π such that x \in A_{i} and y \in A_{i}}$
- I.e. $R (π)$ is the backbone relation $R$ of partition $π$
Transitive closure operator $k_{t} : (A \times A) \to (A \times A)$
- I.e. $k_{t}$ is a relation-to-relation function
- See Closures of Relations 的具体算法

我们定义：

\begin{aligned} R (π_{1} \lor π_{2}) & = k_{t} (R (π_{1}) \cup R (π_{2})) \\ π_{1} \lor π_{2} & = {[a]_{k_{t} (R (π_{1}) \cup R (π_{2}))} ∣ a \in A} \\ π_{1} \leq π_{2} & ⟺ π_{1} \lor π_{2} = π_{2} \end{aligned}

Claim: The $\leq$ relation, defined by $π_{1} \leq π_{2} ⟺ π_{1} \lor π_{2} = π_{2}$ , is a partial order.

Proof: (Reflexive) Since $R (π)$ is an equivalence, already transitive, therefore

\begin{aligned} R (π \lor π) & = k_{t} (R (π) \cup R (π)) \\ = k_{t} (R (π)) \\ = R (π) \end{aligned}

which implies $π \lor π = π$ and then $π \leq π$ .

(Antisymmetric)

\begin{aligned} π_{1} \leq π_{2} & ⟹ π_{1} \lor π_{2} = π_{2} \\ π_{2} \leq π_{1} & ⟹ π_{2} \lor π_{1} = π_{1} \end{aligned}

Since $\lor$ itself is symmetric, $π_{1} \lor π_{2} = π_{2} \lor π_{1}$ , therefore $π_{1} = π_{2}$ .

(Transitive)

\begin{aligned} (1) & π_{1} \leq π_{2} & ⟹ π_{1} \lor π_{2} = π_{2} \\ (2) & π_{2} \leq π_{3} & ⟹ π_{2} \lor π_{3} = π_{3} \end{aligned}

In $(2)$ , replace $π_{2}$ by $π_{1} \lor π_{2}$ , and we have:

\begin{matrix} (3) & π_{1} \lor π_{2} \lor π_{3} = π_{3} \end{matrix}

Since $\lor$ itself is associative, in $(3)$ , replace $π_{2} \lor π_{3}$ by $π_{3}$ , and we have:

\begin{matrix} (4) & π_{1} \lor π_{3} = π_{3} \end{matrix}

Therefore $π_{1} \leq π_{3}$ . $◼$

Share on

Twitter Facebook LinkedIn

Cover ( == Similarity) / Partition ( == Equivalence) / Partition Lattice

0. ReferencesPermalink

1. CoverPermalink

Cover $\Rightarrow$ Similarity RelationPermalink

Cover $\Leftarrow$ Similarity RelationPermalink

Fusion vs Fission (in Haskell)Permalink

2. PartitionPermalink

Partition $\Rightarrow$ Equivalence RelationPermalink

Partition $\Leftarrow$ Equivalence RelationPermalink

IndexPermalink

3. Closure PropertiesPermalink

Closure under Union: ✅ Similarities (Covers) ❌ Equivalences (Partitions)Permalink

Closure under Intersection: ✅ Similarities (Covers) ✅ Equivalences (Partitions)Permalink

4. Partition LatticePermalink

构建 Lattice 的思路Permalink

meet 的两种定义Permalink

“finer-than” relation $\leq$ 的两种释义Permalink

Coarsening & RefinementPermalink

join 的定义Permalink

Share on

Comments

You May Also Enjoy

Python Structural Pattern Matching (`match`/`case` since Python 3.10)

Config Mermaid.js in Minimal Mistakes theme

Config Giscus in Minimal Mistakes theme

Ken Thompson’s `post2nfa` Algorithm

0. ReferencesPermalink

1. CoverPermalink

Cover ⇒ Similarity RelationPermalink

Cover ⇐ Similarity RelationPermalink

Fusion vs Fission (in Haskell)Permalink

2. PartitionPermalink

Partition ⇒ Equivalence RelationPermalink

Partition ⇐ Equivalence RelationPermalink

IndexPermalink

3. Closure PropertiesPermalink

Closure under Union: ✅ Similarities (Covers) ❌ Equivalences (Partitions)Permalink

Closure under Intersection: ✅ Similarities (Covers) ✅ Equivalences (Partitions)Permalink

4. Partition LatticePermalink

构建 Lattice 的思路Permalink

meet 的两种定义Permalink

“finer-than” relation ≤ 的两种释义Permalink

Coarsening & RefinementPermalink

join 的定义Permalink

Share on

Comments

You May Also Enjoy

Python Structural Pattern Matching (match/case since Python 3.10)

Config Mermaid.js in Minimal Mistakes theme

Config Giscus in Minimal Mistakes theme

Ken Thompson’s post2nfa Algorithm

Cover $\Rightarrow$ Similarity RelationPermalink

Cover $\Leftarrow$ Similarity RelationPermalink

Partition $\Rightarrow$ Equivalence RelationPermalink

Partition $\Leftarrow$ Equivalence RelationPermalink

“finer-than” relation $\leq$ 的两种释义Permalink

Python Structural Pattern Matching (`match`/`case` since Python 3.10)

Ken Thompson’s `post2nfa` Algorithm