2
$\begingroup$

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?

2 Answers 2

1

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.

  • 0
    Th$a$nks for your time and help. I think I understand it now.2012-10-01
1

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$.

  • 0
    Thanks for the input. This seems to make sense to me.2012-10-01