Are these Equivalence Relations?

51 Views Asked by At

I am having some trouble determining if these are equivalence relations. Specifically, I am not sure if I am supposed to check for reflexiveness, symmetry and transitivity in the ordered pairs of the relation or every possible ordered pair in the set.

(a) R = {(1, 1),(1, 2),(2, 1),(2, 2),(3, 3)} on set {1, 2, 3}

(b) R = {(1, 1),(1, 2),(2, 1),(2, 2),(3, 3)} on set {1, 2, 3, 4}

(c) R = {(1, 2),(2, 3),(1, 3)} on set {1, 2, 3}

1

There are 1 best solutions below

4
On

To be reflexive $R$ must have all possible $(a,a)$ pairs. 1) does. 2) and 3) do not.

Symmetry. $R$ does not need all possible $(a,b);(b,a)$ pairs. But for every $(a,b)$ pair that it does have, it must have the symmetric $(b,a)$ pair. 1) has the pair $(1,2)$ so it needs $(2,1)$ to be symmetric. It does so that is fine. (And vice versa; it has $(2,1)$ so it needs $(1,2)$ which it does).

on the other hand as 1) does not have $(1,3)$ so it doesn't need $(3,1)$. (And if 1) had $(3,1)$ it would need $(1,3)$; but it doesn't have $(3,1)$ so it does not need $(1,3)$.

Of all the $(a,b)$ (where $a \ne b$) pairs that 1) has; that is $(1,2)$ and $(2,1)$ it must have those in reverse. And it does. So it is symmetric.

It's worth noting that if a relation $R$ didn't have any $(a,b)$ pairs it would be symmetric as it would need any $(b,a)$ pairs.

As for transitive: That means for any $(a,b)$ an $(b,c)$ that it does have it must also have $(a,b)$.

1) has $(1,2)$ and it has $(2,1)$ so it must have $(1,1)$. It does. And it has $(2,1)$ and it has $(1,2)$ is it must have $(2,2)$. It does.

In theory we need to check andy $(a,b)$ and $(b,b)$ so see if it has $(a,b)$ but .... that's trivial. It it has $(a,b)$ it has $(a,b)$ so we cshouldn't have to check those.

Now the only $(a,b),(b,c)$ pairs that 1) has are $(1,2),(2,1)$ and $(2,1),(1,2)$. So we checked those all and transitivity holds. We don't need ot check any pairs it doesn't have (such as $(1,2),(2,3)$ to see if it has $(1,3)$) as those are irrelevant.

ANyway. 1) has reflexivity because it has all $(a,b)$ for every $a$ in the set. 2) fails as it does not have $(,4,4)$. 3) fails entirely.

1) and 2)have symmetry as for all $(a,b);a\ne b$ that they have theeny have $(b,a)$. 3) fails as it has $(1,2)$ but not $(2,1)$ etc.

All three have transitivity. So 1) is the only equivalence relation.

....

==== old answer =====

If you check every possible order pair in the set, than that wouldn't tell you anything about the pairs in relation. So what would be the point?

Also as $(x,x)$ is always a possible pair the the set of possible pairs will always be reflexive and as $(x,y)$ and $(y,x)$ will always be possible the set of all possible pairs will be symmetric and similarly transitive.

But we should we care about what could possibly happen when you are concerned only with what does happen in $R$?

1) is reflexive because they have all possible $(a,a)$ pairs namely $(1,1)$ and $(2,2)$ and $(3,3)$ but 2) and 3) is not because 2) doesn't have $(4,4)$ and 3) has none of $(1,1),(2,2)$ or $(3,3)$. doesn't have any of them. (And what do where care that they are possible if they are not actually in $R$?)

====added later====

In reading you comments I see you are confused about symmetry. And now I understand why you asked about possible pairs which didn't make any sense to me at first but now I can understand your confusion.

To be symmetric then for every pair $(a,b)$ that the set does have then the set must also have $(b,a)$. But it doesn't need to have either $(a,b)$ or $(b,a)$ in the first place.

To be symmetric it must have both, OR it could have neither.

1) as $(1,2)$ so to be symmetric it must have $(2,1)$. ANd it does. But since it doesn't have $(1,3)$ it doesn't have to have (in fact it can't have) $(3,1)$.

For the pairs it does have $(\color{red} 1,\color{blue}1), (\color{red}2,\color{blue}1), (\color{red} 1,\color{blue}2), (\color{red}2,\color{blue}2),(\color{red}3, \color{blue}3)$ to be symmetric it must contain the symmetric pairs: $(\color{blue}1, \color{red} 1), (\color{blue}1,\color{red}2), (\color{blue}2,\color{red} 1), (\color{blue}2,\color{red}2),(\color{blue}3,\color{red}3)$... which it does.

Notice that any $(a,a)$ is always symmetric to itself so we don't actually have to check them. The only ones we need to check are $(a,b)$ where $a\ne b$.

In the case of 1) we have $(1,2)$ so we need $(2,1)$ and we have it. And we have $(2,1)$ and so we need $(1,2)$ and we have it.