Partial and Total orders
Due by Fri, 13 Sep 2019
Recall that a relation $R$ on a set $S$ is a subset of $S\times S$. We have defined reflexive, symmetric and transitive relations. Using these we defined equivalence relations. In this exercise we consider another important class of relations, partial orders. We begin with some definitions. Fix a relation $R$ on a set $S$. In the following, it is helpful to think of
$(a, b)\in R$ as $a \leq b$.
- We say that a reflexive relation $R$ is anti-symmetric if
$\forall x,y\in S\ ((x, y)\in R)\land((y, x)\in R)\implies x = y$.
- We say that $R$ is a partial-order if $R$ is reflexive, anti-symmetric and transitive.
- A partial-order $R$ is said to be a total order if, in addition,
$\forall x,y\in S\ (x, y)\in R\lor (y, x)\in R$ (this means that every pair of elements is comparable).
- An element $a\in S$ is said to be a minimum with respect to the partial order $R$ if
$\forall x\in S\ (x, a)\in R \implies x = a$.
- Fact: If $R$ is a total order on a finite set $S$, there is a unique minimum.
Implement the following in a programming language of your choice. If you use scala you can use the code from the lectures (by copy-paste).
- Define a function to check whether a relation $R$ is anti-symmetric.
- Define a function to check whether a relation $R$ is a partial order.
- Define a function to check whether a relation $R$ is a total order.
- On the set
$S=\{2, 3, 4,\dots, 20\}$, construct sets $R$ corresponding to the following relations:
$(a, b)\in R$ if and only if $a - b$ is even.$(a, b)\in R$ if and only if $a \leq b$.$(a, b)\in R$ if and only if $a | b$ (i.e., $a$ is a divisor of $b$).
- Using the functions you defined, check whether each of the above relations are partial orders.
- Using the functions you defined, check whether each of the above relations are total orders.
- Define a function that given a relation $R$ that is a total order, finds that the (unique) minimum with respect to $R$.
- Use this function to find the minimum for the total order among the relations you defined above.
- Define a function that given a relation $R$ on a set $S$ such that $R$ is a partial order, finds all elements
$a\in S$ such that $a$ is a minimum with respect to $R$.
- Use this function to find all the minima for the partial orders among the three relations you defined above.