Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
Why isn't reflexivity redundant in the definition of equivalence relation?

We had a heated discussion in class today and i still cant be sure if the professor was any good with the solution. The question is:

If a relation is symmetric and transitive, then it will be reflexive too. True/False?

I think it is true. But if someone can give me the counter example!

Source: Exercise 8.46, P195 of Mathematical Proofs, 2nd (not 3rd) ed. by Chartrand et al

share|cite|improve this question

marked as duplicate by Jonas Meyer, t.b., Asaf Karagila, Gerry Myerson, Chris Eagle Jun 1 '12 at 14:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

It is true that for every relation that is symmetric and transitive, there is some set on which it is reflexive. – Michael Hardy Sep 16 '11 at 18:07
up vote 11 down vote accepted

No, it is false. Consider for example the empty relation, i.e. no two elements of a non-empty set are in the relation $R$. Then $R$ is transitive and symmetric, but not reflexive. However, if for every $a$ there is $b$, such that $aRb$, then by symmetry $bRa$ and by transitivity $aRa$. This is the necessary and sufficient condition for a symmetric and transitive relation to be reflexive.

share|cite|improve this answer
also a relation {(1,1)} on set {1,2}, is not reflexive but symmetric and transitive right? – Kraken Sep 16 '11 at 16:23
Right, this does not satisfy the criterion I've stated. There is no element to be in the relation with $2$. I think Theo pointed out this in his comment, but I can't find the comment any more. – Levon Haykazyan Sep 16 '11 at 16:30
@Karan: it is perfectly valid and also appreciated to take such questions to the extreme, like Levon has done in this case. – Alexander Thumm Sep 16 '11 at 16:30
@Levon Haykazyan yeah, it was theo's comment, i guess he deleted it or something, before i could ask him. thanks anyways. – Kraken Sep 16 '11 at 16:32
@Karan: yes, I stated this comment. I found the point made by Levon much better than this comment, so I removed it. Keep in mind that reflexivity is there in particular to ensure that every element is related to something (namely itself). – t.b. Sep 16 '11 at 16:41

One should say, not simply that a relation is reflexive, but that it is reflexive on some particular set. For every relation that is symmetric and transitive, there is some set on which it is reflexive. In one case, that is the empty set.

Later note: I see that some people don't like this answer very much, so I'll add something to it and see if they like it better.

Apparently someone was responding to the sentence that says "In one case, that is the empty set" by saying every relation is reflexive on the empty set. But in fact it is the restriction of the relation to the empty set that is reflexive on the empty set. If you speak of a relation as a whole rather than of its restriction to some set, then there is only one set on which it is reflexive.

"ccc" says "every relation is reflexive on some set", and that is true, and adds "so this is quite tautological as stated". Just how that is an objection to what I said escapes me.

If a relation $R$ is symmetric and transitive, then it follows that it is reflexive on the set $\{x : \exists y\ \ xRy \}$ or on $\{x: \exists y\ \ yRx\}$. It is not reflexive on any smaller set---rather its restriction to that smaller set is reflexive on that smaller set. Nor is it reflexive on any larger set.

So after it has been stated that a relation is symmetric and transitive, it follows that there is just one set on which it is reflexive and therefore just one set on which it is an equivalence relation.

The only reason "reflexive" gets added to "symmetric" and "transitive" is this: One wants to specify some particular set on which the relation is reflexive.

Someone said the relation $R=\{(1,1)\}$ on the set $\{1,2\}$ is not reflexive. But the relation $R=\{(1,1)\}$ is not "on the set ${1,2}$" unless one adds that to the definition of relation; i.e. the set $\{x : \exists y\ \ xRy\}$ is not $\{1,2\}$. I think that proposition should be phrased thus: The relation $\{(1,1)\}$ is not reflexive on the set $\{1,2\}$.

share|cite|improve this answer
But of course every relation is reflexive on some set, so this is quite tautological as stated. – user83827 Sep 16 '11 at 19:04
But that's not as interesting as the fact that every relation that's symmetric and transitive is an equivalence relation on some set. Reflexiveness needs to be mentioned only when you're talking about which set that is. – Michael Hardy Sep 16 '11 at 22:20
Now I see your point and it makes a perfect sense. However you should probably explicitly specify that by a relation you mean a set of ordered pairs (without specifying a domain or a codomain). I don't think it is a common practice to identify relations with different domains or different codomains. – Levon Haykazyan Sep 17 '11 at 6:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.