# 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

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.