How do we show a total ordering using the < symbol.

146 Views Asked by At

Let's say we have a relation R (which is a partial ordering) where x R y means that x comes before or precedes y in the ordering.

We have the following information about R

(a R c)|(c R g)| (g R d)| (d R f) | (g R e) | (e R h) | (h R f) | (b R h) | (i R b) | (i R e)

How do we show total ordering < that is compatible with what we know about the partial ordering above?

Do we just show that each letter is < the other?

1

There are 1 best solutions below

2
On

One obvious thing you can do is to find an actual order the elements compatible with the given information. Here is one:

$$a<c<g<d<i<b<e<h<f$$