PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (26)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] properties of arbitrary joins and meets (Derivation)

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 \lbrace B_i\mid i\in I\rbrace$, and each $ b_i:=\bigvee B_i$ exists, then $ \bigvee \lbrace b_i\mid i\in I\rbrace$ exists and is equal to $ \bigvee B$. Conversely, if we drop the assumption that $ \bigvee B$ exists, but assume instead that $ \bigvee \lbrace b_i\mid i\in I\rbrace$ exists, then $ \bigvee B$ exists and is equal to $ \bigvee \lbrace b_i\mid i\in I\rbrace$.
    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:=\lbrace b_i\mid i\in I\rbrace$. 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 \lbrace b_i\mid i\in I\rbrace$ 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$. $ \qedsymbol$

  4. If $ \bigvee \lbrace a\vee b\mid b\in B\rbrace$ exists, then it is equal to $ a\vee \bigvee B$.
    Proof. Let $ c=\bigvee B$ and $ d=\bigvee \lbrace a\vee b\mid b\in B\rbrace$. 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 $ \lbrace a\vee b\mid b\in B\rbrace$. 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. $ \qedsymbol$
  5. If $ P$ is a Boolean algebra then the following hold:
    1. $ \bigwedge (B')$ exists, where $ B':=\lbrace b'\mid b\in B\rbrace$, and is equal to $ (\bigvee B)'$.
      Proof. Let $ c=\bigvee B$. Then $ b\le c$ for any $ b\in B$, so that $ c'\le b'$, or $ c'$ is a lower bound for $ B'$. If $ d$ is any lower bound of $ B'$, then $ d\le b'$ for every $ b\in B$, so that $ b\le d'$, which implies $ c\le d'$, or $ d\le c'$. This means that $ c'$ is the greatest lower bound of $ B'$, or that $ c'=\bigwedge (B')$. $ \qedsymbol$
    2. $ \bigvee \lbrace a\wedge b\mid b\in B\rbrace$ 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 $ \lbrace a\wedge b\mid b\in B\rbrace$. Now, if $ d$ is an upper bound of $ \lbrace a\wedge b\mid b\in B\rbrace$, then $ a\wedge b\le d$ for every $ b\in B$. So $ b=(a'\vee a)\wedge b=(a'\wedge b)\vee (a\wedge b) \le (a'\wedge b)\vee d \le a'\vee d$. This means that $ a'\wedge d$ is an upper bound of $ B$, so $ c\le a'\vee d$. Therefore, $ a\wedge c \le a \wedge (a'\vee d) = (a\wedge a')\vee (a\wedge d)=a\wedge d$. Hence, $ a\wedge c$ is the least upper bound of $ \lbrace a\wedge b\mid b\in B\rbrace$. $ \qedsymbol$
    3. Define $ B\wedge C:=\lbrace b\wedge c\mid b\in B$ and $ c\in C\rbrace.$ 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 \lbrace d\wedge c\mid c\in C\rbrace$ by 4.b above. Now, $ d\wedge c=\bigvee B\wedge c=\bigvee \lbrace b\wedge c\mid b\in B\rbrace$ again by 4.b. For each $ c\in C$, set $ B_c:=\lbrace b\wedge c\mid b\in B\rbrace$. Then $ \bigvee B_c =d\wedge c$ and $ B\wedge C=\bigcup \lbrace B_c\mid c\in C\rbrace$. Therefore, by (3), $ \bigvee (B\wedge C)$ exists and is equal to $ \bigvee \lbrace \bigvee B_c\mid c\in C\rbrace=\bigvee \lbrace d\wedge c\mid c\in C\rbrace=\bigvee B\wedge \bigvee C$. $ \qedsymbol$

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 \lbrace B_i\mid i\in I\rbrace$, and each $ b_i:=\bigwedge B_i$ exists, then $ \bigwedge \lbrace b_i\mid i\in I\rbrace$ exists iff $ \bigwedge B$ does, and they are equal when one exists.
    4. if $ \bigwedge \lbrace a\wedge b\mid b\in B\rbrace$ exists, then it is equal to $ a\wedge \bigwedge B$.
    5. If $ P$ is a Boolean algebra, then
      1. $ \bigvee (B')$ exists, where $ B':=\lbrace b'\mid b\in B\rbrace$, and is equal to $ (\bigwedge B)'$.
      2. $ \bigwedge \lbrace a\vee b\mid b\in B\rbrace$ exists and is equal to $ a\vee \bigwedge B$ for any $ a\in A$.
      3. Define $ B\vee C:=\lbrace b\vee c\mid b\in B$ and $ c\in C\rbrace.$ 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\vert 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'$ is a complement of $ 2$, then $ 2'\wedge 2=1$, so that $ 2'$ must be odd, but then $ 2'\vee 2=2\cdot 2'\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\vert c$ for all $ a\in A$, while $ \bigwedge A$ is the largest non-negative integer $ d$ such that $ d\vert a$ for all $ a\in A$. If $ A=\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 \lbrace x\wedge a\mid a\in A\rbrace=x\ne 0$.



"properties of arbitrary joins and meets" is owned by CWoo.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: prime numbers, complete lattice, addition, contradiction, odd, complement, complemented, bottom, top, distributive lattice, bounded, easy to see, relation, divisibility, integers, Boolean, iff, greatest lower bound, implies, lower bound, inequality, least upper bound, collection, upper bound, subsets, Boolean algebras, posets, properties
There is 1 reference to this entry.

This is version 9 of properties of arbitrary joins and meets, born on 2008-03-03, modified 2008-03-27.
Object id is 10358, canonical name is PropertiesOfArbitraryJoinsAndMeets.
Accessed 300 times total.

Classification:
AMS MSC: 06A06 (Order, lattices, ordered algebraic structures :: Ordered sets :: Partial order, general)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)