Question

Give an example of a relation on a set that is both symmetric and transitive but not reflexive.Explain what is wrong with the following ‘proof’:Statement:If R is symmetric and transitive, then R is reflexive."Proof":Suppose R is symmetric and transitive. Symmetric means that x R y implies y R x. We apply transitivity to x R y and y R x to give x R x. Therefore,R is reflexive

Answer 1

Explanation:

For a counter example, consider the set X ={ 4,7,8} and define R as {(4,4),(4,8), (8,4), (8,8)}

For this R, we can check that if (x,y) is in R, then (y,x) is in R. Hence it is symmetric. Also if (x,y), (y,z) in R then (x,z) is in R. Thus it is transitive. But since (7,7) is not in R, this relation fails to be reflexive.

The main problem with the "proof" is assuming that every pair (x,y) where x,y are elements in X are also part of R. It could happen that they might be combinations of x,y such that (x,y) are not in R.