0

Not a very mathematical question. Was just wondering... Can every math problem ever created, and that ever will be created be reformulated into a particular example of a finite set of problem classes?

For example, the open problem: Twin Primes can be stated as finding a minimum prime gap, etc, etc. And so can be reformulated as a question of "optimization", even though that in no way helps you solve it.

One overarching theme in math is that we try to come up with efficient objects as well as efficient proofs.

Define a problem class $P$ to be different from another, $Q$, if there exists some problem in $P$ that can't be written as one in $Q$, or vice versa.

Daniel Donnelly
  • 21,342
  • Probably, since all of analysis is basically just ``optimization". – Jacky Chong Oct 19 '16 at 23:40
  • The upper bound to this answer would be a countable infinity. – Q the Platypus Oct 19 '16 at 23:41
  • Depends on how you define "problem class". The neatest rigorous classification I know is that surrounding https://en.wikipedia.org/wiki/P_versus_NP_problem – user8960 Oct 19 '16 at 23:44
  • And most geometry problems are basically checking whether a given property is "geometric" or not. – Jacky Chong Oct 19 '16 at 23:45
  • "One overarching theme in math is that we try to come up with efficient objects as well as efficient proofs. " This is suspect of Bourbakism. I definitely recommend this article: http://www.math.fsu.edu/~wxm/Arnold.htm Physics and engineering are the sources to look to.:) – user8960 Oct 19 '16 at 23:45

1 Answers1

3

First, let's dispense with the trivial example: given a statement $\varphi$, let $P_\varphi$ be the problem "What is the least number which is $0$ if $\varphi$ is true, and $1$ if $\varphi$ is false?" Then $P_\varphi$ is a question about a single finite object, but is equivalent to solving $\varphi$.

Of course, this is a silly example; can we do better?

One approach to this is to look at the quantifier structure. Suppose I have a problem expressed in the form "What is the least $n$ such that [stuff]" - I want to ask, How complicated is [stuff]? This leads naturally to the arithmetic hierarchy, which lets us organize problems according to their intrinsic complexity. For instance, the Twin Prime conjecture is at level $\Pi^0_2$: "For all $n$, there exists $m$ such that $m>n$ and $m, m+2$ are each prime." Meanwhile, the version of it that you state (finding the minimal recurrent gap) is asking about the minimal element of a $\Pi^0_2$-definable set (the set of $k$ such that for all $n$, there is an $m>n$ with $m, m+k$ each prime), and the question of whether there is any recurrent gap is $\Sigma^0_3$.

There is a computability-theoretic connection here. If we let $T_n$ be the set of true $\Sigma^0_n$ sentences, it turns out that $T_n$ is strictly less complicated than $T_{n+1}$: $T_1$ is (basically) the Halting Problem, and $T_{n+1}$ is the Halting Problem "relative to" $T_n$.

Meanwhile, let's attack the stronger question you ask: whether every problem can be reduced to something "finitary." Of course the question is vague, but I would argue the answer is no - for overkill, we could look at the Continuum Hypothesis as an example of a statement which I don't believe can be reduced to a question about finite objects in any nice way. This can in fact be made precise: since CH is not invariant under forcing, Shoenfield absoluteness implies that it is not equivalent to any $\Pi^1_2$ sentence, and I'd argue that $\Pi^1_2$ strictly contains the "finitary" sentences by a wide, wide margin.

You may also be interested in this recent question.

Community
  • 1
Noah Schweber
  • 245,398