[math-fun] Incomparable integers
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!) What if we replace PA by a stronger theory? The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical. But my intuitions may be totally off-base... Jim Propp
Surely the existence of such integers cannot be proven in PA, since there are models (those without nonstandard integers) in which it is false. Charles Greathouse Analyst/Programmer Case Western Reserve University On Tue, Sep 3, 2013 at 2:05 PM, James Propp <jamespropp@gmail.com> wrote:
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!)
What if we replace PA by a stronger theory?
The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical.
But my intuitions may be totally off-base...
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Besides, their size is surely irrelevant: only the sign of the difference is required for comparison. WFL On 9/3/13, Charles Greathouse <charles.greathouse@case.edu> wrote:
Surely the existence of such integers cannot be proven in PA, since there are models (those without nonstandard integers) in which it is false.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Sep 3, 2013 at 2:05 PM, James Propp <jamespropp@gmail.com> wrote:
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!)
What if we replace PA by a stronger theory?
The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical.
But my intuitions may be totally off-base...
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Fred makes a good point (which I didn't understand till I read Andy's post). You could have a number m that's defined to equal 1 if some proposition P is true and 2 otherwise; if we define n as 3-m, then deciding which of them is as larger is just as hard as deciding whether P is true, but it doesn't have anything to do with the bigness of m and n. (Here I'm ducking the issue of finding a specific proposition P such that the existence of a truth-value for P is provable in PA even though P and not-P are undecidable in PA, since it's not germane to my point here, which is that the mathematical question that I raised doesn't really capture my original motivating intuition.) Maybe what I'm asking for is a "naturally occurring" example of such a pair of numbers, but I have no idea how to formalize what I mean by this. Jim Propp On Tuesday, September 3, 2013, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Besides, their size is surely irrelevant: only the sign of the difference is required for comparison. WFL
On 9/3/13, Charles Greathouse <charles.greathouse@case.edu> wrote:
Surely the existence of such integers cannot be proven in PA, since there are models (those without nonstandard integers) in which it is false.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Sep 3, 2013 at 2:05 PM, James Propp <jamespropp@gmail.com> wrote:
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!)
What if we replace PA by a stronger theory?
The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical.
But my intuitions may be totally off-base...
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's a book "Ad Infinitum" by Brian Rotman which has an appendix in which he creates an alternative number system which has "exit points", i.e. values above which numbers are undefined. If you can find a copy you might look at the appendix (which is only 13 pages). I don't recommend buying it because the rest of the book is impenetrable post-modern philosophy in the French style. Brent On 9/3/2013 2:46 PM, James Propp wrote:
Fred makes a good point (which I didn't understand till I read Andy's post). You could have a number m that's defined to equal 1 if some proposition P is true and 2 otherwise; if we define n as 3-m, then deciding which of them is as larger is just as hard as deciding whether P is true, but it doesn't have anything to do with the bigness of m and n.
(Here I'm ducking the issue of finding a specific proposition P such that the existence of a truth-value for P is provable in PA even though P and not-P are undecidable in PA, since it's not germane to my point here, which is that the mathematical question that I raised doesn't really capture my original motivating intuition.)
Maybe what I'm asking for is a "naturally occurring" example of such a pair of numbers, but I have no idea how to formalize what I mean by this.
Jim Propp
On Tuesday, September 3, 2013, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Besides, their size is surely irrelevant: only the sign of the difference is required for comparison. WFL
On 9/3/13, Charles Greathouse <charles.greathouse@case.edu> wrote:
Surely the existence of such integers cannot be proven in PA, since there are models (those without nonstandard integers) in which it is false.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Tue, Sep 3, 2013 at 2:05 PM, James Propp <jamespropp@gmail.com> wrote:
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!)
What if we replace PA by a stronger theory?
The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical.
But my intuitions may be totally off-base...
Jim Propp
What does "true" mean here? Provable within PA? Because if it's undecidable in PA, there's disagreement over whether "true" (independent of any axiom system) has a well-defined meaning. --Dan Jim wrote: ----- . . . You could have a number m that's defined to equal 1 if some proposition P is true and 2 otherwise . . . . . . -----
Here I use the word "true" in its internal sense within PA. But to be clearer (and to avoid using a confusing word like "true"), I should have written
You could have a number m that's defined to equal 1 if P and 2 if not-P, for some particular proposition P in PA.
That isn't problematical, is it? PA lacks a truth-predicate, but it doesn't need to have one for my purpose. Jim Propp On Tue, Sep 3, 2013 at 8:51 PM, Dan Asimov <dasimov@earthlink.net> wrote:
What does "true" mean here? Provable within PA?
Because if it's undecidable in PA, there's disagreement over whether "true" (independent of any axiom system) has a well-defined meaning.
--Dan
Jim wrote:
----- . . . You could have a number m that's defined to equal 1 if some proposition P is true and 2 otherwise . . . . . . ----- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Sep 3, 2013 at 5:46 PM, James Propp <jamespropp@gmail.com> wrote:
(Here I'm ducking the issue of finding a specific proposition P such that the existence of a truth-value for P is provable in PA even though P and not-P are undecidable in PA, since it's not germane to my point here, which is that the mathematical question that I raised doesn't really capture my original motivating intuition.)
I'm not sure what you mean by "existence of a truth value" for P is. But if you talk about provability, rather than truth, this can't be done. Given a proposition P such that "Either P or not-P is provable" is provable, then either P is provable, or not-P is provable. And if P is provable, so is "P is provable", because there exists an N such that N is the goedel number of a proof of P, and a statement of the form "N is the goedel number of a proof of P" is always provable if true. Andy
Sorry for being unclear, Andy. What I meant by "existence of a truth-value for P within PA" is "definability within PA of a number whose value is 1 if P and 0 if not-P". Now that I think about it, I suspect that for every P in PA, there's a way to define (within PA) a number n such that "n=1 iff P" and "n=0 iff not-P" are both provable in PA. But it's 1:00am, so I don't put much faith in what I think or suspect right now. Jim On Wed, Sep 4, 2013 at 12:37 AM, Andy Latto <andy.latto@pobox.com> wrote:
On Tue, Sep 3, 2013 at 5:46 PM, James Propp <jamespropp@gmail.com> wrote:
(Here I'm ducking the issue of finding a specific proposition P such that the existence of a truth-value for P is provable in PA even though P and not-P are undecidable in PA, since it's not germane to my point here, which is that the mathematical question that I raised doesn't really capture my original motivating intuition.)
I'm not sure what you mean by "existence of a truth value" for P is. But if you talk about provability, rather than truth, this can't be done. Given a proposition P such that
"Either P or not-P is provable" is provable, then either P is provable, or not-P is provable. And if P is provable, so is "P is provable", because there exists an N such that N is the goedel number of a proof of P, and a statement of the form "N is the goedel number of a proof of P" is always provable if true.
Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Sep 4, 2013 at 1:07 AM, James Propp <jamespropp@gmail.com> wrote:
Sorry for being unclear, Andy. What I meant by "existence of a truth-value for P within PA" is "definability within PA of a number whose value is 1 if P and 0 if not-P". Now that I think about it, I suspect that for every P in PA, there's a way to define (within PA) a number n such that "n=1 iff P" and "n=0 iff not-P" are both provable in PA. But it's 1:00am, so I don't put much faith in what I think or suspect right now.
I'm still not sure what your definition of "defineable" is. If you use the one that I gave earlier, your statement is trivially true; such an n is defined by the formula "n=1 iff P and n= 0 iff not-P". Andy On Tue, Sep 3, 2013 at 5:05 PM, Andy Latto <andy.latto@pobox.com> wrote:
I'm not sure exactly what you mean by "defineable". I'm assuming what you mean is that there is a formula P(x) with one free variable, such that
ExP(x) ^ ((AxAy P(x) ^ P(y)) -> x=y)
is a theorem of PA,then the number x such that P(x) is defineable in PA.
At risk (once more) of descending to triviality, I venture to observe that "definability" and "constructability" are distinct concepts, which seem in danger of becoming conflated at some points in the discussion. WFL On 9/4/13, Andy Latto <andy.latto@pobox.com> wrote:
On Wed, Sep 4, 2013 at 1:07 AM, James Propp <jamespropp@gmail.com> wrote:
Sorry for being unclear, Andy. What I meant by "existence of a truth-value for P within PA" is "definability within PA of a number whose value is 1 if P and 0 if not-P". Now that I think about it, I suspect that for every P in PA, there's a way to define (within PA) a number n such that "n=1 iff P" and "n=0 iff not-P" are both provable in PA. But it's 1:00am, so I don't put much faith in what I think or suspect right now.
I'm still not sure what your definition of "defineable" is. If you use the one that I gave earlier, your statement is trivially true; such an n is defined by the formula "n=1 iff P and n= 0 iff not-P".
Andy
On Tue, Sep 3, 2013 at 5:05 PM, Andy Latto <andy.latto@pobox.com> wrote:
I'm not sure exactly what you mean by "defineable". I'm assuming what you mean is that there is a formula P(x) with one free variable, such that
ExP(x) ^ ((AxAy P(x) ^ P(y)) -> x=y)
is a theorem of PA,then the number x such that P(x) is defineable in PA.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Tue, Sep 3, 2013 at 2:05 PM, James Propp <jamespropp@gmail.com> wrote:
Are there (positive) integers m,n definable in PA whose existence is provable in PA such that m \geq n and n \geq m are undecidable in PA? (I think that's the right way to ask the question I have in mind, but if my wording evinces misunderstanding of foundational issues, please enlighten me!)
I'm not sure exactly what you mean by "defineable". I'm assuming what you mean is that there is a formula P(x) with one free variable, such that ExP(x) ^ ((AxAy P(x) ^ P(y)) -> x=y) is a theorem of PA,then the number x such that P(x) is defineable in PA. Using that definition of defineable, I think the answer to your question is yes. Here's a proof sketch (note that this involves no paradox, since this is not a proof in PA; it's a proof in some more powerful system, like ZFC, in which consis(PA) is a theorem). Let G be a Goedel sentence for PA, that is, a statement G that says "not-G is provable". G is undecideable in PA (if G is provable, so is not-G, and PA is inconsistent, and if not-G is provable, then G is true, so again PA is inconsistent; since PA is consistent (this is provable in ZF), neither G nor not-G is proveable in ZF) G is false in the standard model of PA; that is, none of 1, 1+1, 1+1+1, 1+1+1+1, ... is the Goedel number of a proof of not-G. So in the model in which those are all the numbers there are, the statement "Ex(x is a proof of G) is false. B ut there are models where there are bigger numbers than all of those, in which there is a number x such that "x is the goedel number of a proof of G" is true. Now let P(x) be "x is the smallest number that is the Goedel number of a proof of G, if such a number exists, or 4 if there is no number that is the Goedel number of a proof of G". let Q(x) be "x is the second smallest number that is the Goedel number of a proof of G, if two such numbers exists, or 3 if there are 0 or 1 numbers that are the Goedel numbers of a proof of G". Then "ExEy(P(x)^Q(y))" is a theorem of PA, but "ExEy(P(x)^Q(y) ^ x < y)" and "ExEy(P(x)^Q(y) ^ y < x)" are undecideable. In the standard model, the first is false and the second is true,
What if we replace PA by a stronger theory?
I think a similar argument works in any stronger omega-consistent theory F, where the proof is in the still stronger theory F + Consis(F).
The underlying intuition is that if there are incomprehensibly big numbers, at some point even comparative notions of bigness should start to fail us, so that, in a certain sense, the well-ordering of the natural numbers should become problematical.
Nonstandard models of PA have numbers that are bigger than all of 1, 1+1, 1+1+1, etc, but I'm not sure they correspond well to your intuitions of "unimaginably big numbers". The axiom schema of induction does its best to assert that no such numbers exist, but it only provides induction on countably many properties, and if you're sufficiently devious, you can (non-constructively) find a model where there are these extra numbers, but the axiom of induction "just happens to work" for each of these countably many properties. Andy
participants (6)
-
Andy Latto -
Charles Greathouse -
Dan Asimov -
Fred Lunnon -
James Propp -
meekerdb