What is a mathematical proof?

The answer is… much simpler than one might think. A mathematical proof is just a set of steps that only produce true statements given the premises.

“Huh?”

Well, when you want to prove something mathematically, you start with a few premises A, B, C, etc. And then you apply operations upon the premises that will always yield true statements given those premises, and you get to where you wanted to.

“Um… what exactly… does that mean?”

Well, I’ll show you a way not to do it. I’ll start with the premise A: x = y plus the usual rules of arithmetic. And then I’ll produce a number of operations upon this premise and prove that 1 = 2.

“What?!”

Don’t worry, the proof will be wrong. And I’ll show where. But let’s go, then.

\begin{aligned}  x &= y\\  x^2 &= xy\\  x^2 + x^2 &= x^2 + xy\\  2x^2 - 2xy &= x^2 - xy\\  2(x^2 - xy) &= 1(x^2 - xy)\\  2&=1  \end{aligned}

Let’s see what I did wrong.

  1. Premise.
  2. Multiplied both sides by x.
  3. Added x^2 to both sides.
  4. Subtracted 2xy from both sides.
  5. Rearranged the numbers.
  6. Divided both sides by (x^2-xy).

As I said, we need all the steps to produce only true results. If our premise is an equality, then which of the above operations on an equality doesn’t always produce true statements?

  • Multiplying both sides of an equality by the same number always produces true statements.
  • Adding the same number to both sides of an equality always produces true statements.
  • Subtracting the same number from both sides of an equality always produces true statements.
  • Rearranging the symbols we’re using, without changing their truth-value, is a null-operation.
  • Dividing both sides of an equality by the same number always produces true statements, unless that number happens to be zero.

Unless that same number happens to be zero. We had defined that x = y, right? So how much is (x^2-xy)?

x^2 - xy = x*x - x*y = x*x - x*x = 0

“Oh! So since one of the operations you performed didn’t always produce a true statement, you picked exactly the case where it wouldn’t, and with that you proved something impossible!”

Yes, exactly. Just look at it: 0*3 = 0*528. That’s obviously true. In fact, you can replace 3 and 528 by any numbers at all, and that will still be a true statement. But you can’t divide both sides by 0, because that is not an operation that produces only true statements from true statements. And that’s exactly what we did, by cleverly hiding the invalid step behind murky language.

So that’s what a mathematical proof is: a number of operations applied on true statements that always yields true statements. Let me give you an example of a mathematical proof that is valid, and was used in another post of mine.

Premises:

\begin{aligned}  A&: P(H|X)+P(\bar H|X) = 1\\  B&:0 < P(H|X) < 1\\  C&:P(H|X) + aP(\bar H|X)<1  \end{aligned}

Since I’m always talking about probabilities, I will use this opportunity to show what a mathematical proof is with one that is useful to the logic of a previous post. Based on these premises, I want to prove the conclusion Z: a < 1. But first I’ll give you the meaning of the premises.

Premise A means that the probability that a proposition is true plus the probability that it is false equals 100%. That is, no matter what the proposition H stands for, we are always sure that it’s either true or it’s not.

Premise B means that we think H is possible, but not certain (in fact, we can never be certain of anything at all, so that’s always valid).

Premise C means that by multiplying the probability that H is false for some a, adding it to the probability that H is true will give a number that’s smaller than one.

Conclusion Z means that the only way the above premises are true is if a < 1.

Let’s go step-by-step. First, we have premise C.

1.\ P(H|X) + aP(\bar H|X) < 1

Now let’s perform an operation: adding 0 to the left side of the equality.

2.\ P(H|X) + aP(\bar H|X) + 0< 1

That is true because the operation of adding 0 to a side of an equality doesn’t change its truth-value. Now we’ll remember that, by the definition of subtraction:

3.\ P(\bar H|X)-P(\bar H|X) = 0

Since a number is always equal to itself, subtracting a number from itself always equals 0. Now, substituting 3. on the left-hand side of 2.:

4.\ P(H|X) + aP(\bar H|X) + P(\bar H|X)-P(\bar H|X)< 1

Replacing a number by another that is equal to it is an operation that always maintains the truth-value of the statement. And now we’ll rearrange the above numbers.

5.\ P(H|X) + P(\bar H|X) + aP(\bar H|X)-P(\bar H|X)< 1

Now if we replace P(H|X) + P(\bar H|X) with 1:

6.\ 1+ aP(\bar H|X)-P(\bar H|X)< 1

This is a valid step because of premise A, and because replacing a number by another that is equal to it always maintains the truth-value of the statement.

7.\ aP(\bar H|X)-P(\bar H|X)< 0

We subtracted 1 from both sides of the inequality. Subtracting a number from both sides of an inequality always produces another true inequality. And so, we will add P(\bar H|X) to both sides, and get:

8.\ aP(\bar H|X)<P(\bar H|X)

And then we can divide both sides of the inequality above to reach our conclusion.

9.\ a< 1

We were allowed to do that because P(\bar H|X) is a positive number, and dividing both sides of an inequality by a positive number maintains its truth-value. I will leave it for you to prove that P(\bar H|X) is a positive number. You will only need premises A and B.

So we just performed a number of steps which, when working in conjunction with the previous statements, always produced new true statements. Since we know that about each of the steps, then we can trust the truth of the conclusion.

Of course, I chose a rather simple example that could be reliably guessed by pure intuition. Still, it’s good to understand what it means to actually prove stuff mathematically. Formally, that is. Mathematics is an art, the art of discovering true things based on other true things. And sometimes you will discover the most incredible and counter-intuitive things by just applying a number of steps that produce only true statements from other true statements.

Advertisements
This entry was posted in Intuitive Mathematics, Mathematics, Probability Theory and tagged , , , . Bookmark the permalink.

4 Responses to What is a mathematical proof?

  1. Pingback: How to prove stuff | An Aspiring Rationalist's Ramble

  2. Pingback: Absence of evidence is evidence of absence | An Aspiring Rationalist's Ramble

  3. tb says:

    Very nice! Enjoyed the explanation and examples.

  4. tb says:

    Very nice! Enjoyed the examples and explanation.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s