Is Induction More Rigorous in First-Order Logic Than Higher-Order Logic?

[MostlyHarmless]

I understand how to construct a proof by induction. I've used it many times, for homework because it was clearly what the book wanted, but when I've tried it in a research setting, it's because I have so little control of the objects in working with. So it has become my impression that since induction is non constructive, when you are able to use it, it's a way of saying: "I don't know why it happens, but it always does."

It seems to me like induction is just really convincing. Of course, I'm wrong, I'm just trying to think about why I'm wrong.

 

[DEvens]

Not sure what you mean by "induction is non constructive."

http://www.wolframalpha.com/input/?i=constructive+proof

It seems like induction is a way of getting arbitrarily many specific examples.

I don't know what you mean by "I don't know why it happens." It seems like induction is demonstrating that it happens because the case before it (or a few cases before it) happened, and there is a rule that tells you how to get to the next case.

 

[micromass]

Induction IS a constructive proof method.

Now, I used to have issues with induction too. It seems intuitively obvious that it holds, but I was never pleased with the lack of rigorous proof of why induction works. Now, that proof actually is available. It turns out that suitable definitions of the natural numbers will make induction a very easy result. (Other approach like the Peano axioms will make it an axiom). I suggest you take a look at set theory and how they define the natural numbers there. Induction will become very obvious. Another thing you can do is to axiomatically define the real numbers as a complete ordered field. Then you can construct the natural numbers as a certain subset of the reals. The construction will make it obvious why induction holds.

 

[Anama Skout]

Suppose there's a chain of people

Person #0 - Person #1 - Person #2 - Person #3 - Person #4 - ...etc

Now, whenever person #n hears a secret, then he tells that secret to person #n+1. And if we know that person #0 heard a secret, then eventually all these persons would have heard that secret. This is basically induction, if ##P(n)## implies ##P(n+1)## and ##P(0)## then ##P## holds for all ##n##, why? If it holds for 0, then since ##P(n)## implies ##P(n+1)## (putting n=0), we have that P(1), and next we get P(2) (putting n=1), ...etc

I hope you get the point.

 

[gleem]

when I've tried it in a research setting, it's because I have so little control of the objects in working with.

What area of research are you trying to apply induction?

 

[MostlyHarmless]

Induction IS a constructive proof method.

Now, I used to have issues with induction too. It seems intuitively obvious that it holds, but I was never pleased with the lack of rigorous proof of why induction works. Now, that proof actually is available. It turns out that suitable definitions of the natural numbers will make induction a very easy result. (Other approach like the Peano axioms will make it an axiom). I suggest you take a look at set theory and how they define the natural numbers there. Induction will become very obvious. Another thing you can do is to axiomatically define the real numbers as a complete ordered field. Then you can construct the natural numbers as a certain subset of the reals. The construction will make it obvious why induction holds.

I suppose I'm mistakingly using constructive and direct proof interchangeably. I've seen some set theory in a basic introductory proofs class, and then in my 2 undergrad Real Analysis classes, but I don't recall any novel construction of the Naturals. Do you have any suggestions as to where I might look?

Suppose there's a chain of people

Person #0 - Person #1 - Person #2 - Person #3 - Person #4 - ...etc

Now, whenever person #n hears a secret, then he tells that secret to person #n+1. And if we know that person #0 heard a secret, then eventually all these persons would have heard that secret. This is basically induction, if ##P(n)## implies ##P(n+1)## and ##P(0)## then ##P## holds for all ##n##, why? If it holds for 0, then since ##P(n)## implies ##P(n+1)## (putting n=0), we have that P(1), and next we get P(2) (putting n=1), ...etc

I hope you get the point.

Like I said, I fully understand how to conduct a proof by induction. My point is that, not all inductive proofs are this cut and dry. Like Micromass said, intuitively it makes why induction should work, but intuition ≠ rigor.

What area of research are you trying to apply induction?

A fairly specific topic in an area of Mathematics called Factorization Theory. It was an undergraduate research ("experience") program.

If you recall the argument that "All horses are the same color" (https://en.wikipedia.org/wiki/All_horses_are_the_same_color). The problem (as I understand it) is that the base case is not strong enough. So then, how do you know when you've started "high enough on the stair case". Or rather that there is even a suitable base case.

 

[Anama Skout]

Do you have any suggestions as to where I might look?

Look at the Peano axioms. If you want a detailed reference on the construction of the naturals (as well as the rationals, reals..) check the celebrated Foundations of Analysis by E. Landau.

Like I said, I fully understand how to conduct a proof by induction.

I didn't explain how a proof by induction should be conducted, rather I explained why they are true

My point is that, not all inductive proofs are this cut and dry. Like Micromass said, intuitively it makes why induction should work, but intuition ≠ rigor.

I provided an intuitive view as well as a rigorous one, namely if you show that ##P(n)\implies P(n+1)## and you have P(0) then $$\begin{array}{ccc}\Big\{P(0)\wedge \big[P(0)\implies P(1)\big]\Big\}&\implies& P(1)\\\Big\{P(1)\wedge \big[P(1)\implies P(2)\big]\Big\}&\implies& P(2)\\\Big\{P(2)\wedge\big[P(2)\implies P(3)\big]\Big\}&\implies& P(3)\\\vdots&&\vdots\\\Big\{P(n)\wedge\big[P(1) P(n)\implies P(n+1)\big]\Big\}&\implies& P(n+1)\\\vdots&&\vdots\end{array}$$ $$\Huge\qquad\qquad\Downarrow\boxed{\color{white}{\boxed{\Huge\color{black}{\text{Till }\longrightarrow \infty}}}}\Downarrow$$

 

[h6ss]

I understand how to construct a proof by induction. I've used it many times, for homework because it was clearly what the book wanted, but when I've tried it in a research setting, it's because I have so little control of the objects in working with. So it has become my impression that since induction is non constructive, when you are able to use it, it's a way of saying: "I don't know why it happens, but it always does."

It seems to me like induction is just really convincing. Of course, I'm wrong, I'm just trying to think about why I'm wrong.

I understand what you mean.

Mathematical induction is not the same as induction in the informal sense. A proof by mathematical induction ultimately reduces to mathematical axioms just as any other good rigorous proof. It is constructive in the sense that it’s a perfectly rigorous technique. But my complaint about mathematical induction is that sometimes it establishes the truth of a theorem without giving much intuition for why the theorem holds or how one might extend it.

 

[HallsofIvy]

I you sure you are not confusing "proof by induction" with "inductive reasoning"? That is essentially what h6ss is talking about. The first is a very specific mathematics method of proof, the second a generic scientific way of reasoning (NOT "proving).

 

[Demystifier]

Speaking of rigorous, should we distinguish induction in first-order logic from induction in higher-order logic? Isn't the induction in first-order logic much more rigorous than induction in higher-order logic?