How Math Proofs Work

434 views

[ad_1]

Math is fascinating to me, though I struggled with math in high school and only took the minimum I needed. (Age changes things, man.) I’m reading a book on Wiles’ proof for Fermat’s Last Theorem and got curious about proofs.

At what point does something move from an assumption with examples (well yeah. Look at this) to a full proof?

Simple example that came to mind:

For any number n, where n is a prime >2, the sum of the factors of n cannot be odd.

In: Mathematics
[ad_2]

> For any number n, where n is a prime >2, the sum of the factors of n cannot be odd.

?? If n is a prime it has no (non-trivial) factors.

Essentially all proofs are set up the same. You write a formula using n, then if it’s also true for n+1, it’s a proof

For soemthing to be a proof, you must be able to reduce it to axioms. In practice, this means it must depend on things that have already been established as a proof – so A depends on B depends on C depeneds on… axioms.

There are many strategies to proof, but they all rely on making some basic assumptions and definitions of things and showing how facts following from them always lead to a particular conclusion.

If n is a prime >2, then it has 2 factors {n, 1}. If it had other factors it would not be prime.

All primes other than 2 are odd because a hypothetical even prime would be of the form 2k where k is an integer (this is basically the definition of an even number) and would thus have 2 as a factor.

The sum of an odd number (2k+1) and 1 is even because 2k+2 has 2 as a factor.

As such, the sum of the factors of primes > 2 is even.

> For any number n, where n is a prime >2

That’s a bit of a weird example, as the “proof” is the definition of a prime. All primes n > 2 have two factors, 1, and the odd number n. if it didn’t it wouldn’t be a prime.

But the main goal of proofs is to take some assumptions and logical steps, and use them to show the truthfulness of the thing you want to prove. If you take a true assumption and apply true steps to those assumptions, everything you derive is also true. If you end in a logical contradiction either the steps you applied are false, or the assumption.

Let’s try a different proof, the proof that sqrt(2) is not rational.

1. Assume that sqrt(2) can be expressed with the integer ratio a/b. (the definition of a rational number).

2. Assume a/b is in it’s lowest form (a and b share no factors).

3. If sqrt(2) = a/b, then 2 = a^2 / b^2 (square both sides)

4. rearrange, a^2 = 2b^2

5. a^2 thus is even. If a^2 is even, then it must be that a itself is also even (odd numbers squared are always odd).

6. a is even, and thus can be represented as 2k, where k is a positive integer.

7. 2 = (2k)^2 / b^2

8. rearrange, 2b^2 = 4k^2 => b^2 = 2k^2

9. By the same logic as steps 4 to 6, b is even and can be represented as 2j where j is a positive integer.

10. therefore, sqrt(2) = 2k / 2j

11. This is a contradiction, as 2k and 2j share a factor of 2: however our assumption in 2 stated they had no common factors.

12. Thus, our assumptions about the rationality of sqrt(2) are false, and therefore sqrt(2) is irrational.

QED (end of proof).

Here we started with an assumption ( The square root of 2 is rational), and from there just took steps to show what the result of that assumption is. Eventually we arrived at something that we know is false, and so we can see the original assumption was false, since that’s the only thing we used that wasn’t automatically know to be true.

You generally start out with something that is assumed to be true and then use stuff like equivalencies to prove that it must also mean that thing you are wanting to prove is true.

There are many different approaches to prove something like showing it its true for every single case or that is is true for a single case but also true for every case subsequent to one that is true or by showing that if it wasn’t true that would mean something that can’t possibly be the case or any number of things.

Proofs you learn in school and in college tend to be simple affairs but some of the newer more out there stuff can’t really be proven just by writing for a few pages with pencil on paper and may even require computers to get it all sorted out.

math proofs at its simplest are just you take known assumptions, and manipulate them to show a result.

so we know integers are prime. and we know primes only have two factors, itself and one.

if we add one to an odd number, it’ll be even. if we add one to an even number, it’ll be odd. However, the only even prime is two, because any other numbers that are even are divisible by two (the definition of even numbers) so we know that all primes that aren’t two are odd. since they’re odd, if we add one, the only other factor of a prime, its even.

boom! We’ve proved it.

We however can’t prove things with examples. i can’t think of examples but even if something is true for the first 100000000000000000 numbers, it might not be true for the first 200000000000000000 numbers

> For any number n, where n is a prime >2, the sum of the factors of n cannot be odd.

A prime number n by definition a number that can’t be formed by multiplying any smaller number together. The only factors you can have is the trivial 1*n.

A even number is n=2k where k is a integer.

A odd number is n=2k+1 where k is a integer.

If a prime number is even it can be written as 2k. So all even number have the factor 2. Because a prime number only can have the factor 1 and itself the only even prime is 2

So both factors of a prime number n >2 are odd

So the sum of the factor of a prime number >2 can be written as 1+(2k+1)= 2k+2 =2(k+1) and that is a even number. So the sum of the factor of a prime number is a even number.

For more and better example look at [https://en.wikipedia.org/wiki/Mathematical_proof](https://en.wikipedia.org/wiki/Mathematical_proof)

Let me start by saying that I get downvoted every time I say this, but I keep saying it anyways. Math is a language based on pure logic. It is the universe’s operating system. When you try to prove something mathematically it is basically the same as trying to prove something verbally – just in this different language.

One of the issues though is that its amazingly difficult to prove something even verbally. Consider “Does God exist?” philosophers haven’t been able to answer that even after thousands of years or trying. If we stepped back and asked “Do you BELIEVE that God exists?” you might say yes, but you could be lying. However we could look into your life, see you going to church, praying when you thought you were alone, etc. and gather up enough evidence that you did believe in god to satisfy ourselves. Math generally lets us close that tiny gap of uncertainty that verbal languages and the real world so often leave us with.

Every proof is going to look different though but all you are trying to do is construct a logical argument that covers off every base.

> For any number n, where n is a prime >2, the sum of the factors of n cannot be odd

Adding things together.

All prime numbers have exactly 2 factors: 1 and itself.

An even number has 2 as a factor.

Assume a prime number >2 that’s even. It must have the following factors: 1, n, 2 and n/2. This is impossible because prime numbers by definition only have 2 factors. Therefor the assumption is wrong, all prime numbers n>2 are odd. This is proof by assuming the opposite and proving it false (this only works when there’s only 2 options).

The prime number n>2 is odd. We just proved that. Any odd number + 1 is even. QED.

Essentially, mathematical proofs are all kind of the same– you take what you know, and you use that information to get to a new conclusion that must be true based on what you know.

As an example, let’s prove a statement– “An even number plus an even number is an even number”

How do we prove this? Well, what do we know? We know that an even number is divisible by 2, since that’s the definition of an even number. In other words, we can think of any even number as “2 times another number.”

So let’s say that I have an even number x, and an even number y. In this case, we can say that x=2n, and that y=2m. In this case, by definition,

x * y = 2n * 2m = 4 * n * m = 2 * (2 * n * m). And since 2, n, and m are all numbers, then 2 * n * m must also be a number. And look, we’re back at the definition of an even number.

This is a brief example of how we can use a list of assumptions and create a new statement using those assumptions.

Note however, that in your post you say

>At what point does something move from an assumption with examples (well yeah. Look at this) to a full proof?

*I did not start this proof by making assumptions.* I began this proof by making statements of fact and definition, and all I did was provide examples to work with in order to prove my statement.

You could also do what is called a “proof by contradiction.” In a proof by contradiction, you assume the opposite of what you’re looking for, and then you prove that by making that assumption, you lead yourself to a logical fallacy.

For example:

Assume that x and y are even numbers, and that x * y is odd. In this case, x * y must be able to be written as 2(n+1), the definition of an odd number. Note that n cannot be odd. If n were odd, then n+1 would be even, and since 2 is even, 2 * (n+1) would have to be even (we just proved this), but this is impossible because our assumption is that 2(n+1) is odd. Thus, n must be even, and n+1 must be odd. But if n+1 is odd, then it isn’t divisible by 2. Thus, the only way to factor n+1 and 2 into x and y, is for x= 2, and y= n+1. But then y has to be odd, which violates an initial assumption.

This proof takes an assertion– 2 even numbers multiplied together can be odd– and proves that it’s impossible by going through the logical conclusion of what must be the case.

These are just two quick methods that can be used to prove a statement. There are other methods too, like induction, that I didn’t get into, but I hope that you can see the use of such techniques.

Happy to answer any questions.

Proofs basically work this way:

1. Say something you know is true.
2. Then, say the same thing, but slightly differently. It must still be true.
3. So, whatever you come towards in the end must also be true.

Let’s see an example. I will postulate that x + (-x) < 1.

Let’s start by saying something we know to be true:

1. 1 – 1 = 0
2. Let’s multiply by x:
3. 1(x) – 1(x) = 0
4. Now, we also know that 0 < 1. So if x < 0, x < 1!
5. So, 1 – 1 < 1.
6. But, then, also 1(x) – 1(x) < 1.

Really ,we never actually said anything new at any point. We stated something we knew was true, and kept reformulating it until we got what we wanted.

I make a statement. I say something like “2+2=4”

The proof then breaks down the definition of every single part of that statement. “Two is a number, countint up, 0, 1, 2. It is two. We have to agree on that to continue.” Okay everyone agrees that 2 is an integer number. “+ means addition. Addition is when you sum two values. Summing is taking the values the result is their combined value in such a way that it is their sum. We must agree on what + means to continue.” “= means that the two sides of the equation are of equal value. We must agree on this to continue.”

Basically proofs break down every single part of the theorem, and reduce them into the basics (or frequently other proofs) that other people generally agree to be true. This way it shows that every aspect of the theorem has been thoroughly thought through and more importantly, provided all the building blocks of the proof are true, then the theorem itself must be true.

Proofs aren’t really about examples and assumptions. We might start a proof with an assumption, but that’s not the proof – that’s the statement we’re trying to prove. And if we give an example, that’s not a proof either, until we can show that it’s true for every example you can imagine. If I show you a hundred examples of something and say “See? That’s proof that it’s true,” all I’ve proved it that it’s true for those hundred examples. You only need to show me *one* example where it’s not true to show I’m wrong.