Prove this relation is an equivalence relationLet S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,16, 17, 18, 19}. Let R be the relation on S defined by “xy is asquare,”a) Prove R is an...

Prove this relation is an equivalence relation

Let S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19}. Let R be the relation on S defined by “xy is a
square,”
a) Prove R is an equivalence relation.

1 Answer | Add Yours

mlehuzzah's profile pic

mlehuzzah | Student, Graduate | (Level 1) Associate Educator

Posted on

I can only answer one of these questions, so I've edited your question to only include the first one:

To be an equivalence relation, you need to satisfy three conditions:

reflexivity, (xRx), symmetry (if xRy, then yRx) and transitivity (if xRy, and yRz, then xRz)

 

Reflexivity:

to show xRx, we need to show that x*x is a square.  This is true by definition.

 

Symmetry:

We suppose that xRy and then try to prove yRx
But: xRy means that xy is a square.  But xy=yx (multiplication is "commutative") so yx is a square, and yRx.  So the relation is symmetric.

 

Transitivity:

We suppose that xRy and yRz.  That means xy is a square and yz is a square.  We want to show that xz is a square.  

 `xy=a^2` (for some integer a)
`yz=b^2` (for some integer b)

So `xz = (xy*yz)/(y^2) = (a^2b^2)/(y^2) = ( (ab)/y )^2`    

Now, we haven't really shown that xz is a perfect square, because we still need ab/y to be an integer.  But a,b, and y are integers, so ab/y is rational.  If you square a rational number and get an integer, then the rational number must actually be an integer as well.  Thus xz *is* a perfect square, and our relation is transitive.

 

The relation is reflexive, symmetric, and transitive.  Thus it is an equivalence relation.

We’ve answered 318,917 questions. We can answer yours, too.

Ask a question