# equivalence relation

• Oct 22nd 2013, 11:19 AM
ronanbrowne88
equivalence relation
question

An equivalence relation R defined on a set contains
the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R A x A.

have to do this for a assignment but have no idea where to start I missed the class covering this. could anyone tell me the basic technique how to solve this so i know where to start at least!
• Oct 22nd 2013, 11:32 AM
SlipEternal
Re: equivalence relation
An equivalence relation on A is a subset of A x A with certain properties. The three pairs you show do not currently satisfy those properties.

1. You need reflexivity: For all $\displaystyle a \in A,(a,a) \in R$.
2. You need symmetry: If $\displaystyle (a,b) \in R$, then $\displaystyle (b,a) \in R$.
3. You need transitivity: If $\displaystyle (a,b)\in R$ and $\displaystyle (b,c) \in R$ then $\displaystyle (a,c) \in R$.
• Oct 22nd 2013, 11:43 AM
ronanbrowne88
Re: equivalence relation
sorry wrote question wrong

An equivalence relation R defined on a set A ={1,2,3,4}contains
the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R ≠ A x A.
• Oct 22nd 2013, 11:44 AM
SlipEternal
Re: equivalence relation
What I am saying is, add pairs until you satisfy those three properties.
• Oct 22nd 2013, 11:48 AM
ronanbrowne88
Re: equivalence relation
im sorry i dont understand
• Oct 22nd 2013, 12:04 PM
SlipEternal
Re: equivalence relation
Check: for any $\displaystyle a \in A$, do you have $\displaystyle (a,a) \in R$? No. So, add those pairs that you are missing. $\displaystyle (1,2) \in R$. Do you have $\displaystyle (2,1) \in R$? No. So add that pair. Etc.

Edit: By add those pairs, I mean add the pairs to the list of pairs you know must be in $\displaystyle R$. You started with the three given pairs. Then, from those three, you use the properties to figure out which other pairs must also be in $\displaystyle R$. In the end, you should find 10 pairs in $\displaystyle R$. If another equivalence relation $\displaystyle R'$ has $\displaystyle R \subseteq R'$ and you know $\displaystyle R' \setminus R \neq \emptyset$, then it is easy to show that $\displaystyle R' = A \times A$. In other words, $\displaystyle R$ is the unique equivalence relation on $\displaystyle A$ with those three pairs.
• Oct 22nd 2013, 03:35 PM
Plato
Re: equivalence relation
Quote:

Originally Posted by ronanbrowne88
question
An equivalence relation R defined on a set contains
the pairs (1,1 ), (1,2 ), ( 2,3). Find R, given that R A x A.
have to do this for a assignment but have no idea where to start I missed the class covering this. could anyone tell me the basic technique how to solve this so i know where to start at least!

Define $\displaystyle F=\{(1,1),(1,2),(2,3)\}$. The diagonal is $\displaystyle \Delta_A=\{(1,1),(2,2),(3,3),(4,4)\}$

Define $\displaystyle G=F\cup\Delta_A$ and $\displaystyle H=(G\circ G)\cup G$

Define $\displaystyle R=H\cup H^{-1}$.

Show that $\displaystyle R$ is an equivalence relation.