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 stumbling again in proving things in maths. the task is to prove that this statement

$A \sim B : \Longleftrightarrow \sum_{a\in A} a = \sum_{b\in B} b $

is an Equivalence Relation on Power Set of {0,1,2} with total order $\leq$.

my start is this:

a) Reflexiv: $A \sim A \Longrightarrow \sum_{a\in A} a = \sum_{a\in A} a$ this is OK
b) Symmetric:.. how do i do this, how can i use the notion of total order here?
i am really stuck, :( i also need to show the equivalence classes here

thanks a lot for help in advance

share|improve this question

2 Answers 2

up vote 3 down vote accepted

To show that $\sim$ is symmetric you must show that if $A\sim B$, then $B\sim A$. But this is easy, because equality is symmetric: if $A\sim B$, then by definition $\sum_{a\in A}a=\sum_{b\in B}b$, so $\sum_{b\in B}b=\sum_{a\in A}a$, and therefore $B\sim A$, again by the definition of $\sim$.

Transitivity of $\sim$ follows similarly from transitivity of equality. Assume that $A\sim B$ and $B\sim C$. Then by the definition of $\sim$ we know that $\sum_{a\in A}a=\sum_{b\in B}b$ and $\sum_{b\in B}b=\sum_{c\in C}c$; can you now put the pieces together to conclude that $A\sim C$?

You’ll have one equivalence class for each possible sum of a subset of $\{0,1,2\}$. There are only eight subsets, so you can simply make a list:

$$\begin{array}{rcc} \text{Subset}:&\varnothing&\{0\}&\{1\}&\{2\}&\{0,1\}&\{0,2\}&\{1,2\}&\{0,1,2\}\\ \text{Sum}:&0&0&1&2&1&2&3&3 \end{array}$$

Now which subsets have the same sums and therefore belong to the same equivalence class?

share|improve this answer
    
thanks but how do i include the total order in the proof, –  doniyor Nov 16 '12 at 21:40
    
@doniyor: It doesn’t actually enter into the argument in any way: the equivalence relation $\sim$ is completely independent of the order $\le$ on $\{0,1,2\}$. –  Brian M. Scott Nov 16 '12 at 21:43
    
oh okay, thanks. but can you please explain me again how you came to know the equivalence classes? i cannot find the way to come to this intuitivly :( –  doniyor Nov 16 '12 at 21:46
1  
@doniyor: $A\sim B$ means that $\sum_{a\in A}a=\sum_{b\in B}b$: the subsets $A$ and $B$ have the same sum. Two subsets of $\{0,1,2\}$ are $\sim$-related if and only if they have the same sum. By definition of equivalence class two subsets of $\{0,1,2\}$ are in the same equivalence class if and only if they’re $\sim$-related. Put the two together: $A$ and $B$ are in the same equiv. class if and only if they have the same sum. Thus, there must be one equiv. class for each of the four possible sums, and as you can see from the table, each equiv. class has exactly two members. –  Brian M. Scott Nov 16 '12 at 21:52
    
perfect! Great Help! thanks a lot –  doniyor Nov 16 '12 at 21:57

Note that mapping a set $S\subset \{0,1,2\}$ to its element sum $\sum_{x\in S} x$ is a function $f$ (to be presice: a function from the power set of $\{0,1,2\}$ to e.g. the reals, but these details don't evenmatter). Note that any relation of the from $$A\sim B:\iff f(A)=f(B)$$ is an equivalence relation, by the very properties of the role-model of equivalence: equality

  • $A\sim A$ because $f(A)=f(A)$.
  • $A\sim B$ implies $B\sim A$ because $f(A)=f(B)$ is just the same as $f(B)=f(A)$.
  • If $A\sim B$ and $B\sim C$ then $A\sim C$ because if $f(A)=f(B)=f(C)$, then $f(A)=f(C)$.
share|improve this answer
    
great! Thank you –  doniyor Nov 17 '12 at 4:56

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.