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.

|cite|improve this question
$\endgroup$
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I really like Kunen's book (what little I know about this stuff I learned from this book and Jech's Set Theory). But you're right that Kunen's book (and Jech's) are not easy reads, at least when initially learning this stuff. I supplemented with Ciesielski's Set Theory for the Working Mathematician, especially when I was still getting used to ordinals and cardinals. $\endgroup$ – Jason DeVito Nov 19 '11 at 5:19
  • $\begingroup$ @process91 thanks for the info. I happen to own GEB, but I've yet to read it, so maybe I'll put it sooner on my to-read list (I bought it because I'm a huge fan of Lewis Carroll and saw it started with a piece written by him). — "without giving a rigorous definition to what "elementary" means [...]" — would this still be within the bounds of logic, to analyze the structure mathematics rigorously and categorize it in a meaningful way, or would it be something else? is this even possible? $\endgroup$ – iDontKnowBetter Nov 19 '11 at 5:32
  • $\begingroup$ @fakaff I am thinking about it in the following, very propositional way (and you should definitely read GEB for more background about this): If everything is proved from starting axioms, your definition of elementary would be something like "it takes no more than X steps from an axiom to B". As a result, you would get a finite list of theorems provable by X steps, because with a finite number of steps you could exhaust all possibilities. This does not, however, really address the issue of what we mean when we say "elementary", which is... $\endgroup$ – process91 Nov 19 '11 at 13:32
  • $\begingroup$ @fakaff ... more about the simplicity of tools involved. Indeed, each step of a complicated proof can be made "simpler" in some sense by replacing an advanced step (say something with is based on complex variables) with the steps used to prove that step in the first place. This does not aid our understanding, however, and would not likely be seen as being more "elementary" for this reason. The hitch is linking a precise definition of "elementary" with our intuitive notion of the term; indeed, this is what any definition in mathematics tries to do. $\endgroup$ – process91 Nov 19 '11 at 13:41
  • 1
    $\begingroup$ @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. $\endgroup$ – process91 Nov 20 '11 at 2:21
5
$\begingroup$

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!

|cite|improve this answer
$\endgroup$
  • $\begingroup$ cool! definitely beyond my level of education, but something to keep in mind for the future. $\endgroup$ – iDontKnowBetter Nov 19 '11 at 6:09
-3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I downvoted this answer. I cannot make out what you mean by "provability " in a certain space S of a certain theorem X. $\endgroup$ – Srivatsan Nov 19 '11 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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