Partitions and equivalence relations

[simo1]

i don't have a specific question. i just need an explanation on what this topic is about. i am not understanding it

 

[Deveno]

A partition of a set is a division of that set into disjoint non-empty subsets. For example, if our set is:

$S = \{a,b,c\}$ then possible partitions are:

$\{\{a,b,c\}\}$

$\{\{a,b\},\{c\}\}$

$\{\{a,c\},\{b\}\}$

$\{\{b,c\},\{a\}\}$

$\{\{a\},\{b\},\{c\}\}$

These are important because EVERY equivalence relation on a set partitions that set. If we define:

$[a] = \{x \in S: a \sim x\}$, then for any $b \in S$, either $a \sim b$, in which case $b \in [a]$, so that $[a] = $ (this follows from TRANSITIVITY and SYMMETRY of an equivalence relation when $a \neq b$, and from REFLEXIVENESS when $a = b$), or else $b$ is NOT related to $a$, in which case $[a] \cap = \emptyset$ (this is the "disjointness" condition).

Here is the "standard example":

On the set of integers, we say $a$ and $b$ are "congruent modulo 2" if:

$a - b$ is even (a multiple of 2). It is standard to see this is a bona fide equivalence relation:

$a \sim a$ for any integer $a$, since a - a = 0 is even (0 = 2*0).

If $a \sim b$, that is: $a - b = 2k$, then $b - a = -2k = 2(-k)$, so $b - a$ is also even, and so: $b \sim a$.

Finally, if $a \sim b$ and $b \sim c$, we have:

$a - b = 2k$
$b - c = 2m$ so that:

$a - c = a + (-b + b) - c = (a - b) + (b - c) = 2k + 2m = 2(k+m)$, which is also even.

The equivalence class of 0, [0], is called the set of even integers, and the equivalence class of 1, [1], is called the odd integers. This indeed is a partition of the integers since:

$[0] \cup [1] = \Bbb Z$
$[0] \cap [1] = \emptyset$.

One common way equivalence relations show up is with FUNCTIONS. For ANY function:

$f:A \to B$, we can define an equivalence relation on $A$ by:

$x \sim a \iff f(x) = f(a)$.

For example, if $A = B = \Bbb R$, and $f(x) = x^2$, the equivalence class of a real number x is: $[x] = \{x,-x\}$, unless $x = 0$, where we have: $[0] =\{0\}$. Here we get a separate equivalence class for EACH non-negative real number.

This equivalence relation is often denoted $A/f$.

We can create a NEW function:

$\tilde{f}:A/f \to B$ by defining: $\tilde{f}([a]) = f(a)$. This new function has the same RANGE as $f$, but the domain set is "smaller" (since we lumped all the domain elements that map to $f(a)$ in with $a$, for each $a \in A$).

Equivalence can be thought of as an abstraction of "equality", where we require things to merely share some property instead of being exactly equal. Requiring that this shared property is reflexive, symmetric and transitive let's us use our intuition about equality, to reason about things that are merely "similar".

We use equivalences everyday: for example-

4 quarters = 1 dollar.

Obviously, 4 quarters are "different things" than a dollar bill, but both have the same purchasing power. In financial transactions, the actual denominations of the currency used typically does not matter, what matters is the VALUE of that currency: I can pay for a $10 purchase with:

1 10 dollar bill
2 5 dollar bills
1 5 dollar bill and 5 1 dollar bills
10 1 dollar bills
40 quarters, and so on.