0

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 \lor xRb$.

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

2. Case: $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 the 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.

My counterexample: $R = \{(d,a),(d,b),(d,c),(c,a),(c,b),(b,a)\}$ For this total order $b$ is neither the largest nor the smallest element.

pseudomarvin
  • 861
  • 1
    In Case $1$, say...the fact that $b<x$ does not imply that $b<y$ for any other element $y\in B$! – lulu Aug 15 '16 at 21:07
  • 1
    As to the logic: as you phrased it, the problem is asking you to find the error in the proof. Exhibiting a counterexample only shows that the theorem is false, but that is not the same as finding the flaw. Of course, you can take your counterexample and walk it through the cases and see where the "proof" breaks down. – lulu Aug 15 '16 at 21:09
  • 1
    "1. Case: bRx. Since x was arbitrary, we can conclude that ∀x∈B(bRx), " Um.... x was arbitrary but determining that bRx was not. bRx is only true on non-arbitrary x for which we examined the x and determined a non-arbitrary attribute of it. – fleablood Aug 15 '16 at 21:17
  • 1
    Two easier counter examples: a) Let A have three or more elements. At most one is the smallest, at most one is the largest, so all the rest are neither. b) Let A = $\mathbb R$ with order "<". Let b = 1. Done. End of counter example. – fleablood Aug 15 '16 at 21:39

2 Answers2

2

The underlying error is in arguing as if

$$\forall x(b\mathrel{R}x\lor x\mathrel{R}b)\tag{1}$$

implied

$$\forall x(b\mathrel{R}x)\lor\forall x(x\mathrel{R}b)\;.\tag{2}$$

Here $(1)$ is true, but $(2)$ is not, yet it’s $(2)$ that’s being used in the individual case arguments. $(2)$ does imply $(1)$, but the converse implication is false: $(2)$ is a much stronger statement than $(1)$.

Brian M. Scott
  • 616,228
1

Choosing the $x$ initially was arbitrary. However determining which of the conditions $xRb$ or $bRx$ was not an arbitrary distinction and once we have determine which, $x$ can no longer be considered arbitrary.

This is exactly the same as the following proof all integers are both even and odd:

Arbitrarily pick $n$. Either $n$ is odd or even. If $n$ is odd then as $n$ was arbitrary all integers are odd. If $n$ is even then as $n$ was arbitrary all integers are even.

That's so wrong that it's almost incomprehensible. This proof of total order simply relies upon a technical term the student may not be totally comfortable with and the proof uses the unfamiliarity to distract the student as the proof makes a baldly ludicrous logical fallacy, which would never have held up if the student weren't distracted about the meaning of total order.

====

It's important to note that finding a counterexample doesn't expose the flaw. It only shows the statement is false and the proof must fail somewhere but it doesn't determine where.

This statement is obviously false because it is absurd. In this case a counter example is trivial. Just take $\mathbb R$ and then number $1$. $1$ is neither the smallest nor the largest real number.

fleablood
  • 124,253