Show that $\text{Part}(A)$ is a complete lattice

82 Views Asked by At

Let $A$ be a set and let $\text{Part}(A)$ denote the collection of all partitions of $A$. Define the relation $\leq $ on $\text{Part}(A)$ by $P_1\leq P_2$ if and only if for every $A_1 \in P_1$ there exists $A_2\in P_2$ such that $A_1\subset A_2$. One can check that $\leq$ is a partial order on $\text{Part}(A)$.

I am asked to show that $(\text{Part}(A),\leq)$ is a complete lattice.

My attempt:

It suffices to show that every subset $\mathcal T\subset \text{Part}(A)$ has an infimum.

Let $$\bigcap \mathcal T :=\bigg\{\bigcap_{t\in\mathcal T}f_t \mid f:\mathcal T\to\mathcal P(A), f_t\in t \text{ for all } t\in \mathcal T\bigg\} $$

In particular $\bigcap \mathcal T :=\{A\}$ if $\mathcal T=\emptyset$.

I claim that $\bigcap \mathcal T - \{\emptyset\} =\inf \mathcal T$.

The case $\mathcal T=\emptyset$ is easy so assume $\mathcal T\neq \emptyset$.

First we check that $\bigcap \mathcal T - \{\emptyset\}$ is a partition of $A$. Clearly the elements of $\bigcap \mathcal T - \{\emptyset\}$ are disjoints and nonempty. Let us show that the elements of $\bigcap \mathcal T - \{\emptyset\}$ cover $A$. Let $a\in A$. For each $t\in\mathcal T$ there exists a unique $f_t\in t $ (axiom of choice not needed) such that $a\in f_t$. Hence $a\in \bigcap_{t\in\mathcal T}f_t \in \bigcap \mathcal T - \{\emptyset\} $.

It is clear that $\bigcap \mathcal T - \{\emptyset\} $ is a lower bound for $\mathcal T$. Let us show that it is the greatest lower bound for $\mathcal T$. Let $P$ be a lower bound for $\mathcal T$ and let $A \in P$. Then, for each $t\in \mathcal T$ there exists a unique $f_t\in t$ (axiom of choice not needed) such that $A\subset f_t$. Hence $A\subset \bigcap_{t\in\mathcal T}f_t \in \bigcap \mathcal T - \{\emptyset\} $.

Is this correct? Am I missing something? Thanks a lot for your help.


Edit: Alternatively one can work with $\text{Equi}(A)$, the collection of all equivalence relations on $A$. Define the relation $\preceq $ on $\text{Equi}(A)$ by $E_1\preceq E_2$ if and only if $E_1\subset E_2$. Then $ \preceq $ is a partial order on $\text{Equi}(A)$ and one can check that $(\text{Equi}(A),\preceq)$ is order isomorphic to $(\text{Part}(A),\leq)$.

Now if $\mathcal E\subset \text{Equi}(A)$ then we can check that $\bigcap \mathcal E=\inf \mathcal E$ (define $\bigcap \mathcal E:=A\times A$ if $\mathcal E=\emptyset$). Hence $(\text{Equi}(A),\preceq)$ is a complete lattice, and so is $(\text{Part}(A),\leq)$.

In fact, given $\mathcal T \subset \text{Part}(A)$ one can check that

$$\bigcap \mathcal T -\{\emptyset\}=A \backslash \bigcap_{t\in \mathcal T} E_t $$ where $E_t$ is the equivalence relation on $A$ induced by partition $t$ and $\bigcap_{t\in \mathcal T} E_t:=A\times A$ if $\mathcal T=\emptyset$.