[SOLVED] Equivalence Relations

**Ryaη** · October 22nd 2008, 08:54 AM

Prove that if R is a symmetric, transitive relation on A and the domain of R is A, then R is reflexive on A.

I'm not really sure where to start.

**Plato** · October 22nd 2008, 09:25 AM

Originally Posted by Ryaη

Prove that if R is a symmetric, transitive relation on A and the domain of R is A, then R is reflexive on A.

If $x \in A$ then by the fact that $\mbox{dom}R=A \Rightarrow \quad \left( {\exists y \in A} \right)\left[ {\left( {x,y} \right) \in R} \right]$ .
By symmetry we know that ${\left( {y,x} \right) \in R}$ .
Now you finish.

**Ryaη** · October 22nd 2008, 07:45 PM

Originally Posted by Plato

If $x \in A$ then by the fact that $\mbox{dom}R=A \Rightarrow \quad \left( {\exists y \in A} \right)\left[ {\left( {x,y} \right) \in R} \right]$ .
By symmetry we know that ${\left( {y,x} \right) \in R}$ .
Now you finish.

Would you then go on to say:

Since ${\left( {x,y} \right) \in R}$ and ${\left( {y,x} \right) \in R}$ and since transitivity holds on R, then xRy and yRx $\Rightarrow$ xRx (which is the definition of being reflexive)?

Therefore R is reflexive on A.

**Jhevon** · October 22nd 2008, 07:51 PM

Originally Posted by Ryaη

Would you then go on to say:

Since ${\left( {x,y} \right) \in R}$ and ${\left( {y,x} \right) \in R}$ and since transitivity holds on R, then xRy and yRx $\Rightarrow$ xRx (which is the definition of being reflexive)?

Therefore R is reflexive on A.

yup

i'd word it to fit the definition more, you know, with quantifiers and all that, but yes, that's the basic idea

**Ryaη** · October 22nd 2008, 08:17 PM

How could I word this to fit the definition better?

Let $x \in A$ . $\mbox{dom}R=A \Rightarrow \left( {\exists y \in A} \right)\left[ {\left( {x,y} \right) \in R} \right]$ .
By symmetry we know ${\left( {y,x} \right) \in R}$ .
Since ${\left( {x,y} \right) \in R}$ and ${\left( {y,x} \right) \in R}$ , then by transitivity we know (xRy and yRx) $\Rightarrow$ xRx. (definition of being reflexive)

Therefore R is reflexive on A.

**Jhevon** · October 22nd 2008, 08:19 PM

Originally Posted by Ryaη

How could I word this to fit the definition better?

Let $x \in A$ . $\mbox{dom}R=A \Rightarrow \left( {\exists y \in A} \right)\left[ {\left( {x,y} \right) \in R} \right]$ .
By symmetry we know ${\left( {y,x} \right) \in R}$ .
Since ${\left( {x,y} \right) \in R}$ and ${\left( {y,x} \right) \in R}$ , then by transitivity we know (xRy and yRx) $\Rightarrow$ xRx. (definition of being reflexive)

Therefore R is reflexive on A.

look at how the definitions are in your text, for instance, they usually end with phrases like "for all $x,y \in R$ "

**Ryaη** · October 22nd 2008, 08:28 PM

It's getting kind of late here. Now that I have the main idea down, I'll work on refining it tomorrow. Thank you for all the help!

Thread: [SOLVED] Equivalence Relations

LinkBack

Thread Tools

Display

[SOLVED] Equivalence Relations

Similar Math Help Forum Discussions

Mathematical logic--> Binary relations, orders, and equivalence relations/classes

Question on equivalence relations and equivalence classes

[SOLVED] Help with equivalence relations

Help with equivalence relations

equivalence relations

Search Tags