Why $yC_1x \iff yC_2x$ implies $C_1 = C_2$? $C_i$ is a relation.

Question

Here is the text from the book Topology by Munkres:

Studying equivalence relations on a set $A$ and studying partitions of $A$ are really the same thing. Given any partition $\scr D$ of $A$, there is exactly one equivalence relation on $A$ from which it is derived.

The proof is not difficult. To show that the partition $\scr D$ comes from some equivalence relation, let us define a relation $C$ on $A$ by setting $xCy$ if $x$ and $y$ belong to the same element of $\scr D$. Symmetry of $C$ is obvious; reflexivity follows from the fact that the union of the elements of $\scr D$ equals all of $A$; transitivity follows from the fact that distinct elements of $\scr D$ are disjoint. It is simple to check that the collection of equivalence classes determined by $C$ is precisely the collection $\mathscr{D}$.

To show there is only one such equivalence relation, suppose that $C_1$ and $C_2$ are two equivalence relations on $A$ that give rise to the same collection of equivalence classes $\mathscr{D}$. Given $x\in A$, we show that $yC_1 x$ if and only if $yC_2 x$, from which we conclude that $C_1=C_2$. Let $E_1$ be the equivalence class determined by $x$ relative to the relation $C_1$; let $E_2$ be the equivalence class determined by $x$ relative to the relation $C_2$. Then $E_1$ is an element of $\scr D$, so that it must equal the unique element of $D$ of $\scr D$ that contains $x$. Similarly, $E_2$ must equal $D$. Now by definition, $E_1$ consists of all $y$ such that $yC_1x$; and $E_2$ consists of all $y$ such that $yC_2x$. Since $E_1=D=E_2$, our result is proved.

The text of course proves that $yC_1x \iff yC_2x$, but why it implies $C_1 = C_2$? For example suppose elements are humans, so we can define $C_1$ for "person x and person y are in relation $C_1$ if each of them has two hands"; and, $C_2$ for "person x and person y are in relation $C_2$ if each of them has two foots". $yC_1x \iff yC_2x$ holds but $C_1 \ne C_2$?

Edit - PS - we ignore the set of people with two foots and less than two hand and with two hands and less than two foots.

Answer 1

There are persons with two foots and less than two hands; so there is no $\iff$ relationship between the two

The source of the confusion here is what $C_1=C_2$ means; since there is no "intrinsic way" to know what does it mean for two completely abstract relationships to be equal, we call them equal if they act in the same way.

Answer 2

This is a fairly subtle point.

Define $C_1$ to be the relation on $\mathbb{N}$ given by $x C_1 y$ if and only if $x-y$ is even.

Define $C_2$ to be the relation on $\mathbb{N}$ given by $x C_2 y$ if and only if $x-y+1$ is odd.

These are not verbatim the same relation, but actually the collection of all pairs related by $C_1$ is the same as the collection of all pairs related by $C_2$.

We say the relations have different definitions in intension but the same definition in extension: their descriptions are different but their ultimate outcome is the same. $C_1$ will view $x$ as being related to $y$ if and only if $C_2$ does.

If we have "$y C_1 x$ if and only if $y C_2 x$", then we have that $C_1$ and $C_2$ are the same in extension. We usually write $C_1 = C_2$ for "$C_1$ and $C_2$ are the same in extension", and we will (perhaps slightly sloppily, depending on your point of view) call them equal. Most people do not actually distinguish between equality and equality-in-extension; when they say "equal" they mean "equal in extension".

Answer 3

The point is that a relation on a set $S$ is defined as a subset of $S^2$. We write $x C y$ to mean that the pair $(x,y) \in C$. So if two relations are the same as subsets, they are the same.

Answer 4

A relation on $A$ is a subset of $A\times A$, and $xC_1y$ is shorthand for $(x,y)\in C_1$, where $(x,y)$ is an ordered pair.

Thus a relation is determined by the pairs of elements that are in relation with each other, if you have $xC_1y\iff xC_2y$ the subsets $C_1$ and $C_2$ of $A\times A$ are the same set, even if you originally specified the $2$ relations in (apparently) different ways

Answer 5

It depends on how we define a relation. Usually a relation on $A$ is a subset of $A \times A$. In this case, the implication is clear. However, it would also be natural to define a relation as a formula on two variables. It is not the usual definition, but it is natural. It is also closer to a sentence in English, so perhaps more intuitive. In this case, indeed there is no implication.

Answer 6

A set is determined by the elements in it: two sets $X, Y$ are equal provided $x\in X$ iff $x\in Y$. A relation on $A$ is just a certain subset of $A\times A$, and you've shown that a point $(x, y)\in A\times A$ lies in $C_1$ iff it lies in $C_2$.