Take the 2-minute tour ×
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.

I need help with this problem:

Suppose $\sim$ is a relation on a set $S$ which is both symmetric and transitive. Let $A = \{x∈S\ \vert \text{ for some }y∈S, x\sim y\}$. Prove that $\sim$ is an equivalence relation on $A$.

could anyone assist me with this or send me some place that will help me understand?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

This problem stems from a mistake quite often made by beginners, who ‘prove’ that every symmetric, transitive relation is reflexive and therefore an equivalence relation. They argue as follows:

Let $\sim$ be a symmetric, transitive relation on a set $A$, and let $a\in A$ be arbitrary; I’ll show that $a\sim a$. Let $b$ be any element of $A$ such that $a\sim b$; then by symmetry $b\sim a$, so by transitivity $a\sim a$. Since $a$ was arbitrary, $\sim$ is reflexive.

Unfortunately, the claimed result simply isn’t true. For example, let $A=\{0,1\}$, and let $\sim$ be the relation $\{\langle 0,0\rangle\}$: $0\sim 0$, but $0\not\sim 1$, $1\not\sim 0$, and $1\not\sim 1$. You can easily check that $\sim$ is symmetric and transitive, but it’s obviously not reflexive. (For that matter, $\varnothing$ is a symmetric, transitive relation on any set $A$ whatsoever, but it’s reflexive only when $A=\varnothing$.)

The problem with the argument is that there may not be any $b\in A$ such that $a\sim b$. If there is such a $b$, the rest of the argument is fine, but if there isn’t, it can’t be carried out at all. In your problem this hole in the argument has been filled: instead of trying to prove that $\sim$ is reflexive on all of $A$, which (as we’ve just seen) it may not be, you’re to prove only that it’s reflexive on $S$, the set of points in $A$ that are $\sim$-related to some point of $A$. A fairly simple modification of the highlighted argument above will do the trick.

share|improve this answer
    
Thanks for your time and help. I think I understand it now. –  blutuu Oct 1 '12 at 13:42
add comment

Let $x\in A$. Then choose $y\in S$ so that $x\sim y$. Since the relation is symmetric on $A$, you have $y\sim x$. Apply transitivity to see that $x\sim x$.

share|improve this answer
    
Thanks for the input. This seems to make sense to me. –  blutuu Oct 1 '12 at 13:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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