Closure Operator from Closed Elements

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \preceq}\right)$ be an ordered set.

Let $C \subseteq S$.

Suppose that $C$ is a subset of $S$ with the property that every element of $S$ has a smallest successor in $C$.

Let $\operatorname{cl}: S \to S$ be defined as follows:

For $x \in S$:

$\operatorname{cl} \left({x}\right) = \min \left({C \cap x^\succeq}\right)$

where $x^\succeq$ is the upper closure of $x$.

That is, let $\operatorname{cl} \left({x}\right)$ be the smallest successor of $x$ in $C$.


Then:

$\operatorname{cl}$ is a closure operator on $S$
The closed elements of $\operatorname{cl}$ are precisely the elements of $C$.


Proof

Inflationary

$x$ is a lower bound of $x^\succeq$.

Hence by Lower Bound for Subset, $x$ is also a lower bound of $C \cap x^\succeq$.

By the definition of smallest element, $x \preceq \operatorname{cl} \left({x}\right)$.

$\Box$


Order-Preserving

Suppose that $x \preceq y$.

Then:

$C \cap y^\succeq \subseteq C \cap x^\succeq$

By Smallest Element of Subset:

$\operatorname{cl} \left({x}\right) \preceq \operatorname{cl} \left({y}\right)$


Idempotent

Let $x \in S$.

For each $x \in S$:

$\operatorname{cl} \left({x}\right) = \min \left({ C \cap x^\succeq}\right)$

Thus:

$\operatorname{cl} \left({x}\right) \in \left({ C \cap x^\succeq}\right) \subseteq C$

That is to say, $\operatorname{cl} \left({x}\right)$ is its own smallest successor in $C$.

Thus:

$\operatorname{cl} \left({x}\right) = \operatorname{cl} \left({\operatorname{cl} \left({x}\right) }\right)$

$\Box$


When $x \in C$, $x$ is the minimum of $C \cap x^\succeq$

Hence, elements of $C$ are closed elements with respect to $\operatorname{cl}$.

Suppose that $x$ is closed with respect to $\operatorname{cl}$.

Then:

$x = \min \left({C \cap x^\succeq}\right)$

so in particular: $x \in C$

$\blacksquare$