7
$\begingroup$

Recently I was trying to prove something, more or less elementarily, but eventually started going in circles. My prof said that the proof involves mathematical tools that I've not seen yet, and that it's unlikely there is an elementary proof.

Which got me wondering: would there be a way to prove that there is no elementary proof to a particular theorem, or even a particular kind of theorem? (other than trivial cases such as theorems already involving non-elementary maths)

So, I guess, to rephrase: a way to prove that theorem $X$ can be proved using mathematical tools that are not higher than those needed to state $X$ in the first place?

Or how about theorems that are true but maybe have no proof; can this be known? Can we prove that a theorem may or may not be true, but would have no proof if it were?


I guess this is more metamathematics than mathematics, as it would involve theorems about the properties of theorems.... is there a branch of math that studies this sort of thing? Is this what "proof theory" is?

If there is such a subject: any book recommendations that would be accessible to someone in his 2nd undergrad year? This subject is interesting to me.

3 Answers 3

7

I don't know of any way to prove that a theorem can or cannot be proven by "elementary" methods, and without giving a rigorous definition to what "elementary" means I doubt one would be able to proceed in this direction.

What I do know, is that you should look up Gödel's incompleteness theorems. The branch of math that these sorts of things are studied under is logic. An excellent book on this topic is Gödel, Escher, Bach. It is appropriate for an undergrad, indeed it was written as a popular book and assumes very little mathematical knowledge, although the more math you understand the deeper some parts of the book will seem.

I caution you, the book will seem fairly abstruse at times, and indeed it is a tome (upwards of 700 pages). The part you are interested in is about half way through. I would recommend taking your time. Once you realize how interwoven the content really is with the presentation, you will realize (perhaps) how dense the book is and how much you may have missed. I Think Surely Most Everything Truly Abstracts.*

As a gentler introduction, I would recommend listening to this podcast of Radiolab on loops. It's a great show in general, but if you want to just hit the part about Gödel it is 38 minutes in.

Unprovability, in mathematics, is called independence. One method commonly used to prove independence is called forcing. From the wikipedia article, I see that it is covered in Set Theory: An Introduction to Independence Proofs, by Kenneth Kunen. I have not read this book, but from the online preview and the comments on the wikipedia page I would have to say that it requires a strong mathematical background.

  • 1
    @fakaff I don't want to answer your question directly, not because it is not a good question or it is unclear (on the contrary, it is an excellent question!). I don't wish to address it directly because my limited answer would provide very little motivation for *why* it is the answer, and you will gain more from exploring it through a well thought out presentation like the one in GEB. I will tell you that your question is directly addressed in that book, both whether questions like that have yes and no answers and whether math can be formalized to that level.2011-11-20
5

There has been successful work towards formalizations of something that may be not not too far from what you are asking for. The most interesting is the Reverse Mathematics program pioneered by Harvey Friedman.

It is not clear to what degree (if at all) the scales developed in the Reverse Mathematics program match informal notions of "elementary proof." That notion varies widely between fields. For example, in prime number theory, "elementary proof" means roughly a proof that does not use deep tools from the theory of complex variables. In that sense, there is an elementary proof of the Prime Number Theorem, found independently by Erdős and Selberg. But it is much harder than the non-elementary proof!

  • 0
    cool! definitely beyond my level of education, but something to keep in mind for the future.2011-11-19
-3

Yes, you are right. As far as I know the works concerning your answer is on metalogic. I think books about Godel's Incompleteness theorem. and Logicians like Russell could give you a little hint. I have scanned some books about this but it's not as easy as it seems. Definitions are mandatory to make the discussion about "provability " in a certain space S of a certain theorem X. category theory, set theory ( foundations of Mathematics).. One good venture in your kind of question.

  • 2
    I downvoted this answer. I cannot make out what you mean by *"provability " in a certain space S of a certain theorem X*.2011-11-19