More questions about Relations

[XodoX]

More questions about "Relations"

I have some more questions...

1) How do I exactly define an equivalence relation? I know it needs to be reflexive, symmetric, and transitive. That's too much to check for, and it's very confusing. There must be something else. No? This is important, because I see equivalence relation everywhere.

2) What exactly is a partition? Like: find the partition of E $$\wedge$$F and E $$\vee$$ F ( omitted the given sets ). Is it really just two sets joined? Set A (1,2) set B (3,4) would be set P ( 1,2,3,4) ?

3) I also have some questions about the notations.

"A relation R on a set A is called reflexive if (a,a) $$\in$$ R for every element a $$\in$$ A".

So, that means if you have the following relations on {1,2,3,4} and R 1 = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)

This wouldn't be reflexive, because it dosen't contain (1,1), (2,2), ( 3,3), (4,4). What here is exactly the (a,a)?? What's the first a and what's the second a? Dosen't make sense to me. There seems to be a,a in R1 , but that can't be it. One a must be from the {1,2,3,4} and the other a from the R 1 = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4). I don't get it.

Thank you!

 

[tiny-tim]

Hi XodoX!

1) How do I exactly define an equivalence relation? I know it needs to be reflexive, symmetric, and transitive. That's too much to check for …

No it isn't!

That's the definition! Live with it!

You can't choose your relations! ​

2) What exactly is a partition? Like: find the partition of E $$\wedge$$F and E $$\vee$$ F ( omitted the given sets ). Is it really just two sets joined? Set A (1,2) set B (3,4) would be set P ( 1,2,3,4) ?

Sorry, not following you.

… This wouldn't be reflexive, because it dosen't contain (1,1), (2,2), ( 3,3), (4,4). What here is exactly the (a,a)?? What's the first a and what's the second a? Dosen't make sense to me. There seems to be a,a in R1 , but that can't be it. One a must be from the {1,2,3,4} and the other a from the R 1 = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4). I don't get it.

The relation is a subset of R x R, not of R X R1 …

R1 is the relation!

One a must be from the {1,2,3,4} and the other a from the {1,2,3,4} also …

so a could be 3, so (3,3) would have to be in the subset R1 of R x R (and it isn't).

 

[abiyo]

To help you see how an equivalence relation is related to partition, let me give you a fictitious example. Consider a town. This town has rivers and mountains. So sometimes to be able to visit a friend means to be able to climb a mountain or swim a river. Let's define an equivalence relation in this town as follows. Two houses are related if there is a path between them. That is you don't need to climb a mountain or swim a river. You can just walk. Now let's prove if this is an actual equivalence relation. It is reflexive. Take a house then there is a path to this house.(obvious) Take two houses a and b. If there is a path between a and b, then there is a path between b and a. (Just go the reverse way). Now for the final case consider there is a path between a and b. There is also a path between b and c. is there a path between a and c? yes! just go on the path from a to b and then from b to c. But let's see what this does. You will have a couple of houses on one side of the mountain, a couple others on the other side, some more by the side of the river. So the houses of the town are partitioned in pieces. And each partition means something. Being a member of the partition is being related i.e if you live by the side of the river, there is a path to all the houses on the river. This is just to help you grasp what ER is. A fully rigorous proof and detailed treatment can be found in a good mathematic book in your library. Good luck.

 

[XodoX]

Hi XodoX!


No it isn't!

That's the definition! Live with it!

You can't choose your relations! ​

Sorry, not following you.


The relation is a subset of R x R, not of R X R1 …

R1 is the relation!

One a must be from the {1,2,3,4} and the other a from the {1,2,3,4} also …

so a could be 3, so (3,3) would have to be in the subset R1 of R x R (and it isn't).

Yeah, it is. There's not always something to check for. Like: "Define that R is an equivalence relation on the set A.".

Or:

Define the equivalence R_pi for a partition pi.


So there must be some other way to find it out.

To help you see how an equivalence relation is related to partition, let me give you a fictitious example. Consider a town. This town has rivers and mountains. So sometimes to be able to visit a friend means to be able to climb a mountain or swim a river. Let's define an equivalence relation in this town as follows. Two houses are related if there is a path between them. That is you don't need to climb a mountain or swim a river. You can just walk. Now let's prove if this is an actual equivalence relation. It is reflexive. Take a house then there is a path to this house.(obvious) Take two houses a and b. If there is a path between a and b, then there is a path between b and a. (Just go the reverse way). Now for the final case consider there is a path between a and b. There is also a path between b and c. is there a path between a and c? yes! just go on the path from a to b and then from b to c. But let's see what this does. You will have a couple of houses on one side of the mountain, a couple others on the other side, some more by the side of the river. So the houses of the town are partitioned in pieces. And each partition means something. Being a member of the partition is being related i.e if you live by the side of the river, there is a path to all the houses on the river. This is just to help you grasp what ER is. A fully rigorous proof and detailed treatment can be found in a good mathematic book in your library. Good luck.

Thanks! Sounds complicated, though. I'll try to apply it.

 

[xxxx0xxxx]

The partition P of a set A by the equivalence relation R is the set of all subsets of A containing just those elements of A that are related to each other by R.

Example: Partition {a,b,c} using the identity relation.
Answer: the partition is {{a},{b}.{c}} since only a=a, b=b, and c=c under identity, and identity is obviously reflexive, symmetric, and transitive.

The properties of reflexivity, symmetry and transitivity guarantee that the sets in the partition are mutually exclusive, and that their union will be the original set.

 

[Fredrik]

1) How do I exactly define an equivalence relation? I know it needs to be reflexive, symmetric, and transitive. That's too much to check for.

You define one with a phrase like "x~y if blah-blah-blah". Then you verify that the three requirements are satisfied. This is usually very easy. For example, let ~ be the equivalence relation on ℝ² defined by "(a,b)~(c,d) if a=c". This says that two points in the plane are considered "equivalent" if and only if they're on the same vertical line. Perhaps we shouldn't use the word "equivalent" before we've shown that it's an equivalence relation, but it's not hard at all to verify that the three requirements are satisfied:

Reflexivity: Is (a,b) on the same vertical line as (a,b)?

Symmetry: Suppose that (a,b) is on the same vertical line as (c,d). Does this imply that (c,d) is on the same vertical line as (d,c)?

Transitivity: Suppose that (a,b) is on the same vertical line as (c,d), and that (c,d) is on the same vertical line as (e,f). Does this imply that (a,b) is on the same vertical line as (e,f)?

The answer to all three questions is obviously "yes", so in this case it was trivial to verify that the binary relation we defined is an equivalence relation. I would say that it's usually trivial. Most of the time it's so trivial that you can determine if it's an equivalence relation in 30 seconds or less, just by looking at the definition.

2) What exactly is a partition? Like: find the partition of E $$\wedge$$F and E $$\vee$$ F ( omitted the given sets ).

I don't understand your example question. The phrase "an equivalence relation partitions the set" refers to the easily proved fact that every member of the set belongs to exactly one equivalence class. In my example above, the equivalence classes are the vertical lines, and the relation ~ can be said to partition the plane because the plane is the disjoint union of all vertical lines.

3) I also have some questions about the notations.

"A relation R on a set A is called reflexive if (a,a) $$\in$$ R for every element a $$\in$$ A".

So, that means if you have the following relations on {1,2,3,4} and R 1 = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)

This wouldn't be reflexive, because it dosen't contain (1,1), (2,2), ( 3,3), (4,4).

There's something wrong with the sentence I highlighted. It doesn't make sense as it stands. You probably meant to say: R1 = {(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)} is a relation on A={1,2,3,4}.

Yes, R1 is a binary relation on A, because it's a subset of A×A. It's not an equivalence relation. One way to see this is to note that it's not reflexive since (3,3) isn't a member of R1. You objected to that in your most recent post, but you explicitly stated that the members of R1 are (1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4), and nothing else. (3,3) isn't on that list.

What here is exactly the (a,a)?? What's the first a and what's the second a?

They mean the same thing. (It would be very confusing to use a single symbol for two different things in the same expression).

Note that the sentence you quoted said that for all a in A, ***some statement involving a***. You need to think about what the words "for all" mean. For example, if I say that "for all days of the week x, x has 24 hours", it means "Monday has 24 hours, Tuesday has 24 hours, Wednesday has 24 hours, Thursday has 24 hours, Friday has 24 hours, Saturday has 24 hours, Sunday has 24 hours".

There's not always something to check for. Like: "Define that R is an equivalence relation on the set A.".

Or:

Define the equivalence R_pi for a partition pi.

There's something wrong with the highlighted sentences. You can define an equivalence relation R, and if you've been told what relation R is, you can try to verify that it's an equivalence relation. But you can't "define that it's an equivalence relation". That doesn't make sense.

The second highlighted sentence makes sense if a "partition" is a specific way to describe the set as a union of disjoint subsets. (I still don't know what exactly pi refers to). For example, if you've been told that the plane is a disjoint union of vertical lines, and you're asked to find the equivalence relation that partions the set in that particular way, it's very easy to see that it's the binary relation ~ that I defined above.

 

[xxxx0xxxx]

I have some more questions...

1) How do I exactly define an equivalence relation? I know it needs to be reflexive, symmetric, and transitive. That's too much to check for, and it's very confusing. There must be something else. No? This is important, because I see equivalence relation everywhere.

Turns out, that every partition defines a unique equivalence relation:

For {a,b,c} the equivalence relations are:

Partition >>>>>>>>> Relation
--------- ----------------------
{{a},{b},{c}} Identity: {<a,a>,<b,b>,<c,c>}
{{a,b},{c}} Equiv Rel: {<a,a>,<a,b>,<b,b>,<b,a>,<c,c>}
{{a},{b,c}} Equiv Rel: {<a,a>,<b,b>,<b,c>,<c,c>,<c,b>}
{{a,c},{b}} Equiv Rel: {<a,a>,<a,c>,<b,b>,<c,c>,<c,a>}
{{a,b,c}} Equiv Rel: {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}