Equivalence class in X as a subset of $\mathscr P(X)$

Question

Due to Halmos:

There is no standard notation for the equivalence class of $x$ with respect to $R$; we shall usually denote it by $x/R$, and we shall write $X/R$ for the set of all equivalence classes $\ldots$

Exercise: show that $X/R$ is indeed a set by exhibiting a condition that specifies exactly the subset $X/R$ of the power set $\mathscr P(X)$.

~P. R. Halmos, Naive Set Theory (p. 28)

EDIT: Taking the answers I've received thus far, here's what I'm currently working with.

Let $X$ be a set, and let $R$ be an equivalence relation in $X$. Then $x/R$ (or $[x]$ if you prefer) is a set comprising the elements $y$ such that $(x, y) \in R$. Each such equivalence class for each element $x \in X$ is a subset of $X$ and therefore a member of $\mathscr P(X)$.

This in turn means that $X/R$, the set of all $x/R$ for our given $X$ and our given equivalence $R$, is a set of subsets of $X$, making it a subset of $\mathscr P(X)$. Now, I've worked through two examples:

If we let $X = \{1, 2, 3, 4\}$ and let $R$ be the relation of equality in $X$, then $X/R = \{\{1\}, \{2\}, \{3\}, \{4\}\}$. This is a subset of $\mathscr P(X)$ as expected.

If we let $X = \{1, 2, 3\}$ and let $R$ be the cartesian product $X \times X$, then $X/R = \{\{1, 2, 3\}\}$, which is a subset of $\mathscr P(X)$ as expected.

As for how one can come up with a general specification that achieves both of these results:

$$X/R = \{S \in \mathscr P(X): (s \in S) \iff ([t \in S] \land [s \space R \space t]) \}$$

Or, in English, the set of equivalence classes in $X$ with respect to a given relation $R$ is the set of all sets $S$ in the power set of $X$ for which an element $s$ is only in $S$ if there is also $t$ in $S$ and $s$ and $t$ stand in equivalence to one another.

This strikes me as a massive cop out, but I'm stuck on how to take it more primitive.

Answer 1

You might have missed that the equivalence relation $R$ is given. Formally, $R$ is a given subset of $X \times X$. The notation $X/R$ has something to do with $R$ itself, so it makes no sense to ignore the given equivalence relation $R$ and think of $X/R$ as something to do with all equivalence relations.

Also, you left out something quite important in your first "..." and I'll put it back in (maybe it was left implicit by the author, but for present purposes it's very worthwhile to be as explicit as possible):

We shall write $X/R$ for the set of all equivalence classes of the equivalence relation $R$.

So each element of $X/R$ is a certain equivalence class of the equivalence relation $R$, which is a certain subset of $X$, which is a certain element of $\mathscr P(X)$. Since each element of $X/R$ is an element of $\mathscr P(X)$ it follows that $X/R$ is a subset of $\mathscr P(X)$.

Now, Halmos' exercise is asking for a bit more than that, he's asking you to write the exact mathematical expression that specifies which elements of $\mathscr P(X)$ are in its subset $X/R$, so there's still work to be done.

Added: One thing that is clearly missing from your latest specification is quantifiers: the defining condition $$(s \in S) \iff ([t \in S] \land [s \space R \space t]) $$ of your set builder notation has no quantifiers on the variables $s$ and $t$, which violates the grammar of set builder notation: there should be no free variables except for $S$. There's actually some "quantifier words" in your English translation, e.g. "there is also $t$ in $S$", however I don't think you're on the right track there.

Here's a defining condition that could work $$(S \ne \emptyset) \,\,\text{and}\,\, \bigl(\forall s \in S, \forall t \in X, \space (s \space R \space t) \iff t \in S \bigr) $$

Answer 2

Your initial thought was wrong. $X/R$ denotes the set of all equivalence classes of the elements of $X$ with respect to the equivalence relation $R$ defined. Then

$$X/R=\{x/R:x\in X\},$$

where $x/R$ denotes the equivalence class of $x$ (I prefere the notation $[x]$):

$$x/R=\{y\in X:(x,y)\in R\}.$$

As you can see, $x/R$ is a subset of $X$ and thus an element of $P(X)$. That means $X/R$ is a collection of elements of $P(X)$. Hence $X/R$ is a subset of $P(X)$.

Noe, why is he worried about this?Well, because, as we have seen, $X/R$ is a set of subsets, so it may be not a set (do you know Russell's paradox?). However, the fact that $X/R\subset P(X)$ ensures that $X/R$ is actually a set. The reasoning is:

$$ X \mbox{set} \Rightarrow $P(X) \mbox{set} $$

and any subset of a set is itself a set.

P.S. I misunderstood Halmos's exercise, the reasoning may be useful though.

Answer 3

It's been a while since the original question went up, so I'll try to give a complete answer here.

As Lee Mosher notes, $R$ is given, not arbitrary, so we can use it in our final condition.

The fact that $R$ is an equivalence relation means that given some $x \in X$, the equivalence class of $x$ is a set of elements $y \in X$ such that $(x, y) \in R$.

As you've described above, we know that

• every equivalence class is a subset of $X$
• $X/R$ is a set of these subsets of $X$, and is therefore itself a subset of $\mathscr P(X)$
• every equivalence class is disjoint; we can't have any overlap in the subsets that we select with our condition.

I think the only condition that satisfies these constraints is the following:

$$X/R = \{S \in \mathscr P(X)\setminus\{\varnothing\}: (S \times S) = \{ (a, b) \in R: a \in S \lor b \in S \}$$

In English, this condition selects for subsets $S$ of $\mathscr P(X)$ (without the empty set, which can't be an equivalence class) where every element satisfies the relation $R$ to every other element in that same subset $S$.

The filter on $R$ selects out ordered pairs within the relation $R$ that concern elements that exist within the subset $S$ being considered.