Ha, I just got it. Pretty good, of course x<N holds for all numbers you try. But of course, there is a simple one line proof that ~P(N+1), so the inductive-conjecture with x<N certainly has a proof in the negative. This only applies to P where there is no proof of the existence of a counter example.
I understood (perhaps wrongly?) the original question to be “is there some fixed N that is sufficient regardless of P?” Did you mean instead “does there exist some P that has a finite sufficient N?”?
Wouldn’t a counterexample itself be proof of the existence of the counterexample?
If counterexamples are a subset of proofs of the existence of a counterexample, then:
(No counterexamples < N AND no simple proof of a counterexample) IMPLIES
(No counterexamples < N AND no counterexample) IMPLIES
(No counterexample)
But the absence of a counterexample is identical with the truth of the conjecture, which is what we were trying to prove. Once you are willing to look at N+1, by induction you are looking at all the positive integers, which takes forever.
Ha, I just got it. Pretty good, of course x<N holds for all numbers you try. But of course, there is a simple one line proof that ~P(N+1), so the inductive-conjecture with x<N certainly has a proof in the negative. This only applies to P where there is no proof of the existence of a counter example.
I understood (perhaps wrongly?) the original question to be “is there some fixed N that is sufficient regardless of P?” Did you mean instead “does there exist some P that has a finite sufficient N?”?
Wouldn’t a counterexample itself be proof of the existence of the counterexample?
If counterexamples are a subset of proofs of the existence of a counterexample, then:
(No counterexamples < N AND no simple proof of a counterexample) IMPLIES
(No counterexamples < N AND no counterexample) IMPLIES
(No counterexample)
But the absence of a counterexample is identical with the truth of the conjecture, which is what we were trying to prove. Once you are willing to look at N+1, by induction you are looking at all the positive integers, which takes forever.