### Introduction to Proofs in Mathematics

We first check the equation for small values of n :. Next, we assume that the result is true for k , i. By mathematical induction, the equation is true for all values of n. Allegedly, Carl Friedrich Gauss — , one of the greatest mathematicians in history, discovered this method in primary school, when his teacher asked him to add up all integers from 1 to Using induction, we want to prove that all human beings have the same hair colour. Now assume S k , that in any group of k everybody has the same hair colour.

If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. Clearly something must have gone wrong in the proof above — after all, not everybody has the same hair colour. Can you find the mistake? Everything that can be proved using weak induction can clearly also be proved using strong induction, but not vice versa.

The Fundamental Theorem of Arithmetic The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number , or it can be written as the product of prime numbers in an essentially unique way. S 1 is an exception, but S 2 is clearly true because 2 is a prime number. Now let us assume that S 1 , S 2 , …, S k are all true, for some integer k. By our assumption, we know that these factors can be written as the product of prime numbers.

To prove that this prime factorisation is unique unless you count different orderings of the factors needs more work, but is not particularly hard. It turns out that the principle of weak induction and the principle of strong induction are equivalent: each implies the other one. They are also both equivalent to a third theorem, the Well-Ordering Principle : any non-empty set of natural numbers has a minimal element, smaller than all the others.

The well-ordering principle is the defining characteristic of the natural numbers. These axioms are called the Peano Axioms , named after the Italian mathematician Guiseppe Peano — Proof by Contradiction Proof by Contradiction is another important proof technique.

## Proof Tutorial 1: Introduction to Mathematical Proofs

If all our steps were correct and the result is false, our initial assumption must have been wrong. Suppose that not all natural numbers are interesting, and let S be the set of non-interesting numbers.

By the well ordering principle, S has a smallest member x which is the smallest non-interesting number. This curious property clearly makes x a particularly interesting number. This is a contradiction because we assumed that x was non-interesting. In the early 20th century, mathematics started to grow rapidly, with thousands of mathematicians working in countless new areas. David Hilbert — set up an extensive program to formalise mathematics and to resolve any inconsistencies in the foundations of mathematics.

### See a Problem?

This included proving all theorems using a set of simple and universal axioms, proving that this set of axioms is consistent , and proving that this set of axioms is complete , i. He proved than in any sufficiently complex mathematical system with a certain set of axioms, you can find some statements which can neither be proved nor disproved using those axioms. It is also not possible to prove that a certain set of axioms is consistent, using nothing but the axioms itself. Problems with self-reference can not only be found in mathematics but also in language. The sentence above tries to say something about itself.

If it is true then the sentence tells us that it is false. If it is false, then the sentence tells us that it is not false, i.

• The Smallest Detail.
• MAT Numbers, Equations, and Proofs | Math.
• MCSE Training Kit Microsoft Windows 2000: Network Infrastructure Administration;
• The Professional Chefs Art of Garde Manger;

In effect, the sentence is neither true nor false. Today we know that incompleteness is a fundamental part of not only logic but also computer science, which relies on machines performing logical operations. Surprisingly, it is possible to prove that certain statements are unprovable.

If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. Clearly something must have gone wrong in the proof above — after all, not everybody has the same hair colour. Can you find the mistake? Everything that can be proved using weak induction can clearly also be proved using strong induction, but not vice versa. The Fundamental Theorem of Arithmetic The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either a prime number , or it can be written as the product of prime numbers in an essentially unique way.

S 1 is an exception, but S 2 is clearly true because 2 is a prime number. Now let us assume that S 1 , S 2 , …, S k are all true, for some integer k. By our assumption, we know that these factors can be written as the product of prime numbers. To prove that this prime factorisation is unique unless you count different orderings of the factors needs more work, but is not particularly hard. It turns out that the principle of weak induction and the principle of strong induction are equivalent: each implies the other one. They are also both equivalent to a third theorem, the Well-Ordering Principle : any non-empty set of natural numbers has a minimal element, smaller than all the others.

The well-ordering principle is the defining characteristic of the natural numbers. These axioms are called the Peano Axioms , named after the Italian mathematician Guiseppe Peano — Proof by Contradiction Proof by Contradiction is another important proof technique. If all our steps were correct and the result is false, our initial assumption must have been wrong. Suppose that not all natural numbers are interesting, and let S be the set of non-interesting numbers. By the well ordering principle, S has a smallest member x which is the smallest non-interesting number.

This curious property clearly makes x a particularly interesting number. This is a contradiction because we assumed that x was non-interesting. In the early 20th century, mathematics started to grow rapidly, with thousands of mathematicians working in countless new areas. David Hilbert — set up an extensive program to formalise mathematics and to resolve any inconsistencies in the foundations of mathematics. This included proving all theorems using a set of simple and universal axioms, proving that this set of axioms is consistent , and proving that this set of axioms is complete , i.

He proved than in any sufficiently complex mathematical system with a certain set of axioms, you can find some statements which can neither be proved nor disproved using those axioms. It is also not possible to prove that a certain set of axioms is consistent, using nothing but the axioms itself. Problems with self-reference can not only be found in mathematics but also in language. The sentence above tries to say something about itself. If it is true then the sentence tells us that it is false. If it is false, then the sentence tells us that it is not false, i.

In effect, the sentence is neither true nor false. Today we know that incompleteness is a fundamental part of not only logic but also computer science, which relies on machines performing logical operations. Surprisingly, it is possible to prove that certain statements are unprovable. One example is the Continuum Hypothesis , which is about the size of infinite sets. His insights into the foundations of logic were the most profound ones since the development of proof by the ancient Greeks. Please enable JavaScript in your browser to access Mathigon. Log in to Mathigon Facebook Google.

Axioms and Proofs World of Mathematics This article is from an old version of Mathigon and will be updated soon. Introduction Imagine that we place several points on the circumference of a circle and connect every point with each other. You start from a general statement you know for sure is true and draw conclusions about a specific case.

[Discrete Mathematics] Direct Proofs

For example, if you know for a fact that all sheep like to eat grass, and you also know that the creature standing in front of you is a sheep, then you know with certainty that it likes grass. This form of reasoning is water tight. It can only go wrong if your premise is false, that is if you're wrong about all sheep liking grass, or if your observation is wrong, that is, the creature you're looking at is not actually a sheep.

But if those two things are correct, then your conclusion follows necessarily from your premise: it is true everywhere and for eternity. Dividing both sides by gives. Mathematics is all about proving that certain statements, such as Pythagoras' theorem, are true everywhere and for eternity.