3

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.

15
  • 6
    Just to be the devil's advocate, isn't the existence of discovery of ANYTHING only due to our limitations? I mean the discovery of Pluto only happened because we didn't have good enough telescopes at first. The discovery of the pineapple (by Europeans) due to hot having good enough boats or the correct motivation.
    – Daron
    Feb 19 at 23:12
  • 1
    Real mathematicians constantly create new systems of axioms, which the Perfect Mathematician is incapable of. But for discoveries within a fixed axiomatic system you are more or less correct, only surface information is available to us limited humans, and depth information has to be discovered, see What is the difference between depth and surface information?
    – Conifold
    Feb 20 at 4:48
  • 3
    [Nitpick: multiplying 2 numbers is just a calculation, not a discovery. A discovery involves ending up with some meaningful result (which may involve calculations), e.g. this multiplication could give you a previously-unknown number with some rare properties, like how you could discover a new prime number through other calculations.]
    – NotThatGuy
    Feb 20 at 5:16
  • 1
    Should we assume that this Perfect Mathematician doesn't just implode into a black hole because of information-energy equivalence?
    – nick012000
    Feb 20 at 9:41
  • 2
    Your "Perfect Mathematician" would not necessarily be able to answer the mathematical question, "What is the correct formulation of the Hodge Conjecture?" See for instance Grothendieck's paper "Hodge's general conjecture is false for trivial reasons," which was really about showing that the letter of the conjecture needed to be tweaked; the conjecture (in a slightly different form) is still a major open problem. Feb 20 at 16:17
4

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.

16
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Geoffrey Thomas
    Feb 21 at 12:25
  • So, what exactly is the difference between a "mathematical statement" and a "mathematical sentence"? You use a bunch of mathematical jargon in this answer without explaining what it means.
    – nick012000
    Feb 21 at 23:58
  • @nick012000 - The answer only refers to an "arithmetical sentence", not a more general notion of an arbitrary "mathematical" sentence/statement. user21820 , would "arithmetical sentence" be something like a well-formed formula in first-order logic where the "vocabulary" consists of the symbols and functions used in the Peano axioms for arithmetic, which are listed on p. 76 here?
    – Hypnosifl
    Feb 22 at 0:50
  • Also, when you mention an oracle as powerful as the ω-th Turing jump that could decide all arithmetical statements, would it do that just based on the Peano axioms plus some non-computable rules for checking infinite collections of statements deduced in some way from those axioms (checking every possible triplet of a whole number and two prime numbers to see if any violate Goldbach's conjecture, for example), including collections of statements "deduced" by some lower-level oracle?
    – Hypnosifl
    Feb 22 at 3:31
  • 1
    @nick012000: Both phrases you ask about are meaningless for the exact reason I stated in my answer: "true mathematical statement" is as meaningless as "true jyxowvazic statment" in the sense that we have not defined "mathematical statement". While I did not intend the typo there, it is correct even with the typo. Concerning defining mathematical jargon, you are welcome to ask for help in understanding what you do not know, but I am not obliged to type out hundreds of pages to teach you something you can learn from any introductory text to logic. If you want references, ask.
    – user21820
    Feb 22 at 12:44
3

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?

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.

1

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.
4
  • I don't have any issue with your post here (and did not downvote it), but it does not answer the mathematical question that is clearly what the asker is interested in. Mathematically, relative to any chosen standard model N of PA, of course all truths about that model, denoted Th(N), are fixed and cannot be created (as you said), and may (or may not) be discovered (or believed). The question here was essentially asking whether having a deductive closure oracle was strong enough to allow you to discover every mathematical theorem. As my answer showed, it is impossible even for just Th(N).
    – user21820
    Feb 21 at 8:05
  • On the other hand, your post does address one possible interpretation of the asker's question title "why can anything be discovered at all".
    – user21820
    Feb 21 at 8:07
  • @user21820 I'm not sure where you got that idea. I'm just answering the (philosophical) question as written. The question starts by establishing an entity that already knows every discovery we could possibly make. Then the actual question is very much about the definition of discovery. It mentions "human insufficiencies and limitations", which is arguably the reason we discovered things when we did instead of much earlier or just knowing it all along. If the question is indeed looking for what you say, then I'd argue it's in need of a significant edit or rewrite.
    – NotThatGuy
    Feb 21 at 8:30
  • 1
    The question did not start by assuming an entity that already knows every discovery. It explicitly defined what it meant by "perfect mathematician" by saying: "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". That is literally the description of an oracle for Th(ZFC). Nothing more to say. I don't know why you can't read the question as it is written.
    – user21820
    Feb 21 at 8:43
1

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.

4
  • "The Perfect Mathematician in your argument is logically contradictory, as I mentioned above. ZFC is either incomplete or inconsistent." -- Can you elaborate on this? I don't see the connection.
    – Alex
    Feb 21 at 19:21
  • @Alex see Godel's incompleteness theorems. Incomplete means that there are propositions P, such that neither P nor not-P can be proven. Inconsistent means that for any proposition P, both P and not-P can be proven. Feb 21 at 19:26
  • I know all this, but how exactly does this prove the Perfect Mathematician is logically contradictory?
    – Alex
    Feb 21 at 19:42
  • @Alex According to classical logics, if "A or B" is true, then either A is true or B is true (or possibly both). Since "no true mathematical statement would be unknown to the Mathematician", if he knew "A and B" is true, he would also know which of A or B or both is true. In classical logics, for any "P", "P or not-P" is true. So the Mathematician would know which is true P or not-P, for any P. If by "know" one means "justified true belief", then the Mathematician must have justification for choosing between P and not-P. But that justification would be a proof, hence all true P provable. Feb 21 at 19:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.