Bottom Relation is Bottom in Ordered Set of Auxiliary Relations

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $L = \left({S, \vee, \preceq}\right)$ be a bounded below join semilattice.

Let ${\it Aux}\left({L}\right)$ be the set of all auxiliary relations on $S$.

Let $P = \left({ {\it Aux}\left({L}\right), \precsim}\right)$ be an ordered set where $\precsim \mathop = \subseteq\restriction_{{\it Aux}\left({L}\right) \times {\it Aux}\left({L}\right)}$

Let $B = \left\{ {\left({\bot_L, x}\right): x \in S}\right\}$

where $\bot_L$ denotes smallest element in $L$.


Then

$B \mathop = \bot_P$


Proof

By Bottom Relation is Auxiliary Relation:

$B \mathop \in {\it Aux}\left({L}\right)$

By definition

$B$ is upper bound for $\varnothing$ in $P$

We will prove that

$\forall R \in {\it Aux}\left({L}\right): R$ is upper bound for $\varnothing \implies B \mathop \precsim R$

Let $R \in {\it Aux}\left({L}\right)$

By condition $(iv)$ of definition of auxiliary relation:

$B \mathop \subseteq R$

Thus by definition of $\precsim$:

$B \mathop \precsim R$

$\Box$

By definition of supremum:

$B \mathop = \sup_P \varnothing$

Thus by Supremum of Empty Set is Smallest Element:

$B \mathop = \bot_P$

$\blacksquare$


Sources