3

Determine the properties of an equivalence relation.

I'm not sure if I am understanding this correctly.

A. $\{(a,b)|\ a$ and $ b$ are the same age$\}$

B.$\{(a,b)|\ a$ and $ b$ have the same parents$\}$

C. $\{(a,b)|\ a$ and $ b$ share a common parent$\}$

D. $\{(a,b)|\ a$ and $ b$ have met$\}$

A. Reflexive

Symmetric - If $a$ is the same age as $b$ then $b$ if the same age as $a$

Transitive - If $a$ is the same age as $b$ and $b $ is the same age as $c,$ then $a$ is the same age as $c.$

B. Reflexive

Symmetric - If $a$ has the same parents as $b,$ then $b $ has the same parents as $a$

Transitive - If $a$ has the same parents as $ b,$ and be has the same parents as $c$, then $a$ has the same parents as $c.$

C. Reflexive

Symmetric - If $a$ shares a common parent with $b$, then b shares a common parent with a

NOT Transitive - If $a$ shares a common parent with $b$, and $b$ shares a common parent with $c,$ then a doesn't necessarily have to have a common parent with $c.$

D. Reflexive

Symmetric - If $a$ has met $b$, then $b$ has met $a$

NOT transitive - If $a$ has met $b$ and $b$ has met $c$ then $a$ has met $ c$

To be an equivalence relation the set has to have all three properties, correct? If the set has the Reflexive and Transitive property, but is Antisymmetric we say it is a partially ordered set?

EDIT:

D. $\{(a,b)|\ a$ and $ b$ speak a common language$\}$

Reflexive Symmetric Not Transitive

I Added this one because similar to D. I wasn't sure about the Reflexive property. Can one speak a common language with themselves? I originally thought it was Reflexive, but now believe it may not be.

Socrox
  • 83
  • 1
    Are you sure that D. is reflexive? Did you ever "meet yourself"? Indeed to be an equivalence relation it must be reflexive, symmetric and transitive. To be a partial order the relation must be reflexive, antisymmetric and transitive. – drhab Apr 16 '15 at 18:17
  • That makes sense. So as far as the other answers go I have the right idea? – Socrox Apr 16 '15 at 18:21
  • A hasse diagram can be drawn for partially ordered sets, but you wouldn't draw one if the set was an equivalence relation? – Socrox Apr 16 '15 at 18:22
  • Yes, it looks good to me. Here only the relations $A$ and $B$ are equivalence relations. – drhab Apr 16 '15 at 18:23
  • Hasse diagrams are not for equivalence relations. – drhab Apr 16 '15 at 18:24
  • Thanks a lot. Maybe you could review my edit and provide some insight? – Socrox Apr 16 '15 at 18:40
  • does D not reflexive? – Surdz May 19 '16 at 02:09

1 Answers1

1

This looks correct to me.

Another way to approach this is to try to partition people based on the relation.

So for part A, you can partition people into distinct sets:

  • First set is all people aged 0
  • Second set is all people aged 1
  • Third set is all people aged 2

Etc. For part B, you can part consider all pairs of people in the population:

  • First set is all children of person 1 and person 2
  • Second set is all child of person 1 and person 3
  • Third set is all children of person 2 and person 3

For the last two examples, these partitions don't exist.

A partition is a division of a set into several non-overlapping sets. For example, you can partition $\{A, B, C, D, E\}$ into $\bigg\{\{A, B\}, \{C, E\}, \{D\}\bigg\}$ but not $\bigg\{\{A, B, C\}, \{C, D, E\}\bigg\}$. The second is not a partition since the sets overlap at $C$.

For part A, if you have Alice aged 20, Bob aged 21, and Carol aged 20, then you can partition $\{\text{Alice}, \text{Bob}, \text{Carol}\}$ as $\bigg\{\{\text{Alice}, \text{Carol}\}, \{\text{Bob}\}\bigg\}$ : one set for every aged 20, on for every aged 21, etc.

Every equivalence relation induces a partition like this. That is one way to check your results.

DanielV
  • 23,556