Proof

Overview

Mathematical proofs can use logical connectives to reach conclusions:

means that implies - if is true, then is true.
means that if and only if (iff) - implies and implies .
(congruence) means that two expressions are exactly equal.

Proofs may involve sets of numbers (NIS: the symbol for each set):

The integers, , are whole numbers.
The natural numbers, , are counting numbers (nonnegative integers). In maths, these are . In computer science, these are .
The rational numbers, , are numbers that can be represented as a fraction , where and are integers.
The irrational numbers are numbers that cannot be represented as a fraction , where and are integers. This includes numbers such as and .
The real numbers, , include both rational and irrational numbers.

Proofs may also use interval notation to represent sets of numbers:

:
:
:
:
:
:
or :

Proof methods

Disproof by counter-example

Disproof by counter-example is where a statement is shown to be false generally by having one specific counter-example where it is not false. Consider a statement:
This can be disproved by finding a single for which is true but is not.

Proof by deduction

Proof by deduction is where a logical mathematical argument is used to show that a statement is true. A proof may start by representing general numbers:

An even integer is , for some integer .
An odd number is , for some integer .
A multiple of is , for some integer .

Proof by exhaustion

Proof by exhaustion is where a statement is shown to be true by testing every possible case.

Proof by contradiction

Proof by contraction is where a statement is assumed to be false, then a contradiction is found, showing that the original statement must be true. The two following proofs are required (IS):

Proof of the irrationality of :
- Assume that is rational, so for some integers , , where and are coprime.
- Squaring gives , so .
- Because , is even, so itself is even.
- If is even, then for some integer .
- Then, , so .
- Because , is even, so itself is even.
- and are both even, but this contradicts the assumption that and are coprime, as they both share a factor of 2. Thus, the assumption must be false, so is irrational.
Proof of the infinity of primes:
- Assume that there is a finite list of primes, so there is a largest prime number .
- Consider multiplying all the prime numbers together, .
- Consider . As it is 1 more than a multiple of every prime, it is not divisible by any prime (dividing by any prime leaves a remainder of 1).
- Thus, is either prime, or divisible by a prime larger than (all numbers are either prime or have prime factors).
- This contradicts the assumption that there are a finite number of primes, as there is some prime number larger than . Thus, the assumption must be false, so there are an infinite number of primes.