For each of the relations in parts a, b and c below, answer the following three

Question

For each of the relations in parts a, b and c below, answer the following three questions:

Is the relation reflexive, anti-reflexive, or neither?

Is the relation symmetric, anti-symmetric, or neither?

Is the relation transitive?

If the relation does not have one of the properties, give a counterexample. (Normally this will be an ordered pair that is in the relation when the property forbids it, or isn’t in the relation when the property requires it.)

a) The domain is a set of people; (x, y) is in the relation if person x is taller than person y.

b) The domain is the set of real numbers; (x, y) is in the relation if x - y is a rational number.

c) The domain is A = {a, b, c, d}; the relation is {(a,b), (a, a), (b, b), (b, a), (c, d), (d, c)}.

Explanation / Answer

Let R be a binary relation on A. R is reflexive if for all x A, (x, x) R. R is symmetric if for all x, y A,          (x, y) R implies (y, x) R. R is transitive if for all x, y, z A, (x, y) R and (y, z) R implies (x, z) R. A relation R is anti reflexive if ( x , y) R implies x = y. A relation R is anti symmetric if (x, y) and ( y, x) R implies x = y.

a) If person x is taller than y, then (x, y) R. Since a person cannot be taller than himself, (x , x) does not belong to R. Therefore, R is not reflexive. It is anti- reflexive since x is taller than y implies x y. The relation is not symmetric as ( x, y) R implies x is taller than y so that y cannot be taller than x and hence ( y, x) does not belong to R. The relation R is transitive as ( x, y) R and (y, z) R imply that x is taller than y and y is taller than z so that (x, z) R.

b) (x, y ) R if x – y is a rational number. Since x – x = 0 and since 0 is a rational number, ( x, x) R. Thus R is reflexive. The relation is not anti-reflexive as ( x, y) R implies x –y is a rational number. This does not imply that x y as x – x = 0 is a rational number. The relation is symmetric as ( x, y) R implies that x – y is a rational number which implies that y – x = - (x – y) is a rational number which implies that ( y, x) R. The relation is not anti symmetric as ( x, y) and ( y, x) R implies that ( x – y) and ( y – x) are both rational numbers. It does not imply that x = y. The relation R is transitive as ( x, y) R and (y, z) R imply that x – y and y –z are rational numbers so that x – z = ( x – y) + ( y – z) is also a rational number which implies that ( x, z) R.

c) The relation is not reflexive as ( c, c) and ( d, d) do not belong to R. The relation is not anti reflexive as ( a, a) and ( b, b) R. The relation is symmetric as ( a, b) , (b, a), (c, d), ( d, c) R. The relation is not anti symmetric as ( a, b)and( b, a) R does not imply that a = b. R is not transitive as (c, d) and (d, c) R , but ( c, c) does not R.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.