Prove Reflexive Closure of R on S

[icantadd]

Homework Statement

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.

Homework 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''$$

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?

 

[mighty2000]

Your proof is mostly correct, but there are a few small errors and missing pieces. Here is a corrected version:

1) It is indeed obvious that R ⊆ R'.

2) To show that R' is reflexive, you need to show that for any s ∈ S, (s,s) ∈ R'. This is because the reflexive closure of R is defined as the smallest reflexive relation that contains R, so you need to show that R' contains all the elements of the form (s,s). Your argument for this part is correct, but you should specify that aRb ∈ R implies (a,b) ∈ R' (instead of dR'd).

3) To show that R' is the smallest such set, you need to show that for any other reflexive relation R'' that contains R, R' ⊆ R''. Your argument for this part is also mostly correct, but there are a few issues:

- When you say "Assuming 1)", you should specify that this is assuming (a,b) ∈ R. This is because R' contains both (a,b) ∈ R and (a,a) ∈ {(s,s) | s ∈ S}.
- When you say "it is obvious that (a,b) ∈ R'' because R ⊆ R''", this is not quite correct. The fact that R ⊆ R'' only tells us that (a,b) ∈ R'' or (b,a) ∈ R''. We need to use the fact that R'' is reflexive to show that (a,b) ∈ R''.
- Your example with S = {1,2,3}, R = {(1,2)} and R'' = {(1,1),(2,2),(1,2)} is not a counterexample. In fact, R'' is not a reflexive relation because (3,3) is not in R''. So this example actually supports your argument.

Here is a corrected version of the proof:

Let R'' be another reflexive relation on S such that R ⊆ R''. To show that R' ⊆ R'', we need to show that for any (a,b) ∈ R', we have (a,b) ∈ R''. There are two cases:

- If (a,b) ∈ R, then this is already true because R ⊆ R''.
- If a = b, then (a,a) ∈ {(s,s) | s ∈ S}.