Multiplicative Auxiliary Relation iff Images are Filtered

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R$ be an auxiliary relation on $S$.


Then $\mathcal R$ is multiplicative if and only if

for all $x \in S$: $\mathcal R\left({x}\right)$ is filtered

where $\mathcal R\left({x}\right)$ denotes the $\mathcal R$-image of $x$.


Proof

Sufficient Condition

Let $\mathcal R$ be multiplicative.

Let $x \in S$.

Let $a, b \in {\mathcal R}\left({x}\right)$.

By definition of $\mathcal R$-image of element:

$\left({x, a}\right), \left({x, b}\right) \in \mathcal R$

By definition of multiplicative relation:

$\left({x, a \wedge b}\right) \in \mathcal R$

By definition of $\mathcal R$-image of element:

$a \wedge b \in {\mathcal R}\left({x}\right)$

By Meet Precedes Operands:

$a \wedge b \preceq a$ and $a \wedge b \preceq b$

Thus

$\exists c \in {\mathcal R}\left({x}\right): c \preceq a \land c \preceq b$

Hence ${\mathcal R}\left({x}\right)$ is filtered.

$\Box$

Necessary Condition

Suppose that

for all $x \in S$: ${\mathcal R}\left({x}\right)$ is filtered

Let $a, x, y \in S$ such that

$\left({a, x}\right), \left({a, y}\right) \in \mathcal R$

By definition of $\mathcal R$-image of element:

$x, y \in {\mathcal R}\left({a}\right)$

By Auxiliary Relation Image of Element is Upper Set:

${\mathcal R}\left({a}\right)$ is upper set.

By assumption:

${\mathcal R}\left({a}\right)$ is filtered.

By Filtered in Meet Semilattice:

$x \wedge y \in {\mathcal R}\left({a}\right)$

Thus by definition of $\mathcal R$-image of element:

$\left({a, x \wedge y}\right) \in \mathcal R$

$\blacksquare$


Sources