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
    thanks but how do i include the total order in the proof,2012-11-16
  • 0
    @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\}$.2012-11-16
  • 0
    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 :(2012-11-16
  • 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.2012-11-16
  • 0
    perfect! Great Help! thanks a lot2012-11-16
  • 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)$.