- #1

- 2,194

- 198

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>