Hello, dear friend, you can consult us at any time if you have any questions, add  WeChat:  zz-x2580

COMP9020 

Equivalence and Order Relations
Textbook (R & W) - Ch. 3, Sec. 3.4-3.5
Ch. 11, Sec. 11.1-11.2
Problem set 4 + quiz
1
Equivalence Relations and Partitions
Relation R is called an equivalence relation if it satisfies
(R), (S), (T).
Every equivalence R defines equivalence classes on its domain S .
The equivalence class [s] (w.r.t. R) of an element s ∈ S is
[s]R = { t ∈ S : tRs }
This notion is well defined only for R which is an equivalence
relation. Collection of all equivalence classes is a partition of S :
S =
⋃˙
s∈S [s]R (∪˙ denotes a disjoint union)
Example
R = {(m, n) ∈ Z : m mod 2 = n mod 2}
[0] = {. . . ,−4,−2, 0, 2, 4, . . .} (same as [−2], [2], . . .)
[1] = {. . . ,−3,−1, 1, 3, 5, . . .}
2
Thus the equivalence classes are disjoint and jointly cover the
entire domain. It means that every element belongs to one (and
only one) equivalence class.
We call s1, s2, . . . representatives of (different) equivalence classes
For s, t ∈ S either [s] = [t], when sRt, or [s]∩ [t] = ∅, when s 6Rt.
We commonly write s ∼R t when s, t are in the same equivalence
class.
In the opposite direction, a partition of a set defines the
equivalence relation on that set. If S = S1 ∪˙ . . . ∪˙ Sk , then we
specify s ∼ t exactly when s and t belong to the same Si .
Example
Z = {. . . ,−3, 0, 3, . . .} ∪˙ {. . . ,−2, 1, 4, . . .} ∪˙ {. . . ,−1, 2, 5, . . .}
m ∼ n if, and only if, m mod 3 = n mod 3
[0] = [3] = [6] = . . . [0] ∩ [1] = ∅ = [0] ∩ [2]
3
If the relation ∼ is an equivalence on S and [S ] the corresponding
partition, then
ν : S −→ [S ], ν : s 7→ [s] = { x ∈ S : x ∼ s }
is called the natural map. It is always onto.
Exercise
When is ν also 1–1 ?
Only when ∼ is the identity on S .
4
If the relation ∼ is an equivalence on S and [S ] the corresponding
partition, then
ν : S −→ [S ], ν : s 7→ [s] = { x ∈ S : x ∼ s }
is called the natural map. It is always onto.
Exercise
When is ν also 1–1 ?
Only when ∼ is the identity on S .
5
A function f : S −→ T defines an equivalence relation on S by
s1 ∼ s2 iff f (s1) = f (s2)
These sets f←(t), t ∈ T that are nonempty form the
corresponding partition
S =
⋃
t∈T
f←(t)
Exercise
When are all f←(t) 6= ∅?
When f is onto.
6
A function f : S −→ T defines an equivalence relation on S by
s1 ∼ s2 iff f (s1) = f (s2)
These sets f←(t), t ∈ T that are nonempty form the
corresponding partition
S =
⋃
t∈T
f←(t)
Exercise
When are all f←(t) 6= ∅?
When f is onto.
7
Example: Congruence Relations
Z −→ Zp: Partition of Z into classes of numbers with the same
remainder (mod p); it is particularly important for p prime
Zp = {0, 1, . . . , p − 1}
One can define all four arithmetic operations (with the usual
properties) on Zp for a prime p; division has to be restricted when
p is not prime.
Standard notation: m ≡ n (mod p)
def
= remainder of dividing m by p = remainder of dividing n by p
NB
(Zp,+, ·, 0, 1) are fundamental algebraic structures known as rings.
These structures are very important in coding theory and
cryptography.
8
Modular Arithmetic
Example
Z5 = {0, 1, 2, 3, 4}
+5 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
n −n
0 0
1 4
2 3
3 2
4 1
∗5 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
n n−1
0 −
1 1
2 3
3 2
4 4
9
Exercise
3.5.6 Calculate the following in Z7.
(b) 5 + 6 = 4
(c) 4 ∗ 4 = 2
(d) for any k ∈ Z7, 0 + k = k
(e) for any k ∈ Z7, 1 ∗ k = k
10
Exercise
3.5.6 Calculate the following in Z7.
(b) 5 + 6 = 4
(c) 4 ∗ 4 = 2
(d) for any k ∈ Z7, 0 + k = k
(e) for any k ∈ Z7, 1 ∗ k = k
11
Exercise
Solve the following for x in Z5.
(a) 2 + x = 1 ⇒ x = 4
(b) 2 ∗ x = 1 ⇒ x = 2−1 = 3
(c) 2 ∗ x = 3 ⇒ x = 3 ∗ 2−1 = 3 ∗ 3 = 4
Exercise
Solve the following for x in Z6.
(d) 5 + x = 1 ⇒ x = 2
(e) 5 ∗ x = 1 ⇒ x = 5 (since 25 mod 6 = 1)
(e) 2 ∗ x = 1 undefined (since 2 · k mod 6 6= 1 for all k ∈ Z6)
12
Exercise
Solve the following for x in Z5.
(a) 2 + x = 1 ⇒ x = 4
(b) 2 ∗ x = 1 ⇒ x = 2−1 = 3
(c) 2 ∗ x = 3 ⇒ x = 3 ∗ 2−1 = 3 ∗ 3 = 4
Exercise
Solve the following for x in Z6.
(d) 5 + x = 1 ⇒ x = 2
(e) 5 ∗ x = 1 ⇒ x = 5 (since 25 mod 6 = 1)
(e) 2 ∗ x = 1 undefined (since 2 · k mod 6 6= 1 for all k ∈ Z6)
13
Exercise
Solve the following for x in Z5.
(a) 2 + x = 1 ⇒ x = 4
(b) 2 ∗ x = 1 ⇒ x = 2−1 = 3
(c) 2 ∗ x = 3 ⇒ x = 3 ∗ 2−1 = 3 ∗ 3 = 4
Exercise
Solve the following for x in Z6.
(d) 5 + x = 1 ⇒ x = 2
(e) 5 ∗ x = 1 ⇒ x = 5 (since 25 mod 6 = 1)
(e) 2 ∗ x = 1 undefined (since 2 · k mod 6 6= 1 for all k ∈ Z6)
14
Example: Equivalence Classes in Geometry
Starting from the rectangle
a
b
c
d
and identifying the points in the interval [a, b] with the points in
[c , d ] (in this direction) results in a cylinder, while identifying also
[a, c] and [b, d ] gives a torus.
Points in the interior of the rectangle are not ‘glued’ together; thus
the equivalence classes (for the cylinder) have either one or two
elements, while for the torus there is also one class with four
elements (which are the four elements?)
Identifying [a, b] with [d , c] (in that direction) gives a one-sided
Moebius strip; furthermore, putting it together with identifying
[a, c] and [b, d ] gives a one-sided closed surface (“Klein bottle”).
15
A Klein bottle cannot be embedded in 3 dimensions without
self-intersection.
16
Supplementary Exercise
Exercise
3.6.6 Show that m ∼ n iff m2 ≡ n2 (mod 5) is an equivalence on
S = {1, . . . , 7}. Find all the equivalence classes.
(a) It just means that m ≡ n (mod 5) or m ≡ −n (mod 5), e.g.
1 ≡ −4 (mod 5). This satisfies (R), (S), (T).
(b) We have
[1] = {1, 4, 6}
[2] = {2, 3, 7}
[5] = {5}
17
Supplementary Exercise
Exercise
3.6.6 Show that m ∼ n iff m2 ≡ n2 (mod 5) is an equivalence on
S = {1, . . . , 7}. Find all the equivalence classes.
(a) It just means that m ≡ n (mod 5) or m ≡ −n (mod 5), e.g.
1 ≡ −4 (mod 5). This satisfies (R), (S), (T).
(b) We have
[1] = {1, 4, 6}
[2] = {2, 3, 7}
[5] = {5}
18
It is often necessary to define a function on [S ] by describing it on
the individual representatives t ∈ [s] for each equivalence class [s].
If φ : [S ] −→ X is to be defined in this way, one must
define φ(t) for all t ∈ S , making sure that φ(t) ∈ X
make sure that φ(t1) = φ(t2) whenever t1 ∼ t2,
ie. when [t1] = [t2]
define φ([s])
def
= φ(s).
The second condition is critical for φ to be well-defined.
Example
[S ] = {0, 4, 8, . . .} ∪˙ {1, 5, 9, . . .} ∪˙ {2, 6, 10, . . .} ∪˙ {3, 7, 11, . . .}
φ : [S ] −→ Z2 defined by φ(n) = n mod 2
φ(0) = 0 = φ(4) = φ(8) = . . .
19
Example
Example of a not well-defined ‘function’ on equivalence classes:
φ : {0, 3, 6, . . .} ∪˙ {1, 4, 7, . . .} ∪˙ {2, 5, 8, . . .} −→ Z5
φ(n)
?
= n mod 5
Problem: [0] = [3] = [6] = . . . in Z3; however,
0 mod 5 = 0, 3 mod 5 = 3, 6 mod 5 = 1 . . .
20
Supplementary Exercise
Exercise
3.6.10
R is a binary relation on N× N, i.e. it is a subset of N4
(m, n)R (p, q) if m ≡ p (mod 3) or n ≡ q (mod 5).
(a) R ∈ (R)?
Yes: (m, n) ∼ (m, n) iff m ≡ m (mod 3) or n ≡ n (mod 5) iff true
or true.
(b) R ∈ (S)?
Yes: by symmetry of . ≡ . (mod n).
(c) R ∈ (T)?
No — for arbitrary two pairs (m1, n1) and (m2, n2) one can create
a chain (m1, n1)R(m2, n1) and (m2, n1)R(m2, n2), but
(m1, n1) 6R(m2, n2).
21
Supplementary Exercise
Exercise
3.6.10
R is a binary relation on N× N, i.e. it is a subset of N4
(m, n)R (p, q) if m ≡ p (mod 3) or n ≡ q (mod 5).
(a) R ∈ (R)?
Yes: (m, n) ∼ (m, n) iff m ≡ m (mod 3) or n ≡ n (mod 5) iff true
or true.
(b) R ∈ (S)?
Yes: by symmetry of . ≡ . (mod n).
(c) R ∈ (T)?
No — for arbitrary two pairs (m1, n1) and (m2, n2) one can create
a chain (m1, n1)R(m2, n1) and (m2, n1)R(m2, n2), but
(m1, n1) 6R(m2, n2).
22
Supplementary Exercise
Exercise
3.6.10
R is a binary relation on N× N, i.e. it is a subset of N4
(m, n)R (p, q) if m ≡ p (mod 3) or n ≡ q (mod 5).
(a) R ∈ (R)?
Yes: (m, n) ∼ (m, n) iff m ≡ m (mod 3) or n ≡ n (mod 5) iff true
or true.
(b) R ∈ (S)?
Yes: by symmetry of . ≡ . (mod n).
(c) R ∈ (T)?
No — for arbitrary two pairs (m1, n1) and (m2, n2) one can create
a chain (m1, n1)R(m2, n1) and (m2, n1)R(m2, n2), but
(m1, n1) 6R(m2, n2).
23
Supplementary Exercise
Exercise
3.6.10
R is a binary relation on N× N, i.e. it is a subset of N4
(m, n)R (p, q) if m ≡ p (mod 3) or n ≡ q (mod 5).
(a) R ∈ (R)?
Yes: (m, n) ∼ (m, n) iff m ≡ m (mod 3) or n ≡ n (mod 5) iff true
or true.
(b) R ∈ (S)?
Yes: by symmetry of . ≡ . (mod n).
(c) R ∈ (T)?
No — for arbitrary two pairs (m1, n1) and (m2, n2) one can create
a chain (m1, n1)R(m2, n1) and (m2, n1)R(m2, n2), but
(m1, n1) 6R(m2, n2).
24
Order Relations
Total order ≤ on S
(R) x ≤ x for all x ∈ S
(AS) x ≤ y , y ≤ x ⇒ x = y
(T) x ≤ y , y ≤ z ⇒ x ≤ z
(L) Linearity — any two elements are comparable:
for all x , y either x ≤ y or y ≤ x (and both if x = y)
25
On a finite set all total orders are “isomorphic”
x1 ≤ x2 ≤ · · · ≤ xn
On an infinite set there is quite a variety of possibilities.
Examples
discrete with a least element, e.g. N = {0, 1, 2, . . .}
discrete without a least element, e.g. Z = {. . . , 0, 1, 2, . . .}
various dense/locally dense orders
rational numbers Q : ∀p, q ∈ Q (p < q ⇒ ∃r ∈ Q (p < r < q))
S = [a, b] — both least and greatest elements
S = (a, b] — no least element
S = [a, b) — no greatest element
other [0, 1] ∪ [2, 3] ∪ [4, 5] ∪ . . .
26
Partial Order
Definition
A partial order on S satisfies (R), (AS), (T); need not be (L)
(S ,) is called a poset — partially ordered set
To each (partial) order one can associate a unique quasi-order
x ≺ y iff x y and x 6= y
It satisfies (AS) and (T); it satisfies (L) if it corresponds to a total
order (we could call it a total quasi-order); it does not satisfy (R)
for any pair x , y .
27
Example
Exercise
11.1.8 For ω1, ω2 ∈ Σ∗ define ω1 ω2 when ω2 = νω1ν ′ for
some ν, ν ′.
Is (Σ∗,) a partial order?
Yes.
Relation means being a substring; it is a partial order:
(R) ω = λωλ, hence ω ω
(AS) if ω1 = νω2ν
′ and ω2 = χω1χ′ for some ν, ν ′, χ, χ′ then
ν = ν ′ = χ = χ′ = λ, hence ω1 = ω2
(T) if ω1 = νω2ν
′ and ω2 = χω3χ′ then ω1 = νχω3χ′ν ′
28
Example
Exercise
11.1.8 For ω1, ω2 ∈ Σ∗ define ω1 ω2 when ω2 = νω1ν ′ for
some ν, ν ′.
Is (Σ∗,) a partial order?
Yes.
Relation means being a substring; it is a partial order:
(R) ω = λωλ, hence ω ω
(AS) if ω1 = νω2ν
′ and ω2 = χω1χ′ for some ν, ν ′, χ, χ′ then
ν = ν ′ = χ = χ′ = λ, hence ω1 = ω2
(T) if ω1 = νω2ν
′ and ω2 = χω3χ′ then ω1 = νχω3χ′ν ′
29
Exercise
11.6.16 Properties of four relations defined on P = {1, 2, . . .}?
R1 if m|n
R2 if |m − n| ≤ 2
R3 if 2|m + n
R4 if 3|m + n
R1 R2 R3 R4
(R)
(S)
(AS)
(T)
Equivalence ? ? ? ?
Partial order ? ? ? ?
30
Exercise
11.6.16 Properties of four relations defined on P = {1, 2, . . .}
R1 if m|n
R2 if |m − n| ≤ 2
R3 if 2|m + n
R4 if 3|m + n
R1 R2 R3 R4
(R) Yes Yes Yes
(S) Yes Yes Yes
(AS) Yes
(T) Yes Yes
Equivalence Yes
Partial order Yes
31
Hasse Diagram
Every finite poset can be represented as a Hasse diagram, where
a line is drawn upward from x to y if x ≺ y and there is no z such
that x ≺ z ≺ y
Example
11.1.1(a) Hasse diagram for positive divisors of 24
1
3
6
12
24
4
8
2
p q if, and only if, p | q
(Named after mathematician Helmut Hasse (Germany), 1898–1979)
32
Ordering Concepts
Definition
Minimal and maximal elements (they always exist in every
finite poset)
Minimum and maximum — unique minimal and maximal
element
lub (least upper bound) and glb (greatest lower bound) of a
subset A ⊆ S of elements
lub(A) — smallest element x ∈ S s.t. x a for all a ∈ A
glb(A) — greatest element x ∈ S s.t. x a for all a ∈ A
Lattice — a poset where lub and glb exist for every pair of
elements
(by induction, they then exist for every finite subset of
elements)
33
Examples
Pow({a, b, c}) with the order ⊆
∅ is minimum; {a, b, c} is maximum
11.1.4
Pow({a, b, c}) \ {{a, b, c}} (proper subsets of {a, b, c})
Each two-element subset {a, b}, {a, c}, {b, c} is maximal.
But there is no maximum
{1, 2, 3, 4, 6, 8, 12, 24} partially ordered by divisibility is a
lattice
e.g. lub({4, 6}) = 12; glb({4, 6}) = 2
{1, 2, 3} partially ordered by divisibility is not a lattice
{2, 3} has no lub
{2, 3, 6} partially ordered by divisibility is not a lattice
{2, 3} has no glb
34
Examples
{1, 2, 3, 12, 18, 36} partially ordered by divisibility is not a
lattice
{2, 3} has no lub (12, 18 are minimal upper bounds)
1
2 3
12 18
36
35
NB
An infinite lattice need not have a lub (or no glb) for an arbitrary
(infinite!) subset of its elements, in particular no such bound may
exist for all its elements.
Examples
(Z,≤) — neither lub nor glb;
(F(N),⊆) — all finite sets of natural numbers
has no arbitrary lub property
glb exists for infinitely many elements: it is the intersection,
hence always finite;
(I(N),⊆) — all infinite sets of natural numbers
may not have an arbitrary glb
lub exists for infinitely many elements: it is the union, which
is always infinite.
36
Exercise
11.1.5 Consider poset (R,≤)
(a) Is this a lattice?
(b) Give an example of a non-empty subset of R that has no upper
bound.
(c) Find lub({ x ∈ R : x < 73 })
(d) Find lub({ x ∈ R : x ≤ 73 })
(e) Find lub(
{
x : x2 < 73
}
)
(f) Find glb(
{
x : x2 < 73
}
)
37
Exercise
(a) It is a lattice.
(b) subset with no upper bound: R>0 = { r ∈ R : r > 0 }
(c) and (d) lub({ x : x < 73 }) = lub({ x : x ≤ 73 }) = 73
(e) lub(
{
x : x2 < 73
}
) =
√
73
(f) glb(
{
x : x2 < 73
}
) = −√73
38
Exercise
11.1.13 F(N) — collection of all finite subsets of N; ⊆-order
(a) Does it have a maximal element?
(b) Does it have a minimal element?
(c) Given A,B ∈ F(N), does {A,B} have a lub in F(N)?
(d) Given A,B ∈ F(N), does {A,B} have a glb in F(N)?
(e) Is (F(N),⊆) a lattice?
39
Exercise
11.1.13 F(N) — collection of all finite subsets of N; ⊆-order
(a) No maximal elements
(b) ∅ is the minimum
(c) lub(A,B) = A ∪ B
(d) glb(A,B) = A ∩ B
(e) (F(N),⊆) is a lattice — is has finite union and intersection
properties.
40
Exercise
11.1.14 I(N) = Pow(N) \ F(N) — all infinite subsets of N
(a) Does it have a maximal element?
(b) Does it have a minimal element?
(c) Given A,B ∈ I(N), does {A,B} have a lub in I(N)?
(d) Given A,B ∈ I(N), does {A,B} have a glb in I(N)?
(e) Is (I(N),⊆) a lattice?
41
Exercise
11.1.14 I(N) = Pow(N) \ F(N) — all infinite subsets of N
(a) N is the maximum
(b) No minimal elements (∅ is not in I(N))
(c) lub(A,B) = A ∪ B
(d) glb(A,B) = A ∩ B if it exists; it does not exist when A ∩ B is
finite, eg. when empty.
(e) (I(N),⊆) is not a lattice — it has finite union but not finite
intersection property; eg. sets 2N and 2N+ 1 have the empty
intersection.
42
Well-Ordered Sets
Well-ordered set: every subset has a least element.
NB
The greatest element is not required.
Examples
N = {0, 1, . . .}
N1 ∪˙ N2 ∪˙ N3 ∪˙ . . ., where each Ni ' N
and N1 < N2 < N3 · · ·
NB
Well-order sets are an important mathematical tool to prove
termination of programs.
43
Ordering of a Poset — Topological Sort
For a poset (S ,) any linear order ≤ that is consistent with is
called topological sort. Consistency means that a b ⇒ a ≤ b.
Example
e
a
b
c
d
f
The following all are topological sorts:
a ≤ b ≤ e ≤ c ≤ f ≤ d
a ≤ e ≤ b ≤ f ≤ c ≤ d
. . . . . .
a ≤ e ≤ f ≤ b ≤ c ≤ d
44
Combining Orders
Product order — can combine any partial orders. In general, it is
only a partial order, even if combining total orders.
For s, s ′ ∈ S and t, t ′ ∈ T define
(s, t) (s ′, t ′) if s s ′ and t t ′
45
Exercise
11.2.1 Let A = {1, 2, 3, 4} with the usual order, and S = A×A
with the product order.
(a) A chain with seven elements?
(b) A chain with eight elements?
46
Exercise
11.2.1 Let A = {1, 2, 3, 4} with the usual order, and S = A×A
with the product order.
(a) A chain with seven elements?
(1, 1) (1, 2) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) (other solutions exist)
(b) A chain with eight elements?
The above is a maximal chain.
No chains of eight elements.
47
Example
11.2.4 Take (S ,1), (T ,2) to be any total orders of more
than one element. Then S × T with the product order is not a
total order: for any s1 ≺ s2, t1 ≺ t2 the pair (s1, t2) and (s2, t1) are
not comparable.
48
Exercise
11.2.10 Take (S ,1), (T ,2) to be any posets (even chains)
and define the combined order v on S × T
(s, t) v (s ′, t ′) if s s ′ or t t ′
Is v a partial order?
Not a partial order, as it may not satisfy (AS) nor (T).
49
Exercise
11.2.10 Take (S ,1), (T ,2) to be any posets (even chains)
and define the combined order v on S × T
(s, t) v (s ′, t ′) if s s ′ or t t ′
Is v a partial order?
Not a partial order, as it may not satisfy (AS) nor (T).
50
Ordering of Functions
S — arbitrary set (no order required)
(T ,T ) — partially ordered set
M = {f : S −→ T} — set of all functions from S to T
It has a natural partial order:
f g iff ∀s ∈ S (f (s) T g(s))
NB
For finite S = {s1, . . . , sn} this is essentially a generalised product
order: (f (s1), . . . , f (sn)) (g(s1), . . . , g(sn)).
In most applications S has a linear ordering; however, it does not
affect the order of the functions defined on S (only the order on T
matters).
51
Practical Orderings
They are, effectively, total orders on the product of ordered sets.
Lexicographic order — defined on all of Σ∗. It extends a
total order already assumed to exist on Σ.
Lenlex — the order on (potentially) the entire Σ∗, where the
elements are ordered first by length.
Σ(1) ≺ Σ(2) ≺ Σ(3) ≺ · · · , then lexicographically within each
Σ(k). In practice it is applied only to the finite subsets of Σ∗.
Filing order — lexicographic order confined to the strings of
the same length.
It defines total orders on Σi , separately for each i .
52
Examples
Exercise
11.2.5 Let B = {0, 1} with the usual order 0 < 1. List the
elements 101, 010, 11, 000, 10, 0010, 1000 of B∗ in the
(a) Lexicographic order
000, 0010, 010, 10, 1000, 101, 11
(b) Lenlex order
10, 11, 000, 010, 101, 0010, 1000
11.2.8 When are the lexicographic order and lenlex on Σ∗ the
same?
Only when |Σ| = 1.
53
Examples
Exercise
11.2.5 Let B = {0, 1} with the usual order 0 < 1. List the
elements 101, 010, 11, 000, 10, 0010, 1000 of B∗ in the
(a) Lexicographic order
000, 0010, 010, 10, 1000, 101, 11
(b) Lenlex order
10, 11, 000, 010, 101, 0010, 1000
11.2.8 When are the lexicographic order and lenlex on Σ∗ the
same?
Only when |Σ| = 1.
54
Supplementary Exercise
11.6.12 Draw a Hasse diagram for a poset with exactly 5
members, 2 of which are maximal and 1 of which is the poset’s
minimum.
55
Supplementary Exercise
11.6.12 Draw a Hasse diagram for a poset with exactly 5
members, 2 of which are maximal and 1 of which is the poset’s
minimum.
•
•
•
•
•
•
•
•
•
•
and more . . .
56
Supplementary Exercise
Exercise
11.6.6 True or false?
(a) If a set Σ is totally ordered, then the corresponding
lexicographic partial order on Σ∗ also must be totally ordered.
(b) If a set Σ is totally ordered, then the corresponding lenlex order
on Σ∗ also must be totally ordered.
(c) Every finite partially ordered set has a Hasse diagram.
(d) Every finite partially ordered set has a topological sorting.
(e) Every finite partially ordered set has a minimum.
(f) Every finite totally ordered set has a maximum.
(g) An infinite partially ordered set cannot have a maximum.
57
Supplementary Exercise
Exercise
11.6.6
(a) and (b) – True; this is the idea behind various lex-sorts
(c) Yes.
(d) Yes.
(e) False – consider a two-element set with the identity as p.o.
(f) True – due to the finiteness
(g) False, eg. Z<0
58
Summary
Equivalence relations ∼, equivalence classes [S ]
Special equivalence relations on Z: notation m ≡ n (mod p);
Zp
Orderings: total, partial; lub, glb, lattice, topological sort
Hasse diagrams
Specific orderings: product, lexicographic, lenlex
Coming up . . .