Additional Forms of Proof

Additional Forms of Proof

AU: Dec.-11,12, Marks 8

We will discuss additional forms of proofs with the help of some examples. We will discuss

1. Proofs about sets.

2. Proofs by contradiction.

3. Proofs by counter example.

A Proof about Sets

The set is a collection of elements or items. By giving proofs about the sets we try to prove certain properties of the sets.

For example if there are two expressions A and B and we want to prove that both the expressions A and B are equivalent then we need to show that the set represented by expression A is same as the set represented by expression B. Let PUQ = QUR if we map expression A with PUQ and expression B with QUR then to prove A = B we need to prove PUQ = QUP.

This proof is of the kind "if and only if" that means an element x is in A if and only if it is in B. We will make use of sequence of statements along with logical justification in order to prove this equivalence.

Let us prove PUQ = QUP.

Hence PUQ = QUP. Thus A = B is true as element x is in B if and only if x is in A.

Proof by Contradiction

In this type of proof, for the statement of the form if A then B we start with statement A is not true and thus by assuming false A we try to get the conclusion of statement B. When it becomes impossible to reach to statement B we contradict ourself and accept that A is true.

For example -

Prove PUQ = QUP.

Proof

• Initially we assume that PUQ = QUP is not true. That is PUQ ≠ QUP.

• Now consider that x is in Q, or x is in P. Hence we can say x is in PUQ (according to definition of union).

• But this also implies that x is in QUP according to definition of union.

• Hence the assumption which we made initially is false.

• Thus PUQ = QUP is proved.

Example 1.3.1 Prove that √2 is not rational.

AU: Dec.-11, Marks 8

Solution:

Proof: We will assume that, √2 is a rational number. That means we can write

√2 = a/b     ...(1)

where a and b are integers and a/b is irreducible and can be simplified to lowest term. Squaring on both sides of equation (1),

2 = a²/b²

i.e.  2b² = a²

This shows that L.H.S. is even (i.e. multiple of two). Hence R.H.S. is also even. Now if we write a = 2 k then,

2b² = (2 k)² = 4k²

b² = 2 k²

This means, even b is an even number. This is contradiction our assumption that a/b simplified to lowest term because a and b are both even. So √2 cannot be rational.

Example 1.3.2 Prove that if n is a positive integer such that n mod 4 is 2 or 3 then n is not a perfect square. AU: Dec.-12, Marks 6

Solution: The method of contra positive is used. According to method of contra position for proving "If A then B" we prove if not A then not B.

Here we prove - IF n is a perfect square then n mod (4) must be 0 or 1.

Consider that there exists a positive integer n such that n mod 4 is 0 or 1. Then n is a perfect square i.e. n = m², where m is another positive integer. Following are some cases -

1) If m mod 4 = 0 then m = 4i.

For instance - IF i = 1 then m is perfect square

Here i = 1, 4, 9, ...

2) If m mod 4 = 1, then m = 4i + 1.

Here i = 2, 6, 12, 20, ...

3) If m mod 4 = 2, then m = 4i + 2.

Here we fail to identify value of i that will make m as perfect square.

4) If m mod 4 = 3 then m = 4i + 3.

Again there does not exist any value of i which lead to m as perfect square. This proves that n is a positive integer such that n mod 4 is 2 to 3 and n is not a perfect square.

Proof by Counter Example

In order to prove certain statements, we need to see all possible conditions in which that statement remains true. There are some situations in which the statement can not be true. For example -

There is no such pair of integers such that

a mod b = b mod a

Proof: Consider a = 2 and b = 3. Then clearly

2 mod 3≠ 3 mod 2

Thus the given pair is true for any pair of integers but if a = b then naturally

a mod b = b mod a

Thus we need to change the statement slightly. We can say

a mod b = b mod a, when a = b.