3
$\begingroup$

I've read about the fundamental theorem of equivalence relations. The idea that an equivalence relation on a set $X$ partitions $X$ is understandable. But the idea that for any partition of $X$ there is an equivalence relation on $X$ is a little weird.

Suppose I partition $\mathbb{N}$ as follows:

$$\{\{\text{primes}>3\},\{\text{even numbers}\},\{1\}\}$$

Then what would be the corresponding equivalence relation?

$\endgroup$
3
  • 3
    $\begingroup$ Note that the set of sets you suggest is not a partition of $\mathbb N$. Edit: Your question is discussed in great detail on Velleman's book. See Theorem 4.6.6 and onwards (second edition). $\endgroup$
    – Git Gud
    Dec 26, 2014 at 0:39
  • $\begingroup$ More specifically, there are naturals which don't fit in any of the sets of your suggested partition (such as 3 and 9). $\endgroup$
    – Dasherman
    Dec 26, 2014 at 0:55
  • $\begingroup$ @GitGud Yes. I forgot the non-prime odd numbers. $\endgroup$
    – Red Banana
    Dec 26, 2014 at 1:08

2 Answers 2

10
$\begingroup$

The equivalence relation would be "belongs to the same set of the partition". Nobody said that it had to be expressed without referring to the partition.

(And where is $9$ in your partition?)

$\endgroup$
3
  • $\begingroup$ Yes. I forgot the non-prime odd numbers. Silly mistake. $\endgroup$
    – Red Banana
    Dec 26, 2014 at 1:13
  • 1
    $\begingroup$ Another thing: I was thinking about equivalence relation in the sense of equality. That's why it didn't make sense, but the equivalence relation could be about anything, right? $\endgroup$
    – Red Banana
    Dec 26, 2014 at 2:01
  • 1
    $\begingroup$ @Vÿska Exactly. Equivalence doesn't mean equality. I could define an equivalence relation on the set of natural numbers, such that "any two numbers are related". $\endgroup$
    – Ypnypn
    Dec 26, 2014 at 3:25
2
$\begingroup$

Let $P$ be a partition of set $S$. Then we can define the relation $R=\{ (a, b)\mid \exists T\in P: a\in T \wedge b\in T\}$. Which is basically the relation "belongs to the same set of the partition" (as said by the other answer). This relation can quite easily be proven to be an equivalence relation.

For some intuitive understanding:

Reflexive: an element $x$ of $S$ does of course belong to the same set of the partition as $x$.

Transitive: if $x$ is in the same set of the partition as $y$ and $y$ is in the same set of the partition as $z$ then $x$ and $z$ belong to the same set of the partition.

Symmetry: if $x$ is in the same set of the partition as $y$, then $y$ is in the same set of the partition as $x$.

You should be able to write a more formal proof on your own.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .