Scribd
Upload
218 views1 page

Relation Examples

The document provides proofs that three different relations are equivalence relations: 1) The relation R on a set A is antisymmetric if and only if R intersect R inverse is a subset of the diagonal relation. 2) The relation R on ordered pairs of positive integers such that ((a,b),(c,d)) is in R if and only if ad=bc. 3) The relation R on functions from positive integers to positive integers such that (f,g) is in R if and only if f is theta of g.

Uploaded by

ShehanWickramarathne
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
218 views1 page

Relation Examples

The document provides proofs that three different relations are equivalence relations: 1) The relation R on a set A is antisymmetric if and only if R intersect R inverse is a subset of the diagonal relation. 2) The relation R on ordered pairs of positive integers such that ((a,b),(c,d)) is in R if and only if ad=bc. 3) The relation R on functions from positive integers to positive integers such that (f,g) is in R if and only if f is theta of g.

Uploaded by

ShehanWickramarathne
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sample Relation Proofs

1. Show that the relation R on a set A is antisymmetric if and only if RR


1
is a subset of the diagonal
relation = {(a, a)|a A}.
Proof: Assume that R is antisymmetric, but R R
1
. Then there are elements a, b A with
a = b such that (a, b) RR
1
. Thus, (a, b) R, and (a, b) R
1
. The latter implies that (b, a) R
by the denition of R
1
. But then we have (a, b) R, and (b, a) R, with a = b, contradicting that
R is antisymmetric. Thus, R R
1
.
Now assume that R R
1
, but R is not antisymmetric. Then there are elements a, b A with
a = b such that (a, b) R and (b, a) R. Then (a, b) R
1
(since (b, a) R), so that (a, b) RR
1
.
Since a = b, this contradicts that R R
1
. Thus, R is antisymmetric.
2. Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) R if and
only if ad = bc. Show that R is an equivalence relation.
Proof: We need to show that R is reexive, symmetric, and transitive.
Reexive: Since ab = ba for all positive integers, ((a, b), (a, b)) R for all (a, b). Thus R is reexive.
Symmetric: Notice that if ad = bc, then cb = da for all positive integers a, b, c, and d. Thus
((a, b), (c, d)) R implies that ((c, d), (a, b)) R, so R is symmetric.
Transitive: Assume that ((a, b), (c, d)) R and ((c, d), (e, f)) R. Then ad = bc and cf = de. Solv-
ing the second for c, we get c = de/f, and plugging it into the rst we get ad = b(de/f). Multiplying
both sides by f, and canceling the d on both sides yields af = be. Thus ((a, b), (e, f)) R. Thus R is
transitive.
3. Let R be the relation on the set of functions from Z
+
to Z
+
such that (f, g) R if and only if f is
(g). Show that R is an equivalence relation.
Proof: We need to show that R is reexive, symmetric, and transitive.
Reexive: Since 1 f(x) f(x) 1 f(x) for all x 1, f = (f), so R is reexive.
Symmetric: If f = (g), then there exists positive constance C
1
, C
2
, and x
0
such that
C
1
g(x) f(x) C
2
g(x) for all x x
0
.
This implies that
g(x)
1
C
1
f(x) and g(x)
1
C
2
f(x) for all x x
0
,
which is equivalent to
1
C
2
f(x) g(x)
1
C
1
f(x) for all x x
0
.
Thus g = (f), and R is symmetric.
Transitive: If f = (g), then there exists positive constance C
1
, C
2
, and x
0
such that
C
1
g(x) f(x) C
2
g(x) for all x x
0
.
Similarly if g = (h), then there exists positive constance C
3
, C
4
, and x
1
such that
C
3
h(x) g(x) C
4
h(x) for all x x
1
.
Then
f(x) C
1
g(x) C
1
(C
3
h(x)) for all x max{x
0
, x
1
},
and
f(x) C
2
g(x) C
2
(C
4
h(x)) for all x max{x
0
, x
1
}
Thus,
C
1
C
3
h(x) f(x) C
2
C
4
h(x) for all x max{x
0
, x
1
}.
and f = (h). Thus R is transitive.
1

You might also like