Relations question (discrete math)

[rygard]

I'm not sure if this is the right forum for this question, this may be taught in calculus but I'm not sure.

Let X = {1, 2, 3, 4, 5, 6}. Define a relation R on X x X by (a,b)R(c,d) if ad=bc. Show that R is an equivalence relation on X x X. List one member of each equivalence class of X x X given by relation R. Describe the relation R in familiar terms.

Now, I'm a bit confused about some of this. First of all, is each element of the relation R supposed to be a pair of ordered pairs? Like ((1,2),(1,2))? Also, if that's the case, then i have to show that it's an equivalence relation, so i have to show reflexivity, symmetry, and transitivity. If it's pairs of ordered pairs, I can do the reflexive part, like ((1,1),(1,1)) , ((2,2),(2,2)) is that right? How am I supposed to find all the elements that satisfy (a,b)R(c,d) and satisfy the equivalency relation requirements? I've tried listing all the cartesian products of X x X and trying to find all the relations that satisfy the rule, and then trying to find ones that are symmetrical, transitive etc., but it's taking forever. Is there some kind of trick or pattern that I'm missing? Or am I being too specific and supposed to do this in a more abstract way? Thanks in advance for any help

 

[rygard]

Actually I think i figured out the first part...It's supposed to be more abstract according to my teacher, so i tried for the definition : relation R on X x X defined by (a,b),(c,d)∈R if (ad)=(bc). Then i have to show it's a reflexive relation, so i wrote ∀(a,b)∈X^2, (a,b)R(a,b) and it fits the rule because ab = ab

Then for symmetry i have (a,b)R(c,d) implies (c,d)R(a,b) and this fits the rule because ad = bc and cb=da are the same by commutative property of multiplication.

Transitive and everything after that is where I'm stuck now

 

[pka]

\(\displaystyle \begin{array}{l}
\left( {a,b} \right)R\left( {c,d} \right)\; \wedge \;\left( {c,d} \right)R\left( {e,f} \right) \\
ad = bc\quad \quad \wedge \quad cf = de \\
adf = bcf \\
adf = bde \\
af = be \\
\left( {a,b} \right)R\left( {e,f} \right) \\
\end{array}\)

 

[rygard]

\(\displaystyle \begin{array}{l}
\left( {a,b} \right)R\left( {c,d} \right)\; \wedge \;\left( {c,d} \right)R\left( {e,f} \right) \\
ad = bc\quad \quad \wedge \quad cf = de \\
adf = bcf \\
adf = bde \\
af = be \\
\left( {a,b} \right)R\left( {e,f} \right) \\
\end{array}\)

Thank you very much. Now for the equivalence class part....normally you have [1] = { } and all the elements in the brackets are things that are related to 1, but how do equivalence classes work when you have a rule like (a,b)R(c,d)? Because each element of relation R for the set X = {1,2,3,4,5,6} times itself is in this case a pair of ordered pairs, do i have to do ordered pairs for equivalence classes? Like [(1,2)] = {(1,2), (2,4) . . .} ???

 

[pka]

relation R for the set X = {1,2,3,4,5,6} times itself is in this case a pair of ordered pairs, do i have to do ordered pairs for equivalence classes? Like [(1,2)] = {(1,2), (2,4) . . .}

[(1,2)] = {(1,2), (2,4) ,(3,6)}
[(2,1)]=[(2,1),(4,2),(6,3)}
[(1,1)={(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)}
etc

There are 36 pairs in XxX.

 

[daon]

This is very similar to the equivilance classes that are the rational numbers. The main difference here being the set X instead of \(\displaystyle \mathbb{Z}\).

Think of (a,b) as a/b...

So [(1,1)] = {(a,a) | a is a member of X}.. intuitively think 1/1 = 2/2 = ... = 6/6 i.e. "one"
[(2,1)] = {(2a,a) | a and 2a are members of X} .... think "two"
[(1,3)] = {(a,3a) | a and 3a are members of X} .... think "one third"

etc...

 

[rygard]

relation R for the set X = {1,2,3,4,5,6} times itself is in this case a pair of ordered pairs, do i have to do ordered pairs for equivalence classes? Like [(1,2)] = {(1,2), (2,4) . . .}

[(1,2)] = {(1,2), (2,4) ,(3,6)}
[(2,1)]=[(2,1),(4,2),(6,3)}
[(1,1)={(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)}
etc

There are 36 pairs in XxX.

So is each ordered pair in X x X an equivalence class of its own? As in 36 different equivalence classes in this case?

 

[pka]

So is each ordered pair in X x X an equivalence class of its own? As in 36 different equivalence classes in this case?

Absolutely NOT.
We have given you several equivalent classes.
Some contain four terms and one contains six terms.
The union of all these classes must have 36 terms.

 

[rygard]

I think i understand it now. So for, say, [(1,1)] = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)}, those elements in that equivalence class are ONLY in that equivalence class and no others, and the union of all the equivalence classes will make the 36 elements of X x X? Is any of this right?

 

[daon]

I think i understand it now. So for, say, [(1,1)] = {(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)}, those elements in that equivalence class are ONLY in that equivalence class and no others, and the union of all the equivalence classes will make the 36 elements of X x X? Is any of this right?

Yes, the union must be \(\displaystyle X \times X\) and each equivilance class as a set will be disjoint from the others. That is what is meant by a partition.

 

[rygard]

Ok, I think I'm starting to get the hang of this stuff. Thanks for the help everyone

 

[goldie3465]

I don't understand, working with elements XxX X={1, 2} this is confusing how to list elements with only two numbers?

 

[daon]

I don't understand, working with elements XxX X={1, 2} this is confusing how to list elements with only two numbers?

The cross product of two sets AxB is the SET OF ALL ORDERED PAIRS (a,b) where a is from the first set A and b is from the second set B.

X x X = {(a,b) | a is in X and b is in X}. This set consists of EVERY POSSIBILITY.

For X={1,2}, all the possibilities are (1,1), (1,2), (2,1), (2,2). Make sense? Therefore the set of these form the cross product of X with itself. As an exercise, try X x X x X. The elements will look like (a,b,c) but follow the same rules.