# Homework Help: Reflexive closure

1. Jan 14, 2009

1. The problem statement, all variables and given/known data
Suppose R is a relation on S, and define $$R' = R \cup \{(s,s) \vert s \in S$$. 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, $$R' \subset R''$$

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

1)
it is obvious that $$R \subset R'$$

2) (note: show R' is reflexive).
Let $$aRb \in R$$, thus $$a,b \in S$$, thus $$aRa \in \{(s,s) \vert s \in S\}$$, and $$bRb \in \{(s,s) \vert s \in S \}$$ 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. $$R \subset R''$$. I need to show that $$R' \subset R'' \text{ i.e. } (a,b) \in R' \text{ implies } (a,b) \in R''$$. Proof:
Let (a,b) in R'. Then 1) $$(a,b) \in R$$ or 2) a = b. Assuming 1) it is obvious that $$(a,b) \in R'' \text{ because } R \subset R''$$.

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?