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.