Try
A relation records which ordered pairs are allowed. Suppose one local routing rule R permits a step from a to b and from b to c, and also includes the shortcut from a to c. A second rule S permits a step from b to a and from c to b. Applying the first rule and then the second is a new relation, not a function: an input may have several possible intermediate or final points.
We write S∘R for “first R, then S.” Thus x is related to z by S∘R exactly when there exists an intermediate y with xRy and ySz. Compute the output pairs before reading the table. Do not assume that the word “first” follows left-to-right written order.
| First R step | Possible S step from its endpoint | Resulting pair in S∘R |
|---|
| a→b | b→a | (a,a) |
| a→c | c→b | (a,b) |
| b→c | c→b | (b,b) |
There are no other R steps, so this table exhausts the composite. Repeated witnesses, if there were any, would not create duplicate elements of the relation: it is a set of pairs. Now reverse the order. From b, S reaches a, and R then reaches b or c. From c, S reaches b, and R then reaches c. Consequently R∘S has pairs (b,b), (b,c), (c,c), different from S∘R.
Predict
The inverse relation R⁻¹ reverses every pair: xR⁻¹y means yRx. Unlike an inverse function, this always exists as a relation, even when R has several outputs or shared outputs. Predict whether reversing a two-step route also reverses the order of its two rules.
It does. A route xRySz reverses to zS⁻¹yR⁻¹x. Therefore (S∘R)⁻¹=R⁻¹∘S⁻¹. The same intermediate y proves both directions of this equality. A correct proof states which pair is being tested and where the witness comes from; checking one finite routing table cannot establish the identity for arbitrary relations.
Next predict which operations preserve transitivity. Recall that transitivity requires every internal two-step route xRyRz to have a shortcut xRz. A relation with no internal two-step routes is transitive, even if it lacks every loop. This vacuous case is useful for counterexamples, not an exception to the definition.
Experiment
On three distinct points p,q,r, take U consisting only of p→q and V consisting only of q→r. Draw each relation separately. Each is transitive because no output in that relation can begin another step of the same relation. Their union contains p→q→r but not p→r, so the union is not transitive. Adding the missing shortcut repairs this particular union; it does not prove all unions are transitive.
For a changed experiment, add all three loops and the reverse of each displayed arrow to the separate relations. The first now identifies p with q, while the second identifies q with r. Each is an equivalence relation: it contains every pair within each of its blocks. List the union and test reflexivity, symmetry and transitivity separately.
Check the three axioms after the change
Both relations contain (p,p), (q,q), (r,r). The first also contains (p,q),(q,p); the second also contains (q,r),(r,q). Each is reflexive and symmetric, and within each block every required transitive shortcut is present. The union is still reflexive and symmetric. It fails transitivity because (p,q) and (q,r) are present while (p,r) is absent. Their intersection contains just the three loops and is an equivalence relation.
Keep a proof ledger with three columns: operation, property claimed, and either a general witness argument or a counterexample whose input hypotheses have been checked. An unexplained missing arrow is not enough unless the starting relations satisfy the promised assumptions.
Understand
All relations in the following arguments are on one fixed set X. Their intersection contains the pairs belonging to both; their union contains the pairs belonging to at least one. Reflexivity quantifies over every element of X, so changing X changes the assertion.
Inverse and intersection preserve transitivity. If xR⁻¹y and yR⁻¹z, then zRy and yRx. Transitivity of R gives zRx, hence xR⁻¹z. If two consecutive pairs belong to R∩S, they belong to R and also to S. Transitivity in each gives the same shortcut in each, so the shortcut lies in the intersection. The union counterexample above explains why replacing “both” with “at least one” breaks that proof: its two premises may come from different relations.
Self-composition preserves transitivity, but need not equal the original relation. If R is transitive, every witness xRyRz gives xRz, proving R∘R is contained in R. The reverse containment is not automatic. For the nonempty relation consisting only of p→q with p and q distinct, the self-composite is empty, although R is transitive. If R is reflexive as well, any pair xRy factors through x using xRxRy, giving the reverse containment and equality.
To prove R∘R itself transitive, start with witnesses xRaRy and yRbRz for its two premises. Transitivity in R gives aRb and then aRz. The route xRaRz now witnesses that (x,z) belongs to R∘R. Merely knowing R∘R is a subset of a transitive relation would not suffice: arbitrary subsets can lose required shortcuts.
Mixed composition can fail. Use five distinct points 0,1,2,3,4. Let R contain only 0→3 and 1→4; let S contain only 3→1 and 4→2. Each is transitive because it has no internal two-step route. Their composite S∘R contains exactly 0→1 and 1→2. It lacks 0→2 and is not transitive. A chain in a mixed composite has steps of types R,S,R,S. Neither input hypothesis permits collapsing the middle S,R pair. This identifies the failure in a proposed proof rather than just exhibiting a number of arrows.
Equivalence intersections. For any family of equivalence relations on X, every diagonal pair belongs to every member. Reversing a pair in every member stays in every member. Two consecutive pairs in every member have their shortcut in every member. Thus the intersection is reflexive, symmetric and transitive. If the family is empty, its intersection relative to X×X is X×X, which also has all three properties. This convention specifies the ambient universe; it does not turn the empty-family intersection into the empty relation.
Apply
A useful stronger hypothesis repairs composition of equivalence relations. Let E and F be equivalence relations and suppose F∘E=E∘F. This is called commutation. We will prove C=F∘E is an equivalence relation rather than assuming its properties transfer automatically.
For reflexivity use xExFx, with intermediate x. For symmetry, reverse a witness xEyFz to zFyEx. This gives a pair in E∘F; commutation places it in F∘E, as required. For transitivity, write two witnesses xEaFy and yEbFz. Their middle segment aFyEb lies in E∘F. By commutation there is t with aEtFb. Now transitivity of E gives xEt, and transitivity of F gives tFz. These two steps witness xCz. The intermediate t need not equal y; its existence is exactly what the commuting hypothesis supplies.
Test the hypothesis with the three-point equivalences from Experiment. There is a route pEqFr, so (p,r) belongs to F∘E. But reversing it fails: r has only itself as an E-neighbor, and rFp is false. Thus (r,p) is absent, and this composite is not symmetric. The hypothesis was doing real work.
Changed case: one relation is the identity
Let Δ consist of every pair (x,x). For any relation E, both E∘Δ and Δ∘E equal E, as a witness calculation shows. They therefore commute. If E is an equivalence relation, the theorem applies and the composite is an equivalence relation. This verifies a family of examples, while the general proof above covers all commuting equivalences.
Continue
In the practice, give complete finite pair lists when asked to refute closure. Check the input axioms before pointing to the missing output shortcut. For general claims, start with arbitrary related points, name witnesses, and construct the witness or reversed pair demanded by the conclusion.
The deeper commuting-equivalence task reuses the same composition convention throughout. Keep “subset” separate from “equal,” especially for R∘R: a transitive relation supplies every shortcut, but without an appropriate intermediate point an existing single edge need not factor into two edges. These distinctions prepare later graph-path and equivalence-class arguments without treating a picture as a universal proof.
