Strong induction to prove a finite poset has at least one maximal element - two questions

Question

I don't understand this answer. It aims to prove that a finite poset has at least one maximal element.

First, I don't understand why it is relevant to use a (strong) induction when the argument actually concerns a finite poset. Isn't induction a way of proving things up to infinity?

Second, in his induction he starts with the base case $|X| =1$. Then, he says assume $|X|=n>1$ and that the result holds for posets having cardinality less than n. This I don't understand. I would have said instead: "let $n\geq 1$ and assume the result is true for all $k$ such as $1\leq k \leq n$ and let $|X|=n+1$". In fact, with his way we could have $|X| = 36$ and then his method of picking one element $a$ (and showing there exists a $c$ depending on this $a$ that is maximal) wouldn't work.

Thank you in advance.

Answer 1

First, I don't understand why it is relevant to use a (strong) induction when the argument actually concerns a finite poset. Isn't induction a way of proving things up to infinity?

Induction is a method of proving that a statement is true for every natural number. Here, the statement to be proven is: for every $n\in\mathbb N$, and for every partially ordered set $X$, if $|X|=n$ then $X$ has a maximal element.

Remark: It is a little misleading to describe induction as a way of "proving things up to infinity", since that statement can be easily be interpreted in such a way that it is wrong. Whilst induction proves that a statement holds for arbitrarily large natural numbers, it has nothing to say about whether the statement holds for e.g. infinite cardinals. In fact, some statements provable by induction do not even make sense in the infinite case. There is a cousin of induction called "transfinite induction" that can be used to prove statements about well-ordered sets (including ones that are "larger" than the set of natural numbers), but the details are technical and are beyond my paygrade.

Second, in his induction he starts with the base case $|X| =1$. Then, he says assume $|X|=n>1$ and that the result holds for posets having cardinality less than n. This I don't understand. I would have said instead: "let $n\geq 1$ and assume the result is true for all $k$ such as $1\leq k \leq n$ and let $|X|=n+1$". In fact, with his way we could have $|X| = 36$ and then his method of picking one element $a$ (and showing there exists a $c$ depending on this $a$ that is maximal) wouldn't work.

It seems your confusion lay in how a strong induction proof is structured. Typically, strong induction proofs are presented in the following way: prove the statement is true for $n=1$; then, let $n>1$, assume the statement is true for $k$ such that $1\le k<n$, and then show that the statement is true for $n$. A variant of this method is to let $n\ge 1$, assume the statement holds for $k$ such that $1\le k\le n$, and then show that the statement is true for $n+1$. The difference is just a matter of notation.

This is not the only way a strong induction proof can be structured. For instance, the base case could be $n=0$, and then the inductive step would have to be appropriately modified. In rare cases, the base case could be an integer other than $0$ or $1$.

Remark: Sometimes strong induction is structured in yet another way, and the base case does not have to be handled differently to all the other cases.