Discrete �Mathematics

Chapter 8

Relations

大葉大學 資訊工程系 黃鈴玲(Lingling Huang)

Outline

• 8.1 Relations and their properties
• 8.3 Representing Relations
• 8.4 Closures of Relations
• 8.5 Equivalence Relations
• 8.6 Partial Orderings

​

Ch8-2

8.1 Relations and their properties.

※The most direct way to express a relationship between elements of two sets is to use ordered pairs.

For this reason, sets of ordered pairs are called binary relations.

Ch8-3

Example 1.

A : the set of students in your school.

B : the set of courses.

R = { (a, b) : a∈A, b∈B, a is enrolled in course b }

Def 1

Let A and B be sets. A binary relation from A to B is �a subset R of A× B = { (a, b) : a∈A, b∈B }.

Def 1’. We use the notation aRb to denote that (a, b)∈R, and aRb to denote that (a,b)∉R.

Moreover, a is said to be related to b by R if aRb.

Ch8-4

Example (上例) : A : 男生, B : 女生, R : 夫妻關系� A : 城市, B : 州, 省 R : 屬於 (Example 2)

Note. Relations vs. Functions

A relation can be used to express a 1-to-many

relationship between the elements of the sets

A and B.

( function 不可一對多，只可多對一 )

Ch8-5

Def 2. A relation on the set A is a subset of A × A

( i.e., a relation from A to A ).

Example 4. � Let A be the set {1, 2, 3, 4}. Which ordered pairs are � in the relation R = { (a, b)| a divides b }?

Sol :

Ch8-6

R = { (1,1), (1,2), (1,3), (1,4),

(2,2), (2,4),

(3,3),

(4,4) }

Example 5. Consider the following relations on Z.

R₁ = { (a, b) | a ≤ b }

R₂ = { (a, b) | a > b }

R₃ = { (a, b) | a = b or a = −b }

R₄ = { (a, b) | a = b }

R₅ = { (a, b) | a = b+1 }

R₆ = { (a, b) | a + b ≤ 3 }

Ch8-7

Which of these relations

contain each of the pairs

(1,1), (1,2), (2,1), (1,−1),

and (2,2)?

Sol :

●

Example 6. How many relations are there on a set with n elements?

Ch8-8

Sol :

A relation on a set A is a subset of A×A.

⇒ A×A has n² elements.

⇒ A×A has 2ⁿ² subsets.

⇒ There are 2ⁿ² relations.

Def 3. A relation R on a set A is called reflexive (反身性)� if (a,a)∈R for every a∈A.

Example 7. Consider the following relations on

{1, 2, 3, 4} :

R₂ = { (1,1), (1,2), (2,1) }

R₃ = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄ = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

which of them are reflexive ?

Ch8-9

Sol :

R₃

Properties of Relations

Example 8. Which of the relations from

Example 5 are reflexive?

​

​

​

​

​

Ch8-10

R₁ = { (a, b) | a ≤ b }

R₂ = { (a, b) | a > b }

R₃ = { (a, b) | a = b or a = −b }

R₄ = { (a, b) | a = b }

R₅ = { (a, b) | a = b+1 }

R₆ = { (a, b) | a + b ≤ 3 }

Sol : R₁, R₃ and R₄

Example 9. Is the “divides” relation on the set of positive integers reflexive?

Sol : Yes.

Def 4.

(1) A relation R on a set A is called symmetric

if for a, b∈A,� (a, b)∈R ⇒ (b, a)∈R.

(2) A relation R on a set A is called � antisymmetric (反對稱) if for a, b∈A,

(a, b)∈R and (b, a)∈R ⇒ a = b.

Ch8-11

i.e., a≠b and (a,b)∈R ⇒ (b, a)∉R� 若a=b則不要求， (a,a)∈R or (a, a)∉R 皆可

Ch8-12

Example 10. Which of the relations from Example 7

are symmetric or antisymmetric ?

R₂ = { (1,1), (1,2), (2,1) }

R₃ = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄ = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

​

Sol :

R₂, R₃ are symmetric

R₄ are antisymmetric.

Example 11. Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?

Sol : It is not symmetric since 1|2 but 2 | 1.

It is antisymmetric since a|b and b|a implies a=b.

• 補充 :

antisymmetric 跟 symmetric可並存

Ch8-13

∀(a, b)∈R, a≠b

sym. ⇒ (b, a)∈R

antisym. ⇒ (b,a)∉R

故若R中沒有(a, b) with a≠b即可同時滿足

eg. Let A = {1,2,3}, give a relation R on A s.t.

R is both symmetric and antisymmetric, but

not reflexive.

Sol :

R = { (1,1),(2,2) }

Def 5. A relation R on a set A is called � transitive(遞移) if for a, b, c ∈A, � (a, b)∈R and (b, c)∈R ⇒ (a, c)∈R.

Ch8-14

Example 15. Is the “divides” relation on the set of positive integers transitive?

Sol : Suppose a|b and b|c

⇒ a|c

⇒ transitive

Ch8-15

Example 13. Which of the relations in Example 7 are

transitive ?

R₂ = { (1,1), (1,2), (2,1) }

R₃ = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

R₄ = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }

​

Sol :

R₂ is not transitive since � (2,1) ∈ R₂ and (1,2) ∈ R₂ but (2,2) ∉ R₂.

R₃ is not transitive since � (2,1) ∈ R₃ and (1,4) ∈ R₃ but (2,4) ∉ R₃.

R₄ is transitive.

​

Ch8-16

Example 16. How many reflexive relation are there on a set with n elements?

Sol : A relation R on a set A is a subset of A×A.

⇒ A×A has n² elements

⇒ R contains (a,a) ∀a∈A since R is reflexive

⇒ There are 2ⁿ²⁻ⁿ reflexive relations.

Exercise: 7, 43

Example 17. Let A = {1, 2, 3} and B = {1, 2, 3, 4}.

The relation R₁ = {(1,1), (2,2), (3,3)}

and R₂ = {(1,1), (1,2), (1,3), (1,4)} can be

combined to obtain

R₁ ∪ R₂ = {(1,1), (2,2), (3,3), (1,2), (1,3), (1,4)}

R₁ ∩ R₂ = {(1,1)}

R₁ － R₂ = {(2,2), (3,3)}

R₂ － R₁ = {(1,2), (1,3), (1,4)}

R₁ ⊕ R₂ = {(2,2), (3,3), (1,2), (1,3), (1,4)}

Ch8-17

Combining Relations

Def 6. Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite (合成) of R and S is the relation consisting of ordered pairs (a,c), where a∈A, c∈C, and for which there exists an element b∈B such that (a,b)∈R and (b,c)∈S. We denote the composite of R and S by S °R.

Ch8-18

Example 20. What is the composite of relations R and S, where R is the relation from {1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), �(2, 0), (3, 1), (3, 2), (4, 1)}?

Sol. S °R is the relation from {1, 2, 3} to {0, 1, 2} with� S °R = {(1, 0), (1,1), (2, 1), (2, 2), (3, 0), (3, 1)}.

Ch8-19

Def 7. Let R be a relation on the set A. �The powers Rⁿ, n = 1, 2, 3, …, are defined recursively by R¹ = R and Rⁿ⁺¹ = Rⁿ °R.

Sol. R² = R °R = {(1, 1), (2, 1), (3, 1), (4, 2)}.

Example 22. Let R = {(1, 1), (2, 1), (3, 2), (4, 3)}.�Find the powers Rⁿ, n=2, 3, 4,….

R³ = R² °R = {(1, 1), (2, 1), (3, 1), (4, 1)}.

R⁴ = R³ °R = {(1, 1), (2, 1), (3, 1), (4, 1)} = R³.

Therefore Rⁿ = R³ for n=4, 5, ….

Thm 1. The relation R on a set A is transitive if and � only if Rⁿ ⊆ R for n = 1, 2, 3, ….

Exercise: 54

8.3 Representing Relations

Suppose that R is a relation from A={a₁, a₂, …, a_m}

to B = {b₁, b₂,…, b_n }.

The relation R can be represented by the matrix

M_R = [m_ij], where

Ch8-20

Representing Relations using Matrices

Example 1. Suppose that A = {1, 2, 3} and B = {1, 2}� Let R = {(a, b) | a > b, a∈A, b∈B}.� What is the matrix M_R representing R?

Sol :

Ch8-21

0

0

1

1

1

0

R = {(2, 1), (3, 1), (3, 2)}

Note. 不同的A,B的元素順序會製造不同的 M_R 。� 若A=B, 行列應使用相同的順序。

Exercise: 1

※ The relation R is symmetric iff (a_i,a_j)∈R ⇒ (a_j,a_i)∈R. � This means m_ij = m_ji (即M_R是對稱矩陣).

Ch8-22

※ Let A={a₁, a₂, …,a_n}. �A relation R on A is reflexive iff (a_i,a_i)∈R,∀i.

i.e.,

a₁

…

a₂

…

a₁

a_n

:

a_n

:

a₂

對角線上全為1

※ The relation R is antisymmetric iff � (a_i,a_j)∈R and i ≠ j ⇒ (a_j,a_i)∉R.

This means that if m_ij=1 with i≠j, then m_ji=0.

i.e.,

Ch8-23

※ transitive 性質不易從矩陣直接判斷出來，需做運算

Example 3. Suppose that the relation R on a set is represented by the matrix

Ch8-24

Is R reflexive, symmetric, and/or antisymmetric ?

Sol :

reflexive

symmetric

not antisymmetric

eg. Suppose that S={0, 1, 2, 3}. Let R be a relation

containing (a, b) if a ≤ b, where a ∈ S and b ∈ S. � Is R reflexive, symmetric, antisymmetric ?

​

Sol :

Ch8-25

∴ R is reflexive and

antisymmetric,

not symmetric.

Exercise: 7

Def. irreflexive(非反身性) : (a,a)∉R, ∀a∈A

Example 4. Suppose the relations R₁ and R₂ on a set A are represented by the matrices

Ch8-26

Sol :

What are the matrices representing R₁ ∪ R₂ and �R₁ ∩ R₂?

Example 5. Find the matrix representing the relation S°R, where the matrices representing R and S are

Ch8-27

Sol :

Example 6. Find the matrix representing the relation R², where the matrix representing R is

Ch8-28

Sol :

Exercise: 14

Example 8. Show the digraph of the relation �R={(1,1),(1,3),(2,1),(2,3),(2,4), (3,1),(3,2),(4,1)} on the set {1,2,3,4}.

Sol :

Ch8-29

vertex(點) : 1, 2, 3, 4

edge(邊) : (1,1), (1,3),

(2,1), (2,3), (2,4),

(3,1), (3,2),

(4,1)

Representing Relations using Digraphs

Def 1. A directed graph (digraph) consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs).

Exercise: 26,27

※ The relation R is reflexive iff � for every vertex, �

Ch8-30

(每個點上都有loop)

※ The relation R is symmetric iff for any vertices x≠y, either �

兩點間若有邊，必只有一條邊

※ The relation R is antisymmetric iff for any x≠y,

(兩點間若有邊，必為一對不同方向的邊)

or

or

or

※ The relation R is transitive iff � for a, b, c ∈A, � (a, b)∈R and (b, c)∈R ⇒ (a, c)∈R.

This means:

Ch8-31

⇒

(只要點 x 有路徑走到點 y，x 必定有邊直接連向 y)

Example 10. Determine whether the relations R and S are reflexive, symmetric, antisymmetric, and/or transitive

Ch8-32

Sol :

R :

irreflexive(非反身性)的定義在 p.528

即 (a,a)∉R, ∀a∈A

not reflexive,

symmetric

not antisymmetric

not transitive

(b→a, a→c, b→c)

Exercise: 31

reflexive,

not symmetric,

not antisymmetric,

not transitive

(a→b, b→c, a→c)

8.4 Closures of Relations

The relation R={(1,1), (1,2), (2,1), (3,2)} on the set A={1, 2, 3} is not reflexive.

Q: How to construct a smallest reflexive relation R_r such that R⊆ R_r ?

Ch8-33

※ Closures

Sol: Let R_r = R ∪ {(2,2), (3,3)}.

i. e., R_r = R ∪ Δ, where Δ={(a, a)| a ∈ A}.

R_r is a reflexive relation containing R that is as small as possible. It is called the reflexive closure of R.

Example 1. What is the reflexive closure of the � relation R={(a,b) | a < b} on the set of integers ?

Sol : R_r = R ∪ Δ = {(a,b) | a < b} ∪ { (a, a) | a∈Z }

= { (a, b) | a ≤ b, a, b∈Z }

Ch8-34

Example :

The relation R={ (1,1),(1,2),(2,2),(2,3),(3,1),(3,2) } on the set A={1,2,3} is not symmetric. Find a smallest symmetric relation R_s containing R.

Sol : Let R⁻¹={ (b, a) | (a, b)∈R }

Let R_s= R∪R⁻¹={ (1,1),(1,2),(2,1),(2,2),(2,3),

(3,1),(1,3),(3,2) }

​

R_s is called the symmetric closure of R.

Example 2. What is the symmetric closure of the relation R={(a, b) | a > b } on the set of positive integers ?

Sol :

R∪{ (b, a) | a > b } = { (c, d) | c ≠ d }

Ch8-35

Exercise: 1,9

Def :

1.(reflexive closure of R on A)

R_r=the smallest reflexive relation containing R.

R_r=R∪{ (a, a) | a∈A , (a, a)∉R}

2.(symmetric closure of R on A)

R_s=the smallest symmetric relation containing R.

R_s=R∪{ (b, a) | (a, b)∈R and (b, a) ∉R}

3.(transitive closure of R on A) (後面再詳細說明)

R_t=the smallest transitive relation containing R.

R_t=R∪{(a, c) | (a, b)∈R_t and (b, c)∈R_t, but (a, c)∉R_t}(repeat)

Ch8-36

Note. There is no antisymmetric closure，因若不是antisymmetric，� 表示有a≠b, 且(a, b)及(b, a)都∈R，此時加任何pair� 都不可能變成 antisymmetric.

Paths in Directed Graphs

Ch8-37

Def 1. A path from a to b in the digraph G is a sequence of edges (x₀, x₁), (x₁, x₂), …, (x_n-1, x_n) in G, where n∈Z⁺, and x₀= a, x_n= b. This path is denoted by x₀, x₁, x₂, …, x_n and has length n.

Ex.

A path from 1 to 5�of length 4

Theorem 1 Let R be a relation on a set A. There is a path of length n, where n∈Z⁺, from a to b if and only if�(a, b) ∈ Rⁿ.

Transitive Closures

Ch8-38

Def 2. Let R be a relation on a set A. The connectivity relation R* consists of pairs (a, b) such that there is a path of length at least one from a to b in R.

i.e.,

Theorem 2 The transitive closure of a relation R equals the connectivity relation R*.

Lemma 1 Let R be a relation on a set A with |A|=n.� then

Ch8-39

Example. Let R be a relation on a set A, where

A={1,2,3,4,5}, R={(1,2),(2,3),(3,4),(4,5)}.

What is the transitive closure R_t of R ?

Sol :

∴R_t = R ∪ R² ∪ R³ ∪ R⁴ ∪ R⁵

= {(1,2),(2,3),(3,4),(4,5),

(1,3), (2,4), (3,5),

(1,4), (2,5),

(1,5)}

Theorem 3 Let M_R be the zero-one matrix of the relation R on a set with n elements. Then the �zero-one matrix of the transitive closure R* is��

Example 7. Find the zero-one matrix of the transitive closure of the relation R where��Sol :

Exercise: 25

Ch8-40

8.5 Equivalence Relations (等價關係)

Def 1. A relation R on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

Ch8-41

Example 1.

Let R be the relation on the set of integers such that aRb if and only if a=b or a=−b. Then R is an equivalence relation.

Example 2.

Let R be the relation on the set of real numbers such that aRb if and only if a−b is an integer. �Then R is an equivalence relation.

Example 3. (Congruence Modulo m)

Let m ∈ Z and m > 1. Show that the relation

R={ (a,b) | a≡b (mod m) } is an equivalence relation on the set of integers.

Ch8-42

Note that a≡b(mod m) iff m | (a−b).

∵① a≡a (mod m) ⇒ (a, a)∈R ⇒ reflexive

② If a≡b(mod m), then a−b=km, k∈Z

⇒ b−a= (−k)m ⇒ b≡a (mod m) ⇒ symmetric

③ If a≡b(mod m), b≡c(mod m)

then a−b=km, b−c=lm

⇒ a−c=(k+l)m ⇒ a≡c(mod m) ⇒ transitive

∴ R is an equivalence relation.

Sol :

( a is congruent to b modulo m, a 與b除以m後餘數相等)

Ch8-43

Example 4.

Let l(x) denote the length of the string x.

Suppose that the relation

R={(a,b) | l(a)=l(b), a,b are strings of English letters }

Is R an equivalence relation?

Sol :

① (a,a)∈R ∀string a ⇒ reflexive

② (a,b)∈R ⇒ (b,a)∈R ⇒ symmetric

③ (a,b)∈R,(b,c)∈R ⇒ (a,c)∈R ⇒ transitive

Yes.

Ch8-44

Example 7.

Let R be the relation on the set of real numbers such that xRy if and only if x and y differ by less than 1, that is |x− y| < 1. Show that R is not an equivalence relation.

Sol :

① xRx ∀x since x− x =0 ⇒ reflexive

② xRy ⇒ |x− y| < 1 ⇒ |y− x| < 1 ⇒ yRx � ⇒ symmetric

③ xRy, yRz ⇒ |x− y| < 1, |y− z| < 1 ⇒ |x− z| < 1 � ⇒ Not transitive

Exercise: 3, 23

🗴

Def 3.

Let R be an equivalence relation on a set A.

The equivalence class of the element a∈A is

[a]_R = { s | (a, s)∈R }

For any b∈[a]_R , b is called a representative of this equivalence class.

Ch8-45

Note:

If (a, b)∈R, then [a]_R=[b]_R.

Equivalence Classes

Example 9.

What are the equivalence class of 0 and 1

for congruence modulo 4 ?

Sol :

Let R={ (a,b) | a≡b (mod 4) }

Then [0]_R = { s | (0,s)∈R }

= { …, −8, −4, 0, 4, 8, … }

[1]_R = { t | (1,t)∈R } = { …,−7, −3, 1, 5, 9,…}

Ch8-46

Exercise: 25, 29

Def.

A partition (分割) of a set S is a collection of disjoint nonempty subsets A_i of S that have S as their union.

In other words, we have A_i ≠∅, ∀i,

A_i∩A_j = ∅ , for any i≠j, and ∪A_i = S.

Ch8-47

Equivalence Classes and Partitions

Example 12.

Suppose that S={1, 2, 3, 4, 5, 6}. The collection

of sets A₁={1, 2, 3}, A₂={4, 5}, and A₃={6} form a partition of S.

Ch8-48

Thm 2.

Let R be an equivalence relation on a set A.

Then the equivalence classes of R form a partition of A.

Sol :

R={ (a, b) | a, b∈ A₁}∪ { (a, b) | a, b∈ A₂}

∪ { (a, b) | a, b∈ A₃}� ={(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2),� (3, 3), (4,4), (4, 5), (5,4), (5, 5), (6, 6)}

Exercise: 47

Example 13. �List the ordered pairs in the equivalence relation R�produced by the partition A₁={1, 2, 3}, A₂={4, 5}, and �A₃={6} of S={1, 2, 3, 4, 5, 6}.

Ch8-49

Example 14.

The equivalence classes of the congruence modulo 4 relation form a partition of the integers.

Sol :

[0]₄ = { …, −8, −4, 0, 4, 8, … }

[1]₄ = { …, −7, −3, 1, 5, 9, … }

[2]₄ = { …, −6, −2, 2, 6, 10, … }

[3]₄ = { …, −5, −1, 3, 7, 11, … }

Ch8-50

8.6 Partial Orderings

Def 1. A relation R on a set S is called a partial ordering (偏序) or partial order if it is reflexive, antisymmetric, and transitive. A set S together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R).

Example 1.

Show that the “greater than or equal” (≥) is a partial ordering on the set of integers.

Sol :

① x ≥ x ∀x∈Z ⇒ reflexive

② If x ≥ y and y ≥ x then x = y. ⇒ antisymmetric

③ x ≥ y, y ≥ z ⇒ x ≥ z ⇒ transitive

Exercise: 1, 5, 9

Ch8-51

Def 2.

The elements a and b of a poset (S, ) are called comparable if either a b or b a. When a and b are elements of S such that neither a b or b a, a and b are called incomparable.

Example 5.

In the poset (Z⁺, |), are the integers 3 and 9 comparable? Are 5 and 7 comparable?

Sol :

3|9 ⇒ comparable

Exercise: 14

Ch8-52

Def 3. If (S, ) is a poset and every two elements of S are comparable, S is called a totally ordered or linearly ordered set, and is called a total order (全序) or a linear order. A totally ordered set is also called a chain.

Example 6.

The poset (Z, ≤) is totally ordered, because a ≤ b or �b ≤ a whenever a and b are integers.

Example 7.

The poset (Z⁺, |) is not totally ordered.

Ch8-53

Lexicographic Order (辭彙編纂的)

The words in a dictionary are listed in alphabetic, or lexicographic, order, which is based on the ordering of the letters in the alphabet.

Def. Let (A₁, ₁) and (A₂, ₂) be two posets. The lexicographic ordering on A₁ × A₂ is defined as� (a₁, a₂) (b₁, b₂) either if a_{1 1} b₁ or � if both a₁ = b₁ and a_{2 2} b₂

We obtain a partial ordering by adding equality to the ordering on A₁ × A₂.

Ch8-54

Example 9.

In the poset (Z×Z, ), where is the lexicographic ordering constructed from the usual ≤ relation on Z.� (3, 5) (4, 8), � (3, 8) (4, 5),� (4, 9) (4, 11)

Exercise: 17

Hasse Diagrams (用來描述poset中元素的大小關係)

將poset用圖形表示，若a, b是comparable且 a b，�則將ab間連一條邊，並將b節點放在a節點的上面，�但若a b c，則不畫ac間的邊。

Ch8-55

Example 12.

Draw the Hasse diagram representing the partial ordering {(a, b) | a divides b} on {1, 2, 3, 4, 6, 8, 12}.

Sol :

Ch8-56

Example 13.

Draw the Hasse diagram for the partial ordering �{(A, B) | A ⊆ B} on the power set P(S) where S={a, b, c}.

Sol :

Exercise: 23

Ch8-57

Maximal and Minimal Elements

Def.

An element a∈S is maximal in the poset (S, ) if there is no b∈S such that a b. Similarly, an element a∈S is minimal if there is no b∈S such that b a.

a is the greatest element of the poset (S, ) if b a�for all b∈S. a is the least element of (S, ) if a b �for all b∈S.

Example 12 中� 8, 12 是maximal，�1是least也是minimal，�沒有greatest element

Ch8-58

Ex

A={2, 6}

upper bound of A: 6, 12

lower bound of A: 1, 2

Def.

Let A be a subset of a poset (S, ). If u is an element of S such that a u for all elements a∈A, then u is called an upper bound of A.

If l is an element of S such that l a for all elements a∈A, then l is called an lower bound of A.

Ch8-59

Ex

A₁={d, e}, A₂={b, c}

​

least upper bound of A₁= f

A₁ has no greatest lower bound

A₂ has no least upper bound

greatest lower bound of A₂= a

Def.

Let A be a subset of a poset (S, ). An element x is called the least upper bound of A if x is an upper bound of A and x z whenever z is an upper bound of A.

Let A be a subset of a poset (S, ). An element x is called the greatest lower bound of A if x is a lower bound of A and y x whenever y is a lower bound of A.

Ch8-60

Lattices

Def. A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice.

Example 21.

Determine whether the following posets are lattices.�(a) (b) (c)

yes

yes

(b,c) 沒有l.u.b. ⇒ no

Ch8-61

Example 22.

Is the poset (Z⁺, |) a lattice?

Sol :

For any a, b∈Z⁺, �gcd(a,b) is the greatest lower bound of a, b. lcm(a,b) is the least upper bound of a, b.

⇒ Yes

Example 23.

Determine whether the posets ({1, 2, 3, 4, 5}, |) and ({1, 2, 4, 8, 16}, |) are lattices.

Sol :

In ({1, 2, 3, 4, 5}, |), 2 and 3 has no l.u.b. ⇒ No.

In ({1, 2, 4, 8, 16}, |), �any a, b has l.u.b. and g.l.b. ⇒ Yes.

Exercise: 43

Ch8-62

Topological Sorting

Suppose that a project is made up of 20 different tasks. Some tasks can be completed only after others have been finished. How can an order be found for these tasks?

Def.

A total ordering is said to be compatible (相容) with the partial ordering R if a b whenever aRb.

Constructing a compatible total ordering from a partial ordering is called topological sorting.

Lemma 1.

Every finite nonempty poset (S, ) has at least one minimal element.

Ch8-63

Exercise: 62

Example 26.

Find a compatible total ordering for the poset �({1, 2, 4, 5, 12, 20}, | ).

Sol :

Topological sorting 的方式：逐次output minimal element，� 即得到由小到大的compatible total ordering

1

2

5

4

12

20

2跟5的順序可交換，12跟20也是