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 am given to prove this proposition on equivalence classes.

Each element of $A$ is an element of one and only one equivalent class.

The part that is confusing is one and only one. It sounds like an existential statement, the existence of an equivalence class and that that equivalence class is unique. How should one understand this proposition in "common" logic terms, namely "for every", "there exists", if..then,...?

So far here is my understanding, or say 'translation' of the proposition:

There exists a unique equivalence class such that each element of $A$ belongs to that equivalence class.

This understanding is doubtful, at least for me, because it implies that all elements of $A$ belong to one equivalence class, which is wrong.

I am not looking for a proof, just an understanding of the proposition. Thanks!

share|improve this question
    
I'm confused by the downvote to this question. –  Asaf Karagila Feb 17 '13 at 23:26
3  
Do you think "Each boy is a member of one and only one football team" means the same as "There exists a unique football team such that each boy is a member of that team"??? –  Peter Smith Feb 17 '13 at 23:27
    
@PeterSmith Good point! I'm still looking at answers bellow for more enlightenment. –  nt.bas Feb 17 '13 at 23:32

3 Answers 3

up vote 4 down vote accepted

If $E$ is an equivalence relation on $A$ then for every $a\in A$ there exists an equivalence class $B$ such that $a\in B$, and for every equivalence class $C$, $a\in C$ implies $C=B$.

So there exists such equivalence class, and it is unique.

Note, however, that $\forall a\exists B\ldots$ is not the same as $\exists B\forall a\ldots$. The former is what I wrote above, and the latter is the statement that all the elements are in the same equivalence class.

share|improve this answer
3  
No, OP has the quantifiers in the wrong order. It's not "There exists a unique equivalence class such that each element of A belongs to that equivalence class"; it's "For each element of A, there exists a unique equivalence class such that the element belongs to that equivalence class", and this is exactly the source of their confusion. –  MJD Feb 17 '13 at 23:26
    
@MJD: Oh, sorry. I misread the question. Anyway I've corrected my answer now. –  Asaf Karagila Feb 17 '13 at 23:27
    
@AsafKaragila Thanks! But i assume $a \in A$ is the element "generating" the equivalent class $B$. Is that right? p.s. by "generating" i mean: $B = \{x \in A: a \sim x\}$ where $\sim$ is the equivalence relation. –  nt.bas Feb 17 '13 at 23:48
    
@nt.bas: Because there is a unique such $B$ the relation $\{\langle a,B\rangle\mid a\in B, B\text{ an equivalence class}\}$ is a function and we can say that $a$ "generates" it. –  Asaf Karagila Feb 17 '13 at 23:50
    
@AsafKaragila thanks for the info on functions but i was asking about $a \in A$. I mean i don't understand if one has to prove the proposition with respect to $a$ or $x$. More clearly, is it: "For every $a \in A$, there exists one unique equivalence class B such that $a \in B$" OR "For every $x \in A$, there exists one unique equivalence class B such that $x \in B$". Understood that $B \subset A$. I don't understand the relationship between $a \in A$ and $x \in B$. –  nt.bas Feb 18 '13 at 0:17

There exists a unique equivalence class such that each element of A belongs to that equivalence class.

This understanding is doubtful, at least for me, because it implies that all elements of A belong to one equivalence class, which is wrong.

You are right to be doubtful, because your translation is wrong. You are being asked to prove that for each element $a$ in $A$, the element $a$ belongs to exactly one equivalence class. But your translation, as you observed, says there is one equivalence class to which every element of $a$ belongs.

This subtle difference catches many beginning mathematics students. But the order of the quantifiers ("there exists" and "for each") is important. For example, it is true that for each number $x$, there is exactly one number $y$ that is the square of $x$. But it is completely false that there is exactly one number $y$ which, for each number $x$, is the square of $x$.

It is correct to say that a number $x$ has one and only one square. But we don't mean by this that every number has the same square! And similarly when we say that an element of $A$ is in "one and only one" equivalence class, we don't mean that every element is in the same class. We just mean that each element is in one class, not zero, and not more than one.

share|improve this answer
    
Thanks! actually i'm not a math student but a biotech one so confusions like these are kind of expected. –  nt.bas Feb 18 '13 at 0:20
    
@nt.bas If you're studying math, that makes you a math student. –  MJD Feb 18 '13 at 0:53
    
I guess it does. Thanks for the explanation by the way! –  nt.bas Feb 18 '13 at 1:09

You are asked to show that any given element $x\in A$ belongs to precisely one equivalence class. Thus, that for that given element $x\in A$ there exists an equivalence class $E$ such that $x\in E$ and that if $F$ is any other equivalence class with $x\in F$ then $E=F$. Of course for any other element $y$ its unique equivalence class might be different than $E$.

share|improve this answer
    
Thanks! I was more confused about the order of quantifiers. –  nt.bas Feb 18 '13 at 1:12

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.