1

I was reading this definition of transitive closure of a relation, where is written that the transitive closure is minimal:

the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal (Lidl and Pilz 1998:337).

I couldn't find any definition of a minimal relation on the web. When is a relation minimal?

danza
  • 1,205

1 Answers1

2

"Minimal" does not really mean something by itself.

What we can speak of is a minimal thing with such-and-such property, which means a thing that (a) has such-and-such property, but (b) no smaller thing has such-and-such property.

Concretely, in a definition such as

If $R$ is a relation, then its transitive closure $R^+$ means the minimal transitive relation that contains $R$.

what it says is that

  1. $R^+$ is a transitive relation that contains $R$ as a subset, and
  2. There is no proper subset of $R^+$ that is both transitive and contains $R$.

A definition of this form secretly implies a claim that there is exactly one $R^+$ that satisfies those two conditions. In general this needs to be proved. In the present case one can easily see that we can find $R^+$ as the intersection of all subsets of $X\times X$ that are transitive and contain $R$.

hmakholm left over Monica
  • 286,031