An equivalence is symmetric (under
reversal), transitive and reflexive. Each of these properties interacts
sensibly with repetition, so let's examine
them severally and jointly. The universal identity fits poorly in these
discussions, so the treatment here mostly avoids repeat(0). When n is positive
(i.e. not 0), I'll describe repeat(n, r) as a positive repeat
of r; when
n is in natural m, I'll describe repeat(m, r) as a later repeat
of r than
repeat(n, r) and repeat(n, r) as an earlier repeat
of r than repeat(m,
r).
Suppose that we have some natural n for which repeat(i) commutes with reverse for all i in n. If n is empty then repeat(n, r) and repeat(n, reverse(r)) are the universal identity, which is its own reverse; thus repeat(0) does indeed commute with reverse. Otherwise, n is i&unite;{i} for some i in n and we can use the basic properties of repeat to obtain repeat(n, reverse(r)) = repeat(i, reverse(r))&on;reverse(r) = reverse(repeat(i, r))&on;reverse(r) = reverse(r&on;repeat(i, r)) = reverse(repeat(i&unite;{i}, r)) = reverse(repeat(n, r)), for arbitrary relation r, whence reverse commutes with repeat(n). As this arises whenever reverse commutes with repeat(i) for each i in n, we can induce that reverse commutes with every output of repeat.
In particular, this implies that every repeat of a symmetric (equal to own reverse) relation is also symmetric.
A relation is transitive precisely if it subsumes its composite with itself, i.e. its image under repeat(2); and any relation is (hence subsumes) its own image under repeat(1). As I'll now show, this generalises to: any positive repeat of a transitive relation subsumes each later repeat of it.
Given a transitive relation r, suppose we have a positive natural n for which every earlier positive repeat of r subsumes repeat(n, r); this holds fatuously for n = 1 and the definition of transitivity says it holds for n = 2 (when the only earlier positive repeat is r itself). Now n is positive, so it's i&unite;{i} for some i in n; for this i, repeat(n&unite;{n}, r) = repeat(i, r)&on;(r&on;r) and r is transitive so subsumes r&on;r; thus repeat(n, r) = repeat(i, r)&on;r subsumes repeat(i, r)&on;(r&on;r) = repeat(n&unite;{n}, r). Aside from repeat(n, r), all other positive repeats of r earlier than repeat(n&unite;{n}, r) are earlier than repeat(n, r), so subsume repeat(n, r), which we've just seen subsumes repeat(n&unite;{n}, r); thus every earlier positive repeat of r subsumes repeat(n&unite;{n}, r) also. By (iterative) induction we can thus infer that every positive repeat of r subsumes all later repeats of r.
The interaction of multiplication with the the ordering on {naturals} implies that 2.n > n for any positive natural n; consequently, repeat(n, r)&on;repeat(n, r) = repeat(2, repeat(n, r)) = repeat(2.n, r) is a later repeat than repeat(n, r) which thus subsumes its self-composite so is transitive; every repeat of a transitive relation is likewise transitive.
Conversely to transitivity, consider a relation that is subsumed by its repeat(2); i.e. an r for which r&on;r subsumes r. Suppose we have some positive natural n for which repeat(n, r) subsumes every earlier positive repeat of r, notably including r itself; this fatuously holds for n = 1. As n is positive, it is i&unite;{i} for some i in n and repeat(n&unite;{n}, r) = repeat(n, r)&on;r = repeat(i, n)&on;(r&on;r) which subsumes repeat(i, n)&on;r = repeat(n, r) since r&on;r subsumes r; so repeat(n&unite;{n}, r) subsumes repeat(n, r) and, via it, all earlier positive repeats of r. This being true whenever repeat(n, r) subsumes all earlier positive repeats of r, (iterative) induction implies that this holds true for all positive n.
Note that positive repeats of a relation can subsume later ones without the relation being reflexive (which, as we'll see below, would suffice): for example, the strict ordering of the rationals or reals is equal to all of its positive repeats, thanks to there being plenty of rationals (and reals) between any two reals or rationals; yet no real or rational is < itself or > itself. The case of a co-transitive relation with no fixed points is thus potentially interesting to study; in order to be subsumed by its self-composite, without using fixed points to make this easy, it has to have an intermediate value, via which the composite relates, between any two values it does relate. This inescapably gives you an infinite sub-division, after the fashion of the ordering on rationals.
As for transitivity, each positive repeat of a relation with this converse-to-transitive property inherits this property, thanks to the self-composite being a later repeat of the original relation because 2.n > n for positive n.
A relation is reflexive precisely if every (left or right) value of it is a fixed point (i.e. if it relates x to y then it also relates x to x and y to y). Thus its collections of left and right values are equal; and the relation subsumes this collection. If r relates x to y, hence also y to y, then r&on;r relates x via y to y, so r&on;r subsumes r; so any reflexive relation has the converse-to-transitive property just discussed and all later repeats of it subsume all earlier positive repeats.
Now any positive repeat of a relation r can be written as r&on;repeat(n, r) = repeat(n, r)&on;r for some natural n, using a basic property of repeat. Since every left value of a composite is a left value of the left component and every right value of the composite is a right value of of the right component, we can infer that every left or right value of any positive repeat of r is a left or right (as appropriate) value of r, hence that the values of a positive repeat of r are all values of r. Since each positive repeat of r subsumes r, its collection of values subsumes that of r; and we've just shown the converse of this, so all positive repeats of a reflexive relation have the same collection of values.
A transitive relation that also has the converse-to-transitive property above is thus necessarily equal to all of its later repeats; this, in particular, applies to any transitive reflexive relation. An equivalence is just one of these last that's also symmetric. In particular, every collection is an equivalence, hence equal to all its repeats (as should be no surprise).
We can restrict any relation (on both sides) to its collection of fixed points; the result (may well be empty but) is necessarily the maximal reflexive relation the original subsumes. We can equally unite any relation with its collection of values to make it reflexive; this is the minimal reflexive relation that subsumes the original. We can extract a (maximal) symmetric part of a relation by intersecting it with its reverse; or unite it with its reverse to obtain a symmetric relation (the minimal one subsuming it). I'm not sure there's much of interest to say about any of these. However, inducing transitivity is often useful; and there's a dual to it that I may as well cover, too.
The transitive closure
of a relation, r, is defined to be T(r) =
unite(: repeat(n, r)&on;r ←n :{naturals}) = unite({positive repeats of
r}). Whenever T(r) relates x to y and y to z, there are some positive naturals
n, m for which repeat(n, r) relates x to y and repeat(m, r) relates y to z, by
virtue of T(r) being the union it is. A
basic property of repeat then gives us repeat(n, r)&on;repeat(m, r) =
repeat(k, r) for some positive natural k, so T(r) subsumes repeat(n,
r)&on;repeat(m, r), which relates x via y to z, ensuring that T(r) is transitive
for every relation r. Given the way that it's constructed, furthermore, any
transitive relation that subsumes r must also subsume T(r), so T(r) is also the
intersection of all transitive relations that subsume r: it's
the minimal transitive relation that subsumes r.
One can also define a core
for any relation by intersecting its
positive repeats, C(r) = intersect(: repeat(n, r)&on;r ←n |{naturals}).
Suppose C(r) relates x to z; then, for every natural k, repeat(k, r) relates x
to z. Now, for any naturals n, m there is some natural k for which repeat(n,
r)&on;repeat(m, r) = repeat(k, r), so repeat(n, r)&on;repeat(m, r) relates x to
z; this being true for all n, m it is also true for the intersection of
repeat(n, r)&on;repeat(m, r) over all n, m; which is just C(r)&on;C(r); so this
also relates x to z. Thus C(r)&on;C(r) subsumes C(r), the
converse-to-transitive property discussed above. Dual to the case for
transitive closure, C(r) is the maximal co-transitive relation that r subsumes;
it subsumes any other co-transitive relation that r subsumes.
If r doesn't subsume the intersection of later positive repeats of r, then the r in C(r)'s intersection doesn't relate some x to z, that all later positive repeats do relate; consequently C(r) won't subsume C(r)&on;C(r), so C(r) isn't transitive. One could define the core of r to be unite(: intersect(: repeat(m, r) ←m :{natural m: n in m}) ←n |{naturals}), the union, over naturals n, of the intersection of all repeats of r (strictly) later than repeat(n, r); this would then be transitive and co-transitive, but r might not subsume it (nor need it subsume r), making it a poor choice of thing to specify as core of r. The dual intersection – over naturals n, of the union of all repeats of r later than repeat(n, r) – would likewise be transitive and co-transitive, but might not subsume r (nor need r subsume it).
Since composing mappings gives a mapping and composing monics gives a monic, each repeat(n, r) for positive natural n is a mapping if r is and a monic if r is, hence also iso if r is. However, uniting many mappings (or monics) won't necessarily give you a mapping (or monic) as the union, so the transitive closure isn't necessarily a mapping or monic when the relation from which it's derived is. The core, in contrast, is trivially a mapping or monic if derived from a mapping or monic, since it's subsumed by the source relation and the uniqueness properties defining mapping and monic are inherited by anything subsumed by a relation with those properties.
Every fixed point of a relation is also a fixed point of both its transitive closure and its co-transitive core. Earlier results ensure that the transitive closure of a transitive relation is that relation; and the core of any converse-to-transitive relation (notably including any reflexive relation) is that relation. The core of a transitive relation is necessarily transitive (albeit possibly empty), the transitive closure of a reflexive relation is necessarily reflexive (it has the same collection of values as the original, which it subsumes) and both the transitive closure and the core of a symmetric relation are symmetric.
Written by Eddy.