Let $M \neq \emptyset$ be a finite partially ordered set. Then how to show that $M$ has at least one maximal element?

My effort:

If $M$ has only one element, then that element is (vacuously) the maximal element of $M$. So let's suppose that every set having $n-1$ ($n \geq 2$) elements has at least one maximal element, and let $M$ have $n$ elements, say, $a_1, \ldots, a_n$.

Then the set $M - \{a_n \}$ has a maximal element, say, $a$. So, for each $i = 1, \ldots, n-1$, we have the following: $$a \leq a_i \ \implies \ a = a_i.$$ In other words, for each $i=1, \ldots, n-1$, we can conclude that if $a \neq a_i$, then either $a_i \leq a$ (but $a \not\leq a_i$) or $a$ and $a_i$ are not comparable.

Now let's suppose that $a_n \leq a_i$ for some $i = 1, \ldots, n-1$. If $a$ were to precede $a_n$, then we would have $a \leq a_n \leq a_i$ for the same $i$ and so $a \leq a_i$ by transitivity of the partial order and hence $a=a_i$ by the maximality of $a$; thus we would have $a_n = a$. But $a \in M- \{a_n \}$. So $a \neq a_n$. Thus we have a contradiction.

Hence if $a_n$ were to precede some $a_i$, then $a$ could not precede $a_n$, and so $a$ would be a maximal element of $M$; on the other hand, if $a$ were to precede $a_n$, then $a_n$ could not precede any $a_i$, and so $a_n$ would be a maximal element of $M$.

Hence the result follows by induction.

Is the above reasoning correct?

  • $\begingroup$ A maximal element is not the same as a maximum. $\endgroup$ Jun 6 '15 at 14:24
  • $\begingroup$ Is the part of my proof where I proceed from $n-1$ to $n$ incorrect? $\endgroup$ Jun 6 '15 at 14:48
  • $\begingroup$ Expand the argument and we'll see. Do you use the correct definition of maximal? $\endgroup$ Jun 6 '15 at 14:53
  • $\begingroup$ @HennoBrandsma, please have a look at my latest edit. $\endgroup$ Jun 7 '15 at 4:49
  • $\begingroup$ In the first case (some $a_i \ge a$), you rightly conclude $a = a_n$ which is a contradiction (as $a$ cannot be $a_n$ by definition), not a proof that $a$ is maximal. So you know $a$ does not proceed $a_n$ (as this led to the contradiction). Now you know $a$ is maximal by the void implication rgument in my answer. $\endgroup$ Jun 7 '15 at 8:17

A maximal element $m \in M$ is such that for all $x \in M$, $x \ge m$ implies $x = m$. This is not the same as a maximum, which is an $m$ such that for all $x \in M$, we have $x \le m$, and this is the definition you seem to be using.

To adapt your proof somewhat, as the induction idea is good, (the case $n=1$ is still trivial), suppose is maximal in $M \setminus \{a_n\}$.

If $a_n \ge m$, then $a_n$ is maximal: suppose $x \in M$ is such that $x \ge a_n$. If $x \neq a_n$ (so $x \in M \setminus \{a_n\}$), then $x \ge m$ by transitivity, but then $x = m$ by maximality. But then $m \ge a_n \ge m$ so $m = a_n$ which cannot be. So $x = a_n$ and $a_n$ is maximal.

On the other hand, if not $a_n \ge m$, then the condition $\forall x \in M: (x \ge m \rightarrow x=m)$ is true, as it already holds for all $x \in M$ unequal to $a_n$ and is voidly true for $a_n$, as the left hand side of the implication is false.

In either case, $M$ has a maximal element.


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.