# Prob. 5, Sec. 4.1 in Kreyszig's functional analysis book: A finite partially ordered set has a maximal element

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?

• A maximal element is not the same as a maximum. Jun 6 '15 at 14:24
• Is the part of my proof where I proceed from $n-1$ to $n$ incorrect? Jun 6 '15 at 14:48
• Expand the argument and we'll see. Do you use the correct definition of maximal? Jun 6 '15 at 14:53
• @HennoBrandsma, please have a look at my latest edit. Jun 7 '15 at 4:49
• 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. 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.