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.

Alex
  • 509
  • 3
  • 12
  • That counterargument does not contradict your main argument at all. What it only does is to change the scope to some other mathematical framework. If you restate the question as "under each possible foundational system" your question seems to state a proper argument. – Ghostpunk Feb 19 '21 at 21:44
  • Having set on formal foundations (a set of axioms and rules to infer from them) it seems quite straightforward that the Perfect Mathematician could apply the rules repeatedly and discover everything that can be discovered, because that is basically all a real mathematician can do (except not instantly). But how about choosing the axioms ? It seems to me like the guy who invented non euclidean geometry or imaginary numbers truly invented something, and the PM wouldn't be better at it than they were. But I am not sure. – armand Feb 19 '21 at 23:08
  • 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 '21 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?](https://philosophy.stackexchange.com/a/59428/9148) – Conifold Feb 20 '21 at 04: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 '21 at 05: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 '21 at 09:41
  • @nick012000 no, because as I mentioned in the question, nomological contradiction (which is what you're talking about) does _not_ suffice. – Alex Feb 20 '21 at 11:15
  • 1
    @Alex No, I'm not talking about logical contradiction. I'm talking about the minimum amount of possible energy used to store 1 bit of information. This guy has an infinite amount of information stored in him, therefore he should collapse into a black hole, due to exceeding the maximum allowed by his Schwarzschild radius. – nick012000 Feb 20 '21 at 12:27
  • 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. – Charles Staats Feb 20 '21 at 16:17
  • @nick012000 I said you were talking about __NOMOlogical__ contradiction, which roughly means there can't be such a thing in a world with our laws of nature. There is nothing __logically__ contradictory however in the world where such an event doesn't occur at all. We can imagine such a world without holding any contradictory thoughts. E.g., I can imagine a possible world where black holes don't form at all without any contradiction, but I can't imagine a world where two times two does not equal four. – Alex Feb 20 '21 at 16:30
  • 1
    Reminds me of Michelangelo who said roughly "I don't *create* a statue -- all of it is already there, in this block of marble! I just chisel away the obscuring pieces." – Peter - Reinstate Monica Feb 20 '21 at 18:04
  • OP, I'm wondering whether/how you apply your reasoning to other areas. What about music? You could argue that music is not created by the author, because all they are doing is writing a possible combination of notes/silencies/instruments, etc. – Martin Argerami Feb 20 '21 at 21:19
  • 1
    @nick012000: Although you are right that it seems (based on current scientific knowledge) impossible for the halting oracle to exist in any physical form, I think it's clear that the asker is curious about the power of having such oracles (this is a standard notion in computability theory), and my answer provides a complete analysis for that question. – user21820 Feb 21 '21 at 07:40
  • 1
    @Alex: I added a lot more detail to my answer, including some famous conjectures. Have a look, and feel free to ask about any of the mathematics involved. =) – user21820 Feb 21 '21 at 11:16
  • It seems your assumption from your concern is V=L(Godel's axiom of construction) and there exists oracle machine. But keep in mind in physical reality there're not such oracle deciding any problem in a single step, it's TM at best thus can only find surface information within a formal system usually like most cloud apps, not those depth info. Humans are uniquely capable to do the latter due to intuitions or any words starting with "in" metaphorically... – Double Knot May 04 '21 at 22:48

5 Answers5

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.

user21820
  • 623
  • 1
  • 7
  • 17
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/120004/discussion-on-answer-by-user21820-why-can-anything-be-discovered-in-mathematics). – Geoffrey Thomas Feb 21 '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 '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](https://en.wikipedia.org/wiki/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](https://www.math.wisc.edu/~miller/old/m571-08/keisler.pdf)? – Hypnosifl Feb 22 '21 at 00: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](https://en.wikipedia.org/wiki/Goldbach%27s_conjecture), for example), including collections of statements "deduced" by some lower-level oracle? – Hypnosifl Feb 22 '21 at 03: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 '21 at 12:44
  • @Hypnosifl: Yes to your first question; that is one possible axiomatization of PA, and "arithmetical sentence" is simply "sentence over the language of PA". Another can be found [on wikipedia](https://en.wikipedia.org/wiki/Peano_axioms#Equivalent_axiomatizations). The actual choice is irrelevant because all these systems are (in some technical sense that does not matter) equivalent. – user21820 Feb 22 '21 at 12:45
  • @Hypnosifl: To your second question, the reason I did not explain that general claim for higher than Σ1 is because it is not so easy to prove the equivalence. I actually gave a sketch of proof in [this post](https://math.stackexchange.com/a/2582086/21820), which is also linked from the final section of my linked post on the generalized incompleteness theorem. The key is that you can interpret any Σ[k+1]-sentence as a claim about halting of some program that uses the k-th jump, and thereby determine the truth-value of that sentence by asking the ω-th jump one question. [cont] – user21820 Feb 22 '21 at 12:49
  • [cont] Goldbach's conjecture is actually Π1; it says "every even positive integer is two or the sum of two primes", where "is the sum of two primes" can be expressed by a Σ0-sentence because it only requires bounded quantifiers. Only the outermost "every even positive integer" requires an unbounded "∀". So to determine the truth-value of Goldbach's conjecture you only need the halting oracle (1st jump). [cont] – user21820 Feb 22 '21 at 12:55
  • [cont] But I think you got a vague idea for higher levels of the hierarchy. Look at the twin-prime conjecture, which is Π2. Let TP be the program `k=1; while(true){ if(¬H("p=k; while(true){ if(prime(p)∧prime(p+2)) return; p++; }")) return; k++; }` where `H` is the halting oracle and `prime` is a program that decides primality. Then TP halts iff Twin-Prime is false. So you can use the 2nd jump to determine the truth-value of Twin-Prime. – user21820 Feb 22 '21 at 13:03
  • Thanks--maybe you could check my conceptual understanding of the levels of the hierarchy? From a book by Roger Penrose I came across the idea of an "oracle machine" which combines the capabilities of a Turing machine with a special operation where it can consult an oracle to learn whether some lower-level machine halts or not when given a particular input. So, would the first Turing jump give the set of all arithmetical/computational questions that can be answered by a level 1 oracle machine whose oracle tells it whether a given Turing machine program+input halts? – Hypnosifl Feb 22 '21 at 23:10
  • (cont.) And then the second Turing jump would give the set of all such questions that can be answered by a level 2 oracle machine which can solve the halting problem for either a Turing machine or a level 1 oracle, and so on? So then if a level ω oracle machine can solve the halting problem for a Turing machine or any finite-level oracle, that would be the lowest level machine that can decide the truth-value of any well-formed formula about arithmetic, expressed in first-order logic? – Hypnosifl Feb 22 '21 at 23:12
  • @Hypnosifl: That's right! Though we must be a bit careful. A level-1 machine M can consult the halting oracle H0 for level-0 machines multiple times, and the number of times is not necessarily bounded over all inputs (e.g. it is permitted that M can consult H0 k times on input k). So the set of programs *using* the first jump is equivalent to level-1 machines, and the set of programs using the k-th jump is equivalent to level-k machines, exactly as you thought. But in fact non-trivially we can invoke the k-th jump just once to compute anything that can be computed by a level-k machine! [cont] – user21820 Feb 23 '21 at 06:11
  • [cont] That is essentially the main content of the post that I linked to in my earlier comment at "All that remains is to show that the output behaviour of a program P that uses H[n] as an oracle can also be captured by a Σ[n+1]-sentence θ", since it is easy to prove by induction that the truth-value of a Σ[n+1]-sentence can be obtained by just one invocation of the (n+1)-th jump. [cont] – user21820 Feb 23 '21 at 06:19
  • [cont] And yes, since the level-ω machine can solve the halting problem for any finite-level machine, it can decide the truth-value of any arithmetical sentence. But you need the incompleteness theorem to know that it is the lowest possible, which again needs the theorem that halting of a level-k machine is expressible as a Σ[k+1]-sentence. So there is really some non-trivial phenomenon here (in case it wasn't fully clear from my earlier comments). Please feel free to ask me more, and we can [continue in chat](https://chat.stackexchange.com/rooms/120069) at length! – user21820 Feb 23 '21 at 06:23
  • You conclusion seems "... it is not powerful enough to enable us to decide all true sentences in whatever ω-model of ZFC". Also you indicated "Riemann Hypothesis is known to be equivalent to a Π1-sentence, so your powerful mathematician would already be able to solve it." At least seems your oracle at the 1st Turing jump already solved RH. But RH is a depth-level info entailed by PA if it's true and resists proof so far notoriously. So for practical purpose here what other aspects can mathematical logic help to resolve RH? (ideal oracle with ω-jump seems moot and no help for depth-level info.) – Double Knot May 05 '21 at 03:30
  • @DoubleKnot: Your comment makes little sense. I never claimed that logic can help to resolve RH. And I do not believe it can. And "depth-level info" makes no sense at all. – user21820 May 05 '21 at 06:08
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?

niels nielsen
  • 7,173
  • 1
  • 13
  • 24
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.

k-wasilewski
  • 295
  • 1
  • 9
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.
NotThatGuy
  • 4,003
  • 13
  • 18
  • 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 '21 at 08: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 '21 at 08: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 '21 at 08: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 '21 at 08: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.

  • "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 '21 at 19:21
  • @Alex see [Godel's incompleteness theorems](https://plato.stanford.edu/entries/goedel-incompleteness/). 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. – Math Keeps Me Busy Feb 21 '21 at 19:26
  • I know all this, but how exactly does this prove the Perfect Mathematician is logically contradictory? – Alex Feb 21 '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. – Math Keeps Me Busy Feb 21 '21 at 19:58