0

Learning math every day I still cannot answer one question: do my proofs complete, or, have I missed some special case?

In order to answer that I am going go through some logic books and the books about the proof theory, as I hope to get answers there.

If you are an experienced mathematician, tell me please, is that a good idea? Can logic and proof theory answer the question "Is the proof correct and complete?" ?

If so, what would you advice me to look at first? There are many subfields of logic and I am not sure what "kind" of logic deals with the correctness of proofs.

Thank you.

  • 2
    I don't think you will find what you are looking for in those books, as logic and in particular proof theory are not about acquiring these basic skills. – Andrés E. Caicedo Feb 01 '18 at 21:40
  • well, if the skill is basic, how would you advice to achieve it? @AndrésE.Caicedo – jupiter_jazz Feb 01 '18 at 21:46
  • 1
    It's surprisingly hard concept to pin down/define etc. Writing good proofs is an artform. The best way to know if a proof is correct, at least at first, is to ask someone who would know. You get better at it with practice. – Ryan A Feb 01 '18 at 21:49
  • 1
    @Kirill Try a book on proof techniques. $\textit{How to Prove It}$ by Velleman is a great book. I think it offers exactly what you are looking for. – Sprinkle Feb 01 '18 at 21:50
  • thank you, @Sprinkle ! It sounds similar to some book of Polya - the name of that was somehow similar :) I will look at that. – jupiter_jazz Feb 01 '18 at 22:00
  • @RyanA the main problem I meet in this approach - I do not want to exercise in writing bad proofs. In order to find out how a good proof should look like, I try to look at that as on some mathematical object. That means, I try to understand its' structure and analyze his properties. I do not think that is a bad approach. – jupiter_jazz Feb 01 '18 at 22:04

1 Answers1

2

The basic idea of a proof is you chain together a sequence of logical implications. How do you know a proof is correct? There is a definitive way. Hopefully the following helps.

Consider:

Statement $P$: $p$ is a prime number larger than $2$ Statement $Q$: $p$ is an odd number.

By writing $P\implies {Q}$, you are saying "if $P$ is true, then $Q$" is true.

Proving this statement requires basic knowledge of prime numbers and isn't difficult.

In a long proof, such as proving $\pi$ is transcendental, you are chaining together say dozens of implications via sound arguments. $P_1\implies P_2 \implies ... \implies P_n$, where each pair requires it's own reasoning.

There is no inherit difference between how proofs are done in any field of math. The trick is how do you chain the statements together? If all links in the chain are logically valid, then the proof is correct. That is the only criteria needed. The rest boils down to taste/preference. For example, maybe there is a shorter proof where certain hypotheses can be relaxed. This is a matter of style, but never influences whether or not the proof is correct or not.

This requires any combination of the following three:

$(1)$. Technical expertise

A student, now matter how brilliant and talented at logical thinking, is not going to prove a research level theorem about compact operators in Hilbert Spaces by only knowing calculus theorems. This is knowledge, and the more you know, the more resources you can pool from to prove a theorem.

$(2)$ Tricks of the trade

Here I refer to common methods/themes of proving theorems in a field of math that are not immediately obvious to newcomers, but most experts would attempt a proof using these tricks.

An example from PDEs: Prove there is a unique solution to a given PDE. The common trick is to say assume there are two solutions, $u$ and $v$. You then define $w=u-v$ and prove $w=0$, this shows that $u=v$ so the solutions are actually the same. If an expert is trying to show a solution to some poorly researched PDE is unique, you can bet that he/she will start with this strategy.

This is just one of many "tricks." This trick is so common that most people studying PDEs, even at only the advanced undergraduate level, have likely been exposed to this trick, and if not, can probably deduce this is a common way of proving a result.

$(3)$. Ingenuity/creativity

This cannot be taught. This is required when trying to prove something where the first two techniques are not working. For the Millenium Prize problems, not only do you have to likely chain dozens of statements together, each link in the chain is difficult to prove even to experts, and no one has an idea how to link them together.

  • Thank you for the answer! There are some "proofs" that I - personally - do not accept as proofs, as they seem to be too informal for me. E.g. 1) Handshaking lemma. The one usually proves that with a logical argument like "it is clear, that we count the elements twice, hence the lemma is true". I would say - we have an identity we have to check. And some proof will be not a proof until it comes clearly from one side of the equation to another. 2) Every subspace of $\mathbb{R}^n$ has a basis. We need to observe cases - is the subspace empty, or contains only $0$, or... – jupiter_jazz Feb 01 '18 at 22:14
  • 1
    agreed, handwaiving is not a proof technique ;). Basically, a mathematical statement must be precise "counting elements twice" in of itself is not rigorous mathematics. What I wrote applies specifically to mathematically rigorous statements. This way, there is absolutely zero room for ambiguity. – Kernel_Dirichlet Feb 01 '18 at 22:16
  • ... so on. But my questions meets especially these points - how to prove without loosing some of the cases, how to be sure that the proof is complete? I was sure that is logic that says "there is either this, or not", so there is no third possibility. – jupiter_jazz Feb 01 '18 at 22:16
  • So that is called the "law of the excluded middle", this basically means something is either true OR false, but not both. While I am unfortunately not a logician, most mathematicians do not worry about proofs being something either than true or false. A proof is either correct or not. Mathematics is much more than studying the nuts and bolts of proving theorems themselves. Unless you plan on getting a PhD in mathematical logic, just focus on the ideas I discussed in my answer! Finally, if my answer is sufficient, don't forget to accept it, not just upvote! – Kernel_Dirichlet Feb 01 '18 at 22:30