Question

(a) Explain what is wrong with the following ‘proof’:Statement:IfRis symmetric and transitive, thenRis reflexive."Proof":SupposeRis symmetric and transitive. Symmetric means thatx R yimpliesy R x. We apply transitivity tox R yandy R xto givex R x. Therefore,Ris reflexive.(b) Give an example of a relation on a set that is both symmetric and tran-sitive, but not reflexive

Answer 1

Explanation:

Recall that, in this case, the subset of X for which R is defined is called the domain of R. The mistake occurs when we assume that the domain R is the whole set X, but it could happen that R is not defined for some elements of X.

Recall the following example:

X = {2,4,6}.

We can define R as follows {(2,2), (4,4), (2,4), (4,2)}. We can easily check that this is a transitive and symmetric relation, but since we don't have the element (6,6) it fails to be reflexive.