Thread: Equivalence classes: Armstrong - Groups and Symmetry - clarification

1. Equivalence classes: Armstrong - Groups and Symmetry - clarification

I am reading Armstrong: Groups and Symmetry Chapter 12: Partitions

In talking about partitions and equivalence classes Armstrong writes on Page 60 (see attachment for the relevant pages of Armstrong's book):

================================================== ====

Let X be a set and R be a subset of the cartesian product X x X. In other words, R is a collection of ordered pairs (x,y) whose coordinates x,y come from X. Given two points x and y of X we shall say that x is related to y if the ordered pair (x,y) happens to lie in R. If properties (a), (b) and (c) [properties of equivalence class - see Armstrong page 60 attached] are valid, then we call R an equivalence relation on X. For each x$\displaystyle \in$ the collection of points which are related to it irs written and called the equivalence class of x.

(12.1) Theorem R(x) = R(y) whenever (x,y) $\displaystyle \in$ R

================================================== ====

Although Armstrong writes "If properties (a), (b) and (c) are valid, then we call R an equivalence relation on X" he clearly believes that R is an equivalence relation and the Theorem seems to be a statement of this.

My questions are as follows:

If R actually is an equivalence relation then we have

x is related to y iff the ordered pair (x,y) happens to lie in R

Now if x is related to y then if R is an equivalence relation then y must be related to x - that is the ordered pair (y,x) must lie in R

BUT (x,y) can lie in R and (y,x) might not - so R does not seem to be an equivalence relation?

Second question: Is Theorem 12.1 above a statement that R is an equivalence relation. If so, how is the statement of the theorem equivalent to R possessing the three defining properties of an equivalence relation.

Peter

2. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

Originally Posted by Bernhard
(12.1) Theorem R(x) = R(y) whenever (x,y) $\displaystyle \in$ R
My questions are as follows:
If R actually is an equivalence relation then we have
Second question: Is Theorem 12.1 above a statement that R is an equivalence relation. If so, how is the statement of the theorem equivalent to R possessing the three defining properties of an equivalence relation.
No sure of what you are really asking there,
Theorem 12.1 says Given a equivalence relation R if R(x)=R(y) then $\displaystyle (x,y)\in R$.

The idea is that any partition of a set determines an equivalence relation by relating members of any cell in a partition. Moreover, any equivalence relation on a set gives rise to a partition of the set.

3. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

My understanding now is that R is an equivalence relation only if there is a condition on (x,y) such that the three properties of an equivalence relation hold. So Arrmstrong is not asserting that any set of ordered pairs is an equivalence relation - of course.

Peter

4. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

suppose we have a partition of a set X into disjoint subsets, say P1,P2,etc. so X = UPj, and for j ≠ k, Pj ∩ Pk = Ø.

we can define xRy iff x,y are both in the same Pj.

since we have a partition, every element x of X is in SOME Pj, and clearly x is in the same Pj as itself, so xRx.

now if xRy, then then we have x,y in Pj, for some Pj, so y,x are in Pj as well. thus yRx (basically, "and" is symmetric).

finally, if xRy, and yRz, then clearly all of x,y, and z are all in the same Pj. so any two of them are in the same Pj, in particular, x and z. so xRz.

on the other hand, if we define [x] = {y in X: xRy}, where R is an equivalence relation, then we have:

X = [x1] U [x2] U [x3]....., or perhaps more succinctly, X = U[xj], xj in X. since every xRx, so any x is at least in the equivalence class [x].

so the only thing is to show that these equivalence classes are disjoint: i.e., either:

a) [x] = [y] or
b) [x] ∩ [y] = Ø

so suppose z is in [x] ∩ [y]. since z is in [x], xRz. since z is in [y], yRz. since R is an equivalence relation, zRy, and then by transitivity, xRy.

now if yRw, (that is w is in [y]), then xRw by transitivity, so w is in [x]. so [y] is contained in [x]. and if xRu, so u is in [x],

then xRu, so uRx, and xRy, so uRy, and thus yRu, so [x] is contained in [y]. since [x] and [y] contain each other, they are equal sets, [x] = [y].

in other words, partitions are the "plain set" version of coset sets in groups. and we can form a "set of subsets" which acts "similar" to the original set

(replacing elements x with equivalence classes [x]), or a quotient set X/R, precisely when R is an equivalence relation.

5. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

Thanks Deveno - most instructive

I can see that if you define xRy as you do - "we can define xRy iff x,y are both in the same Pj.", then you get symmetry in the equivalence realtion via your argument "now if xRy, then then we have x,y in Pj, for some Pj, so y,x are in Pj as well. thus yRx (basically, "and" is symmetric)."

The trouble for me was that Armstrong used the language of ordered pairs, viz.

"Given two points x and y of X we shall say that x is related to y if the ordered pair (x,y) happens to lie in R" (Armstrong page 61 - see attachment)

In the cased of ordered pairs, as I see it, R is only an equivalence relation if a condition that satisfies the three propoerties of an equivalence relation ie reflexivity, symmetry and transitivity.

I think my mistake was to interpret Armstrong as saying that R was an equivalence relation anyway - but in fact I think he was saying ONLY if the three conditions are satisfied. [Case of misinterpreting the text]

Peter

6. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

well a relation IS a subset of X x X, that is, saying xRy is equivalent to saying (x,y) is in R. and it's easy to come up with relations that are NOT equivalence relations:

1. the relation xRy iff x < y, is not an equivalence relation (it's neither reflexive nor symmetric) on any subset of the real numbers.
2. the relation xRy iff (x,y) lies on the unit circle in the euclidean plane is not an equivalence relation (here, symmetric means symmetric about the line y = x, the diagonal of RxR. this relation actually IS symmetric, but it's not reflexive, since some (actually a LOT of) points on the line y = x do not lie on the circle).

that is to say, equivalence relations on R (the real numbers) have a geometric interpretation, we can draw pictures of them.

the important thing about equivalence relations, is that they generalize the familiar properties of equality: equivalent to equivalent is equivalent. in fact, equality in equations is actually an equivalence relation on the set of allowable expressions (in other words, if we just start with sets, we can use some of these sets to define a notion of "="). this is a very powerful notion, that we can "choose the level of what we regard as "single things" (elements)". so, in different contexts, 1 might mean:

the set {0}.
the integer (natural number) s(0) (= 0 "+ one")
the equivalence class [1] of integers congruent to 1 modulo k
an nxn matrix with integer entries, 1's on the diagonal, and 0's elsewhere.
an identity mapping f(x) = x on a set S (which might have other, smaller sets as its "elements").

we're allowed to view things fluidly, regarding objects as "atomic", or "molecular", whichever lends clarity to understanding.

7. Re: Equivalence classes: Armstrong - Groups and Symmetry - clarification

Very much appreciate your considerable help

Peter