0
$\begingroup$

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

2 Answers 2

3

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?

  • 0
    @doniyor: My pleasure; you’re welcome!2012-11-16
1

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