Constructing Hasse diagram from a relation?

238 Views Asked by At

Is there a mathematical way to construct a Hasse / POSET diagram?

For instance, the transitive closure of $R$ will be a set of all the binary relations including those that are transitive. It's my understanding if there are transitive relations or reflexive relations they should be removed for the Hasse diagram. Unsure if there is some mathematical language to describe this.

1

There are 1 best solutions below

5
On BEST ANSWER

If you think of a set $X$ with a relation $R$ as a directed graph (with vertex set $X$ and edge set $R$), then this is called a transitive reduction of the graph, or a minimum equivalent digraph. According to Wikipedia, these differ in that transitive reductions are allowed to introduce new edges (which don't change reachability), whereas minimum equivalent digraphs are always subgraphs of the original. Other sources don't necessarily make this distinction. For a finite acyclic graph, the transitive reduction is unique and is always a subgraph.

If the relation is a partial order, the reduced relation is called the covering relation.