Homework Problem Set 5 MATH 8

Homework Problem Set 5
MATH 8
Problem 1: Prove the general Triangle Inequality for any n 2 N and for any real numbers
a1; a2; : : : ; an 2 R:
Xn
i=1
ai


Xn
i=1
jaij
Problem 2: For each of the following relations on the given sets, prove or give a counterex-
ample for whether the relation is reexive, symmetric, or transitive, i.e., determine which of
these properties the given relation has:
 On the set R, we dene the relation a by x a y , jx ?? yj < 5.
 For a xed set X, we dene the relation b on the power set P(X) by A b B ,
AB = (A [ B) n (A \ B).
 For a nonempty xed set X, we dene the relation c on the power set P(X) by
A c B , A \ B 6= ;.
 Dene the relation d on the set R2 by (x1; y1) d (x2; y2) , x1 + y1 < x2 + y2.
 Dene the relation e on the set R  [0; 1] by (x1; y1) e (x2; y2) , [x1 = x2 and
y1 = 1 and y2 = 0].
Problem 3: For each of the relations, prove whether or not it is an equivalance relation,
and if it is, describe the equivalence classes:
 Dene the relation a on the set R2 by (x1; y1) a (x2; y2) , x1 + x2 = y1 + y2.
 Dene the relation b on the set R2 by (x1; y1) b (x2; y2) , x21
+ x22
= y2
1 + y2
2.
 Dene c on N by a c b , a j b (where the bar signies divides”).
 Fix some m 2 N and let d be the relation on Z dened by a d b , m j (b ?? a).
 Dene e on P(N) by X e Y , 1 2 (X \ Y ).
1
Problem 4: Prove that for any two relations R; S  A  B:
 (R [ S)??1 = R??1 [ S??1
 (R \ S)??1 = R??1 \ S??1
Problem 5: Let A and B be nite sets A = fa1; : : : ; ang and B = fb1; : : : ; bmg, n;m 2 N.
For every relation R  A  B construct its relation matrix TR 2 M(n;m; fT; Fg) (here
M(n;m; fT; Fg) stands for the set of all n m matrices with entries being proposition that
are either true T or false F) whose elements are the propositions
TR(i; j) = aiRbj ; 8i = 1; : : : ; n; 8j = 1; : : : ; m:
Dene addition and multiplication of relation matrices by logical operations _ and ^, re-
spectively (as matrices over the ring of propositions). For instance, for two 2  2 relation
matrices we would have

P(1;1) P(1;2)
P(2;1) P(2;2)

+

Q(1;1) Q(1;2)
Q(2;1) Q(2;2)

=

P(1;1) _ Q(1;1) P(1;2) _ Q(1;2)
P(2;1) _ Q(2;1) P(2;2) _ Q(2;2)


P(1;1) P(1;2)
P(2;1) P(2;2)



Q(1;1) Q(1;2)
Q(2;1) Q(2;2)

=

(P(1;1) ^ Q(1;1)) _ (P(1;2) ^ Q(2;1)) (P(1;1) ^ Q(1;2)) _ (P(1;2) ^ Q(2;2))
(P(2;1) ^ Q(1;1)) _ (P(2;2) ^ Q(2;1)) (P(2;1) ^ Q(1;2)) _ (P(2;2) ^ Q(2;2))

:
5.a
 If TR is the relation matrix of the relation R, what is the relation matrix of R??1?
 If TR and TS are relation matrices of relations R  A  B and S  B  C, what is
the relation matrix of the composition relation S  R?
5.b Express the following properties of a relation R  A  A by means of algebraic prop-
erties of its relation matrix TR and give a rigorous justication:
 That R is reexive
 That R is irreexive
 That R is symmetric
 That R is antisymmetric
 That R is transitive
 That R has the comparable property
2
6: Let M(2) be the set of all 2  2 matrices with real entries. A matrix A 2 M(2) is
called positive, A  0, if 8(x; y) 2 R2 we have (x; y)  A  (x; y)>  0. Dene the relation
 M(2) M(2) by
A  B , B ?? A  0; 8A;B 2 M(2):
 Is  a partial order on the set of all 2  2 matrices M(2)?
 Is  a strict partial order?
 Does (M(2);) have upper and lower bounds?
 Does the set of all positive 2  2 matrices have upper and lower bounds with respect
to ? Does it have a least or greatest elements?
 Is  a linear order on M(2)?
3