properties of arbitrary joins and meets

In this entry, we list and prove some of the basic properties of arbitrary joins and meets. Some of the properties work in general posets, while others work only in lattices, and sometimes only in Boolean algebras.

Let $P$ be a poset and $B$ and $C$ are subsets of $P$ such that $\bigvee B$ and $\bigvee C$ exist.

1. $b\le \bigvee B$ for any $b\in B$. More generally, if $A\subseteq B$ and $\bigvee A$ exists, then $\bigvee A\le \bigvee B$.

2. if $b\le a$ for every $b\in B$, then $\bigvee B\le a$.

3. If $B=\bigcup \{B_i\mid i\in I\}$, and each $b_i:=\bigvee B_i$ exists, then $\bigvee \{b_i\mid i\in I\}$ exists and is equal to $\bigvee B$. Conversely, if we drop the assumption that $\bigvee B$ exists, but assume instead that $\bigvee \{b_i\mid i\in I\}$ exists, then $\bigvee B$ exists and is equal to $\bigvee \{b_i\mid i\in I\}$.

   Proof.

   Let $b=\bigvee B$. For each $i\in I$, and each $c\in B_i\subseteq B$, we clearly have that $c\le b$. So $b_i\le b$, or that $b$ is an upper bound of the collection $D:=\{b_i\mid i\in I\}$. If $d$ is any upper bound of $D$, then $b_i\le d$. For any $c\in B$, $c\in B_i$ for some $i\in I$, so that $c\le b_i$ and hence $c\le d$. This shows that $b\le d$, or that $b$ is the least upper bound of $D$.

   Conversely, suppose $D:=\bigvee \{b_i\mid i\in I\}$ exists and is equal to $d$. Then for any $b\in B$, $b\in B_i$ for some $i\in I$, so that $b\le b_i$, and hence $b\le d$. This shows that $d$ is an upper bound of $B$. If $f$ is any upper bound of $B$, then $f$ is an upper bound of $B_i$ in particular, so $b_i\le f$. Since $i$ is arbitray, $d\le f$, or that $d$ is the least upper bound of $B$. ∎

4. If $\bigvee \{a\vee b\mid b\in B\}$ exists, then it is equal to $a\vee \bigvee B$.

   Proof.

   Let $c=\bigvee B$ and $d=\bigvee \{a\vee b\mid b\in B\}$. We want to show that $a\vee c=d$. Since $b\le c$ for all $b\in B$, we have that $a\vee b\le a\vee c$, and so $d\le a\vee c$ as $d$ is the least upper bound of $\{a\vee b\mid b\in B\}$. On the other hand $a\vee b\le d$, so that $a\le d$ and $b\le d$, for all $b\in B$, the last inequality means that $c\le d$ as well. Therefore $a\vee c\le d$, and we are done. ∎

5. If $P$ is a Boolean algebra then the following hold:

   1. $\bigwedge (B^{\prime })$ exists, where $B^{\prime }:=\{b^{\prime }\mid b\in B\}$, and is equal to ${(\bigvee B)}^{\prime }$.

      Proof.

      Let $c=\bigvee B$. Then $b\le c$ for any $b\in B$, so that $c^{\prime }\le b^{\prime }$, or $c^{\prime }$ is a lower bound for $B^{\prime }$. If $d$ is any lower bound of $B^{\prime }$, then $d\le b^{\prime }$ for every $b\in B$, so that $b\le d^{\prime }$, which implies $c\le d^{\prime }$, or $d\le c^{\prime }$. This means that $c^{\prime }$ is the greatest lower bound of $B^{\prime }$, or that $c^{\prime }=\bigwedge (B^{\prime })$. ∎

   2. $\bigvee \{a\wedge b\mid b\in B\}$ exists and is equal to $a\wedge \bigvee B$ for any $a\in A$.

      Proof.

      Let $c=\bigvee B$. Then $b\le c$ for any $b\in B$ and so $a\wedge b\le a\wedge c$. Therefore $a\wedge c$ is an upper bound of $\{a\wedge b\mid b\in B\}$. Now, if $d$ is an upper bound of $\{a\wedge b\mid b\in B\}$, then $a\wedge b\le d$ for every $b\in B$. So $b=(a^{\prime }\vee a)\wedge b=(a^{\prime }\wedge b)\vee (a\wedge b)\le (a^{\prime }\wedge b)\vee d\le a^{\prime }\vee d$. This means that $a^{\prime }\wedge d$ is an upper bound of $B$, so $c\le a^{\prime }\vee d$. Therefore, $a\wedge c\le a\wedge (a^{\prime }\vee d)=(a\wedge a^{\prime })\vee (a\wedge d)=a\wedge d$. Hence, $a\wedge c$ is the least upper bound of $\{a\wedge b\mid b\in B\}$. ∎

   3. Define $B\wedge C:=\{b\wedge c\mid b\in B\text{ and }c\in C\}.$ Then $\bigvee (B\wedge C)$ exists and is equal to $\bigvee B\wedge \bigvee C$.

      Proof.

      Let $d=\bigvee B$ and $e=\bigvee C$. Then $\bigvee B\wedge \bigvee C=d\wedge \bigvee C=\bigvee \{d\wedge c\mid c\in C\}$ by 4.b above. Now, $d\wedge c=\bigvee B\wedge c=\bigvee \{b\wedge c\mid b\in B\}$ again by 4.b. For each $c\in C$, set $B_c:=\{b\wedge c\mid b\in B\}$. Then $\bigvee B_c=d\wedge c$ and $B\wedge C=\bigcup \{B_c\mid c\in C\}$. Therefore, by (3), $\bigvee (B\wedge C)$ exists and is equal to $\bigvee \{\bigvee B_c\mid c\in C\}=\bigvee \{d\wedge c\mid c\in C\}=\bigvee B\wedge \bigvee C$. ∎

Remarks.

• All of the properties above can be dualized: assume that $B$ and $C$ are subsets of a poset $P$ such that $\bigwedge B$ and $\bigwedge C$ exist, then:

  1. if $A\subseteq B$ and $\bigwedge A$ exists, then $\bigwedge B\le \bigwedge A$.

  2. if $a\le b$ for every $b\in B$, then $a\le \bigwedge B$.

  3. if $B=\bigcup \{B_i\mid i\in I\}$, and each $b_i:=\bigwedge B_i$ exists, then $\bigwedge \{b_i\mid i\in I\}$ exists iff $\bigwedge B$ does, and they are equal when one exists.

  4. if $\bigwedge \{a\wedge b\mid b\in B\}$ exists, then it is equal to $a\wedge \bigwedge B$.

  5. If $P$ is a Boolean algebra, then

     1. $\bigvee (B^{\prime })$ exists, where $B^{\prime }:=\{b^{\prime }\mid b\in B\}$, and is equal to ${(\bigwedge B)}^{\prime }$.

     2. $\bigwedge \{a\vee b\mid b\in B\}$ exists and is equal to $a\vee \bigwedge B$ for any $a\in A$.

     3. Define $B\vee C:=\{b\vee c\mid b\in B\text{ and }c\in C\}.$ Then $\bigwedge (B\vee C)$ exists and is equal to $\bigwedge B\vee \bigwedge C$.

• Notice that for property 5 above, the condition that $P$ be Boolean can not be dropped. For example, consider the set $P$ of non-negative integers. For any two elements $a,b\in P$, define $a\le b$ by the divisibility relation $a|b$. It is easy to see that $P$ is a bounded distributive lattice, with top element $0$ and bottom element $1$. However, it is not complemented (suppose $2^{\prime }$ is a complement of $2$, then $2^{\prime }\wedge 2=1$, so that $2^{\prime }$ must be odd, but then $2^{\prime }\vee 2=2\cdot 2^{\prime }\ne 0$, a contradiction).

  More generally, for any subset $A$ of $P$, define $\bigvee A$ to be the smallest non-negative integer $c$ such that $a|c$ for all $a\in A$, while $\bigwedge A$ is the largest non-negative integer $d$ such that $d|a$ for all $a\in A$. If $A=\mathrm{\varnothing }$, define $\bigvee A=1$ and $\bigwedge A=0$. Then it is not hard to see that $P$ is in addition a complete lattice. However, if we take $A$ to be the set of all odd prime numbers, then $\bigvee A=0$, so that for any $x\in P$, $x\wedge \bigvee A=0$. But if $x$ is any element in $A$, then $\bigvee \{x\wedge a\mid a\in A\}=x\ne 0$.

Title	properties of arbitrary joins and meets
Canonical name	PropertiesOfArbitraryJoinsAndMeets
Date of creation	2013-03-22 17:52:38
Last modified on	2013-03-22 17:52:38
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	12
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 06A06