18
$\begingroup$

I have a student who is working in their spare time on proving or disproving a conjecture of the form

$$\exists x.\forall y.\phi(x,y).$$

Right now their strategy is to construct an $x$ and then show $\forall y.\phi(x,y)$. So far so good.

The student has several times now brought me an $x$ and a "proof" that it works for all $y$ only for me to quickly point out a counterexample $y$. That's fine too; proof-writing can be tricky business.

But what's more worrisome is how they react to the counterexample: the $x$ the next time we meet will usually be a slight variation on the old $x$, adjusted just enough to handle the old $y$. Now since this problem is open, it's conceivable that such back and forth could eventually produce a valid proof. But I'm doubtful.

What I'd like to convey to the student is that they can't just react to the counterexamples I give them; they have to keep their eye on the bigger picture if they're going to inoculate their $x$ against any conceivable $y$. But so far these conversations have had little effect.

I could fairly easily just keep generating counterexamples and hope that they'll realize what's happening. But is there perhaps a nice exercise or analogy that would illustrate the issue faster and more clearly? Or should I focus on the trouble they seem to be having finding counterexamples for themselves?

$\endgroup$
  • 2
    $\begingroup$ What level is this? Graduate, undergraduate first learning proofs? $\endgroup$ – Chris C Feb 21 '15 at 21:24
  • 5
    $\begingroup$ A parable about ellipses and increasingly complex epicycles comes to mind. If a patchwork proof is becoming increasingly complex, maybe a change of perspective is needed :-) $\endgroup$ – Richard Feb 22 '15 at 6:43
  • 2
    $\begingroup$ There is a good literature related to matters like the ones you mention here; check google scholar for O Zaslavsky counterexamples as a first step... $\endgroup$ – Benjamin Dickman Feb 23 '15 at 6:20
  • 3
    $\begingroup$ Are you familiar with Proofs and Refutations by Lakatos? The student you describe seems to be engaged in what Lakatos calls "monster-incorporation". $\endgroup$ – mweiss Feb 23 '15 at 23:28
  • 3
    $\begingroup$ Have you tried, instead of providing your student a counter-example, to ask her or him about its faulty proof? Justifying every step until the faulty one is identified by the student herself might trigger some more understanding. $\endgroup$ – Benoît Kloeckner Feb 27 '15 at 14:38
4
$\begingroup$

Instead of providing your student a counter-example, you could try to ask her or him about its faulty proof. Justifying every step until the faulty one is identified by the student herself might trigger some more understanding.

$\endgroup$
  • $\begingroup$ Obvious, but a good point indeed! $\endgroup$ – Dirk Feb 27 '15 at 22:04
  • $\begingroup$ This ended up working in a strange sort of way. In our talk we came across a place where they had demonstrated the converse of the (unfortunately false) lemma that they wanted. They still tried to patch, but I showed them how anything strong enough to salvage their proof could be trivially recast as an $x$, bypassing the rest of their argument. So now they have taken a different perspective: rather than looking for an $x$ directly, they're hunting for an argument to build one from. $\endgroup$ – forritari Feb 28 '15 at 1:49
9
$\begingroup$

Given the student's computer science background, I'd draw a programming analogy.

Consider the example here:

You start with this:

<p>
    <label for="field">My field</label>
    <input type="text" id="field">
</p>

then you get rid of all that annoying boilerplate and put it in a function:

 createFieldHtml( id, label )

this is good, I'm saving myself so many lines!

createFieldHtml( id, label, defaultValue )

yea, I need a default value too, that was easy to add.

createFieldHtml( id, label, defaultValue, type )

cool, I can use it for checkboxes now too

createFieldHtml( id, label, defaultValue, type, labelFirst )

UX designer said label has to be after checkbox.

createFieldHtml( id, label, defaultValue, type, labelFirst, isDate )

it now renders a date picker when needed. Hm.. params are getting a bit out of hand

createFieldHtml( id, label, defaultValue, type, labelFirst, isDate, containerCssClasses )

there was this one case where I need to add CSS classes

createFieldHtml( id, label, defaultValue, type, labelFirst, isDate, containerCssClasses, fieldCssClasses, disabled, clearAfter, helpText, uploadPath )

aaaaaaaaaaaaaaaaaaaaa

The context is different, but the lesson is the same: at some point your current approach becomes unwieldy as you keep trying to dodge special cases. A good programmer, at this point, would say it's time to refactor the program, to restructure the logic of the code to achieve the same end.

It's easy to stretch the analogy too far, but hopefully it gets the point across that it might be time to take a different approach.

$\endgroup$
  • $\begingroup$ Thanks. I'll take an approach similar to this. $\endgroup$ – forritari Feb 25 '15 at 1:26
7
$\begingroup$

I think the situation is tricky. Without knowing more about the actual problem it may well be that this proof by patchwork will be finished after a few iterations. This happens when every counterexample you give has another new "component" that the earlier ones did not have. So every new $x$ can handle a new case and there are only finitely many of these cases. If this is the case, there would be no need to discourage this strategy. Indeed many good proofs where discovered exactly this way (I guess).

An example: Consider global of minimizers of functions on $\mathbb{R}$, so a theorem like: Every “such” function has a global minimizer. One may start with "Every continuous functions" but this fails since there is $f(x) = x$ on the set $\mathbb{R}$. Hence one needs to rule out functions that are unbounded from below. Then take "Every continuous function that is bounded from below". But still a function like $\exp(x)$ does not fit the bill. The problem is that the minimizer hides at infinity. There are several possibilities now e.g. like restricting the domain to a compact set or assuming a growth condition at infinity. In the end one may arrive at a nice theorem like "a continuous function, bounded from below, defined on a compact set has a minimizer" (and then realize that "bounded from below" is indeed redundant) or "a continuous function $f$, bounded from below, with $f(x)\to\infty$ for $x\to\infty$ has a minimizer" (and realize that one could generalize "continuous" to "lower semi-continuous")…

However, the situation may be different in that there could be an infinite sequence of counterexamples . It seems like you feel that this will be the case. In this situation it could be best to wait until the student realizes this himself. He would learn the most this way.

I guess it is quite an important skill to learn if "proof by patchwork" is going to lead somewhere or not…

$\endgroup$
  • 3
    $\begingroup$ He would learn the most this way if he were the one finding the counterexamples. :) $\endgroup$ – Mark Fantini Feb 22 '15 at 21:00

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.