Recipe

Test a relation for transitivity

Use when: you're given a relation R on a set A and asked whether every two-step chain already has its shortcut pair in R

Goal: an answer, backed by either a complete check of every chain or one specific broken chain

Taught in Transitive relations

1. 1

   Scan R for every pair whose second entry matches another pair's first entry; each match is one chain to check.

   Example

   R = \{(1,2),(2,3),(1,3)\} on \{1,2,3\} has one chain: (1,2) with (2,3), sharing the middle element 2.

   Why: transitivity only makes a claim about chains that actually exist in R, so chains that are not present need no checking.

2. 2

   A chain (a,b) and (b,c) requires the pair (a,c) to also be in R; check whether it actually is.

   Example

   The chain (1,2) with (2,3) requires (1,3); that pair is already in R, so this chain checks out.

   Why: transitivity is defined exactly as "every such shortcut pair must be present," not "most of them."

3. 3

   Every chain's shortcut pair present means R is transitive; even one missing shortcut pair makes R not transitive.

   Example

   For R = \{(1,2),(2,3)\} on \{1,2,3\}: the chain (1,2),(2,3) requires (1,3), which is missing, so R is not transitive.

   • every chain's shortcut pair is present — R is transitive.
   • at least one chain's shortcut pair is missing — R is not transitive; name that specific missing pair.

   Why: transitivity is a universal condition across every chain in R, so a single counterexample settles the answer.