4
$\begingroup$

I have a problem with a proof I found in Velleman's "How to prove it". This is sort of interesting, because it is the very first time I cannot see the structure of a proof presented in the book. The following are the theorem and Velleman's proof.

Theorem:
Suppose $R$ is a partial order on a set $A$, and $B \subseteq A$. If $R$ is a total order and $b$ is a minimal element of $B$, then $b$ is the smallest element of $B$.

Velleman's Proof:
Suppose $R$ is a total order and $b$ is a minimal element of $B$. Let $x$ be an arbitrary element of $B$. If $x = b$, then since $R$ is reflexive, $bRx$. Now suppose $x \neq b$. Since $R$ is a total order, we know that either $xRb$ or $bRx$. But $xRb$ can’t be true, since by combining $xRb$ with our assumption that $x \neq b$ we could conclude that $b$ is not minimal, thereby contradicting our assumption that it is minimal. Thus, $bRx$ must be true. Since $x$ was arbitrary, we can conclude that $ \forall x \in B(bRx)$, so $b$ is the smallest element of $B$.

Problem
My problem is with the structure of the proof. In particular, I see a bit as a "rabbit out of the hat" the fact that we start by assuming that $x \neq b$.
In the pages of the book before the the actual proof, the author presents the scratch work behind the proof. Now, I can see the logic behind it (the all problem about the $x$ being or not being equal to $b$), but I do not see how this smoothly enters in the picture of the proof. Just consider that using "Proof Designer" (the software that can be found on Velleman's site and that goes along the book), I could actually prove the theorem without starting with the assumption that $x \neq b$. Indeed, the proof in words should go along the following lines:

Proof:
Assume that $B \subseteq A$, that $R$ is a total order, and that $b$ is a minimal element of $B$. Let $x \in B$ be arbitrary. Thus, by the fact that $b$ is minimal, we have that if $(x,b) \in R$, then $x=b$. Proceed by cases.
1. $(x,b) \notin R$:
Since $x \in B$ and $b \in B$, we can conclude that $x \in A$ and $b \in A$. From the completeness of $R$ we have that either $(x,b) \in R$ or $(b,x) \in R$. Thus, by assumption that $(x,b) \notin R$, we have that $(b,x) \in R$.
2. $x=b$:
Since $x \in B$ and $b \in B$, we can conclude that $x \in A$ and $b \in A$. From the reflexivity of $R$ we have that $(b,b) \in R$. But, since by assumption $x=b$, we can conclude that $(b,x) \in R$. QED

QUESTIONS:
Is my proof sound?
Is there somebody who can give me a feedback on what is actually the structure of Velleman's proof?
I actually tried to replicated Velleman's structure of the proof with "Proof Designer", but I did not succeed.

Thanks a lot for any help.

PS: Conditional on my proof being sound, any feedback on the writing is more than wellcome.

$\endgroup$
  • $\begingroup$ It's not so much "rabbit out of the hat" as you might think. What he does in the proof with $x$ is first noting that either $x = b$ or $x \neq b$. Then he says that if $x = b$ we're done, so the only case that is left to check is if $x \neq b$. He assumes that this is the case and goes on with the proof. $\endgroup$ – Arthur Mar 14 '14 at 12:53
  • $\begingroup$ Ok, I do see this. Maybe we can say that my way of looking at proofs is still a bit "mechanical"? [Even if I truly love "Proof Designer", and it has helped me a lot, I do think it makes users a bit too rigid] $\endgroup$ – Kolmin Mar 14 '14 at 13:02
  • $\begingroup$ Let's say that my problem is with the fact that he "notes" that either $x=b$ or $x \neq b$. So the speak, the fact that he "notes" it lies outside the structure of the proof that comes from the way in which the problem is given. $\endgroup$ – Kolmin Mar 14 '14 at 13:04
  • $\begingroup$ Now, this is not a problem in itself. On the contrary. We could say that I would like to know when I can "note" things, so to say (...and maybe this last statement sounds like asking an advice on how to get intuition). $\endgroup$ – Kolmin Mar 14 '14 at 13:05
  • 1
    $\begingroup$ But what "is behind" your choice of 1 and 2 ? The fact that $(x,b) \notin R$ or $(x,b) \in R$ ... Then you exploit the fact that : "if $(x, b) \in R$, then $x=b$, and proceed with the two cases. Vellman's proof start from the same assumption and exploit also the fact that, "if $(x, b) \notin R$, then $x \ne b$, because $R$ is total and if we have that $x = b$, then by reflexivity : $(b, b) \in R$. $\endgroup$ – Mauro ALLEGRANZA Mar 14 '14 at 13:07
3
$\begingroup$

To be honest I don't see a lot of difference between Velleman's proof and yours. Both are proofs by division into cases, and actually I would say yours is better written and better set out than his: you make the two cases clear, whereas he muddles them up together in one paragraph.

Your choice of cases is $(x,b)\in R$ or not; his is $x=b$ or not. To me, they are both sensible ideas to consider and neither is more "rabbit-out-of-hatty" than the other. And in fact logically they are identical: when $b$ is a minimal element in a partial order we have $(x,b)\in R$ if and only if $x=b$.

As a final remark (though from one of your comments above I think you already realise this), don't forget that sometimes there is no alternative to pulling rabbits out of hats! I have seen various books on proof (though I don't know Velleman's) and many of them contain lots of good advice. But sometimes you just need a bright idea, and there really isn't any way to teach that.

$\endgroup$
  • $\begingroup$ I am starting to get closer to realizing what's going on. However, I have a problem with one of your statements, which -to me- seems to be the most important one, namely: "when $b$ is a minimal element in a partial order we have $(x,b) \in R$ if and only if $x=b$". Is this really an if and only if? I didn't consider it such, because if it is the case, then my question is kinda trivial and it really seems it's a matter of taste. $\endgroup$ – Kolmin Mar 14 '14 at 13:20
  • 2
    $\begingroup$ @Kolmin: "If" is because $R$ is reflexive; the "only if" direction is the definition of "minimal element". $\endgroup$ – Henning Makholm Mar 14 '14 at 13:23
  • 1
    $\begingroup$ Yes it is if and only if. "If $(x,b)\in R$ then $x=b$" is true by definition of minimal, and the converse is true because $R$ is reflexive. In fact both of these remarks occur in your proof, and in Velleman's too! $\endgroup$ – David Mar 14 '14 at 13:26
  • $\begingroup$ Thus, I would say that the main thing that is not explicit in Velleman's proof is the fact that this is an iff and, from this, we can interchange $(x,b) \notin R$ with $x \neq b$, hence getting the cases he uses. $\endgroup$ – Kolmin Mar 14 '14 at 13:36
  • $\begingroup$ I would say that is a reasonable assessment. He does all this implicitly of course, but as you said, not explicitly. $\endgroup$ – David Mar 14 '14 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.