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?

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

1 Answer 1


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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .