Why can anything be discovered in mathematics at all?

Question

Imagine a Perfect Mathematician that has superhuman abilities -- if you give him or her a formal foundational system for mathematics like ZFC with all the underlying logical machinery, he or she is able to deduce all of the possible deducible statements in that system in an instant.

Then no true mathematical statement would be unknown to the Mathematician. For example, if you tell him or her that you just made the calculation 2,541,658,478,879 times 56,856,436,487 and you discovered (the key word here) that the result was 144,509,643,876,028,894,458,073, then the Mathematician will answer "Yep, knew that. Not a discovery to me."

Does this imply that something is discovered in math in practice only because of our human insufficiencies and limitations?

A possible counterargument to the above, it seems to me, lies in showing that the idea of this Perfect Mathematician is logically contradictory (nomological contradiction does not suffice here). I don't know how to show this, though, and I believe there may be other lines of counterattack, e.g. showing that no formal foundational system like ZFC can ever equate to the entirety of mathematics, most likely arguing from the standpoint of platonism or something like that.

Answer 1

None of the other answers (so far) addressed the actual mathematical inquiry here.

Firstly, your question is straightforwardly formalized as follows: Suppose you have an oracle O that when given any computable formal system S and a sentence Q can determine in finitely many steps whether or not Q is a theorem of S. Then you ask whether or not O can be used to generate all and only true arithmetical sentences. (This notion of finite-step oracles is a standard way of formalizing programs that can use oracles. See any text on computability theory for technical details, but finer details don't really matter.)

Note that I changed "true mathematical statement" to "true arithmetical sentence", because the former is meaningless but the latter is meaningful once you assume the existence of the structure (ℕ,0,1,+,·). So what is the answer to the formalization of your question?

No! To see why, observe that we can trivially construct such an O using the halting oracle (the oracle that solves the halting problem for programs). But by the generalized incompleteness theorem, the set T of all true arithmetical sentences is not the theorems of any formal system that has a proof verifier program that is permitted to invoke the halting oracle! So O cannot generate T.

In fact, the very same theorem in the linked post generalizes to every finite Turing jump (the (k+1)-th jump is the oracle that solves the halting problem for programs that can invoke the k-th jump), as was briefly mentioned at the end of the linked post. Thus the answer is still no even if you allow your oracle O to invoke any finite jump (not just be able to determine deducibility over any foundational system).

In other words, if you want to generate all true arithmetical sentences, you need an oracle that is at least as powerful as the ω-th jump, in the sense that you need to be able to invoke any finite jump you like. This directly corresponds to the quantifier complexity of the arithmetical sentence (arithmetical hierarchy). We can computably decide the truth-value of any Σ0-sentence, since we can enumerate all the cases when all quantifiers are bounded. It is not hard to see that we can decide the truth-value of any Σ1-sentence using the first jump (halting oracle), by asking whether the program that tries each possible value of the outer "∃" one by one halts or not. It turns out that we can in general decide the truth-value of any Σ[k]-sentence using the k-th jump.

Note that there have been extremely difficult mathematical problems that were shown (in a slightly stronger foundational system) to be equivalent to some arithmetical sentence of very low complexity. For example, Riemann Hypothesis is known to be equivalent to a Π1-sentence, so your powerful mathematician would already be able to solve it. But both Twin-Prime Conjecture and P≠NP are only known to be Π2, so we can solve them using the second jump but your powerful mathematician may not be able to solve them. However, your powerful mathematician can tell you whether ZFC proves or disproves any of them, and maybe that is good enough for you (if you assume ZFC does not prove any false arithmetical sentence).

For the curious, the mathematical content of this answer does not rely on any assumptions except the existence of (ℕ,0,1,+,·) as a model of PA and the existence of all finite jumps. These assumptions are provided by a very weak system known as ACA, so you can be assured that there are no sneaky philosophical assumptions that this answer relies on.

Note also that we in fact cannot extend the notion of "true arithmetical sentence" to "true mathematical statement". In the first place, "true arithmetical sentence" is defined as "arithmetical sentence true in N where N = (ℕ,0,1,+,·). So "true mathematical statement" is as meaningless as "true jyxowvazic statment" in the sense that we have not defined "mathematical statement".

Even if we fix our foundational system, say as ZFC, we cannot define "true ZFC statement" in the same manner because we would need to define it as "sentence over ZFC true in M" where M is some specific model of ZFC. But ZFC cannot prove the existence of a model of ZFC, again by the incompleteness theorem (in conjunction with the semantic completeness theorem for FOL), so this fails. The same goes for essentially any reasonable foundational system, not just ZFC.

Neither can we define "true set-theoretic sentence" as "sentence over ZFC that is true in V" where V is class of all sets (i.e. the meta-universe), because if this notion was definable by a predicate Tr then we can explicitly write down (by the same diagonalization as in Godel's original proof of the incompleteness theorem) a sentence D over ZFC such that we can prove D⇔¬Tr(str(D)) where str(D) is the string representing D, and then get D⇔¬D, which we certainly do not want to get. This fact was discovered by Tarski, and is called Tarski's undefinability theorem.

But anyway all that does not matter for the original inquiry. If the halting oracle is not powerful enough to enable us to decide all true arithmetical sentences, then of course it is not powerful enough to enable us to decide all true sentences in whatever ω-model of ZFC (i.e. model of ZFC that has the standard naturals) that we might ever specify.

Answer 2

I am not entirely certain what exactly you mean, but here are some thoughts which might qualify as an answer.

The enterprise of mathematics makes use of both discovery of unexpected results and invention of new branches of mathematics. To be all-knowing, your ultimate mathematician-being would need to have in its possession every as-yet uninvented, new branch of mathematics and all as-yet undiscovered connections between those branches (which would count as "discoveries" in this context).

If this were real, then you could go up to that being and state, "every quantum field theory in n dimensions corresponds uniquely to an anti-De Sitter space conformal field theory in n-1 dimensions" and that being would reply, "yup yup, I knew all that 10^-43 seconds after the big bang".

So it seems to me that you are describing the Hilbert Programme, where the ultimate mathematician can be constructed out of materials currently on hand, after which nothing would be unknown or undiscovered ever again in the field of mathematics. But Goedel disproved that for any formal system of logical reasoning complex enough to contain self-reference, did he not?

Answer 3

I'm not sure exactly what you mean by "discovery" here. If your Perfect Mathematician knows every true math statement, does it mean he knows every theory possible to define within this mathematical system? You know there is an infinite number of those?

If so, your PM must be some kind of demon, all right. But doesn't his posession of god-like abilities make your question trivial? Because yes, we, humans, can only "discover" the knowledge we do not posess, that's the definition of the term, I guess...

Now, regarding the @nielsnielsen Hilbert-Goedel answer. I can't agree. All Hilbert thought should be possible is to deduce all the mathematics from some logical axioms. It has nothing to do with our demon mathematician nor with our question at hand, it's something totally different. Our question asks about the human ability to discover something in math. Hilbert tried to found math on logic. Not related.

Answer 4

To discover something is to find information, a place, or an object, especially for the first time.

Discovery basically means expanding your body of knowledge or possession ("you" being in either the singular or the plural). This is something we can and do definitely do.

You can "discover" that your partner is having an affair. Obviously some people already knew this, but you personally didn't, so you are discovering it because you're expanding what you personally know.

By some definitions, especially in the scientific community, "a discovery" might require adding to the body of knowledge of humanity as a whole. If it's already known by others, it's not "a discovery", even if it's new to you personally.

Discovery, for the most part, involves finding information that already exists rather than creating new information. I'm not sure the latter is strictly speaking even possible.

• You can discover a new island, despite this island having been there all the time.
• You can discover a previously unknown element in chemistry, despite that element existing before.
• Even if you create / discover a cure or a completely new element, the process to create it will already be known to an entity with perfect information of the physical world and unlimited capacity to explore all possibilities.

Answer 5

Imagine a Perfect Mathematician [who] is able to deduce all of the possible deducible statements in [ZFC] in an instant.

Then no true mathematical statement would be unknown to the Mathematician.

That is incorrect, at least with standard propositional logic or standard predicate logic.

In standard logics, one of P or not-P must be true for any proposition P. But in ZFC, it is either true that there are some cases where neither P nor not-P is provable, or it is true that P and not-P are both provable for every P.

There is a family of logics (intuitionist logics) where no distinction is made between "truth" and "provability". However, ZFC is not compatible with intuitionist logic, and generally the axiom of choice (one of the axioms of ZFC) is rejected by intuitionists.

[other stuff] Does this imply that something is discovered in math in practice only because of our human insufficiencies and limitations?

In my opinion, yes. Mathematical theorems are true prior to our noticing proofs for those theorems. They are "discovered" only in the sense that we learn about them at some moment in time.

A possible counterargument to the above, it seems to me, lies in showing that the idea of this Perfect Mathematician is logically contradictory.

The Perfect Mathematician in your argument is logically contradictory, as I mentioned above. ZFC is either incomplete or inconsistent. That is, either there are propositions in ZFC for which neither the statement nor its negation may be proven, or alternatively, all propositions are provable. Somewhat ironically, if one can prove that ZFC is consistent within ZFC, then ZFC must be inconsistent.

But, I don't think the impossibility of the Perfect Mathematician, ruins the notion that mathematical discovery is, in a sense, like the discovery of previously unknown (but nevertheless existing) islands.