What is wrong with this putative proof?

Question

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 1

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.

Answer 2

The problem is that for arbitary $x$ we have $xRb$ or $bRx$ which can be written formally: $$\forall x\in B\,\,\, \ \ \ \ \ \ ((xRb) \text{ or }( bRx))$$

and after that he says that : $$(\forall x\in B \, \, \, \, (xRb)) \text{ or } (\forall x\in B \, \, \, \, (bRx))$$

and this two propositions are not equivalent!

Answer 3

Look at the cases. The first case uses an equivocation. It says simultaneously that $x$ is a specific $x$, so that it can be compared to $b,$ and then says that it is arbitrary, meaning it can be any number. But $x$ cannot both be a specific number and any number. Consider the real numbers, and fix $b=0, x=-1$. This is akin to saying $-1 < 0$, therefore $0$ is the largest real number.

Answer 4

The proof shows that for an arbitrary $x$, either $bRx$ or $xRb$. Therefore $\forall x(xRb\lor bRx)$. So far so good.

But $\forall x(P(x)\lor Q(x))$ is not equivalent to $\forall xP(x)\lor\forall x Q(x)$.

Answer 5

The problem is that $x$ isn't arbitrary anymore when you assume case 1 or 2. Indeed, once you assume case 1, $x$ belongs to the set $ U =\{k \in B: bRk\}$. Continuing to say that $x$ is arbitrary from here on is akin to affirming $U = B$. Obviously, there is no reason to assume this (because if you did you'd have proven the "theorem" just by assuming its truth). Likewise for case 2.

Answer 6

Yes $x$ is arbitrary, but the same relation $bRx$ does not necessarily hold for all $x$, only one of the two relations holds for any given $x$, that does not imply the same one holds for all $x$.

Answer 7

It is true that for arbitrary $x$ either $bRx$ or $xRb$. But, it could be different for different $x$'s. You might have an $x_1$ so that $x_1Rb$ and an $x_2$ so that $bRx_2$. Just because one of them is true for a particular arbitrary $x$ doesn't mean the same relation is true for all $x$.