# Is it enough to point the definitions given in the book for proving this relation?

I'm reading Allufi's Algebra, CHAPTER 0:

Prove that if $\sim$ is a relation on a set $S$, then the corresponding family $P_{\sim}$ is indeed a partition of $S$: That is, it's elements are nonempty, disjoint and their union is $S$.

I can't understand how to provide a proof on this, I thought I could only provide the definitions given in the book:

A relation on a set $S$ is simply a subset $R$ of the product $S \times S$. If $(a,b)\in R$ we say that $a$ and $b$ are related by $R$ and we write $a R b$.

And:

A partition of $S$ is a family of disjoint, nonempty subsets of $S$ whose union is $S$.

If the relation is defined that way, I guess these definitions are the proof. Is there semething wrong? Is this the real proof or do I need to express it in a more formal way?

Also, I felt something wrong when answering the question: He asks me to prove something about a set $S$, but I kinda feel in a lack of warranty on the content of this set, it isn't specified anywhere, I mean, it could be an empty set, couldn't it? I also read somewhere that the author wants me to use the axiom of choice for this, does it have something to do with this lack of warranty?

-
What is the definition of $P_\sim$ (given in the text)? – Arthur Fischer Feb 24 '13 at 6:18
Isn't $P_\sim$ an equivalence relation, maybe? There is a one to one correspondence between the set $R$ of equivalence relations on a set $S$ and the set $P$ of partitions of $S$. – Pedro Tamaroff Feb 24 '13 at 6:22
I'm not sure if this is the answer, but here says: "the quotient of the set $S$, with respect to the equivalence relation $\sim$ if the set $S/ \sim := P_{\sim}$ of equivalence classes of elements of $S$ with respect to $\sim$. – Voyska Feb 24 '13 at 6:26
Gustavo: I notice you haven't accepted any answers to your more recent questions; have you been unhappy with the answers? You can always edit a question, or comment below answers, if you'd like more clarification, or if the answers do not address some lurking doubt/question. – amWhy Mar 4 '13 at 14:53

The actual exercise should say:

Let $\sim$ be an equivalence relation on $S$, and let $P_\sim$ the collection of equivalence classes of $\sim$. Then $P_\sim$ is a partition of $S$.

If you look closely, the exercise is referred from the actual text and the text which refers to it seems to be implicitly suggesting that $\sim$ is an equivalence relation. (I don't consider this good writing, but that what it seems to me.) As Martin points out in the comment below, this is actually corrected in the errata. The link is quite useful for future questions where it seems almost obvious that a typo occurred.

I am using this version to back up my answer.

-
There must be a reason the list of errata is as short as it is. The exercise is actually corrected there. – Martin Feb 24 '13 at 6:37
@Martin: Will you flag this for plagiarism if I incorporate this into my answer? :-P – Asaf Karagila Feb 24 '13 at 6:41
Sure thing! :-) – Martin Feb 24 '13 at 6:42
@Martin: Done and done. Also short errata lists can be a consequence of no one actually reading the book in-depth. :-) – Asaf Karagila Feb 24 '13 at 6:44
Oh no! Proper attribution -> No flag >:-(( – Martin Feb 24 '13 at 6:53

First, there’s an error in the statement of the problem: it should specify that $\sim$ is an equivalence relation on $S$, and it should specify that $S\ne\varnothing$.

Unfortunately, you’ve not even begun to provide a proof. A proof that $\mathscr{P}_\sim$ is a partition of $S$ is a convincing explanation of why the members of $\mathscr{P}_\sim$ are pairwise disjoint, non-empty subsets of $S$ whose union is $S$. I’m going to do most of it.

You need to begin by understanding exactly what $\mathscr{P}_\sim$ is: $\mathscr{P}_\sim=\{[s]_\sim:s\in S\}$, where for each $s\in S$ the equivalence class $[s]_\sim$ of $s$ is defined to be $[s]_\sim=\{t\in S:t\sim s\}$. These equivalence classes $[s]_\sim$ are the members of $\mathscr{P}_\sim$; you’re to demonstrate that each of them is non-empty, that they are pairwise disjoint, and that their union is all of $S$.

The first and last of these are easy. Since $\sim$ is an equivalence relation, it’s reflexive: $s\sim s$ for each $s\in S$. Thus, for each $s\in S$ we have $s\in[s]_\sim$, which clearly implies that $[s]_\sim\ne\varnothing$. It also ensures that the union of the sets $[s]_\sim$ is all of $S$. We have to work a little harder for the third.

Suppose that two of the members of $\mathscr{P}_\sim$ have non-empty intersection. Specifically, suppose that $s,t\in S$, and $[s]_\sim\cap[t]_\sim\ne\varnothing$. Then there is some $u\in[s]_\sim\cap[t]_\sim$. By the definition of equivalence class this means that $u\sim s$ and $u\sim t$. The relation $\sim$ is symmetric, so $s\sim u$. And $\sim$ is transitive, so $s\sim u$ and $u\sim t$ together imply that $s\sim t$ and hence that $s\in[t]_\sim$. Suppose that $v$ is any member of $[s]_\sim$; then $v\sim s$, and we already know that $s\sim t$, so $v\sim t$ (why?), and therefore $v\in[t]_\sim$. This shows that $[s]_\sim\subseteq[t]_\sim$. I’ll leave it to you to show that $[t]_\sim\subseteq[s]_\sim$ as well (HINT: $t\sim s$) and hence that $[s]_\sim=[t]_\sim$.

In other words, if two members of $\mathscr{P}_\sim$ have non-empty intersection, they are actually the same set, just with a different name. This means that if I pick to members of $\mathscr{P}_\sim$ that are actually different sets, they must be disjoint. In short, $\mathscr{P}$ is a collection of pairwise disjoint sets. Put that together with what we showed in the fourth paragraph, and you’ve shown that $\mathscr{P}_\sim$ is a partition of $S$.

Note that I did not need to know anything about $S$ beyond the fact that it’s non-empty. (One doesn’t normally talk about a partition of a non-empty set.) And the axiom of choice doesn’t come into the argument.

-