Lesson plan

Transitive closure

In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of . For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". More formally, the transitive closure of a binary relation on a set is the smallest (w.r.t. ⊆) transitive relation on such that ⊆ ; see . We have = if, and only if, itself is transitive. Conversely, transitive reduction reduces a minimal relation from a given relation such that they have the same closure, that is, ; however, many different with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory.

Back to article

Article summary

In mathematics, the transitive closure of a homogeneous binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of . For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". More formally, the transitive closure of a binary relation on a set is the smallest (w.r.t. ⊆) transitive relation on such that ⊆ ; see . We have = if, and only if, itself is transitive. Conversely, transitive reduction reduces a minimal relation from a given relation such that they have the same closure, that is, ; however, many different with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.