3

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.

user153330
  • 1,726
  • 2
    A relation is a set of ordered pairs. The statement $yC_1x\iff yC_2x$ means precisely that the ordered pairs in the first relation are precisely the ordered pairs of the second relation. Hence the sets are the same. – symplectomorphic Mar 20 '16 at 21:44
  • As there are people with one hand and two feet, the two equivalence relations are not the same. – user317176 Mar 20 '16 at 22:06
  • 1
    @DougM - otherwise they have prosthetic hand. –  Mar 20 '16 at 22:43

6 Answers6

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.

Robert Israel
  • 448,999
  • I thought that a relation means the reason for 'connectivity'. What that is called, the reason for 'connectivity'? I don't know how to it more clear, sorry my maths is weak. –  Mar 20 '16 at 21:49
  • In Enderton's book A Mathematical Introduction to Logic, for example, a relation is defined as a set of ordered pairs. – Dominic108 Mar 20 '16 at 21:51
  • It's the same situation with functions. For functions $f_1$ and $f_2$ to be the same, what we need is $f_1(x) = y$ if and only if $f_2(x) = y$. The same function might have different descriptions (what Patrick Stevens is calling "definitions in intension"), but the description is not an intrinsic part of the function. – Robert Israel Mar 21 '16 at 00:23
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.

Ant
  • 21,098
  • I just tried to understand why $yC_1x \iff yC_2x$ implies $C_1 = C_2$? My counterexample oops was bad. How to prove the implication? –  Mar 20 '16 at 21:39
  • By the way, what if we ignore the set of people with two foots and less than two hand and with two hands and less than two foots? –  Mar 20 '16 at 21:42
  • 1
    @Liebe then they would be equal. 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. – Ant Mar 20 '16 at 21:49
  • Thank you very much. Your comment is the answer for what I asked! If you please add it to the answer section so I can 'accept' it for this question not remained unaccepted-answered. –  Mar 20 '16 at 21:59
  • I will be disappointed if no effort is made to make sure that we respect the common usage for the definition of a relation. Actually, I don't care that much, but the definition used should then be clarified in the question. Having a question that becomes difficult because the definition is unclear and a lot of discussions based on this lack of a precise definition should have no place in mathematics. – Dominic108 Mar 20 '16 at 22:06
  • @Dominic108 - Actually in the mentioned book, relation is defined to be a subset of $A\times A$. But the word "relation" (I think) is not good at all. It made me misunderstanding. Why we should call the name of a set "relation" and later on use "relation" literally in the text?! –  Mar 20 '16 at 22:12
  • A subset of $A \times A$ is a set of pairs, because $A \times A$ is a set of pairs. Of course, it is important to use terms that have a meaning in the common usage that matches as much as possible the mathematical definition. A discussion at that level can indeed help someone to understand. Well, fine, but you know that mathematics is based on precise definitions. In this case, a relation is a set of pairs. – Dominic108 Mar 20 '16 at 22:21
  • @Liebe done! :-) – Ant Mar 21 '16 at 00:06
1

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".

Patrick Stevens
  • 36,135
  • Your answer assumes that the definition of a relation is a formula with two variables, but is this definition really the common usage? Do you have any standard textbook that defines a relation in this way? – Dominic108 Mar 20 '16 at 21:58
  • I've been deliberately agnostic about how a relation is defined here. We all know what a relation is: it's a thing that relates things. If you want to implement a relation in set theory, you'll (usually) end up with a collection of ordered pairs, but I prefer not to give that as the definition of a relation because it's… not really what a relation is. Just as a natural number isn't really a finite ordinal, but we implement them in that way in set theory. Does that make sense? – Patrick Stevens Mar 21 '16 at 08:01
  • Well, as long as the answer to the question depends on the specific definition chosen, I think it makes no sense not to discuss definitions. But, I understand that we want to validate the OP reasoning as much as possible and start from there. So, I understand that you we should not jump to fast into a specific definition. The OP was considering a general concept of relation based on sentences in English. So, we have to acknowledge that as much as possible. But, the answer to the question requires that we consider the standard math definition, so we have to bring the OP there. – Dominic108 Mar 21 '16 at 16:04
1

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

Alessandro Codenotti
  • 12,285
  • I thought that a relation means the reason for 'connectivity'. What that is called, the reason for 'connectivity'? I don't know how to it more clear, sorry my maths is weak. –  Mar 20 '16 at 21:51
  • 1
    When we informally say something like "let $xRy$ if $2|x-y$, where $x,y\in\mathbb{N}$ what's meant is "let $R\subseteq\mathbb{N}\times\mathbb{N}={(x,y):2|x-y}$" because that's how relations on a set are defined. Of course in most situations the definition is just cumbersome and unneeded, but it's relevant in this case, because it follows from it that 2 relations are the same if they are the same as sets, regardless of the way we describe them in more or less formal language – Alessandro Codenotti Mar 20 '16 at 21:57
0

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.

Dominic108
  • 638
0

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$.

anomaly
  • 25,364
  • 5
  • 44
  • 85