# Maximal and minimal elements of the partial order relation

Let $A=\{1,2,3,4\}$ and $H$ is the set of antisymmetric relations on $A$.

I think that $H = \{(1,2),(2,3),(3,4),(1,3),(1,4),(2,4)\}$.

How would I find the minimum/maximum and min/max elements?

• That is one antisymmetric relation (even asymmetric), not a set of relations. Nov 28, 2013 at 18:30
• H is the set of all antisymmetric relations on $A$, not just one relation: you've posted one element (one relation) of $H$. Nov 28, 2013 at 18:31
• So my H is just one possibility?
– Paul
Nov 28, 2013 at 18:33

You’ve misunderstood the question: your $H$ is simply one of the antisymmetric relations on $A$. The $H$ of the problem is the set of all antisymmetric relations on $A$; its members are themselves whole relations on $A$, not ordered pairs of elements of $A$. Some other members of $H$, chosen pretty arbitrarily:

\begin{align*} &R_1=\{\langle 1,1\rangle,\langle 2,2\rangle,\langle 3,3\rangle,\langle 4,4\rangle\}\\ &R_2=\{\langle 1,1\rangle,\langle 2,2\rangle,\langle 4,4\rangle\}\\ &R_3=\{\langle 2,1\rangle\}\\ &R_4=\varnothing\\ &R_5=\{\langle 2,1\rangle,\langle 3,1\rangle,\langle 4,1\rangle,\langle 3,2\rangle,\langle 4,2\rangle,\langle 4,3\rangle\} \end{align*}

Notice that $R_2\subsetneqq R_1$, so $R_1$ cannot be a minimal element of $H$, and $R_2$ cannot be a maximal element of $H$. $R_5$ looks pretty big, but it’s not maximal either: $R_1\cup R_5$ is a bigger antisymmetric relation.

$H$ has exactly one minimal element, and it’s actually a minimum element; it shouldn’t be hard to find, especially since I’ve mentioned it here. $H$ has quite a few maximal elements, one of which I’ve also mentioned here; since it has more than one maximal element, however, it does not have a maximum element. (It’s a good exercise to count the maximal elements of $H$. I’ve left the answer below in the spoiler-protected block.)

$H$ has $2^6$ maximal elements.

• Now it makes sense. Thanks!
– Paul
Nov 28, 2013 at 18:40
• @Paul: You’re welcome! Nov 28, 2013 at 18:40