1
$\begingroup$

I'm currently learning about equivalence relations. I understand that an equivalence relation is a relation that is reflexive, symmetric, and transitive. But I'm having trouble proving the transitive property.

For example:

Suppose we have the relation ~ on the set of all functions from $\mathbb{R}$ to $\mathbb{R}$ by the rule f~g iff there is a $k \in \mathbb{R}$ such that $f(x) = g(x)$ for every $x \geq k$ is an equivalence relation.

$$$$ To prove that it is reflexive I said:

Suppose we have a real number k such that for every $x$, $x \geq k$. Then we can choose any k and f(x) = f(x) for all x. So f~f. Thus the relation is reflexive.

^It seems a little short.. and trivial so I'm wondering if this part is even right. $$$$ To prove that it is symmetric I said:

Suppose we have two functions such that f(x) = g(x). Then we can similarly say that g(x) = f(x). So it follows that f~g and g~f. Therefore the relation is symmetric

^Again, I'm a little confused about this. It feels too short.

$$$$ Now I'm having trouble proving the transitive property.

Could someone look over my proofs for the reflexive and symmetric properties of the relation and give me a hint on how to approach the transitive property?

$\endgroup$
3
$\begingroup$

In the argument for symmetry, you've shown that if $f = g$ then $f \sim g$ and $g \sim f$. But this does not guarantee symmetry, which requires that if $f \sim g$ then $g \sim f$. To do this, $f \sim g$ shows that there is a constant $k$ such that $f(x) = g(x)$ for all $x \geq k$, and you need to show that there is a constant $l$ such that $g(x) = f(x)$ for all $x \geq l$.

For transitivity, you must show that if $f \sim g$ and $g \sim h$ then $f \sim h$. In your case, this means there are constants $k$ such that $f(x) = g(x)$ for $x \geq k$ and $l$ such that $g(x) = h(x)$ for $x \geq l$, and you need to show that there is a constant $m$ such that $f(x) = h(x)$ for all $x \geq m$. How might you produce such an $m$ in terms of the other data you have available?

$\endgroup$
  • $\begingroup$ So was my reflexive proof ok? As for symmetry, should I be saying something like: Suppose f~g, then we can say that f(x) = g(x) for some $x \geq k$ but this is also equivalent to saying g(x) = f(x), so g~f. For the transitivity part can we consider k > l? Then we know that x is also greater than l, so f(x) = h(x)? $\endgroup$ – Pandamonium Oct 11 '14 at 2:40
  • $\begingroup$ Yes, it looks good to me. In a proof that a relation is an equivalence relation, reflexivity and symmetry tend to be relatively easy, and may feel almost tautological, whereas transitivity is often (but not always) somewhat more involved. $\endgroup$ – Travis Oct 11 '14 at 2:43
  • $\begingroup$ So for symmetry can we just consider k = l? Also, for transitivity, I didn't really produce an m. I just considered k > l. Is this sufficient for proving transitivity? $\endgroup$ – Pandamonium Oct 11 '14 at 2:48
  • $\begingroup$ For symmetry, that's right---in this case the equivalence relation is defined in terms of equality, which is itself symmetric, so there's not much to prove. For transitivity, you must show there is some $m$ that satisfies the condition. This doesn't mean you have to produce such an $m$, but doing so is often the easiest way of doing this. I think you have the right idea, but you need to be careful about wording. A priori, you just know there are $k$ and $l$ that satisfy the criteria, and you need to make some comment about why you can assume, e.g., that $k > l$. $\endgroup$ – Travis Oct 11 '14 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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