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