Exercise 8.3
Consider the formal text in Exercise 8.2. Describe the partial order representing the dependencies between the definitions given in this text. (Cf. the end of Section 8.5.)
The following is the formal text in Exercise 8.2
There is a partial order because some definitions depend on others, but some don't.
Let's first list the dependencies.
- $bounded\text{-}from\text{-}above$ does not depend on another definition
- $upper\text{-}bound$ does not depend on another definition
- $least\text{-}upper\text{-}bound$ depends on $upper\text{-}bound$
- $p_4$ depends on $least\text{-}upper\text{-}bound$
- $S$ does not depend on another definition
- $p_6$ depends on $S$
- $p_7$ depends on $bounded\text{-}from\text{-}above$ and $p_6$ (which depends on $S$)
- $p_8$ depends on $least\text{-}upper\text{-}bound$ (which depends on $upper\text{-}bound$) and $p_6$ (which depends on $S$)
The following summarises these dependencies visually.
We can see definitions like $S$ and $bounded\text{-}from\text{-}above$ do not depend on other definitions, but are depended on by other definitions.
We can also see some definitions like $p_7$ depend on more than one definition.
Finally, we can see there is no relation between $bounded\text{-}from\text{-}above$ and $S$. This is why the dependencies are a partial order.
