What is wrong with this putative proof?

So I've spent about an hour trying to figure out what is wrong with this proof. Could somebody clearly explain it to me? I don't need a counterexample. For some reason I was able to figure that out.

Thanks.

Theorem. $\;$ Suppose $R$ is a total order on $A$ and $B\subseteq A$. Then every element of $B$ is either the smallest element of $B$ or the largest element of $B$.

Proof. $\;$ Suppose $b\in B$. Let $x$ be an arbitrary element of $B$. Since $R$ is a total order, either $bRx$ or $xRb$.

• Case 1. $bRx$. Since $x$ was arbitrary, we can conclude that $\forall x\in B(bRx)$, so $b$ is the smallest element of $R$.


• Case 2. $xRb$. Since $x$ was arbitrary, we can conclude that $\forall x\in B(xRb)$. so $b$ is the largest element of $R$.

Thus, $b$ is either smallest element of $B$ or the largest element of $B$. Since $b$ was arbitrary, every element of $B$ is either its smallest element or its largest element.

Answer

The fundamental problem with the proof is that it mixes up two valid proof techniques in an invalid way.

The first of these is generalization and goes as follows:

Let $x$ be arbitary. Bla bla bla bla bla and therefore $P(x)$. Since $x$ was arbitrary we have $\forall x\,P(x)$.

The second is case analysis and goes like this:

Bla bla bla and therefore $A\lor B$.
Case 1. Assume $A$. Then bla bla bla bla and therefore $C$.
Case 2. Assume $B$. Then bla bla bla bla and therefore $C$.
Thus we have proved $C$.

The fake proof tries to mix these two motifs, such that the first half of the generalization is outside the case analysis, whereas the second half is inside the cases (and appears twice). This is not allowed -- and the fundamental reason it's not allowed is that it would allow false proofs like this.

One way to express this is that each of the "bla bla bla" parts in the proof schemes above must be a complete self-contained proof of its conclusion, starting with the assumptions that are in play at that point of the proof.

The fallacious part of your fake proof doesn't satisfy that. It starts with "Let $x$ be arbitrary," so it must be a proof by generalization. However, the "Bla bla bla bla bla" that comes before "Since $x$ was arbitary" is not a complete proof. It contains the beginning of the case analysis motif, but not the end of it. Once we start a case analysis we have to conclude it before we can begin to discharge assumptions made before the case analysis started.