Re: relations

Posted by Amit Goyal on Apr 05, 2013; 4:39pm
URL: http://discussion-forum.276.s1.nabble.com/relations-tp7579963p7579968.html

Let A be a set, and let R be a relation on A. Define the relation R'
on A by R' = (A x A) - R.
(1) If R reflexive, is R' necessarily reflexive, necessarily not
reflexive or  not necessarily either?
Ans. R' is necessarily not reflexive.
Proof:
Let A be a non empty set. Let R be a reflexive relation on A. Consider
any x ∈ A. Since R is reflexive, (x, x) ∈ R. And R' = (A x A) - R
implies (x, x) ∉ R'. Hence R' is necessarily not reflexive.

(2) If R symmetric, is R' necessarily symmetric, necessarily not
symmetric or not necessarily either?
Ans. R' is necessarily symmetric.
Proof:
Let A be a non empty set. Let R be a symmetric relation on A. Let (x,
y) ∈  R'. We want to show that (y, x) ∈  R'.
(x, y) ∈  R' implies that  (x, y) ∉  R. Clearly, (y, x) ∉  R because
if (y, x) ∈  R then, by symmetry of R, we get (x, y) ∈  R which is a
contradiction. Hence, (y, x) ∉  R. Thus, (y, x) ∈  R'.

(3) If R transitive, is R' necessarily transitive, necessarily not
transitive or not necessarily either?
Ans. R' is not necessarily either.
Proof:
Proof of R' is not necessarily transitive: A = {x, y, z}, R = {(x,
y)}
Clearly in this example, R is transitive but R' is not. Since, (x, z)
∈  R' and (z, y) ∈  R' but (x, y) ∉  R'.
Proof of R' is not necessarily not transitive:: A = {x, y}, R ={(x,
x), (x, y)}, R' ={(y, y), (y, x)}
Clearly in this example both R and R' are transitive.