Proving Reflexive Closure of a Relation on a Set

[verty]

Suppose R is a binary relation on a set S. The reflexive closure of R is the smallest reflexive relation R' that contains R. (Smallest in the sense that if R'' is some other reflexive relation that contains R, R' is a subset of R'')

Supposed we are given a relation R on a set S. (It was earlier explained that if a relation R is 'on' a set S, dom(R) = S.) Define the relation R' as follows:

R' = R union {(s,s): s is a member of S}

Show that R' is the reflexive closure of R.

I've started to read a book called "Types and Programming Languages" and this excerpt is from the section entitled "Mathematical Preliminaries".

Now I can justify the conclusion to myself by reflecting that there is no tuple in R' that is neither a member of R nor (s,s) with s a member of dom(R), and none of those tuples can be removed because if an (s,s) tuple is excluded, the relation will no longer be reflexive for all s in dom(R), and if one of the other tuples "(p,q), p <> q" is excluded, it will no longer be the case that R is a subset of R'.

But I don't imagine this was what was wanted, an informal discussion. So I'm wondering how this would be said more formally, with reasons included because I imagine reasons should be given at each step.

Also this looks to be a proof by contradiction, so I'm wondering if there is a better way to show this.

Okay, so after writing the above, I decided to try and write out what I hoped would be a good attempt at proving it, but after writing the next part I realize #2 is wrong. I presumably can't show that R' meets the definition by assuming it does and then showing no proper subset of it does. If I must show that it meets the definition, I should show how it meets each part of the definition. Well I'm tired now, I'll think about this perhaps on Saturday, but if you can give be some advice about proofs in general, please do.

My mishapen attempt:

#1: Given: R is a relation on S, R' = R union {(s,s): s is a member of S}
#2: Show: for all relations T, T subset R' and R subset T and T reflexive implies T = R'

#3: Assume #2 false: exists T such that T subset R', R subset T, T reflexive and T <> R'; Show contradiction.

#4: Let U denote R' - T
#5: From 3 and 4, since T subset R' and T <> R', therefore U <> 0

#6: From 1 and 5, let U = {V union W for some sets V and W: V,W subset R'; V subset R; W subset {(s,s): s is a member of S}}

#7: From 3 and 6, V subset R subset T, therefore V subset T

#8: From 4 and 6, V subset U = R' - T

#9: From 7 and 8, since V subset T and V subset R' - T, V = 0 (how do I show this?)

#10: Since U = V union W (from 6) and V = 0 (from 9), therefore U = W

#11: Since U = W (from 10) and U <> 0 (from 5), therefore W <> 0

#12: Since T is reflexive (from 3), for all s member of dom(T), (s,s) member of T

#13: for all (p,q) member of W, p = q (from 6)

<okay, been at this for about 80 minutes, fast forwarding now>

#14: Since W = R' - T and W <> 0 and all tuples in W are reflexive tuples and W intersect T = 0 (why?), and W union T = R', therefore there exists p member of dom(W) subset S for which there does not exist (p,p) in T, hence it is not the case that... <brain crashing at this point>

 

[fopc]

Here's an outline of one approach to a proof.
Given:
Arbitrary relation R on SxS.
Relation E = {(x,x)| for all x in S} (the "equality" relation on SxS, and often denoted R^0).
definition: Reflexive closure of R, denote r(R), has following properties:
1. r(R) is reflexive.
2. R is a subset of r(R).
3. For any reflexive relation R' on SxS [(R a subset of R') -> (r(R) a subset of R')]

Proposition: r(R) = (R U E).
Proof: (direct)
Let T = (R U E), and show that T satisfies the definition of reflexive closure stated above.

1,2. Show that T is reflexive and that R is a subset of T. Pretty obvious.
3. Assume a T' that is reflexive on SxS and that R is a subset of T'.
Show T is a subset of T', i.e., show that
for arbitrary (a,b) [(a,b) in T -> (a,b) in T'].
Now if (a,b) is in T, then either a=b or (a,b) is in R. Again, pretty obvious.
Consider the two cases:
If a=b, then (a,b) is in T', since T' is reflexive.
If (a,b) is in R, then (a,b) is in T', since R is a subset of T'.
Consequently, we shown that T is a subset of T', and
the definition of r(R) is satisfied for T (i.e., T = r(R)).

 

[verty]

Thank you fopc. I am taking note of a number of things.

Firstly, I see you define R well before proceeding. You also choose to use SxS because you know that further on you will need to speak of the elements individually.

Then, I see you list the properties of a reflexive closure knowing you will show them in order.

Then you state the problem and show those properties in order. This is obviously a pattern to be reused. I also see that this shows only as much as it needs to show. It makes no assumptions about S, for instance.

Thank you, I can see that mathematical thinking is different to any other type of thinking; it is thinking out of context, perhaps pure thought or reasoning.

To say that one is given a set or a relation seems odd because a set or relation is not something that can be given as such. I can't say "here, let me give you a set". So this is giving in a new sense. Perhaps it would be better phrased as "If I were to be given some set S with such and such properties, etc, I could know the following about that given set S".

So mathematics is then reasoning about quantity abstracted, and for it to be useful it requires some concrete realisation. Or rather, we practice the abstracted reasoning so that when we find a realisation of it, we can deduce things straight away. So I should probably say that mathematics is practice. To do mathematics is to practice mathematics, and there is no more to it than the practice.

Abstract algebra would merely be a higher level of abstraction, not different in kind from 1+1=2. I should also say then that foundations are arbitrary; mathematics has extremities rather than foundations.

Ok, I think I have a much clearer idea of things now. I have got more than expected from this thread.

 

[honestrosewater]

To say that one is given a set or a relation seems odd because a set or relation is not something that can be given as such. I can't say "here, let me give you a set". So this is giving in a new sense. Perhaps it would be better phrased as "If I were to be given some set S with such and such properties, etc, I could know the following about that given set S".

The mathematical objects are given in the sense that some fact or statement about them is assumed to be true (or to be a theorem). In this case, their existence is assumed. (You can give descriptions of mathematical objects that cannot possibly exist, so whether an object exists is a question that needs to be decided.) The given statements are just the statements that you are assuming to be true, in contrast to those statements that you are trying to prove. Given statements are also generally called assumptions, hypotheses, or premises, and usually in a more specific context, axioms or postulates.