Mathematics desk
< May 14	<< Apr \| May \| Jun >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 15

Natural examples of propositions high up in the arithmetic hierarchy

The article on Arithmetical hierarchy gives many examples of formulae under Pi^0_2, but examples of propositions higher up the hierarchy either come from classes of proposition in Cantor and Baire space or come from recursion theory. Are there concrete, natural examples in arithmetic not below Delta^0_3? — Charles Stewart (talk) 11:41, 15 May 2018 (UTC)[reply]

I'm afraid this is only tangentially related to your actual question, but you might be interested anyway. Alessandro Andretta (and someone else, I think, can't remember who) managed to cook up a problem from dynamical systems to which the answer was a

\Sigma _{4}^{0}

-complete set in the plane. It had something to do with a flow where the set of starting points that ... something ... was of that complexity. It wasn't exactly natural, but it did show that this complexity class could in principle come from some field other than logic. --Trovatore (talk) 20:51, 15 May 2018 (UTC)[reply]

Right. Analysis generally makes use of formulae of higher complexity than arithmetic: the definition of continuity is a Pi^0_3 proposition. Computable analysis can be done in constructive type theory, which can be embedded in arithmetic, but this embedding makes use of recursion theory, since computable reals are defined using recursive functions. — Charles Stewart (talk) 11:56, 16 May 2018 (UTC)[reply]

Looking at the definitions in the article, I think that the Hilbert-Waring theorem is Pi-0-4. But I may have miscounted. 2607:FCD0:100:8303:5D:0:0:B7D4 (talk) 02:46, 22 May 2018 (UTC)[reply]

@Chalst: ^^^^ 2607:FCD0:100:8303:5D:0:0:B7D4 (talk) 02:48, 22 May 2018 (UTC)[reply]

Given that the set of all proofs is infinite, how come we can do math at all?

If we search for the proof of a theorem then, assuming that there exists a proof, it lies in the set of all proofs of all provable theorems. But since this set is infinite, this means that the shortest length of the proof can be arbitrarily large. Almost all provable theorems will thus have a minimum proof length that exceed our ability to find them by some arbitrary large margin.

How can we then explain the fact that there are many proven theorems in mathematics? These theorems cannot be typical theorems, but what makes them atypical that makes their proofs to be short? Count Iblis (talk) 22:31, 15 May 2018 (UTC)[reply]

Luckily we don't do mathematics by searching the space of formal proofs. --Trovatore (talk) 22:35, 15 May 2018 (UTC)[reply]

If the proof of a conjecture would be of an astronomically large length, we would never be able to deduce it. Now, almost all proofs of provable theorems are of astronomically large size, but the math we actually do deals with theorems that have short proof sizes. So, it seems that the math we actually do isn't typical. Count Iblis (talk) 23:04, 15 May 2018 (UTC)[reply]

No, your premise is wrong. That's not how humans do math. It's entirely possible that a correct argument found by a human will have an "astronomically large" formal proof. --Trovatore (talk) 23:13, 15 May 2018 (UTC)[reply]

A novel is about 1,000,000 characters and there are, say, 64 possibilities for each character, so you're saying Dickens had to search through 64^1000000 possibilities before hitting on 'Great Expectations'? --RDBury (talk) 03:45, 16 May 2018 (UTC)[reply]

We don't need to search all possible strings to formulate what we want to say or write. But if there is an answer to some question, then the question that we can easily formulate defines the answer (if an answer exists at all), but there is then no guarantee that it will be small enough that it can be formulated by us. My argument here boils down to the observation that the set of answers is infinite and the questions we ask select the answers from this entire set in a (pseudo)random way, so you should expect that almost all questions are unanswerable in practice. Count Iblis (talk) 05:23, 16 May 2018 (UTC)[reply]

(Not sure I should entertain this, since the probability this devolves into a debate about semantics seems high, but...) Why should theorems with a short (or human-sized) proof be atypical compared to others in any other way that "length of shortest proof"? Human math is probably a very very small subset of the platonic math that could be feasible with infinite computation power, but that does not seem extremely surprising (or interesting) to me. A small part of a gigantic whole can still be a fairly sizeable thing. Tigraan^{Click here to contact me} 11:27, 16 May 2018 (UTC)[reply]

Mathematicians are impressed by powerful theorems, so if the human race are at all good at mathematicians of substance, then we might hope that mathematical knowledge cuts with some depth into the space of possible problems, especially if we allow probabilistic evidence. There are infinitely many propositions, for example, that are of the form e_1=e_2 where the e_i are closed arithmetic expressions; solving such problems is a trivial matter of computation accessible to weaker than average high school students.

A further consideration is that there is no such thing as the shortest proof of a theorem. Provability in ZFC is the most widely recognised benchmark of proof in mathematics, but proofs in ZFC tend to be much longer than proofs in HOL, for example, and the level of informality that is tolerated among mathematicians leads to drastically shorter proofs still. — Charles Stewart (talk) 11:47, 16 May 2018 (UTC) —[reply]

The question is like asking how an ant can find its way to a pile of food when on average the distance from an anthill to some food is halfway round the world. That there is food thousands of miles away doesn't mean there is no food nearby. Just substitute post-grads for ants and PhD theses for food ;-) Dmcq (talk) 13:44, 16 May 2018 (UTC)[reply]

It's a lot worse. Since the number of algorithms we can write in any language is only countably infinite, but the real numbers are uncountable, the measure of the numbers we can even express in the set of all reals is 0. In other words, for a random real number, the chance that we can even address it to talk about it is zero. Still, I often succeed in buying 2 apples (or oranges) ;-). --Stephan Schulz (talk) 14:53, 16 May 2018 (UTC)[reply]

This is a Zeno's paradox type problem, and contains many of the same false assumptions that Zeno has regarding dealing with infinities. The presumption that because infinity is a real mathematical concept, that reality doesn't exist, is contradicted by the fact that reality does, in fact exist. Any supposedly "logical" conclusion contradicted by direct observation must be flawed; mathematical proofs do exist, so any purely deductive process that leads you to the conclusion that they don't is wrong. --Jayron 32 13:52, 18 May 2018 (UTC)[reply]

If humans have proved a theorem, it means the proof is short enough for humans to comprehend. Also, the statement as well as the proof must be reasonably short. We know (from Gödel's speed-up theorem) that there are some short statements whose shortest proofs are extremely long, but maybe those are unusual. So short statements that are provable may tend to have short proofs. 2607:FCD0:100:8303:5D:0:0:B7D4 (talk) 02:52, 22 May 2018 (UTC)[reply]