Proving Reflexive Closure of a Relation on a Set

In summary: This is just a matter of checking that for every s in S, (s,s) is in T. 3,4. Since T is reflexive, it is also a subset of r(T). 5,6. Since r(R) is a subset of r(R), it follows that R is also a subset of T. 7,8. Since T is a subset of r(R), it follows that R is a subset of T. 9,10. Since T is a subset of r(R), it follows that r(R) is a subset of T.
  • #1
verty
Homework Helper
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>
 
Physics news on Phys.org
  • #2
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).
Definiton: 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)).
 
  • #3
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.
 
  • #4
verty said:
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.
 

What does it mean to prove reflexive closure of a relation on a set?

Proving reflexive closure of a relation on a set means showing that the relation contains all possible pairs of elements from the set, including those where the elements are related to themselves.

Why is proving reflexive closure important in mathematics and science?

Proving reflexive closure is important because it ensures that a relation on a set is well-defined and complete. In mathematics and science, it is crucial to have a clear understanding of relations between elements in a set in order to make accurate and valid conclusions.

What are the steps to prove reflexive closure of a relation on a set?

The steps to prove reflexive closure are: 1) Identify the relation and its corresponding set, 2) Check if the relation already has reflexive elements, 3) If not, add reflexive elements to the relation until all elements in the set are related to themselves, 4) Verify that the resulting relation is reflexive by checking if all elements in the set are related to themselves.

Can a relation on a set have multiple reflexive closures?

No, a relation on a set can only have one reflexive closure. This is because the reflexive closure is a unique and well-defined concept that ensures all elements in the set are related to themselves.

How is proving reflexive closure related to other concepts in mathematics and science?

Proving reflexive closure is related to other concepts such as transitivity and symmetry, which are also properties of relations on sets. These properties all contribute to the overall understanding and analysis of relations in various mathematical and scientific contexts.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
943
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
Replies
4
Views
653
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
0
Views
436
Back
Top