I think the philosophical profoundness of undecidability is often exaggerated. I could be way off base here, but..
Consider, in group theory, the statement "There exists an element other than the identity which squares to give the identity". This is "undecidable" in that you can't prove it or disprove it from the group theory axioms, and there are are groups where it's true and groups where it's false. However, this doesn't make people lie awake all night worrying whether it makes maths meaningless, or whether it's true for the "rea...
There are two major differences:
First, Godel's results are much stronger than the claim that one has undecidable statements within the axiomatic system. But one also has that there's no algorithm which can in general say whether a given statement is provable in PA (assuming that PA is in fact consistent). This is a much stronger and weirder claim.
This is also different from your group example because the natural numbers are a very concrete object. So our intuition strongly suggests that there should really be only one thing that actually looks like N in some sense. Some (although not all) senses of that are shown to be wrong by Godel's theorems. Although what is doing more of the work here in some sense are the non-standard models of arithmetic which strictly speaking are distinct from Godel's results.
Simply, if we define a binary property 'P' that can only be tested by algorithms that might not halt, and show, say by computation, that every natural number up to some arbitrarily large number 'N' has the property P, does that mean that there must be a generalized deductive proof that for all natural numbers P holds?
Yes...
How big can N get before there must be a deductive proof that P holds for all natural numbers?
Unfortunately, very big, as a rule, and not explicitly computable.
What if N was larger than Graham's number[1]?
Graham's number woul...
What I'm really asking is, if some statement turns out to be undecidable for all of our Tarskian truth translation maps to models, does that make that conjecture meaningless, or is undecidable somehow distinct from unverifiable. What is the difference between believing "that conjecture is unverifiable" and believing "that conjecture is undecidable."? Are the expectations/restrictions on experience that those two believes offer identical? If so does that mean that the difference between those two believes is a syntactic issue?
See Making...
Let's call the claim that "there is a binary property R which holds for all natural numbers and that there is no counter example that can or will ever be found, but which also cannot be proven to hold for all natural numbers" the "first Potato conjecture". How would one ever show the first potato conjecture, or even offer evidence in it's favor?
Well, you could do it like Goedel did. I don't think you're grokking the distinctions between different sorts of proofs, so reading up on Goedel's proof might be what you want.
P.S. To get li...
A statement can only be said to be provable or unprovable within some axiom system. Gödel's first incompleteness theorem says that for any strong enough axiom system talking about the integers, there will exist true statements about the integers that the system cannot prove.
(ETA ignore the following, it's wrong. Wow I'm really embarrassed right now. Whoever is reading this, please do me a favor and downvote my comment to oblivion - I don't want to delete it because it has replies.)
If you proved the Collatz conjecture to be "undecidable either way"...
The question I want to ask is "is there a proof for every statement about the natural numbers that seems to be inductively verifiable, but is a general recursive decision problem, provided your sample is large enough?" Simply, if we define a binary property 'P' that can only be tested by algorithms that might not halt, and show, say by computation, that every natural number up to some arbitrarily large number 'N' has the property P, does that mean that there must be a generalized deductive proof that for all natural numbers P holds?
How big can N get before there must be a deductive proof that P holds for all natural numbers? What if N was larger than Graham's number[1]? What if we showed thousands of years from now--using computers that are unimaginably strong by today's standards--that every number less than or equal to the number you get when you put Graham's number as both of the inputs to the Ackermann function[2] has a property P. But they still have no generalized deductive proof that all numbers have P, is that enough for these future number theorists to state that it is a scientific fact that all natural numbers have the property P?
It may seem impossible for such a disagreement to come up between induction and deduction, but we are already at a similar (though admittedly less dramatic) impasse. The disagreement centers around the Collatz conjecture, which states that every number is a Collatz number. To test if some number n is a Collatz number, if n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1, and repeat this process with the new number thus obtained, indefinitely, if you eventually reach the cycle 4, 2, 1, then n is a Collatz number. Every number up to 20 × 2^58 has been shown to be a Collatz number[3], and it has been shown that there are no cycles with a smaller period than 35400[4], yet there is still no deductive proof of the Collatz conjecture[5]. In fact, one method of generalized proof has already been shown to be undecidable[6]. If it was shown that no general proof could ever be found, but all numbers up to the unimaginably large ones described above were shown to be Collatz numbers, what epistemological status should we grant the conjecture?
It has been made clear by the history of mathematics that a lack of small counterexamples to a conjecture of the form "for all natural numbers P(n) = 1" where 'P' is a binary function (let's call this an "inductive-conjecture"), is not at all a proof of that conjecture. There have been many inductive-conjectures with that sort of evidence in their favor that have later been shown not to be theorems, just because the counter examples were very large. But what if a proof of the undecidability of a conjecture of that form is given, what then if no counter example had been found up to the insanely large values described above?
If there is a binary property 'R' that holds for all natural numbers, i.e., there is no counter example, and it can be deductively shown that no proof of 'R' holding for all natural numbers exists, then the implications for epistemology, ontology and the scientific/rational endeavor in general are huge. If some facts about the natural numbers don't follow from the application of valid inferences onto axiom and theorems, then what makes us think that all the facts about the natural world must follow from natural laws in combination with the initial state of the universe? If there is such a property, then that means that in a completely deterministic system where you have all the rules describing all the possible ways that things can change, and you have all the rest of the formally verifiable information about the system, there still might be some fact about this system which is true but does not follow from those rules. Those statements would only be verifiable by finite probabilistic sampling from an infinite population with an undetermined standard deviation, but still be true facts. Our crowning example of such a system would of course be the theory of the natural numbers itself if such a binary property were discovered. Suppose the Collatz conjecture were shown to be undecidable, that would mean that there is no counter example, i.e., all numbers are Collatz numbers (since the existence of a counter example would guarantee the conjecture's decidability), but there would also be no generalized proof that no counter example exists (since the existence of such a proof would guarantee the decidability of the conjecture). So since we can't verify the conjecture either way, should we call it meaningless/unverifiable? Or is logically undecidable somehow distinct from literally meaningless? What restrictions/expectations should we have if we believe that an inductive-conjecture is undecidable, and how would those restrictions change if we believed that conjecture was actually unverifiable.
Let's call the claim that "there is a binary property R which holds for all natural numbers and that there is no counter example that can or will ever be found, but which also cannot be proven to hold for all natural numbers" the "first Potato conjecture". How would one ever show the first potato conjecture, or even offer evidence in it's favor? Let's say we knew that some property 'R_b' held of all natural numbers that we might ever test. Then we would have a proof of this and R_b could not be our R. If we get a candidate property 'R_c' that isn't capable of being proven or dis-proven of all natural numbers, then we will never know if it holds for all natural numbers. Could induction even offer us any evidence in this case? Is a finite sample ever representative of an infinite population with no standard deviation even in the case of simple succession? If not, then what evidence could we ever offer for or against the potato conjecture, if an undecidable inductive-conjecture were discovered? If the answer is no evidence one way or the other, does that mean that the potato conjecture is meaningless, or just undecidable?
(But no, really, I'm asking.)
[1]: http://en.wikipedia.org/wiki/Graham's number
[2]: http://en.wikipedia.org/wiki/Ackermann_function
[3]: http://www.ieeta.pt/~tos/3x+1.html
[4]: http://www.jstor.org/pss/2044308
[5]: http://en.wikipedia.org/wiki/Collatz_conjecture
[6]: Quoting Lagarias 1985: "J. H. Conway proved the remarkable result that a simple generalization of the problem is algorithmically undecidable." The work was reported in: J. H. Conway (1972). "Unpredictable Iterations". Proceedings of the 1972 Number Theory Conference : University of Colorado, Boulder, Colorado, August 14–18, 1972. Boulder: University of Colorado. pp. 49–52.