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:

1. Fix representations in some data structures for terms and formulas in the language of sets.
2. 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).
3. 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).

1. Define a function to check whether a relation $R$ is anti-symmetric.
2. Define a function to check whether a relation $R$ is a partial order.
3. Define a function to check whether a relation $R$ is a total order.
4. On the set $S=\{2, 3, 4,\dots, 20\}$, construct sets $R$ corresponding to the following relations:
   1. $(a, b)\in R$ if and only if $a - b$ is even.
   2. $(a, b)\in R$ if and only if $a \leq b$.
   3. $(a, b)\in R$ if and only if $a | b$ (i.e., $a$ is a divisor of $b$).
5. Using the functions you defined, check whether each of the above relations are partial orders.
6. Using the functions you defined, check whether each of the above relations are total orders.
7. Define a function that given a relation $R$ that is a total order, finds that the (unique) minimum with respect to $R$.
8. Use this function to find the minimum for the total order among the relations you defined above.
9. 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$.
10. Use this function to find all the minima for the partial orders among the three relations you defined above.