1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Reflexive closure

  1. Jan 14, 2009 #1
    1. The problem statement, all variables and given/known data
    Suppose R is a relation on S, and define [tex] R' = R \cup \{(s,s) \vert s \in S[/tex]. Prove that R' is the reflexive closure.


    2. Relevant equations
    The reflexive closure of R is the smallest reflexive relation R' that contains R. That is, if there is another R'' that contains R, [tex] R' \subset R'' [/tex]


    3. The attempt at a solution
    I feel like I get it:

    1)
    it is obvious that [tex] R \subset R' [/tex]

    2) (note: show R' is reflexive).
    Let [tex] aRb \in R [/tex], thus [tex] a,b \in S [/tex], thus [tex] aRa \in \{(s,s) \vert s \in S\}[/tex], and [tex] bRb \in \{(s,s) \vert s \in S \}[/tex] Therefore dR'd, and R's is reflexive.

    3) (note: show R' is the smallest such set).
    Let R'' be another reflexive relation on S s.t. [tex] R \subset R'' [/tex]. I need to show that [tex] R' \subset R'' \text{ i.e. } (a,b) \in R' \text{ implies } (a,b) \in R''[/tex]. Proof:
    Let (a,b) in R'. Then 1) [tex] (a,b) \in R [/tex] or 2) a = b. Assuming 1) it is obvious that [tex] (a,b) \in R'' \text{ because } R \subset R'' [/tex].

    Assuming 2): I don't know. I want to say that if a = b, then aR'b is one of the elements making R' reflexive, and therefore would have to be in R''. However, I can't justify this step: consider the following
    S = {1,2,3}
    R = {(1,2)}
    Then
    R' = {(1,1),(2,2),(3,3),(1,2)}.
    And let
    R'' = {(1,1),(2,2),(1,2)}
    Then R'' contains R and is reflexive, but not all the elements of type (s,s) in R' are in R''. Can anyone help me see where I am going wrong?
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?