5
$\begingroup$

Imagine we have

  1. a "home domain" - a set of rules, or a "stage" upon which a question is posed, and
  2. a "question" - a set of conditions posed in language that makes sense and has meaning in the home domain in which it is posed.

Are there mathematical problems that cannot be solved exclusively and entirely upon the stage in which they are posed and in the language they are posed in?

I understand that the language I've used above is a little indefinite. Let me make an example.

The straightedge and compass construction of the regular heptagon was an open problem from antiquity. In the 1800s, Gauss (et al.) proved that the construction was impossible through the machinery of algebra. In this example, the home domain would be geometry, and the question would be the construction of the regular heptagon. This problem was seemingly impossible to prove without the advent of algebra, but I wonder - could it have been done purely geometrically? The problem was translated from the home domain to a target domain and back again - could the problem be solved without doing so?

Mathematicians often say that certain mathematical machinery is "not powerful enough" to solve certain problems - but does that mean that doing so may be incredibly difficult or that such problems are literally impossible to solve without auxiliary techniques?

$\endgroup$
1
  • 1
    $\begingroup$ Roughly said, using "Godel-type" arguments and defining a self-referencing problem may possibly answer your question. Paradoxical problems are usually interesting, but your question is far more challenging than what initially seems. Great question! $\endgroup$
    – sam wolfe
    Nov 21, 2019 at 21:45

1 Answer 1

3
$\begingroup$

This is a great question, and part of the motivation for mathematical logic, especially proof theory and model theory. Unfortunately it is too vague to admit a definite answer, but there are definitely some things we can say which shed light on the situation.


Let me start on a positive note. Godel's completeness theorem (no, that's not a typo) says that in many cases we can stay within our original setting. Specifically, Godel showed the following:

If a sentence $\varphi$ is true in every structure satisfying a theory $T$, then there is a proof of $\varphi$ from $T$.

Here "proof" is meant in a very formal and concrete sense; in particular, in constructing a proof we're reasoning entirely inside the language of $T$.

Of course, the above needs some elaboration - in particular, the sentence and theory in question have to belong to first-order logic, and when we go beyond first-order logic (e.g. to second-order or infinitary logic) we generally lose completeness - but it's an important sufficiency result.


Now let me criticize the above.

First of all, the completeness theorem isn't as satisfying as it may first appear. In particular, we may whip up a theory $T$ with an intended model (e.g. first-order Peano arithmetic (PA)'s intended model is the usual natural numbers) which nonetheless has lots of unintended models which might differ quite strongly from the intended model (e.g. Godel's incompleteness theorem says that this happens with PA). So we may be in a situation where a statement is true (in that it is true in the intended model of our theory) but not provable from our theory since our theory has unintended models.

Second, this doesn't address the issue of proof speedup. Godel also showed that we can often get drastically shorter proofs by passing to more expressive settings, so that introducing a new context can be practically necessary even if it's not genuinely necessary. This is the real issue in mathematics as actually performed (e.g. we can prove Fermat's last theorem without talking about anything other than natural numbers - but should we?).

Finally, there's a linguistic barrier. The sentence $\varphi$ has to be first-order and in the same language as the theory $T$. But sometimes we're interested in statements which don't fit this picture. For example, let's look at the regular heptagon problem. At first glance, the sentence we care about is "A regular heptagon cannot be constructed with straightedge and compass," and the most obvious theory to work in is Euclidean geometry. But the language of Euclidean geometry can't actually express the sentence above - the culprit is that "constructions" aren't actually things it talks about directly (it only talks directly about points, lines, and circles). So we need to go to a larger context to even express our goal - or do some real work to transform our goal into something appropriately expressible.

  • This linguistic barrier issue is, incidentally, at the heart of Godel's incompleteness theorem. The bulk of the proof of GIT consists of showing that even though concepts like provability aren't built directly into the language of arithmetic, they can still be "interpreted" in arithmetic. So sometimes the language you care about is more expressive than it may first appear. (Unfortunately, geometry really isn't.)

So the takeaway from Godel's completeness theorem in light of the concerns above is the following:

If a first-order sentence is true in every model of a first-order theory, then that sentence can be proved from that theory without introducing any new concepts. However, many natural statements we want to prove may not be appropriately first-order, the theory itself may be weaker than intended so that a "true" statement can fail to be "necessarily true" in the sense of the theory, and even ignoring these issues finding a proof in the original theory alone may be prohibitively difficult.

$\endgroup$
1
  • $\begingroup$ Wow, this is a really expansive and complete coverage of my question. I haven't yet had any interactions with rigorous mathematical logic, so this is a great starting point for more reading. I'm really thankful that MSE has people like you who can take my half-baked ideas and really put words to them. Thank you so much! $\endgroup$ Nov 22, 2019 at 5:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .