What does "descends to a partial order" imply?

62 Views Asked by At

For context:

For $i \in \Sigma$, we let $[i]=\{j \in \Sigma: i \geq j \geq i\}$ and define $\Gamma_A := \{[i]:i \geq i\}$. The relation descends to a well-defined partial order on the set $\Gamma_A$,

where $i, j$ are vertices in a directed graph, and $\Sigma$ is the vertice set. The relation $i \geq j$ implies there exists a path $\mu = i\cdots j$ (that is, $s(\mu)=i$ and $r(\mu)=j$).

Does this simply mean, as a restriction to the given set, it is a partial order, whereas it is not, or may not be, on the superset? Or, is there some other intricacy going on here?

Thanks :)

1

There are 1 best solutions below

1
On BEST ANSWER

I'll try to answer the question in view of the comment (which should be integrated into the question to make it self-contained), and assuming that the graphs under consideration are directed graphs.

Note that the operation $[i]$ forms equivalence classes, since $i\ge j\ge i$ implies $j\ge i\ge j$. To make sense of the statement that the relation "descends" to a well-define partial order on $\Gamma_A$, we have to a) define a relation on $\Gamma_A$, b) check that it is well-defined, and c) check that it is a partial order (i.e. that it is reflexive, antisymmetric and transitive).

The natural relation to consider on $\Gamma_A$ is the one in which $[i]\ge[k]$ iff $i\ge k$. This is well-defined if it is independent of the representatives $i$ and $k$ used to represent the equivalence classes $[i]$ and $[k]$. This is indeed the case, since the definition of the equivalence classes ensures that there is a path from every representative to every other representative, so a path from $i$ to $k$ can be extended to a path from $i'$ to $k'$ for any other representatives $i'\sim i$ and $k'\sim k$.

Reflexivity is clear: There is a path from $i$ to $i$. This was already given in the original relation.

The original relation was not antisymmetric (due to the potential presence of cycles), but the new one is: $[i]\ge[j]\ge[i]$ implies $j\in[i]$ and thus $[i]=[j]$.

The original relation was already transitive (if there is a path from $i$ to $j$ and one from $j$ to $k$, they can be concatenated to form a path from $i$ to $k$). This transitivity is inherited by the new relation.