Basics of lattices束そく

1Introduction

The central idea of a lattice束そく is that, in a partially ordered set半順序集合はんじゅんじょしゅうごう, any two elements元げん have a best common upper element and a best common lower element. These are called the join結むすび and the meet交まじわり.

In a total order全順序関係ぜんじゅんじょかんけい, the larger and smaller of two objects are determined immediately. In a partial order半順序関係はんじゅんじょかんけい, two objects may be incomparable. Even then, if there is a best candidate above both and a best candidate below both, a lattice束そく structure is present.

For a lattice束そく, every pair of elements must have both a join結むすび and a meet交まじわり. A partially ordered set is not automatically a lattice; one must check whether the best upper and lower bounds exist.

The words "larger" and "smaller" do not always mean ordinary numerical size. In an inclusion order包含順序ほうがんじゅんじょ they mean being a larger or smaller set, and in a divisibility order整除順序せいじょじゅんじょ they mean divisibility. Therefore the join and meet must always be read from the order being used.

2Terms and definitions

Let $$(P,\text{[PARSE ERROR: Undefined("Command("le")")]})$$(P,\le) be a partially ordered set半順序集合はんじゅんじょしゅうごう. An upper bound上界じょうかい of $$a,b\in P$$a,b\in P is an element $$u\in P$$u\in P such that

A least upper bound最小上界さいしょうじょうかい of $$a$$a and $$b$$b is the smallest element among their upper bounds. It is called the join結むすび and is written

A lower bound下界かかい of $$a,b\in P$$a,b\in P is an element $$l\in P$$l\in P such that

A greatest lower bound最大下界さいだいかかい of $$a$$a and $$b$$b is the largest element among their lower bounds. It is called the meet交まじわり and is written

A partially ordered set is a lattice束そく if every pair of elements has both a join and a meet.

Distinguish an upper bound上界じょうかい from a least upper bound最小上界さいしょうじょうかい, and a lower bound下界かかい from a greatest lower bound最大下界さいだいかかい. When there are several candidates, the join or meet is the best one with respect to the order.

3Strategy

To check whether a partially ordered set is a lattice束そく, do not look only for ordinary maximum and minimum. For every pair $$a,b$$a,b, check the set of common upper bounds and the set of common lower bounds. If the upper bounds have a least element and the lower bounds have a greatest element for every pair, the poset is a lattice.

The existence of several upper bounds is not enough: their set may have no least element, in which case the join does not exist. In a calculation, first collect all common upper or lower bounds, and then look for the least or greatest element within that set.

4Intuitive explanation

The join結むすび $$a\vee b$$a\vee b is the smallest element that is still above both $$a$$a and $$b$$b. The meet交まじわり $$a\wedge b$$a\wedge b is the largest element that is still below both $$a$$a and $$b$$b.

For sets集合しゅうごう ordered by inclusion, "above" means "contains." Therefore the smallest set containing both sets is their union和集合わしゅうごう, and the largest set contained in both is their intersection共通部分きょうつうぶぶん. For positive integers整数せいすう ordered by divisibility, "above" means "is a multiple of," so join becomes least common multiple and meet becomes greatest common divisor.

In a Hasse diagramHasse図ず of a finite partially ordered set有限半順序集合ゆうげんはんじゅんじょしゅうごう, the join is the least element among the common upper bounds—the lowest common element above the pair—and the meet is the greatest element among the common lower bounds—the highest common element below it. If either element is missing for even one pair, the poset is not a lattice.

5Examples

5.11. Powersets ordered by inclusion

For a set $$A$$A, the power set[べき集合] $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(A\right)$$\mathcal P(A) is ordered by inclusion $$\subseteq$$\subseteq. For $$B,C\subseteq A$$B,C\subseteq A,

Thus $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq) is a lattice束そく. Moreover, $$\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$\varnothing is the least element最小元さいしょうげん and $$A$$A is the greatest element最大元さいだいげん. This is a basic example of a Boolean lattice[ブール束].

5.22. Positive integers ordered by divisibility

For positive integers, define $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b to mean that $$a$$a divides $$b$$b. In this order, $$a\vee b$$a\vee b is the least common multiple最小公倍数さいしょうこうばいすう, and $$a\wedge b$$a\wedge b is the greatest common divisor最大公約数さいだいこうやくすう.

For example, for $$6$$6 and $$10$$10, the upper bounds are common multiples of 6 and 10, and the least one is $$30$$30. Hence $$6\vee 10=30$$6\vee10=30. The lower bounds are common divisors of 6 and 10, and the greatest one is $$2$$2. Hence $$6\wedge 10=2$$6\wedge10=2.

6Worked example: finding join and meet in inclusion order

6.1Problem

Let $$A=\{1,2,3\}$$A=\{1,2,3\}, $$B=\{1,2\}$$B=\{1,2\}, and $$C=\{2,3\}$$C=\{2,3\}. Find $$B\vee C$$B\vee C and $$B\wedge C$$B\wedge C in $$\left(\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\right(A),\subseteq )$$(\mathcal P(A),\subseteq).

6.2Explanation

In the inclusion order包含順序ほうがんじゅんじょ, the join結むすび is union. Therefore

This is the smallest set containing both $$B$$B and $$C$$C.

The meet交まじわり is intersection. Therefore

This is the largest set contained in both $$B$$B and $$C$$C.

This example confirms that the abstract definition of a lattice束そく corresponds to the set operations $$\cup$$\cup and $$\cap$$\cap in the powerset ordered by inclusion.

7What changes and what is preserved

An order isomorphism順序同型じゅんじょどうけい preserves comparison, so if a join結むすび or meet交まじわり exists, its corresponding element has the same role on the other side. What is preserved is not a numerical value, but the optimality determined by the order.

8Recognition criteria

• If every pair has a least upper bound最小上界さいしょうじょうかい and a greatest lower bound最大下界さいだいかかい, the poset is a lattice束そく.
• In the inclusion order包含順序ほうがんじゅんじょ, join is $$\cup$$\cup and meet is $$\cap$$\cap.
• In the divisibility order整除順序せいじょじゅんじょ, join is least common multiple and meet is greatest common divisor.
• In a total order全順序関係ぜんじゅんじょかんけい, the larger of two elements is their join and the smaller is their meet.

To decide whether a poset is a lattice束そく, check arbitrary pairs, not only representative examples. If even one pair lacks a join結むすび or a meet交まじわり, that partially ordered set is not a lattice.

9Proof supplement: monotonicity of meet and join

In a lattice束そく, if $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, then

This means that meet and join preserve order.

First prove the statement for meet. The element $$a\wedge c$$a\wedge c is a lower bound of $$a$$a and $$c$$c, so $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}a$$a\wedge c\le a and $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}c$$a\wedge c\le c. Since $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\le b, we also have $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b$$a\wedge c\le b. Hence $$a\wedge c$$a\wedge c is a lower bound of $$b$$b and $$c$$c. Because $$b\wedge c$$b\wedge c is the greatest lower bound of $$b$$b and $$c$$c, it follows that $$a\wedge c\text{[PARSE ERROR: Undefined("Command("le")")]}b\wedge c$$a\wedge c\le b\wedge c.

The join statement is proved dually双対的そうついてき. The element $$b\vee c$$b\vee c is an upper bound of $$b$$b and $$c$$c. Since $$a\text{[PARSE ERROR: Undefined("Command("le")")]}b\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\le b\le b\vee c and $$c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$c\le b\vee c, it is also an upper bound of $$a$$a and $$c$$c. Because $$a\vee c$$a\vee c is the least upper bound of $$a$$a and $$c$$c, we get $$a\vee c\text{[PARSE ERROR: Undefined("Command("le")")]}b\vee c$$a\vee c\le b\vee c.

10Exercise links

11Related links