Results 1 to 4 of 4

Thread: Equivalence Relations

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    7

    Equivalence Relations

    I need help to get started with proving the 'only if' part of the following claim:

    Let r be a relation. Define ~ to be the intersection of all equivalence relations containing r (So ~ is an equivalence relation.)

    Show that x~y if and only if one of the following holds:
    i) x=y
    ii) (x,y) $\displaystyle \in$ r'
    iii) there exist $\displaystyle z_1,z_2,...,z_n$ such that $\displaystyle (x,z_1)\in r', (z_i,z_{i+1})\in r', (z_n,y) \in r' $ where (x,y) $\displaystyle \in$ r' means (x,y) $\displaystyle \in$ r or (y,x) $\displaystyle \in$ r and i=1,...,n-1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Aug 2009
    Posts
    25
    Hello !
    define relation $\displaystyle R$ this way:

    $\displaystyle
    R = \{(x,y); (\exists n \in \mathbb{N})(\exists x_1, x_2,\dots, x_n) (x,x_1)\in r' \& (x_1,x_2)\in r' \&
    $
    $\displaystyle
    (x_2,x_3)\in r' \& \dots \& (x_{n-1},x_n)\in r' \& (x_n,y) \in r' \}
    $

    It is easy to verify that $\displaystyle R$ is an equivalence relation and that $\displaystyle r \subseteq R$.
    Then consider an arbitrary equivalence relation $\displaystyle S$ such that $\displaystyle r \subseteq S$ and, again easily, show that $\displaystyle R \subseteq S$.
    So, you showed that ~ $\displaystyle = R$ !! (and this answers your question).

    note:
    Definition of ~ that you gave is sometimes called 'definition from above', while definition I gave for $\displaystyle R$ is called 'definition from below'. The claim you are proving states that they are equivalent.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    7
    Thanks for the reply!
    I have verified everything except for the reflexivity of $\displaystyle R$.
    In order to show $\displaystyle (x,x)\in R$ can we assume that $\displaystyle \exists x_1$ such that $\displaystyle (x,x_1)\in r'$?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2009
    Posts
    25
    You're right, I omitted to add the diagonal to the definition of $\displaystyle R$.
    (e.g. empty set $\displaystyle r$ would lead to empty$\displaystyle R$ but to ~ = $\displaystyle \{(x,x); x \in A\}$).
    So set $\displaystyle R = \{(x,y); (\exists n \in \mathbb{N})(\exists x_1, x_2,\dots, x_n) (x,x_1)\in r' \& (x_1,x_2)\in r' \&$
    $\displaystyle (x_2,x_3)\in r' \& \dots \& (x_{n-1},x_n)\in r' \& (x_n,y) \in r' \} \cup \{(x,x); x \in A\}
    $
    and it's allright. Sorry for confusion.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Sep 19th 2011, 01:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Apr 29th 2010, 04:30 PM
  3. Replies: 10
    Last Post: Jan 14th 2010, 12:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: Oct 1st 2009, 03:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 16th 2008, 01:08 PM

Search Tags


/mathhelpforum @mathhelpforum