Algebra Chapter 0, exercise 1.3

Question

My question concerns the answer to exercise 1.3:

Given a partition $P$ on a set $S$, show how to define a relation $\sim$ on $S$ such that $P$ is the corresponding partition.

My answer is:

We can define the relation $\sim$ such that $P$ is the corresponding partition as let $X \in P$, if $a \in X$ and $b \in X$ then $a \sim b$.

Is that enough?

I found this online, but they show $P = P_\sim$. Is that necessary?

Define, for $a,b\in S$, $a\sim b$ if and only if there exists an $X\in\mathscr{P}$ such that $a\in X$ and $b\in X$. We will show that $\mathscr{P} = \mathscr{P}_{\sim}$.

• ($\mathscr{P}\subseteq\mathscr{P}_{\sim}$). Let $X\in \mathscr{P}$; we want to show that $X\in\mathscr{P}_{\sim}$. We know that $X$ is nonempty, so choose $a\in X$ and consider $[a]_{\sim}\in\mathscr{P}_{\sim}$. We need to show that $X=[a]_{\sim}$. Suppose $a'\in X$ (it may be that $a'=a$.) Since $a,a'\in X$, $a\sim a'$, so $a'\in[a]_{\sim}$. Now, suppose $a'\in > [a]_{\sim}$. We have $a'\sim a$, so $a'\in X$. Hence $X=[a]_{\sim}\in > \mathscr{P}_{\sim}$, so $\mathscr{P}\subseteq\mathscr{P}_{\sim}$.

• ($\mathscr{P}_{\sim}\subseteq\mathscr{P}$). Let $[a]_{\sim}\in\mathscr{P}_{\sim}$. From exercise I.1.1 we know that $[a]_{\sim}$ is non-empty. Suppose $a'\in[a]_{\sim}$. By definition, since $a'\sim a$, there exists a set $X$ such that $a,a'\in X$. Hence $[a]_{\sim}\subseteq X$. Also, if $a,a'\in X$ (not necessarily distinct) then $a\sim a'$. Therefore, $\mathscr{P}_{\sim}\subseteq\mathscr{P}$, and with 1. we get that the sets $\mathscr{P}$ and $\mathscr{P}_{\sim}$ are equal.

Answer 1

What you found online is just saying an easy thing in an overly complicated manner.

Given a partition $P$, the relation you are looking for is just: $a$ is equivalent to $b$ iff there exists some set in the partition such that both $a$ and $b$ belong to it.

Now the proof that this is actually the relation you are looking for goes this way:

Given an element $a$, it must belong to some set in the partition, call it $X_a$. Then, if $b$ is equivalent to $a$, it must belong to $X_a$. Conversely, every element in $X_a$ is equivalent to $a$. To conclude, you can observe that every set in the partition is non empty, by def of partition. So you have that each set in the partition is exactly the equivalence class of some element, and that each equivalence class belongs to the partition

Answer 2

Your answer is correct, it's the correct partition, but you do need to prove that the partition arising from the equivalence relation is exactly equal to the given partition.

It may seem obvious, but the point of the exercise is to familiarize yourself with the partition-relation correspondence. So you need to make sure they have exactly the same equivalence classes, (i.e. there's an $X$ for every $[a]_\sim$ and an $[a]_\sim$ for every $X$)