Prove equivalence relation

**oldguynewstudent** · June 23rd 2010, 09:26 AM

Please critique the following proof and also let me know if I have defined the equivalence classes correctly.

Let $f:A\longrightarrow B$ . Define a relation $\equiv$ on A by $a_{1}\equiv a_{2}$ iff $f(a_{1})=f(a_{2})$ . Give a quick proof that this is an equivalence relation. What are the equivalence classes? Explain intuitively.

Proof: Test reflexive for $\equiv$ . If $a\in A$ then $(a,a)\in A$ : Given f is a funcion then $f(a_{1})=f(a_{1})$ implies $a_{1}\equiv a_{1}$ because two different values in the domain cannot be mapped to the same value in the range. Therefore $(a_{1},a_{1})\in A$ .

Test symmetric: Let $a_{1}\equiv a_{2}$ where $(a_{1},a_{2})\in A$ . Then we know $f(a_{1})=f(a_{2})$ . But because = is symmetric we know $f(a_{2})=f(a_{1})$ and since $\equiv$ is defined with iff, we know $a_{2}\equiv a_{1}$ which implies $(a_{2},a_{1})\in A$ .

Test transitive: Let $a_{1}\equiv a_{2}$ and $a_{2}\equiv a_{3}$ where $(a_{1},a_{2})(a_{2},a_{3})\in A$ . Then we know $f(a_{1})=f(a_{2})$ and $f(a_{2})=f(a_{3})$ . Because = is transitive we know $f(a_{1})=f(a_{3})$ , but because $\equiv$ is defined with iff, we can conclude that $a_{1}\equiv a_{3}$ . So $(a_{1},a_{3})\in A$ .QED

The equivalence classes in A would be the sets $\{(a_{i},a_{j})\in A$ such that $a_{i}=a_{j})$ .

**Ackbeet** · June 23rd 2010, 09:38 AM

I agree with everything except your intuitive characterization of the equivalence classes.

**MoeBlee** · June 23rd 2010, 09:53 AM

Originally Posted by oldguynewstudent

Proof: Test reflexive for $\equiv$ . If $a\in A$ then $(a,a)\in A$

I think you mean ' $\equiv$ ' , not 'A', as the last symbol there? I.e., this is what we want to prove.

Originally Posted by oldguynewstudent

Given f is a funcion then $f(a_{1})=f(a_{1})$ implies $a_{1}\equiv a_{1}$ because two different values in the domain cannot be mapped to the same value in the range.

No, that is backwards (as well as, though it is irrelevant to the actual proof, you can't assume f is an injection as you have).

All you need to say is that if a=a then f(a)=f(a) so a $\equiv$ a.

Your symmetry and transitivity arguments looked okay, as I glanced over them.

Originally Posted by oldguynewstudent

The equivalence classes in A would be the sets $\{(a_{i},a_{j})\in A$ such that $a_{i}=a_{j})$ .

Wrong. The equivalence classes are not sets of ordered pairs of members of A. Rather, the equivalence classes are certain subsets of A.

E is an equivalence class (per $\equiv$ ) iff there exists an a in A such that E = {x | x $\equiv$ a}.

I.e., E is an equivalence class (per $\equiv$ ) iff there exists an a in A such that E = {x | f(x)=f(a)}.

I.e., the equivalence classes (per $\equiv$ ) are the non-empty (assuming A is nonempty) sets each made up of, for some given a in A, all and only those members of A that map, under the function f, to f(a).

**oldguynewstudent** · June 23rd 2010, 10:16 AM

Yes, thank you very very much. I have trouble with proofs and have requested a meeting with my professor. The professor I had for Discrete knew his stuff but didn't know how to impart that knowledge very well. This professor for Combinatorics has been great so far. This is a great help. Thanks again!

**MoeBlee** · June 23rd 2010, 10:25 AM

In my view, very likely you're not at fault, but rather standard curricula are at fault. In my view, it should be standard for math (and science, and social sciences, and even history and other humanities) students to take a course that teaches them how to work in the predicate calculus (both strictly symbolically and intuitively). Then, for math students, before even calculus, about the first half of a set theory course (through the basics, basic axiom of choice and Zorn's lemma, the naturals, and construction of the reals as a complete ordered field; but don't need the second half that gets into more about transfinite cardinalities, etc.).

Thread: Prove equivalence relation

LinkBack

Thread Tools

Display

Prove equivalence relation

Similar Math Help Forum Discussions

For the following relation, show that R is an equivalence relation and determine the.

Prove or disprove equivalence relation of union and intersection

equivalence relation and equivalence classes

Equivalence relation and order of each equivalence class

Equivalence relation and Equivalence classes?

Search Tags