Results 1 to 4 of 4

Math Help - 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) \in r'
    iii) there exist z_1,z_2,...,z_n such that (x,z_1)\in r', (z_i,z_{i+1})\in r', (z_n,y) \in r' where (x,y) \in r' means (x,y) \in r or (y,x) \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 R this way:

    <br />
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' \&<br />
    <br />
  (x_2,x_3)\in r' \& \dots \& (x_{n-1},x_n)\in r' \& (x_n,y) \in r' \} <br />

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

    note:
    Definition of ~ that you gave is sometimes called 'definition from above', while definition I gave for 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 R.
    In order to show (x,x)\in R can we assume that \exists x_1 such that (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 R.
    (e.g. empty set r would lead to empty R but to ~ = \{(x,x); x \in A\}).
    So set 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' \&
    (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\}<br />
    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: September 19th 2011, 01:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 04:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 03:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 01:08 PM

Search Tags


/mathhelpforum @mathhelpforum