1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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:

    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)}
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted