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$ – Stefan Hamcke Nov 28 '13 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$ – Namaste Nov 28 '13 at 18:31
  • $\begingroup$ So my H is just one possibility? $\endgroup$ – Paul Nov 28 '13 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.

  • $\begingroup$ Now it makes sense. Thanks! $\endgroup$ – Paul Nov 28 '13 at 18:40
  • $\begingroup$ @Paul: You’re welcome! $\endgroup$ – Brian M. Scott Nov 28 '13 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.