Simple Order Product of Pair of Ordered Sets is Lattice iff Factors are Lattices
Theorem
Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.
Let $\struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$ denote the simple (order) product of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$.
Then $\struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$ is a lattice if and only if both $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ are lattices.
Proof
Let $\struct {T, \preccurlyeq_s} := \struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$.
First we note that from Simple Order Product of Pair of Ordered Sets is Ordered Set, $\struct {T, \preccurlyeq_s}$ is an ordered set.
Sufficient Condition
Let $\struct {T, \preccurlyeq_s}$ be a lattice.
Let $x_1$ and $y_1$ be arbitrary elements of $S_1$.
Let $x_2$ and $y_2$ be arbitrary elements of $S_2$.
Then we have that $\tuple {x_1, x_2}$ and $\tuple {y_1, y_2}$ are elements of $T$.
By definition of lattice, $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ admits both a supremum and an infimum.
Let $\tuple {c_1, c_2} = \sup \set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ be the supremum of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$.
Then by definition:
- $\tuple {c_1, c_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ in $T$
- $\tuple {c_1, c_2} \preccurlyeq_s \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_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Upper Bound of Set | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds x_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Simple Order Product | ||||||||||
\(\, \ds \land \, \) | \(\ds x_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) |
Similarly:
\(\ds \tuple {y_1, y_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Upper Bound of Set | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds y_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Simple Order Product | ||||||||||
\(\, \ds \land \, \) | \(\ds y_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) |
Thus:
- $d_1$ is an upper bound of $\set {x_1, y_1}$
and:
- $d_2$ is an upper bound of $\set {x_2, y_2}$.
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}$
and:
- $c_2$ is an upper bound of $\set {x_2, y_2}$.
Now we have:
\(\ds \tuple {c_1, c_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Supremum of Set | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds c_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Simple Order Product | ||||||||||
\(\, \ds \land \, \) | \(\ds c_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) |
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}$.
Also:
- $c_2$ is an upper bound of $\set {x_2, y_2}$
and:
- if $d_2$ is an upper bound of $\set {x_2, y_2}$, then $c_2 \preccurlyeq_1 d_2$
so $\set {x_2, y_2}$ admits a supremum $c_2$ in $\struct {S_2, \preccurlyeq_2}$.
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}$
and:
- $\set {x_2, y_2}$ admits an infimum $c_2$ in $\struct {S_2, \preccurlyeq_2}$.
As $x_1$, $x_2$, $y_1$ and $y_2$ are arbitrary, it follows that both $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ are lattices.
$\Box$
Necessary Condition
Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be lattices.
Let $\tuple {x_1, x_2}$ and $\tuple {y_1, y_2}$ be arbitrary elements of $T$.
Then:
- $x_1$ and $y_1$ are elements of $S_1$
- $x_2$ and $y_2$ are elements of $S_2$.
By definition of lattice, both $\set {x_1, y_1}$ and $\set {x_2, y_2}$ admit both a supremum and an infimum.
Let $c_1 = \sup \set {x_1, y_1}$ and $c_2 = \sup \set {x_2, y_2}$ be the suprema of $\set {x_1, y_1}$ and $\set {x_2, y_2}$ respectively.
Then by definition:
- $c_1$ is an upper bound of $\set {x_1, y_1}$ in $S_1$
- $c_1 \preccurlyeq_1 d_1$ for all upper bounds $d_1$ of $\set {x_1, y_1}$ in $S_1$
and:
- $c_2$ is an upper bound of $\set {x_2, y_2}$ in $S_2$
- $c_2 \preccurlyeq_2 d_2$ for all upper bounds $d_2$ of $\set {x_2, y_2}$ in $S_2$
Let:
- $d_1$ be an arbitrary upper bound of $\set {x_1, y_1}$ in $S_1$
- $d_2$ be an arbitrary upper bound of $\set {x_2, y_2}$ in $S_2$.
\(\ds x_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Upper Bound of Set | |||||||||||
\(\, \ds \land \, \) | \(\ds x_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {x_1, x_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Simple Order Product |
Similarly:
\(\ds y_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Upper Bound of Set | |||||||||||
\(\, \ds \land \, \) | \(\ds y_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {y_1, y_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Simple Order Product |
Thus:
- $\tuple {d_1, d_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$
As $c_1$ and $c_2$ are also upper bounds of of $\set {x_1, y_1}$ and $\set {x_2, y_2}$ respectively, it similarly follows that:
- $\tuple {c_1, c_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$.
Now we have:
\(\ds c_1\) | \(\preccurlyeq_1\) | \(\ds d_1\) | Definition of Supremum of SetDefinition of Simple Order Product | |||||||||||
\(\, \ds \land \, \) | \(\ds c_2\) | \(\preccurlyeq_2\) | \(\ds d_2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {c_1, c_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {d_1, d_2}\) | Definition of Simple Order Product |
Thus:
- $\tuple {c_1, c_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$
and:
- if $\tuple {d_1, d_2}$ is an upper bound of $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$, then $\tuple {c_1, c_2} \preccurlyeq_s \tuple {d_1, d_2}$
so $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ admits a supremum $\tuple {c_1, c_2}$ in $\struct {T, \preccurlyeq_s}$.
Now let:
- $c_1 = \inf \set {x_1, y_1}$ be the infimum of $\set {x_1, y_1}$
and:
- $c_2 = \inf \set {x_2, y_2}$ be the infimum of $\set {x_2, y_2}$.
We use a similar argument to the above, mutatis mutandis, to show that:
- $\set {\tuple {x_1, x_2}, \tuple {y_1, y_2} }$ admits an infimum $\tuple {c_1, c_2}$ in $\struct {T, \preccurlyeq_s}$.
As $\tuple {x_1, x_2}$ and $\tuple {y_1, y_2}$ are arbitrary, it follows that $\struct {T, \preccurlyeq_s}$ is a lattice.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.18 \ \text {(b)}$