Mathematics/Discrete Math/Proofs

Proofs are a formal means to mathematically show that something is true or false. It can be done in three main ways.

Direct Proof

This is a proof in which we directly declare that p → q. We assume that p is true and go on to show that means q is automatically true. Often times, this is a fairly straightforward means of creating proofs.

Direct Proof Example

Let's prove the theorem "If n is an odd integer, then n^2 is odd."

First, we can define an odd number as "any value 2k + 1 where k is an integer".

Thus, we have the first part of our proof, n = 2k + 1 to define any odd integer.

Next, we want to prove that any n^2 is odd, so we have:

n^2 = (2k+1)^2 is odd.
    = 4k^2 + 4k + 1
    = 2(2k^2 + 2k) + 1

By definition of an odd number, we have proven that our n^2 is also odd.

Proof by Contraposition

Sometimes, a direct proof isn't easy to create. An alternative means is to prove the opposite is true, that is by proving ¬p → ¬q.

Proof by Contraposition Example

Let's prove that "If n is an integer and 3n + 2 is odd, then n is odd."

We start by attempting a direct proof first. So by once again defining an odd number as "any value 2k + 1 where k is an integer", we have:

3n + 2 = 2k + 1
3n + 1 = 2k

At this point, we have two variables and not much we can do with them. So we move on to attempt a proof by contraposition. That is, we start by assuming the original statement is false, which gives us the alternative: "If n is an integer and 3n + 2 is odd, then n is even."

We can define an even number as n=2k for any integer k. So we can substitute to get:

3n + 2
3(2k) + 2
6k + 2
2(3k + 1)

As we can see, no matter what value we enter for k, the end result will be a multiple of 2. This means that, if we assume n is even, then 3n + 2 is actually also even, thus proving our contraposition false.

By extension, this means that the opposite of our assumption must have been true after all, which means we have indirectly proven that "If n is an integer and 3n + 2 is odd, then n is odd."

Note About Example

Note that there may be multiple ways to solve a given proof. In our example, we could have solved it directly if we used substitution instead. We would have:

"If n is an integer and 3n + 2 is odd, then n is odd."
We define an odd number as "any value 2k + 1 where k is an integer."

3n + 2
3(2k + 1) + 2
6k + 3 + 2
6k + 4 + 1
2(3k + 2) + 1

No matter what value we enter for k, we will result in a multiple of 2, plus 1. This leads us back to our original definition of an odd number, thus proving our original assumption.

Proof by Contradiction

A proof by Contradiction is similar to a proof by contraposition, in that it is an indirect proof that may start off similarly. However, proof by contradiction attempts to prove a given p in three steps:

• First, assuming ¬p. Aka, assume that p is false.
• Next, prove that ¬p implies both q and ¬q. That is, ¬p → (q ∧ ¬q).
• Since q and ¬q cannot both be true, then ¬p must be false, meaning that p is true.

Proof by Contradiction Example

Let's try to prove that √2 is irrational.

Using proof by contradiction, we first assume the opposite, aka that √2 must be rational.

Thus, by definition of a rational number, then there must be two numbers a, b, such that √2 = a/b. Note that b ≠ 0, and a and b have no factors.

We can then go on to solve:

√2 = a/b
2 = a^2/b^2
2b^2 = a^2

At this point, we can use the definition of an even integer to declare that a^2 must be even. If a is even, then a=2c for some arbitrary integer c. Which gives us:

2b^2 = 4c^2
b^2 = 2c^2

We can now declare that b^2 is even. But wait. We already determined that a/b must be in lowest terms, resulting in a and b having no factors. By definition, if they're both even, then they can be factored, therefore they cannot both be even at once.

Logically, this means our assumption is false, and the original statement (√2 is irrational) must be true.