Wikipedia:Reference desk/Archives/Mathematics/2012 September 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 12

Incompleteness of Arithmetic

If Arithmetic is consistent, can it be "first-order complete" - i.e. such that resolves every first order arithmetical proposition, provided that the Axiom of Induction is formulated in its (original Peano's) second-order version? 77.125.123.63 (talk) 18:27, 12 September 2012 (UTC)

Oh, it's better than that — the second-order version is categorical; it determines the model up to isomorphism. So first order, second order, ninety-seventh order, whatever you want. --Trovatore (talk) 18:35, 12 September 2012 (UTC)

1. "up to isomorphism" is insufficient for me. Is there any (first order) arithmetical proposition that can't be proved in such an arithmetic, nor can its negation be proved in such an arithmetic? 2. If there isn't, so why do mathematicians insist on the first order version (of the Axiom of Induction) and claim that Arithmetic is incomplete, rather than use the second order version (of the Axiom of Induction) - which enables arithmetic to be "complete-up-to-isomorphism"? 77.125.123.63 (talk) 19:06, 12 September 2012 (UTC)

OK, we have to be careful here. I'm assuming that, when you talk about the "original second-order version", you also mean to use second-order logic; is that right? That's necessary to get the categoricity.

The reason mathematicians don't "use" second-order logic is that they don't know how. Second-order logic is extremely powerful (for example it either proves or refutes the continuum hypothesis, assuming, well, basically nothing). But it doesn't have a usable proof system. In fact, no proof system for second-order logic can be both complete (in the sense of Goedel's completeness theorem, sound, and computable.

(I'm leaving to the side the question of whether working mathematicians "use" formal logic at all — I would argue that working mathematics is not really based on formal deduction. But that's another discussion.) --Trovatore (talk) 19:14, 12 September 2012 (UTC)

It's possible that what you wanted to ask about was the second-order version of the Peano axioms, but interpreted in first-order logic (two-sorted first-order logic, with one sort for natural numbers and another sort for sets of natural numbers). In that case you get second-order arithmetic, which despite the name is a first-order theory. Then the answer to your original question is "no" — second-order arithmetic satisfies the hypotheses of Goedel's first incompleteness theorem, so there must be a true (first-order) proposition of arithmetic that second-order arithmetic does not prove. --Trovatore (talk) 19:26, 12 September 2012 (UTC)

Yes, this is what I meant. Thank you.

(

I guess you finally understood I'd referred to the Axiom of Induction when formulated as follows:

$\forall P[[P(0)\land \forall k(P(k)\Rightarrow P(k+1))]\Rightarrow \forall n[P(n)]]$.

)

Additionally, I also guess you also confirm (according to Goedel-Rosser Theorem) that there must be a first-order arithmetical proposition - whether true or false - that second-order arithmetic does not prove nor does it refute, right?

77.125.123.63 (talk) 19:43, 12 September 2012 (UTC)

Yes, that's true. As to the "finally understood" part, though — the difference is not in how the axiom is formulated but in how it's interpreted. In the two-sorted first-order-logic version, you have a sort for the P over which you're universally quantifying, and considering it to range over objects in your universe. In the second-order-logic version (which, I believe, is what Peano originally intended), when you say all P, you really mean all P — that is, all predicates (definable or not) that give a yes-or-no answer to an arbitrary element of the universe. --Trovatore (talk) 20:48, 12 September 2012 (UTC)

Oh, I might also point out that there's no mystery about the truth value of the Goedel–Rosser sentence for second-order arithmetic. It is true. It says "given any proof of me in second-order arithmetic, there is a shorter proof of my negation in second-order arithmetic". Because the sentence has no proof in second-order arithmetic, this claim is (vacuously) true. --Trovatore (talk) 21:08, 12 September 2012 (UTC)

Thankxs. I know that Rosser's sentence is true, however please note that I didn't care about its being true - but rather about whether it can be either proved or refuted - in the second order arithmetic. Btw, I'm from the restrahnt (rather than from the restrnt, if you still remember). 77.125.123.63 (talk) 22:20, 12 September 2012 (UTC)

Gibbs phenomenon

Show that $\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi }{N+1}}\left({\frac {\sin((N+1/2)t)}{\sin(t/2)}}-1\right)dt=\int _{0}^{\pi }{\frac {\sin t}{t}}dt$. For instance, how do you get the limits of integration to match up? You would need a substitution $t'=f(t)$ where $f(0)=0$ and $\lim _{N\rightarrow \infty }f(\pi /(N+1))=\pi$ ; such a substitution $f$ if it exists would therefore not be continuous so it's hard to see what it would be. What's the approach to this problem? Widener (talk) 20:47, 12 September 2012 (UTC)

Your substitution can depend on N. Let u = (N+1)t, although probably you really want u = (N+1/2)t. Rckrone (talk) 23:43, 12 September 2012 (UTC)

Thanks for the tip. Here is my working so far with that substitution:

$\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi }{N+1}}\left({\frac {\sin((N+1/2)t)}{\sin(t/2)}}-1\right)dt$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi }{N+1}}{\frac {\sin((N+1/2)t)}{\sin(t/2)}}dt-{\frac {\pi }{2(N+1)}}$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi }{N+1}}{\frac {\sin((N+1/2)t)}{\sin(t/2)}}dt$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin(u)}{\sin(u/(2N+1))}}(N+1/2)^{-1}du$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin(u)}{u/(2N+1)+O(u^{3}/(2N+1)^{3})}}(N+1/2)^{-1}du$

$=\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin(u)}{u/2+O(u^{3}/(8(N+1/2)^{2}))}}du$

The desired result then follows if you can interchange the limit and the integral, i.e.

$\lim _{N\rightarrow \infty }{\frac {1}{2}}\int _{0}^{\frac {\pi (N+1/2)}{N+1}}{\frac {\sin(u)}{u/2+O(u^{3}/(8(N+1/2)^{2}))}}du={\frac {1}{2}}\int _{0}^{\pi }\lim _{N\rightarrow \infty }{\frac {\sin(u)}{u/2+O(u^{3}/(8(N+1/2)^{2}))}}du$

Is there some rationale for this, like uniform convergence or something? Widener (talk) 04:07, 13 September 2012 (UTC)

Are you asking about the limit and integral commuting? I suppose you're looking for the dominated convergence theorem. The lead says that it does not hold for the Riemann integral (so just consider the integral as the Lebesgue integral). BTW, no need to expand sin into a polynomial, just use $\lim _{x\to 0}{\sin x \over x}=1$. — Quondum 05:08, 13 September 2012 (UTC)

Does that theorem imply $\lim _{N\rightarrow \infty }\int _{0}^{g(N)}f(x,N)dx=\int _{0}^{\lim _{N\rightarrow \infty }g(N)}\lim _{N\rightarrow \infty }f(x,N)dx$ which is what I have got here? Plus is there a better theorem which does not require Lebegue integration? Widener (talk) 10:56, 13 September 2012 (UTC)

It does seem to imply it, minus the limit in the integration bound. I should plead ignorance at this point, lest I lead you astray. The variable integration bound is of a nature that I'd normally ignore as well-behaved. I suppose it depends on what level of rigour "Show that..." requires. Why would you want to avoid Lebesgue integration (sounds like it's a more powerful replacement for Riemann integration)? — Quondum 12:00, 13 September 2012 (UTC)

The statement is true using the Riemann integral, so using a theorem which requires Lebesgue integration doesn't actually prove the statement fully. You would have to independently prove that Riemann integrals are equal to Lebesgue integrals when they exist. I would like to know if you can prove it directly from Riemann integration Widener (talk) 12:36, 13 September 2012 (UTC)

I'm going through Stein and Shakarchi's book which does Fourier analysis in a bit of an unorthodox way; it doesn't use Lebesgue integration (although I have read about it from other sources and I know what it is). Widener (talk) 12:48, 13 September 2012 (UTC)

I was going to mention dominated convergence at the start, but held off because I didn't have time to think it through. Anyway, I'll also point out that the Gibbs phenomenon (and convergence of Fourier series in general) demands the Lebesgue integral in order to be treated rigorously. I mean, the Gibbs phenomenon is a classic example of why L^2 convergence can display counter-intuitive behavior compared to pointwise convergence. So (imo) this problem should be handled by appealing to the appropriate limit interchange theorems you have, not by tedious calculus and substitutions. At the end, you can demonstrate that this is one of the cases in which the Lebesgue integral and Riemann integral agree, and then you'll have shown the result for Riemann integrals as well. SemanticMantis (talk) 14:41, 13 September 2012 (UTC)