Multiplicative Auxiliary Relation iff Congruent

From ProofWiki
Jump to: navigation, 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:

$\forall a, b, x, y \in S: \left({a, x}\right), \left({b, y}\right) \in \mathcal R \implies \left({a \wedge b, x \wedge y}\right) \in \mathcal R$

That is iff $\mathcal R$ is a congruence relation for $\wedge$.


Proof

Sufficient Condition

Let $\mathcal R$ be multiplicative.

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

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

By Meet Precedes Operands:

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

By definition of reflexivity:

$x \preceq x$ and $y \preceq y$

By definition of auxiliary relation:

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

Thus by definition of multiplicative relation:

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

$\Box$

Necessary Condition

Suppose that

$\forall a, b, x, y \in S: \left({a, x}\right), \left({b, y}\right) \in \mathcal R \implies \left({a \wedge b, x \wedge y}\right) \in \mathcal R$

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

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

By Meet is Idempotent:

$a \wedge a = a$

Thus by assumption:

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

$\blacksquare$


Sources