/sci/ - Science & Math

>>11468904
Many ways of how to read that question.
The one you're probably looking for is
>Yes, e.g. the Paris–Harrington theorem
https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem
>For any positive integers n, k, m one can find N with the following property: if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n-element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.
Similarly, to quote from
https://en.wikipedia.org/wiki/Goodstein%27s_theorem
>It was the third example of a true statement that is unprovable in Peano arithmetic, after Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic.

That said, with the more autistic reading of it the answer is more trivially yes in that all undecidable statements are some natural number claims and thus "problems". But yeah, okay.
As it's the core of the incompleteness theorem that you can encode Turing complete expression in the theory, the answer is yes less autistically also in that "problem about algorithms expressed in this way" also work. E.g. the Halting problem is a problem "in" the theory. But yeah okay, you wanted a practical natural number example I guess.

Related to the above encodings is also that you can encode countable structures (count through all polynomial p(x) with coeffs in N and \forall quantify over the argument x) and thus grab problems from those realms.

Interesting undecidable problems are Hilberts tenth
https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem
or the moral matrix problem
>Two 15 × 15 matrices A and B either can be multiplied in some way to yield the zero matrix or not

And then we have the nonstandard models (but I'm out of characters), you can read up explicit ones and any diverging fact about them will be undecidable