Conditions for Lexicographic Order on Pair of Ordered Sets to be Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.

Let $\preccurlyeq_l$ denote the lexicographic order on $S_1 \times S_2$:

$\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} \iff \tuple {x_1 \prec_1 y_1} \lor \tuple {x_1 = y_1 \land x_2 \preccurlyeq_2 y_2}$


Then:

$\struct {S_1 \times S_2, \preccurlyeq_l}$ is a lattice

if and only if all of the following conditions hold:

$(1): \quad \struct {S_1, \preccurlyeq_1}$ is a lattice
$(2): \quad$ Either $\preccurlyeq_1$ is a total ordering, or $\struct {S_2, \preccurlyeq_2}$ has a greatest element and a smallest element
$(3): \quad$ Every doubleton subset of $S_2$ is either unbounded above or admits a supremum, and is also either unbounded below or admits an infimum
$(4): \quad$ Either every doubleton subset of $S_2$ admits a supremum, or every element of $S_1$ has an immediate successor and $\struct {S_2, \preccurlyeq_2}$ has a smallest element
$(5): \quad$ Either every doubleton subset of $S_2$ admits an infimum, or every element of $S_1$ has an immediate predecessor and $\struct {S_2, \preccurlyeq_2}$ has a greatest element.


Corollary

Let $\struct {S_2, \preccurlyeq_2}$ have neither a greatest element nor a smallest element.

Then:

$\preccurlyeq_l$ is a lattice ordering

if and only if:

$\preccurlyeq_1$ is a total ordering

and:

$\preccurlyeq_2$ is a lattice ordering.


Proof

Let $\struct {T, \preccurlyeq_l} := \struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$.

From Lexicographic Order is Ordering we have that $\struct {T, \preccurlyeq_l}$ is an ordered set.


Recall the definition of lexicographic order:

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.

The lexicographic order $\struct {S_1, \preccurlyeq_1} \otimes^l \struct {S_2, \preccurlyeq_2}$ on $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ is the ordered set $\struct {T, \preccurlyeq_l}$ where:

$T := S_1 \times S_2$, that is, the Cartesian product of $S_1$ and $S_2$
$\preccurlyeq_l$ is the relation defined on $T$ as:
$\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} \iff \tuple {x_1 \prec_1 y_1} \lor \paren {x_1 = y_1 \land x_2 \preccurlyeq_2 y_2}$


Lemma $1$

Let $\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2}$.

Then:

$x_1 \preccurlyeq_1 y_1$

$\Box$


Lemma $2$

Let $x_1$ and $y_1$ be non-comparable elements in $S_1$:

$\lnot \paren {x_1 \preccurlyeq_1 y_1}$ and $\lnot \paren {y_1 \preccurlyeq_1 x_1}$

Then $\tuple {x_1, x_2}$ and $\tuple {y_1, y_2}$ are non-comparable elements in $S_1 \times S_2$:

$\lnot \paren {\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} }$ and $\lnot \paren {\tuple {y_1, y_2} \preccurlyeq_l \tuple {x_1, x_2} }$

$\Box$


Recall the definition of lattice:

Let $\struct {S, \preceq}$ be an ordered set.

Then $\struct {S, \preceq}$ is a lattice if and only if:

for all $x, y \in S$, the subset $\set {x, y}$ admits both a supremum and an infimum.


Sufficient Condition

Let $\struct {T, \preccurlyeq_l}$ be a lattice.


Condition $(1)$

Let $x_1, y_1 \in S_1$ and $x_2, y_2 \in S_2$ be arbitrary.

Then $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ admits a supremum and admits an infimum in $T$.


Let $\tuple {c_1, c_2} \in T$ be a supremum of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$.

Thus:

$(1): \quad \tuple {c_1, c_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ in $T$
$(2): \quad \tuple {c_1, c_2} \preccurlyeq_l \tuple {d_1, d_2}$ for all upper bounds $\tuple {d_1, d_2}$ of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ in $T$.


Let $\tuple {d_1, d_2}$ be an arbitrary upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ in $T$.

Then:

\(\ds \tuple {x_1, x_2}\) \(\preccurlyeq_l\) \(\ds \tuple {d_1, d_2}\) Definition of Upper Bound of Set
\(\ds \leadsto \ \ \) \(\ds x_1\) \(\preccurlyeq_1\) \(\ds d_1\) Lemma $1$

and:

\(\ds \tuple {y_1, y_2}\) \(\preccurlyeq_l\) \(\ds \tuple {d_1, d_2}\) Definition of Upper Bound of Set
\(\ds \leadsto \ \ \) \(\ds y_1\) \(\preccurlyeq_1\) \(\ds d_1\) Lemma $1$

Thus:

$d_1$ is an upper bound of $\set {x_1, y_1}$


As $\tuple {c_1, c_2}$ is also an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$, it similarly follows that:

$c_1$ is an upper bound of $\set {x_1, y_1}$

Then:

\(\ds \tuple {c_1, c_2}\) \(\preccurlyeq_l\) \(\ds \tuple {d_1, d_2}\) Definition of Upper Bound of Set
\(\ds \leadsto \ \ \) \(\ds c_1\) \(\preccurlyeq_1\) \(\ds c_1\) Lemma $1$

Thus:

$c_1$ is an upper bound of $\set {x_1, y_1}$

and:

if $d_1$ is an upper bound of $\set {x_1, y_1}$, then $c_1 \preccurlyeq_1 d_1$

so $\set {x_1, y_1}$ admits a supremum $c_1$ in $\struct {S_1, \preccurlyeq_1}$.


Now let $\tuple {c_1, c_2} = \inf \set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ be the infimum of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$.


We use a similar argument to the above, mutatis mutandis, to show that:

$\set {x_1, y_1}$ admits an infimum $c_1$ in $\struct {S_1, \preccurlyeq_1}$


As $x_1$, $x_2$, $y_1$ and $y_2$ are arbitrary, it follows that $\struct {S_1, \preccurlyeq_1}$ is a lattice.

$\Box$


Condition $(2)$

Suppose $\preccurlyeq_1$ is not a total ordering.

Then there exist non-comparable elements $x_1$ and $y_1$ in $S_1$:

$\lnot \paren {x_1 \preccurlyeq_1 y_1}$ and $\lnot \paren {y_1 \preccurlyeq_1 x_1}$

Hence, from Lemma $2$, $\tuple {x_1, x_2}$ and $\tuple {y_1, y_2}$ are non-comparable elements in $T$:

$\lnot \paren {\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} }$ and $\lnot \paren {\tuple {y_1, y_2} \preccurlyeq_l \tuple {x_1, x_2} }$



This theorem requires a proof.
In particular: Chipping away
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Necessary Condition

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ fulfil the conditions that:

$(1): \quad \struct {S_1, \preccurlyeq_1}$ is a lattice
$(2): \quad$ Either $\preccurlyeq_1$ is a total ordering, or $\struct {S_2, \preccurlyeq_2}$ has a greatest element and a smallest element
$(3): \quad$ Every doubleton subset of $S_2$ is either unbounded above or admits a supremum, and is also either unbounded below or admits an infimum
$(4): \quad$ Either every doubleton subset of $S_2$ admits a supremum, or every element of $S_1$ has an immediate successor and $\struct {S_2, \preccurlyeq_2}$ has a smallest element
$(5): \quad$ Either every doubleton subset of $S_2$ admits an infimum, or every element of $S_1$ has an immediate predecessor and $\struct {S_2, \preccurlyeq_2}$ has a greatest element.


This theorem requires a proof.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Conditions_for_Lexicographic_Order_on_Pair_of_Ordered_Sets_to_be_Lattice&oldid=567460"