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 Information
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)reply
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)reply
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)reply
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)reply
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)reply
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:
.
)
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?
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 allP — 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)reply
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)reply
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)reply
Gibbs phenomenon
Show that . For instance, how do you get the limits of integration to match up? You would need a substitution where and ; such a substitution 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)reply
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)? —
Quondum12:00, 13 September 2012 (UTC)reply
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)reply
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)reply
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)reply
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 Information
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)reply
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)reply
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)reply
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)reply
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)reply
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:
.
)
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?
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 allP — 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)reply
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)reply
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)reply
Gibbs phenomenon
Show that . For instance, how do you get the limits of integration to match up? You would need a substitution where and ; such a substitution 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)reply
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)? —
Quondum12:00, 13 September 2012 (UTC)reply
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)reply
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)reply
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)reply