A pair of questions about isomorphism between two posets.

Question

Theorem: Let $P = (X, \le)$ be a finite total order containing n elements. Let $Q = (\{1, 2, \ldots , n\}, \le')$. Then $P \cong Q$.

I have a few questions about the proof of this theorem. In my book it's done by induction. Do the $2$ quotes below contradict each other?

We assume that the result is true for $n = k \ldots$

For starters, template for proving induction is to prove $p(n) \to p(n + 1) $ for all $n$ starting at base case, right? Does the quote above mean $p(n)$ is defined to be $P \cong Q$ and assumed to be true?

Right after that quote comes this sentence:

$\ldots$ and suppose $P$ is a total order on $k + 1$ elements. Let $Q = (\{1, 2, \ldots, k + 1\}, \le')$ . We must show that $P \cong Q$.

To me it sounds like they are assuming $p(n + 1)$ and proving $p(n)$. Is that right?

Answer 1

Let $$p(n)=\mbox{ for all total orders }P\mbox{ with }n\mbox{ elements, }P\simeq Q=(\{1,2,\ldots,n\},\leq')$$ If the base case is not specified, the proof is technically incomplete, but in this case we can take the base case to be either $0$ or $1$ and in either case the total order is trivial because there are fewer than two elements, so the base case is true.

The author is setting up the situation to prove $p(1)\wedge p(2)\wedge \ldots\wedge p(n)\Rightarrow p(n+1)$; the assumption is that $p(i)$ is true for all $i\leq n$, we suppose that $P$ is a total order with $n+1$ elements, and we want to show that $P\simeq Q=(\{1,2,\ldots,n+1\},\leq')$, which is $p(n+1)$. This form of an induction proof is valid and equivalent to all other forms of induction.

Answer 2

In your case $p(n)$ is the assumption that every total order on $n$ elements is isomorphic to $\{1,\ldots,n\}$ with the usual ordering.

The proof then assumes that $p(k)$ holds, and then should proceed to prove that $p(k+1)$ holds as well. Usually this is done by removing the maximal (or minimal) element and using the induction hypothesis.

This is one of these places where using different letters for stating the hypothesis, and when proceeding with the induction step might be helpful. Namely, we state $p(n)$ using $n$ as a variable, then we say "Assume $p(k)$, we'll show that $p(k+1)$ holds as well."