Help understanding an incorrect "least counterexample" inductive proof.

Question

I am studying proofs by the principle of well-order. Below is an exercise I encountered which I am having difficulty understanding.

What is wrong with this "proof" of the following statement?

For every positive integer n,the number n^2+n+1 is even.

Proof:

Let S be the subset of positive integers nn for which n^2+n+1 is odd. >Assume S is nonempty.

Let m be its smallest element.

Then m-1 doesnt belong to S, so (m-1)^2+(m-1)+1 is even.

But (m-1)^2+(m-1)+1 = m^2-m+1 = (m^2+m+1)-2m,(m−1),so m^2+m+1 equals((m-1)^2+(m-1)+1)+2m, which is a sum of two even numbers, which is even.

So m does not belong to S which is a contradiction. Therefore, S is empty, and the result follows.

I know from the beginning that the statement is wrong, it is false, therefore only a counterexample would be given. But I don't know why the page insists on proving it. What has me wondering is that by contradiction it assumes the opposite that n2+n+1 is odd, that is true. Therefore it begins to prove with (m-1) it does not belong to S and that is correct. It is one less than the minimum, obviously it is not in the set S.

This are my questions:

m2+m+1 is odd for all positive integers, so you could use mathematical induction instead of the principle of good order, because it is true for p=1 that expression will always give odd. I don't understand that part, it begins with a contradiction with the principle of good order, when n2+n+1 is odd, always the easiest thing to do with the principle of mathematical induction (I understand that you want to reach a contradiction).But why doing this stuff with a contradiction and the well order. The contradiction is always true. Dont know what contradiction I can get from a true statement 2. Is it valid if the statement at the begginig" m2+m+1 is even" is not true, to contradict it? I understood that only a counter-example has to be given and that's it, no more proof.

3. If you could contradict from the beginning that statement m2+m+1 is odd, always take whatever value it is and always give true, then how is it that you want to reach a contradiction, I don't understand.

4. The page says that the proof is wrong because m-1 is not a positive integer, as I said obviously it is not a positive integer, it is less than the smallest positive integer that the set S has, but this statement comes out of the following affirmation: m must be the next of some natural number (in the case that the proposition m2+m+1 is odd, it would have complied with m different from 1). That is, there exists k element of the positive integers such that m=k +1 then k=m-1. Where k does not belong to S and is a natural prior to m, then (m−1)2+(m−1)+1 must be even, when if I replace m with even or odd, this result will always give me odd in the two cases. Is that my contradiction? or the statement is actually wrong because m-1 is not a positive integer from the start.

Please help I am very confused.

Answer 1

Okay, this was meant to be an exercise in evaluating whether a proof is valid or not.

This is a proof that seems valid. BUt it can't be because it reaches a wrong conclusion. So it is asking you where did it go wrong.

You are essentially saying "Since we know it is wrong, we know it is invalid so we don't care where it went wrong". But we do we have to be able to evaluate proofs, we have to be able to do correct proofs, so we have to be able to explain where an incorrect proof goes wrong, so we won't make mistakes in our proofs.

So we have to spot the error in the proof (which must exist as the proof is wrong).

Here the proof is correctly asserting $m$ is the minimum, and is correctly asserting that if $m-1$ exists as a natural number it would not be in the set. And the rest of the proof follows perfectly that $n=m-1$ would mean $n^2 + n + 1$ is even and if so $(n+1)^2 + (n+1) + 1$ would be even and all would be even.

And note: The prove said assume the set of $n^2 + n+1$ is odd is nonempty. It (deliberately) never showed it was non empty. And therefore this prove, which has only made valid statements, would have proven that the set $n^2 + n + 1$ is odd is empty by contradiction.

Obviously this proof is wrong but where?

And where is that although $m$ is the $m$ and $m-1$ IF IT EXISTED would be less than the min. But it didn't take into account that $m$ could be (and is) equal to $0$ and $m-1$ (as a natural number) might not exist (and indeed it doesn't as $m-1 = 0-1$ is not a natural number.)

Answer 2

To understand the error in this least counterexample (aka minimal criminal) descent argument it helps to first consider a correct such descent.

---

Lemma $ $ Let $\,f_{n,\,\ \color{#c00}{n\ge 1}}$ be an integer sequence with consecutive terms of equal parity $\,\color{#0a0}{f_k\equiv _2 f_{k+1}}$. Then they all have parity the same as the initial element, i.e. $\,f_n\equiv_2 f_1\,$ for all $\,n\ge 1$.

Proof $ $ If not then we can choose a counterexample of least index $\,\color{#c00}{k\ge 2},\,$ i.e. $\,f_k \not\equiv_2 f_1.\,$ But this yields the contradiction that $\,f_{k-1}$ is a smaller index counterexample by $\,\color{#0a0}{f_{k-1}\equiv_2 f_k}\not\equiv_2 f_1$ (note $\,\color{#c00}{k\ge 2}\Rightarrow k-1\ge 1$ so $f_k$ is $\rm\color{#c00}{well\ defined}$, i.e. it has $\rm\color{#c00}{\rm{index }\ge 1})$.

---

The problem with the quoted argument is that it fails to verify that the indices in the descent step remain positive, as we do above in the red text, i.e. $f_1$ is not a counterexample so the least indexed counterexample must have index $\,\color{#c00}{k\ge 2},\,$ so our decremented index $\,k-1\,$ remains positive (well-defined) in our descent step. Forgetting to check that is a descent analog of "forgetting to check the base case" in (ascent) inductive proofs. Note: it is simpler to use $\,f_n = 2n+1\,$ vs. $n^2+n+1.$

In this case it is clearer to do the above proof in ascent (induction) form, using the induction hypothesis that consecutive terms have equal parity to lift the parity of $f_1$ up to all larger index $f_k$ (vs. push-down an opposite parity counterexample till we descend to the contradiction that $f_1$ has opposite parity of itself).

See this answer for how to view (infinite) descent arguments as a contrapositive form of induction.