Discrete Mathematics – How to construct a proof

The current topic is not aimed to Discrete Mathematics only, but to all the Mathematics and to all the Logic processes, when we are dealing with it. It’s little bit theory we need to deal with in order to understand the world of proofs – how to construct a solid proof of a specific problem, how to be sure it is a solid and “bullet proof” and what are the most famous approaches when it comes to proofing.

I. Deductive Proof – Modus Ponens

This Proof involves a lot of deduction chains – Modus Ponens. In short – If X, then Y (I am going to publish later this year a great tutorial of logic processes and logic when it comes to mathematics and we are going to inspect with great detail all the kinds of logic relations between 2 or more states). For example:

Fact A:You are reading this sentence right now.
Fact B:All who read this sentence right now and recognize the words has at least mediocre knowledge of English.

Fact C (or conclusion): You have at least mediocre knowledge of English

In this example we gave deduction with 3 statements involved, facts A and B, and the conclusion C. In short – If A and B, therefore C. If we built our proof using such relations or deductions, you can be absolutely sure your statement is correct (all you need to make sure is that your facts are correct).

II. Formal Proof

The major problem of the previous method of proofing – in most cases it is too long and it needs extra tools in order to proof the different facts involved. The Formal Proof is more likely to be used by you in future and the Formal Proof is the tool you will greatly appreciate. A good example of Formal Proof – imagine you have two functions F and G, both depends on one variable only – x. Therefore you have F(x) and G(x).

You have that F(X)>G(X). If you proof that when you increase X, the difference F(X)-G(X) will be increasing too – you have just created one good Formal Proof. You can say – hey, let’s substitute fact A = “X increases” and fact B = “F(X)-G(X) increases“. We can state that if A, then B – so there is no difference between the previous way of proof and the current one. In the previous method we defined A and B as facts, something we are sure it happens. In this case we didn’t check them, are they correct or not? So we can wrap the whole process of proofing with Modus Ponens, but I recommend the states to be transformed to facts using Formal Proof.

I know it’s little perplexed and some of you will find it annoying, but believe me – when we are dealing with hard theorems and lemmas, such details can save you!

III. IFF – if and only if

When we look through the Modus Ponens example, we said it is constructed by deductive fashion:

If A, then B.

What if we proof that If B, then A? Then we will have two rules (proofs):

If A, then B.
If B, then A.

In this case we add the two statements and relate them with the abbreviation IFF.

You can right down A IFF B (which means A happens only when B happens and vice versa).
For example (maybe some philosophers will disproof that statement, but I recall you it is just an example using our daily routines): My eyes are open IFF I look.

You can observe the statement, if my eyes are open, I look (Modus Ponens part I).
If I look, my eyes are open (Modus Ponens part II). Both of those deductive proofs are right, therefore we can join them in the statement My eyes are open IFF I look.

IV. Set related proofs

When we start dealing with Set Theory in the future tutorials, we will often apply this method. What if we need to compare two sets and proof they are equal? We should proof those two characteristics of the sets(let’s define the sets as A and B):

1. Proof that every element of A, belongs to B .
2. Proof that every element of B, belongs to A.

In other words, following the math notations:

\forall a \in A => a \in B \\
\forall b \in B => b \in A \\

I should add – here the symbol “=>” defines the logic link IF,THEN (simple deduction definition, not a symbol for logical operator). We are going to experience lot of such proofs in the future.

V. Converse and Contrapositive – Differences between the both

Imagine you have the statement  -> A and B = TRUE

(I should add – this statement is equal to TRUE, only when both A and B are true)

By the definition “converse” we apply  NOT(A and B)

Following De Morgan’s laws, when we are applying a NOT to a statement, we should not only change the sub-statements (A and B), but also change the operator (in our case – and). So what this statement means? NOT(A and B) = NOT(A) NOT(and) NOT(B) = NOT(A) or NOT(B). You should pay attention, that the opposite of the operator AND is OR (I will explain that in future, when we start the Set Theory tutorial). So let’s underline:

NOT(A and B) = NOT(A) or NOT(B)
*example of converse*

Now what about contrapositive? Imagine we apply 0 to the statement if A is false, and we apply 1 to the statement if A is true. We have four cases:

• true,true
• true,false
• false,true
• false,false

If we calculate the four cases, we will see the statement (A and B) is true, only when both the statements are true. If (A is true and B is true), then (A and B) is true. What if we put a NOT operator in front of the two statements?

If NOT(A is true and B is true), then NOT(A and B) is true

The Set Theory is tricky one and you can be easily mislead that you cracked the hidden information, but an inexperienced eye will just scratch the surface. The information here is not notated correctly for an experienced eye or someone with respectful background on this field, but I am just outlining some basic concepts. As I promised, we will later dig in the Set Theory field (and I promise you really, really amusement experience).

You have the statement (All x are good). You need to proof that. In order to do that by applying contradiction, you need to think like pessimist. Hey, you say to yourself, this can’t be true. I am sure All x are bad! So you accept this statement and start making deduction steps or formal steps in order to “unwrap” this statement and the sequences of it. You go further and further using Modus Ponens, and voila – you rich a false statement!

VII. Counterexamples

You have the statement (All x are good). You need to proof or disproof it? Well, if you can find such x, which is bad – voila, the proof is one. The statement is wrong, no further steps required!

Because this paragraph is the shortest, I want to add another important detail. We are talking about proofing statements, but how to define a proofed statement? Axiom? Lemma? Theorem? Observation? What is the difference between them? Here is the answer:

1. Axiom – some statement granted for true ( the basic, the fundamentals of mathematics)
2. Lemma – a helping local statement, which is not interesting by itself, but it is a major step in order to retrieve a bigger statement (Observation or Theorem)
3. Observation – a big statement, which is based on finite count of states. For example, if we proof that All the people in the world (planet Earth) are X, from some X, this is not a theorem. It is an observation, because the statement can be applied to finite number of elements (in our case – all the people in the world – is finite count – around 7 billions).
4. Theorem – a big statement, which is based on infinite count of states. For example – all the numbers are X (for some X). The numbers count is infinite, therefore this is a theorem, not an observation!

VIII. Proof by induction

Here comes by mine opinion, the most interesting kind of proof – proof by induction. Let’s go through this proof by an example:

Proof that 2*n is an even number, if n is a positive integer.

Proof by induction

Step 1: The smallest possible n is equal to 0.  Therefore, 2*n equals 2*0 = 0, and 0 is an even number, therefore the statement holds!
Step 2: Let’s take for granted, that for some n equals to k, the statement holds too!
Step 3: Can you proof the statement holds, for n equal to k+1? In other words, we should proof that 2(k+1) is an even number. 2(k+1) = 2*k + 2, which is an even number if 2*k is an even number ( even number + even number = even number). But 2*k is an even number (from step 2), therefore 2(k+1) is an even number and statement holds!

Before going to the next chapter, we will take a short break here and I want to challenge you with this math problem:

Can you proof by induction, that all the natural numbers, equal or greater than 8, can be represented by sum of threes and fives only? In other words:

n \ge 8\\
n = 3*x + 5*y

Please pay attention, that proofing this statement by induction is a must!

One thought on “Discrete Mathematics – How to construct a proof”

1. Jeff Vaughn says:

For the base case, consider m an element of the set {8, 9, 10, 11, 12, 13, 14, 15}. For each number m there exists a j and k elements of N (natural numbers) such that
m = 3*j + 5*k
8 = 3*1 +5*1 ; 9 = 3*3 + 5*0 ; 10 = 3*0 + 5*2 ; 11 = 3*2 + 5*1 ; 12 = 3*4 + 5*0 ; 13 = 3*1 + 5*2 ;
14 = 3*3 + 5*1 ; and 15 = 3*0 + 5*3

For the induction step, we assume for each 7 < n < k there is a pair of numbers j and k such that n = 3*j + 5*k. Then for n = k+1 we see that n = k+1-8 which is less that k, so there is a pair (by our assumption) j and k such that k+1 – 8 = 3*j + 5*k
so k+1 = 3*j + 5*k +8 = 3*j + 5*k + 3*1 + 5*1 = 3*(j+1) + 5*(k+1).

That's the proof, but we should convince ourselves that just because it's true for the base case ( 7 < n < 16 ), that it will be true for the next group of 8; i.e., {16, 17, 18, 19, 20, 21, 22, 23} and it is because each of those is 8 more than some number in the base case. By the induction step, this proves it for each group of 8 from then on.