R generates the equivalence relation a ~ b if and only if there exist elements x1, x2, ..., xn in X such that a = x1, b = xn, and (xi,xi+ 1)∈R or (xi+1,xi)∈R, for i = 1, ..., n-1.
No. Let N be the set of natural numbers and R be the binary relation on N whose only members are (4,5) and (10, 12). there is a unique equivalence relation on N that extends R and is a subset of every equivalence relation that extends R. For each n, (n, n) is in this relation. Thus, this relation does not have the property. Let E be this equivalence relation. There are two ways to construct E from R. Let Sigma be the collection of all equivalence relations on N that extend R. Sigma is non- empty. E is the intersection of the Sigma. The other way to construct E is to construct the chain of binary relations on N; R1,..., Rn,... where Rn is a subset of Rn+1, R1 is the union of R and NxN and Rn+1=RnU{(x,y): (y, x) is in Rn}U( (x, z): there is y such that (x, y) and (y, z) are in Rn}. E is the the union of this chain. E does not
The property you are looking for holds for the transitive closure of R. Let C be the transitive closure of R. As in the case of E, there are two ways to construct C. Let Delta be the class of transitive relations on N that extend R. Delta is nonempty as NxN is in Delta. C is the intersection of Delta. The second way to construct C is to build a chain of binary relations on N as above where R1=R and Rn+1=RnU{ (x,y): the is Z such that (x,z) and (z, y) and in Rn} . C is the union of this chain. C has the property you mention.
In the question you forgot to specify the set on which the relation R is given or at least the needed properties.
If R would be similarity on the set of all triangles (which already is an equivalence relation, what should xi+1 be?
I've decided to state here the question as it is in the book I am reading:
"Let R be a relation on set S. Prove that, in the equivalence relation generated by R, s ~ p if and only if there is a finite sequence (s, s1, s2, ..., sn, p)" such that either sRs1 or s1Rs, s1Rs2 or s2Rs1,..., and either snRp or pRsn."
Sorry, I messed up with indexes in the source question. So now you could see George first example is actually good. And reflexive closure will have an empty sequence in that case!
To build the equivalence relation we need to take reflexive and symmetrical closures too, of course: tsr(R), where 'r' - is ref. closure, 's' - sym. closure and 't' - transitive closure. Order is important here. See, for example: http://web.cecs.pdx.edu/~harry/discrete/slides/Section4.2.pdf
It is not hard to see that reflexive and symmetrical closures will not change the situation for the path sequences.
So all that we need is to show that transitive closure will take us out of the path no more than 1 new element of S, which is not in R.
Good scatch of proof for that is here: http://en.wikipedia.org/wiki/Transitive_closure#Existence_and_description
I agree with the statement of that problem in the case of the finite sets. But, could anyone explain me why we will always have only finite sequence (s, s1, s2, ..., sn, p) even when S and R are infinite sets? If I am wrong somewhere here, please note where then.
Thanks, everybody!
To answer Breuer's question. Let R be any relation on set A. Let C be the transitive closure of R. One way to construct R is to take the family {Rn: n in omega} where R0=R and for each n Rn+1=RnU{(x, y): x and y are in A and there is z such that (x, z) and (z, y) are both in Rn}. C=U{Rn: n in omega}. Let T={n: n is in omega and for all x, y if (x, y) is in Rn, then either (x, y) is in R or there is a finite sequence of members of A such that x is the first member of the sequence, y is the last member of the sequence and if w and z are such that z is the immediate successor of w in the sequence, then (w, z) is a member of R}. By mathematical induction, T is omega. Let (x, y) be any member of C. By construction there is a least n such that (x, y) is in Rn.
- Badges
- Science topic
- Similar topics
- Mathematics