Write a function/program in any programming language to list all the *closed formulas* in the *language of sets*. Recall that this is the *first-order language* with a single constant $\phi$ and a relation $\in$ of degree $2$ (plus the equality relation). A *closed formula* means a formula with no free variables.

The solution can be either a function that we can import and interact with in a REPL/console/notebook or a program to which we give appropriate input (as below) and get output as desired. Concretely:

- Fix representations in some data structures for
*terms*and*formulas*in the language of sets. - Have a function/method giving an output string for each formula (any unambiguous and readable representation is fine. One way is to use unicode for mathematical symbols).
- Define a function (or write a program) to list
`n`

closed formulas given an integer`n`

(as an argument to a function or input to a program). Listing the first`n`

functions in any order is fine, but any given formula should appear for large enough`n`

. For example if`n`

is large enough the formula $\forall A \forall B\exists C(\forall x\ (x\in C \iff (x\in A \lor x\in B )))$ should be output (in your chosen string representation).

**Remark:** It may be useful to recursively define a function giving *all* formulas (including those that are not closed) involving a given finite set of variables and with complexity at most `k`

for some appropriate definition of complexity.

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.