Abstract

• The transitive closure of R is the smallest relation S for which: –R⊆S, – S is transitive. • To express ^r one would need an ‘infinite formula’: {(x, y) | R(x, y) ∨ ∃z(R(x, z) ∧ R(z, y)) ∨∃z, v(R(x, z) ∧ R(z, v) ∧ R(v, y)) ∨∃z, v, w(R(x, z) ∧ R(z, v) ∧ R(v, w) ∧ R(w, y)) ∨ · · ·.