Math 461 Relations and Orders

7 Binary relations
Definition 7.1. A binary relation on a set A is a subset R ⊆ A×A. We usually write
aRb instead of writing ha, bi ∈ R.

Example 7.2. 1. The order relation on N is given by

{hn, mi | n, m ∈ N, n < m}.

2. The division relation D on Nr{0} is given by

D = {hn, mi | n, m ∈ N, n divides m}.

Observation Thus P(N×N) is the collection of all binary relations on N. Clearly

P(N×N) ∼ P(N) and so P(N×N) is uncountable.

Definition 7.3. Let R be a binary relation on A.

1. R is reflexive iff xRx for all x ∈ A.

2. R is symmetric iff xRy implies yRx for all x, y ∈ A.

3. R is transitive iff xRy and yRz implies xRz for all x, y, z ∈ A.

R is an equivalence relation iff R is reflexive, symmetric, and transitive.

Example 7.4. Define the relation R on Z by

aRb iff 3|a − b.

Proposition 7.5. R is an equivalence relation.

Exercise 7.6. Let A = {ha, bi | a, b ∈ Z, b 6= 0}. Define the relation S on A by

ha, biShc, di iff ad − bc = 0.
Prove that S is an equivalence relation.

Definition 7.7. Let R be an equivalence relation on A. For each x ∈ A, the equivalence

class of x is
[x] = {y ∈ A | xRy}.

Example 7.4 Cont. The distinct equivalence classes are

[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Definition 7.8. Let A be a nonempty set. Then {Bi | i ∈ I} is a partition of A iff the
following conditions hold:

2006/02/06 1
Math 461 Relations and Orders

1. ∅ 6= Bi for all i ∈ I.

2. If i 6= j ∈ I, then Bi ∩ Bj = ∅.
S
3. A = i∈I Bi .

Theorem 7.9. Let R be an equivalence relation on A.

1. If a ∈ A then a ∈ [a].

2. If a, b ∈ A and [a] ∩ [b] 6= ∅, then [a] = [b].

Hence the set of distinct equivalence classes forms a partition of A.

Proof. 1. Let a ∈ A. Since R is reflexive, aRa and so a ∈ [a].

2. Suppose that c ∈ [a] ∩ [b]. Then aRc and bRc. Since R is symmetric, cRb. Since R
is transitive, aRb. We claim that [b] ⊆ [a]. To see this, suppose that d ∈ [b]. Then
bRd. Since aRb and bRd, it follows that aRd. Thus d ∈ [a]. Similarly, [a] ⊆ [b]
and so [a] = [b].

Theorem 7.10. Let {Bi | i ∈ I} be a partition of A. Define a binary relation R on A

by
aRb iff there exists i ∈ I such that a, b ∈ Bi .
Then R is an equivalence relation whose equivalence classes are precisely {B i | i ∈
I}.

Example 7.11. How many equivalence relations can be defined on A = {1, 2, 3}?

Sol’n This is the same as asking how many partitions of A exist.

{{1, 2, 3}},
{{1, 2}, {3}}, {{1, 3}, {2}}, {{2, 3}, {1}},
{{1}, {2}, {3}}
Hence there are 5 equivalence relations on {1, 2, 3}.

Exercise 7.12. How many equivalence relations can be defined on A = {1, 2, 3, 4}?

Challenge Let EQ(N) be the collection of equivalence relations on N. Prove that

EQ(N) ∼ P(N).

2006/02/06 2
Math 461 Relations and Orders

8 Linear orders
Definition 8.1. Let R be a binary relation on A.

1. R is irreflexive iff ha, ai∈R

/ for all a ∈ A.

2. R satisfies the trichotomy property iff for all a, b ∈ A, exactly one of the following
holds:
aRb, a = b, bRa.

hA, Ri is a linear order iff R is irreflexive, transitive, and satisfies the trichotomy prop-
erty.

Example 8.2. Each of the following are linear orders.

1. hN, <i

2. hN, >i

3. hZ, <i

4. hQ, <i

5. hR, <i

Definition 8.3. Let R be a binary relation on A. Then hA, Ri is a partial order iff R
is irreflexive and transitive.

Example 8.4. Each of the follow are partial orders, but not linear orders.

1. Let A be any nonempty set containing at least two elements. Then hP(A), ⊂i is
a partial order.

2. Let D be the divisability relation on N+ = Nr{0}. Then hN+ , Di is a partial

order.

Definition 8.5. Let hA, <i and hB, <i be partial orders. A map f : A → B is an
isomorphism iff the following conditions are satisfied.

1. f is a bijection

2. For all x, y ∈ A, x < y iff f (x) < f (y).

In this case, we say that hA, <i and hB, <i are isomorphic and write hA, <i∼
=hB, <i.
Example 8.6. hZ, <i∼
=hZ, >i

2006/02/06 3
Math 461 Relations and Orders

Proof. Let f : Z → Z be the map defined by f (x) = −x. Clearly f is a bijection. Also,
if x, y ∈ Z, then x < y
iff −x > −y
iff f (x) > f (y).
Thus f is an isomorphism.

Example 8.7. hN, <i6∼

= hZ, <i.
Proof. Suppose that f : N → Z is an isomorphism. Let f (0) = z. Since f is a bijection,
there exists n ∈ N such that f (n) = z − 1. But then n > 0 and f (n) < f (0), which is a
contradiction.

Exercise 8.8. Prove that hZ, <i6∼

= hQ, <i.

Example 8.9. hQ, <i6∼

= hR, <i.

Proof. Since Q is countable and R is uncountable, there does not exist a bijection
f : Q → R. Hence there does not exist an isomorphism f : Q → R.

Example 8.10. hR, <i6∼

= hRr{0}, <i.

Proof. Suppose that f : Rr{0} → R is an isomorphism. For each n ≥ 1, let rn = f (1/n).

Then
r1 > r2 > . . . > rn > . . . > f (−1).
Let s be the greatest lower bound of {rn | n ≥ 1}. Then there exists t ∈ Rr{0}
such that f (t) = s. Clearly t < 0. Hence f (t/2) > s. But then there exists n ≥ 1
such that rn < f (t/2). But this means that t/2 < 1/n and f (t/2) > f (1/n), which is a
contradiction.

Question 8.11. Is hQ, <i∼

=hQr{0}, <i?

Definition 8.12. For each prime p,

Z[1/p] = {a/pn | a ∈ Z, n ∈ N}.

Question 8.13. Is hZ[1/2], <i∼

=hZ[1/3], <i?

Definition 8.14. A linear order hD, <i is a dense linear order without endpoints or
DLO iff the following conditions hold.

1. For all a, b ∈ D, if a < b, then there exists c ∈ D such that a < c < b.

2. For all a ∈ D, there exists b ∈ D such that a < b.

3. For all a ∈ D, there exists b ∈ D such that b < a.

Example 8.15. The following are DLOs.

2006/02/06 4
Math 461 Relations and Orders

1. hQ, <i

2. hR, <i

3. hQr{0}, <i

4. hRr{0}, <i

Theorem 8.16. For each prime p, hZ[1/p], <i is a DLO.

Proof. Clearly hZ[1/p], <i linear order without endpoints. Hence it is enough to show
that Z[1/p] is dense. Suppose that a, b ∈ Z[1/p]. Then there exists c, d ∈ Z and n ∈ N
such that a = c/pn and b = d/pn . Clearly a < a + (1/pn ) ≤ b. Consider
r = pcn + p1n = cp+1
pn+1
∈ Z[1/p].
Then a < r < b.

Theorem 8.17. If hA, <i and hB, <i are countable DLOs then hA, <i∼
=hB, <i.
Corollary 8.18. hQ, <i∼
=hQr{0}, <i.
Corollary 8.19. hZ[1/2], <i∼
=hZ[1/3], <i.
Corollary 8.20. If p is any prime, then hZ[1/p], <i∼
=hQ, <i.
Proof of Theorem 8.17. Let A = {an | n ∈ N} and B = {bn | n ∈ N}. First define
A0 = {a0 } and B0 = {b0 } and let f0 : A0 → B0 be the map defined by f0 (a0 ) = b0 .
Now suppose inductively that we have defined a function fn : An → Bn such that
the following conditions are satisfied.

1. {a0 , . . . , an } ⊆ An ⊆ A.

2. {b0 , . . . , bn } ⊆ Bn ⊆ B.

3. fn : An → Bn is an order preserving bijection.

We now extend fn to a suitable function fn+1 .

Step 1 If an+1 ∈ An , then let A0n = An , Bn0 = Bn , and fn0 = fn . Otherwise, suppose for
example that

c0 < c1 < . . . < ci < an+1 < ci+1 < . . . < cm

where An = {c0 , . . . , cm }. Choose some element b ∈ B such that fn (ci ) < b < fn (ci+1 )
and define
A0n = An ∪ {an+1 }
Bn0 = Bn ∪ {b}
fn0 = fn ∪ {han+1 , bi}

2006/02/06 5
Math 461 Relations and Orders

Step 2 If bn+1 ∈ Bn0 , then let An+1 = A0n , Bn+1 = Bn0 , and fn+1 = fn0 . Otherwise,
suppose for example that

d0 < d1 < . . . < dj < bn+1 < dj+1 < . . . < dt

where Bn0 = {d0 , . . . , dt }. Choose some element a ∈ A such that (fn0 )−1 (dj ) < a <
(fn0 )−1 (dj+1 ) and define
An+1 = A0n ∪ {a}
Bn+1 = Bn0 ∪ {bn+1 }
= fn0 ∪ {ha, bn+1 i}.
fn+1 S
Finally, let f = n≥0 fn . Then f : A → B is an isomorphism.

9 Extensions
Definition 9.1. Suppose that R, S are binary relations on A. Then S extends R iff
R ⊆ R.

Example 9.2. Consider the binary relations R, S on N defined by

R = {hn, mi | n < m}
S = {hn, mi | n ≤ m}
Then S extends R.

Example 9.3. Consider the partial order ≺ on {a, b, c, d, e} which is

{hd, bi, hd, ai, hd, ei, hd, ci, ha, bi, he, bi, hc, bi}.

Then we can extend ≺ to the linear order < defined by the transitive closure of

d < e < c < a < b.

Exercise 9.4. If hA, ≺i is a finite partial order, then we can extend ≺ to a linear
ordering < of A.

Question 9.5. Does the analogous result hold if hA, ≺i is a infinite partial order?

Definition 9.6. If A is a set and n ≥ 1, then

An = {ha1 , . . . , an i | a1 , . . . , an ∈ A}.
An n-ary relation on A is a subset R ⊆ An .
An n-ary operation on A is a function f : An → A.

2006/02/06 6