Understand Sets, Partitions, and Equivalence Relations: Help Needed!

[rad0786]

Im kind of lost here can somebody help me out please!

Let S = {a, b, c, d} and let P = { {a}, {b,c}, {d} }. Note that P is a partition of S. Describe the equivalence relation R on S determned by P.

This is a weird question that came out of my textbook.

I know what a set is, and a partition. These are quit simple ideas actually. So what does P = { {a}, {b,c}, {d} } actually mean?

Otherwise, i have no idea how to get started on this - their is no example in the book with this type of question.

"Describe the equivalence relation R on S determned by P." to me means is it either "reflective" "symmetric" or "transitive". But the answer in the back saiys R = {(a,a), (b,b), (c,c), (d,d), (b,c), (c,b)}, but that means nothing to me.

Can somebody help start me off please?

 

[Hurkyl]

P = { {a}, {b,c}, {d} } actually mean?

It is the assertion that P is equal to the set that contains {d}, {a}, and {b,c}, and does not contain anything else.



I suspect from your question that you only know the intuitive meanings of the words "partition" and "equivalence relation" -- check your text and see how it actually defines them.

 

[rad0786]

This question tells me to read a theorm.

Part of the theorm reads "... Conversely, if P is a partition of S, let R be defined by xRy iff x and y are the same piece of the partition. Then R is an equivalence relation and the correspodning partition into equivalence classes is the same as P"

im going to focus on this part of the theorm: xRy iff x and y are the same piece of the partition

Thus, S = {a, b, c, d} and let P = { {a}, {b,c}, {d} }.

so the pieces of the partition are {a}, {b,c}, {d}.

-------------Im not sure how the below comes about -----------------

With the {a} piece, we can have (a,a)
with the {b,c} piece, we can have (b,b) (b,c) (c,b) (c,c)
With the {d} piece, we can have (d,d)

and this gives R = {(a,a), (b,b), (c,c), (d,d), (b,c), (c,b)}

am i getting closer?

 

[HallsofIvy]

This question tells me to read a theorm.

Part of the theorm reads "... Conversely, if P is a partition of S, let R be defined by xRy iff x and y are the same piece of the partition. Then R is an equivalence relation and the correspodning partition into equivalence classes is the same as P"

im going to focus on this part of the theorm: xRy iff x and y are the same piece of the partition

Thus, S = {a, b, c, d} and let P = { {a}, {b,c}, {d} }.

so the pieces of the partition are {a}, {b,c}, {d}.

-------------Im not sure how the below comes about -----------------

With the {a} piece, we can have (a,a)
with the {b,c} piece, we can have (b,b) (b,c) (c,b) (c,c)
With the {d} piece, we can have (d,d)

and this gives R = {(a,a), (b,b), (c,c), (d,d), (b,c), (c,b)}

am i getting closer?

You've got the answer- that's as close as you can get! In words, b and c are equivalent to each other but a and d are only equivalent to themselves.

 

[rad0786]

I got the answer because they gave it to us in the back of the book.

I still don't understand how they get (a,a) from {a} ?

anybody care to explain please?

 

[matt grime]

Because that's the annoying way that they (stupidly written books aimed at the starting student) describe an equivalence relation: as a subset of SxS, which is, I might add, a totally useless way of thinking about it.
Given a partition of S, define a relation on S by xRy iff x,y are in the same component of the partition., Surely you agree that a is in the same part of the partition as a, hence (a,a) is in the subset of SxS so defined by this relation.

For what it's worth, thinking of relations as subsets of SxS is a completely idiotic thing to do, but for some reason they make you learn this bollocks.

I meant to try to rewrite my answer by explicitly treating a relation as being a subset of SxS, but I realized I can't. Why? Because I cannot bring myself to treat a relation as such a thing. Sorry.

 

[rad0786]

This is an indroductory analysis course.
My university won't be offering it next year.
I think they are going to have it included in a 3rd year analysis course, I am not tottaly sure.

 

[Hurkyl]

describe an equivalence relation: as a subset of SxS, which is, I might add, a totally useless way of thinking about it.

That's not entirely true.

First off, if you want to manipulate an equivalence relation as an object, you have to define it as something. :tongue2:

This particular representation has its benefits. For example, a congruence on a monoid M is actually submonoid of MxM. Or, more generally, in universal algebra, a congruence on a $\Omega$-algebra A is actually a sub-$\Omega$-algebra of AxA.

And similarly, in a category, one defines a binary relation on an object A to be a subobject of AxA. (Or, more generally, an object with two "projections" to A that satisfies some property that generalizes the notion of a monic arrow)

 

[rad0786]

okay I am lost, but i don't think I am supposed to understand what Hurkyl just said.

 

[neurocomp2003]

rad: the SxS is just the cartesian product of two elements(heh i hope that's the right term...meaning you take elements a,b from teh set S and you write them as (a,b) and a relation R is a subset of SxS...

Now your question
"Let S = {a, b, c, d} and let P = { {a}, {b,c}, {d} }. Note that P is a partition of S. Describe the equivalence relation R on S determned by P."

NOW given that we already know the answer...it suggests that question is asking you to write all the possible RULES(relations) that occur with in the partition P under the RST(reflex.,sym.,trans) equivalence concept. Your probably understand the reflex and transitive rules...because you did not ask about them. The symmetric rule was the one that you had confusion with. {a} -> implies (a,a) belongs to the relation set R under symmetric relation. Since there is only one element in {a} only the symmetric rule you need to check. Similarly with {d}...therefore from

{a},{d} you can determine the rules (a,a) and (d,d) belong to R under RST.
{b,c} you should be able to do given that. Now if you were working iwth the entire set {a,b,c} you'd get (a,a),(b,b),(c,c) belong to Rfor symmetric relations and if (a,b) and (c,b) belong to R...then (b,a),(b,c),(c,a),(a,c) all belong to R because of RST.

 

[matt grime]

That's not entirely true.
First off, if you want to manipulate an equivalence relation as an object, you have to define it as something. :tongue2:
This particular representation has its benefits. For example, a congruence on a monoid M is actually submonoid of MxM. Or, more generally, in universal algebra, a congruence on a $\Omega$-algebra A is actually a sub-$\Omega$-algebra of AxA.
And similarly, in a category, one defines a binary relation on an object A to be a subobject of AxA. (Or, more generally, an object with two "projections" to A that satisfies some property that generalizes the notion of a monic arrow)

That is an example of over categorification. An equivalence relation is just a partition into disjoint subsets. And I think you overestimated my dismissal; it was written with its intended audience of rad in mind, not you. If ever you actually want to *think* of what an equivalence relation is it is just a partition. If you want to go all category theoretic, what is the pushout of two morphims f:A-->B and g:A-->C? Well, it is the universal object in some diagram, fine, but really it is the coproduct of B and C with the images of f and g identified.

 

[HallsofIvy]

You should have this definition in your book:
An equivalence relation, R, on a set S is a relation (i.e. set of ordered pairs of things from S satisfying 3 properties:
a) reflexive: If x is in S, then (x,x) is in R (every member of Sis equivalent to itself).
b) symmetric: If (x,y) is in R, then (y,x) is also in R (if x is equivalent to y, then y is equivalent to x).
c) transitive: If both (x,y) and (y,z) are in R, then (x,z) is also in R (if x is equivalent to y and y is equivalent to z, then x is equivalent to z).

An "equivalence class" for a particular equivalence relation on a set, S, is a subset of S such that all members of the subset are equivalent to one another and all members of X that are equivalent to something in the subset are also in it.

A partition of a set, S, is a collection of subsets of S such that every member of S is in exactly one of the subsets.

Given an equivalence relation on S, the collection of all equivalence classes is a partition of S: every member of S is in some equivalence class because it is at least equivalent to itself, no member x, of S, can be in two different equivalence classes- if x were in both A and B, then every member of A would be equivalent to x, every member of B would be equivalent to x- by "transitivity", every member of A would be equivalent to every member of B so every member of A would be in B and vice-versa: A= B.

Conversely, any partition of S defines an equivalence relation on S: two members of S are equivalent if and only if they are in the same set of the partition.

Rad0786 said originally, "I know what a set is, and a partition. These are quit simple ideas actually. So what does P = { {a}, {b,c}, {d} } actually mean?"

How can you say you know what a partition is, and then ask what does P={{a}, {b,c}, {d}} "actually mean"?!
It is, of course, a collection of subsets of S= {a, b, c, d}. Every member of S is in exactly one of them: a is in {a}, b is in {b,c}, c is in {b,c}, and d is in {d}. That's how a partition is defined and that what it "actually means"!

As I said above, every partition defines an equivalence relation- two members of S are equivalent if and only if they are in the same set in the partition.
a is in a set that contains only itself- a is equivalent to itself (which it has to be: reflexive property) but not equivalent to anything else. As a set of ordered pairs, the relation must contain the pair (a,a).
b is a set containing both b and c- b is equivalent to itself (of course, reflexive property again) and equivalent to c. The set of ordered pairs must contain both (b, b) and (b, c) (and, by symmetry, (c, b) but we can also get that below).
c is in a set containing both b and c- c is equivalent to itself and equivalent to b. The set of ordered pairs must contain both (c, c) and (c, b) and, by symmety, (b, c) which we already knew.
d is in a set containing only itself- d is equivalent only to itself. The set of ordered pairs must contain (d, d).
The set of ordered pairs, R, representing the relation defined by this partition is {(a,a), (b,b), (c, c), (b, c), (c, b), (d, d)}.

Different example: S is still {a, b, c, d} but now P= {{a, b, c}, {d}}.
Now a, b, c are all equivalent to one another: the pairs representing that are (a,a), (b,b), (c,c) , (a,b), (b,a), (a,c), (c,a), (b,c), (c,b). d is in a set with no other members. The ordered pair representing that is (d,d).
The set of ordered pairs representing this equivalence relation is
{(a,a), (b,b), (c,c) , (a,b), (b,a), (a,c), (c,a), (b,c), (c,b), (d,d)}.

We can do it the other way: Suppose a relation, R, on S, is represented by the set of ordered pairs:
{(a,a), (b,b), (c,c), (d,d), (a,b),(b,a), (c,d), (d,c)}
We can see that a is equivalent to itself (the set of pairs contains (a,a)) and b (the set of pairs contains (a,b)) but not to c or d (there is no (a,c) nor (a,d)) so the equivalence class containing a is {a, b}. Since we already know what equivalence class b is in we don't have to do that for b.
We can see that c is equivalent to itself (the set of pairs contains (c,c)) and and d (the set of pairs contains (c,d)) but not to a or b so the equivalence class containing c is {c, d}. Of course, that is also the equivalence class containing c. The partition of S given by this relation is {{a,b}, {c,d}}.

 

[neurocomp2003]

i think he actually didn't know what a equivalence relation was. since the simple definition of a partition is easy...each element in S belongs to exactly one eleement in P.

 

[Hurkyl]

That is an example of over categorification. An equivalence relation is just a partition into disjoint subsets. And I think you overestimated my dismissal; it was written with its intended audience of rad in mind, not you. If ever you actually want to *think* of what an equivalence relation is it is just a partition.

Yes, I overestimated! Sorry.

But I still think that's not the right way to think of them. :tongue2: To me, any relation (including an equivalence relation), is simply a gadget to tell me when two things are related. So, what I actually prefer is for an equivalence relation on A to actually be a function AxA -> {true, false}.

Since the classical representation is merely the inverse image of true, I guess that's why I don't find it so repulsive.

 

[matt grime]

Define the nicest equivalence relation there is, ie one on Z for a fixed p with x~y iff x=y+np for some integer p. Easy to understand, no need to invoke annoying constructions on ZxZ, or anything. Just as there is no need to define a function as a subset of somethign cross something. Why do it? It's pointless for understanding as a tool for learning what it is until such a stage as it becomes unnecessary to have such a tool.