What is the basis for a proof?

What is the basis for a proof? I am trying to understand what a proof is, what is the most simple example of a proof? like can you have a 'proof' for $1+1=2$?

Solution 1:

What is a proof? Well, commonly in mathematics this either means "a rigorously convincing argument" or a "formal proof". I will talk about the latter here, and I will specifically take the axiomatic approach to what is a proof.

Well first we need to understand what is an "inference rule". An inference rule is a rule which allows us to deduce a formal assertion from previous assertions.

For example, "If $\alpha\land\beta$ [read: $\alpha$ and $\beta$] are true, then $\alpha$ is true". This means that if we assume something which has a certain form then it is permitted to derive a certain statement. For example:

You are wearing a black coat. Therefore you are wearing a coat.

We assumed that you are wearing a coat and that the coat is black, we deduced that you are wearing a coat. It seems trivial, but in fact inference rules come to formalize a very trivial reasoning, or to quote Mr. Spock "It's only logical".

Now what is a proof?

Well... before we talk about that we need a framework. We work with mathematical logic. In this context we have symbols to write our proof (e.g., $\land$ is the letter for "and"). We have inference rules, and we have axioms of logic which are a bit like inference rules, but slightly different. In less-mathy environment there are usually a lot of inference rules and less axioms; while in the course I took in my undergrad there were many axioms but only one inference rule.

In the mathematical logic we also have rules to tell us what sort of strings are valid formulas, sentences or terms in the language. Much like "Chair me dog" is not a valid English sentence. We only care about syntax, about the form, not about the content. Nonsense like "I ate the invisible chair for dinner last night." is syntactically correct, but has no meaning -- we don't care. So legal strings of characters are called formulas or sentences. Formulas and sentences describe some relations, or properties of objects. Terms are also valid strings of letters in the language, but those describe objects rather than properties.

So now can we get to the point? What is a mathematical proof??

Well, one last thing before we get to that. Axioms, we prove things from axioms. What are axioms? Axioms are simply sentences which we assume to be true. We may not even have axioms, in which case we prove something from the axioms of logic and the inference rules, and then whatever we proved is always true in this framework.

Now we can get to the point!

What is a proof? Well, we prove $\varphi$ from a collection of axioms $T$. This means that there is a finite sequence of sentences $\varphi_1,\ldots,\varphi_k$ such that:

1. $\varphi_k=\varphi$, we finish with what we wanted to prove.
2. For every $i<k$, either $\varphi_i$ is either an axiom (sentence from $T$) or it was derived from previous statements using axioms of logic and inference rules.

Now to give a proper example I will have to be specific and tell you what are the symbols, what are the inference rules, the logical axioms, the rules for creating sentences and formulas, what are the axioms and what we want to prove from them...

Well, this is a bit too much for a single post at this hour. However, you should definitely go to your nearest library and open up a book about mathematical logic, preferably an introductory book.

It raises a question, if that is what you need in order to write a proof, why is this site not full of such posts? Well, in mathematics there is a big difference between a formal proof and a rigorous proof. Mathematicians [usually] care about rigor, rather than absolute formality. They also interchange these two terms more often than they should.

However proving something rigorously just means explaining how the proof should look like, in words or symbols. The background framework is often agreed upon "silently" in the background, and it takes practice but one can usually make the needed switches without much notice.

Finally, when you say "can you have a proof that $1+1=2$?" the answer is yes, but in what context? Is it the context of natural numbers with their common axioms (the properties we assume natural numbers have), or is it in the context of the real numbers with the axioms of those?

The two systems are very different, and formal proofs - even of the same claim - in different frameworks can be very different.

However in this case not too different. We use the symbol $2$ to abbreviate the formal term $1+1$. So either proof would be relatively short.

Solution 2:

Belgi and Asaf have answered the question assuming "proof" means "formal proof". As André indicated in the comments, there is an informal notion of proof: A proof is a convincing argument that some fact is true.

Officially, all that counts is the formal proof. On the other hand, almost all proofs one encounters are informal (though, at least in theory, they can be translated into formal proofs.)

Here's an example of an informal proof. I'll begin with some definitions

Definition: By an "integer" we mean any number of the form $0, \pm 1, \pm2 , \pm 3,...$. (So, something like $\frac{2}{3}$ or $\pi$ is not an integer.)

Definition: If $n$ is an integer, we say "n is even" if there is another integer $k$ with the property that $2k = n$.

Theorem: The number $n=6$ is even.

Proof: In order to prove this, we need to find an integer $k$ with the property that $2k = 6$. Well, $k=3$ works, so $n=6$ is even. $\square$

(The symbol $\square$ is often used to denote the end of a proof.)

Ok, that seems like a waste of time. But what have we gained? No longer are we depending on someone's word that 6 is even. We now know it is true. Ok, it still seems like a waste of time.

Here's another one.

Theorem: If $n$ is even and $m$ is even, then so is $m+n$.

Proof: We need to show that we can write $m+n = 2k$ for some integer $k$. By assumption, since $m$ is even $m = 2a$ for some integer $a$. (I'm not using $k$ since I want to use that letter for another purpose later). Since $n$ is even, $n = 2b$ for some integer b.

Then, $m+n = 2a + 2b = 2(a+b)$. So, if I let $k = a+b$ (which is still an integer), then this is the $k$ I'm searching for. This shows that $m+n$ is even. $\square$

Now what have I gained? Before this proof, you could have experimented with many even numbers, adding them together and observing that you always got an even number out. (For example, $2+6 = 8$, $14+ 290 = 304$, etc.)

But even if you were to spend your whole life checking that adding even numbers together gives evens, there is no guarantee that there aren't even numbers that add up to a non-even number. Perhaps it happens very rarely that 2 evens add up to a non-even, perhaps you just needed to check one more case to find that elusive example.

The proof shows that no matter which 2 even numbers you pick, their sum is even. It guarantees that your examples aren't flukes, that they are happening for a reason and that they will happen every time.

Now, let me point out a potential pitfall of this proof. Right where I say "...$k = a+b$ (which is still an integer)..." - why it still an integer? The answer to this question is going to depend on what axioms you are working with and this is going to get back to what Asaf and Belgi were saying.

Solution 3:

I don't fully understand what you mean by "What is the most simple proof to understand what a proof is?" if you want to know what a proof is in the formal sense you will have to read some mathematical logic.

To keep it simple, a proof is a list of statements from a set of assumptions such that each statement has a previous statement that is comes from (or else it's an assumption) and the last statement is what you have proved (if, for example, the last line is $1+1=2$ then you proved it).

The answer to your second question "can you have a 'proof' for 1+1=2 ?" is yes. If you want to prove that you first need to ask yourself what is $1$ ? what is $2$ ? what is $1+1$ ? and then you would want to compare both sides. I answered most of these questions in details before here.

Solution 4:

You are probably asking about formal mathematical proof or maybe you are confused about how trivial mathematical facts like 1+1=2 can be proven. In that sense you should remember that a proof is meaningful only relative to a formal proof system. A string $\pi$ is a proof for a statement $\varphi$ if the pair is accepted by the proof system (think of a proof system as an algorithm/computer program that gets $\pi$ and $\varphi$ and returns YES or NO. Normally a proof system should be sound, i.e. false statements should not have proofs).

If your question is more philosophical then you should first say what do you mean by $1$, $2$, $+$, and $=$ (and there are various opinions about these among philosophers of mathematics and mathematical philosophers). How can we answer the question if we haven't agreed on what these symbols mean?

If you interpret them as symbols in the language of an arithmetic theory like PA or ZFC then your question is easy to answer. Here are two examples:

In the case of PA, $2$ is defined as $S(S(0))$ and $1$ is defined as $S(0)$ and $+$ is defined recursively as $x+0=x$ and $x+S(y)=S(x+y)$; and your question is to show that $S(S(0))=S(0)+S(0)$ which is not difficult. The symbol $S$ is the symbol for successor.

In case of ZFC, $0 = \emptyset, 1 = \{0\}$ and $2=\{0,1\}$ and etc and again the proof is not difficult.

To talk about a formal proof we should fix the meaning of the symbols and the theory, a formal proof outside any proof system is meaningless. Often people omit explicitly mentioning the formal system because it is clear from context, but it is there.

Many will interpret the question as asking about a formal proof inside a theory about symbols as above (somewhat formalist view of mathematics) but that is not the only way. There are other approaches where the linguistic/formal entities are not primary concern of mathematics but secondary means used for the purposes like communicating mathematical results to others, etc. Constructive mathematics and Platonism are two of the famous ones viewpoints. (And honestly, do you know anyone who believes in $1+1=2$ because of a formal proof in PA or ZFC?). Check for example the BHK interpretation of (constructive) proofs.

However, if you are asking more generally about what is a proof, then I think the following story is relevant:

In 1978, as an undergraduate, I attended Shimon's course Graph Algorithms. At some point, one student was annoyed at Shimon's "untraditional" way of analyzing algorithms, and asked whether Shimon's demonstrations constituted a proof and if so what is a proof. Shimon answer was immediate, short, and clear: A proof is whatever convinces me. [Stories about Shimon Even by Oded Goldreich]