makeTruthTable[header0_,vars_]:=Module[{data,header},
header=ToString[#,TraditionalForm]&/@header0;
data=BooleanTable[header0,vars]/.{True->"T", False->"F"};
Text@Grid[Prepend[data,header],Background->{None,{Lighter[Yellow,.9],{White,Lighter[Blend[{Blue,Green}],.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},ItemSize->Automatic]

]

makeTextTable[data0_]:=Module[{data},
data=Table[ToString[#,TraditionalForm]&/@(data0[[i]]),{i,1,Length[data0]}];

Text@Grid[data0,Background->{None,{Lighter[Yellow,.9],{White,Lighter[Blend[{Blue,Green}],.8]}}},Dividers->{{Darker[Gray,.6],{Lighter[Gray,.5]},Darker[Gray,.6]},{Darker[Gray,.6],Darker[Gray,.6],{False},Darker[Gray,.6]}},ItemSize->Automatic]

]

4. Notes on basic proofs

4.1. Introduction

These notes are intended to give examples of some of the types of special proofs that appear in many courses in mathematics. They can be used as a framework to construct your own proofs. It is important to remember, however, that there are many different approaches to proofs that make use of other facts in certain subject. 

For example, the examples we give here on showing a function is one-to-one might not be used in ring theory or calculus.

A number of terms will be used without definition and we encourage you to read the appropriate notes on that section.

4.2. Proving Set Inclusion

While a Venn Diagram may be used to illustrate set inclusion (or equality) its value is limited, usually to three sets. Also, it would not be considered a proof by many. The usual technique to show one set is a subset of another is a direct proof and follows from the definition. If we wish to show X is a subset of Y, we take a typical element  x ∈ X and show that x ∈ Y. 

For example, suppose that for sets A and B, we wish to show that
		A ⋂ B ⊆ A ⋃ B
We can argue as follows. Let x be an element of A ⋂ B . Then x is an element of A and an element of B. Certainly x is an element of A and so is an element of A or B. Hence, x is an element of A ⋃ B . Since there was nothing special about x, it must be true for all elements of  A ⋂ B. So by the definition of subset we conclude  A ⋂ B ⊆ A ⋃ B .

We give the argument again, but this time using more symbols and a brief explanation.

Table 4.2.1.

data={
{"x ∈ A ⋂ B","Take typical element of the alleged subset"},
{"x ∈ A and x ∈ B","from definition of intersection"},
{"x ∈ A ","from logical implication"},
{"x ∈ A or x ∈ B","from logical implication"},
{"x ∈ A ⋃ B","definition"}
};
makeTextTable[data]

This is of course a simple example but does give the essential arguments. As a slightly more difficult example, let’s see how we would show   A ⋂ (B ⋃ C) ⊆ B ⋃ (B ⋂ C). This time we will tabulate our proof. Note that the proof uses cases.

Table 4.2.2.

data={
{"x ∈ A ⋂ (B ⋃ C)","Take typical element of the alleged subset"},
{Column[{"x ∈ A and x ∈ B ⋃ C"},{"x ∈ B or x ∈ C"}],"from definition of intersection"},
{"Case 1 x ∈ B ","We consider two cases"},
{"x ∈ B ⇒ x ∈ B ⋃ (A ⋂ C)","This is first case completed"},
{"Case 2 x ∈ C",""},
{"x ∈ C ⇒ x ∈ A ⋂ C","Remember x ∈ A from line 2 "},
{"x ∈ (A ⋂ C) ⋃ B ","definition of set union"},
{"x ∈ B ⋃ (A ⋂ C)","commutative property of union"}
};
makeTextTable[data]

4.3. Proving Sets Equal

In order to prove two sets are equal, there are two methods commonly used. 

The first is to show that each set is a subset of the other. That is, if  A ⊆ B and  B ⊆ A then A=B.

The second method is to use an algebraic approach based on Boolean Algebra.

If in doubt as to which method to use, the rule of thumb is to prove each set a subset of the other. The Boolean algebra method requires knowing the axioms and elementary results. To illustrate this method, consider how to prove one of De Morgan's laws:  (A ⋂ B)' = A' ⋃ B' . It relies on the following result namely "If  X ⋂ P = ∅ and X ⋃ P = U where U is the universal set, then X = P' ". You may wish to try and prove this result from the axioms of Boolean algebra. We also make use of the more obvious results "∅ ⋂ X = ∅" and "U ⋃ X = U". Anyway, let's continue with establishing De Morgan's law.

Table 4.3.1.

data={
{"(A ⋂ B) ⋃ (A' ⋃ B')",""},
{"= ((A ⋂ B) ⋃ A') ⋃ B'","associative law"},
{"=((A ⋃ A') ⋂ (B ⋃ A')) ⋃ B'","distributive law"},
{"= (U ⋂ (B ⋃ A')) ⋃ B'","invers law"},
{"= (B ⋃ A') ⋃ B'","identity law"},
{"= B' ⋃ (B ⋃ A')","commutative law"},
{"= (B' ⋃ B ) ⋃ A' ","associative law"},
{"= U ⋃ A'","identity law"},
{"= U","result stated above"}
};
makeTextTable[data]

This establishes the first part of what we need to prove. To complete the proof we look at the intersection of the sets.

Table 4.3.2.

data={{"(A ⋂ B) ⋃ (A' ⋃ B')",""},
{"= ((A ⋂ B) ⋂ A') ⋃ (A ⋂ B) ⋂ B'","distributive law"},
{"= (A' ⋂ (A ⋂ B)) ⋃ ((A ⋂ B)) ⋂ B'","commutative law"},
{"= ((A' ⋂ A) ⋂ B) ⋃ (A ⋂ (B ⋂ B'))","associative law"},
{"= (∅ ⋂ B) (A ⋂ ∅)","invers law"},
{"∅ ⋃ ∅","result stated above"},
{"∅","identity law"}
};
makeTextTable[data]

4.4. Proving Functions One-to-One

Often we are required to prove that a function f, f: A ⟶ B is one-to-one, or an injection. A proof of this depends on how the function is given to us and what properties the function has. For functions that are given by some formula there is a standard way. We use the contrapositive of the definition of one-to-one, namely that if f(u) = f(v) then u = v.

For example, suppose that f: N → N is defined by f(n) = (n^2) where N denotes the positive integers. We start by assuming there are integers u and v for which f(u) = f(v). Thus, (u^2) = (v^2) and so (u^2) - (v^2) = 0  . Then, (u-v)(u+v) = 0. Since the product is zero then u-v = 0 or u+v = 0. The first condition tells us that u=v. The second condition says that v = -u. However, since u > 0 this would imply v < 0 which is impossible since v is positive. Hence, u = v as required and f is one-to-one. 

There are other methods used to prove a function is one-to-one. In calculus for example, if f is differentiable then it is sufficent to show that the derivative is positive everywhere or negative everywhere. In linear algebra, if f is a linear transformation it is sufficient to show that the kernal of f contains only the zero vector. If f is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice in the list.

4.5. Proving Functions are Onto

Another problem associated with functions is to show that they are onto. This comes down to showing that for every element in the codomain there exists an element in the domain which maps to it. Again, the method used to establish this property depends on how the function is given and its properties. Typically this property is much harder to establish than showing a function is one-to-one. It is really an existence proof. For functions given by formulas we proceed along the following lines. Let y be any element of the codomain and x an element of the domain. We solve the equation y = f(x) for x. This gives us a possible candidate for a domain element. We prove it is a suitable domain element by substituting this value into the function.

 As an example, let’s prove that f: R ⟶ R defined by f(x) = 5x+2 is onto, where R denotes the real numbers. We let y be a typical element of the codomain and set up the equation y = f(x). then, y = 5x+2 and solving for x we get x =((y - 2)/5). Since y is a real number, then ((y - 2)/5) is a real number and  f(((y - 2)/5)) = 5(((y - 2)/5)) + 2 = y.

It seems that this was too long winded an argument but care does need to be taken. For example, suppose we tried to show the function  f: R ⟶ R defined by  f(x) = (x^2)+ 2x is onto, where R denotes the real numbers. Let’s go through the same type of proof. We let y be a typical element of the codomain and set up the equation y = f(x). then, y = (x^2)+ 2x and using the quadratic equation we see that x = (Sqrt[y + 1])- 1 is a solution. It is easy to check that f(x) = y. However, x is not a real number for all choices of y - take y to be -2. So -2 is not in the range of the function and hence this is not an onto function. Of course, it is simpler to show f is not onto by a counter example.

4.6. Mathematical Induction

Some of the statements of theorems which can be proved using mathematical induction involve an integer variable. An example of such a theorem is

	1 + 2 + 3 + ... + n = ((n(n+1))/2).

Proof by picture

list1=Partition[Flatten[Table[{i,j},{i,2,11},{j,2,12}]],2];
lista2={};
For[k=1,k≤Length[list1],k++,
l=list1[[k]]->True;
AppendTo[lista2,l]
]
lista2;
Grid[{{"","1","2","3","4","5","6","7","8","9","10","11"},
{"1"," "," "," "," "," "," "," "," "," "," "},{"2"," "," "," "," "," "," "," "," "," "," "," "},{"3"," "," "," "," "," "," "," "," "," "," "," "},{"4"," "," "," "," "," "," "," "," "," "," "," "},{"5"," "," "," "," "," "," "," "," "," "," "," "},{"6"," "," "," "," "," "," "," "," "," "," "," "},{"7"," "," "," "," "," "," "," "," "," "," "," "},{"8"," "," "," "," "," "," "," "," "," "," "," "},{"9"," "," "," "," "," "," "," "," "," "," "," "},{"10"," "," "," "," "," "," "," "," "," "," "}},(*Frame->All,*)
Frame->{None,None,lista2},

Background->{None,None,{{{2,11},{2,2}}->Red,{{3,11},{3,3}}->Red,{{4,11},{4,4}}->Red,{{5,11},{5,5}}->Red,{{6,11},{6,6}}->Red,{{7,11},{7,7}}->Red,{{8,11},{8,8}}->Red,{{9,11},{9,9}}->Red,{{10,11},{10,10}}->Red,{{11,11},{11,11}}->Red}}]

1 + 2 + 3 + ... + n = ((n(n+1))/2).

Applying above formula is easy. 

For example, for n = 10 we get 1+2+3+4+5+6+7+8+9+10=((10(10+1))/2) = 5(11) = 55 and for n = 257 we get 1+2+3+...+256+257 = ((257(258))/2) = 257(129) = 33,153.

While there are many simple proofs of this formula, this is the usual “proof by picture.” Do you see it?

Let p(n) denote the statement involving the integer variable n. The Principle of Mathematical Induction states:

	If p(1) is true and, for any integer k ⩾ 1 , p(k+1) is true whenever p(k) is true then p(n) is true for all  n ⩾ 1.
	
It is important to show that the base step and the inductive step in the principle are satisfied. Let’s prove the above result. The first step is to establish the base step p(1). This is easy since the expression on the right of the equals sign in p(1) has value ((1 · 2)/2) which is 1 and this is the value of the left hand side of p(1). Hence p(1) is a true statement. Next we need to establish the inductive part of the proof. We assume that for some k ⩾ 1 that p(k) is true. That is the statement:

	1 + 2 + 3 + ... + k = ((k(k +1))/2),
	
is true for some positive integer k. We must use this to show p(k+1) is a true statement. In such proofs we think of the equals sign as separating two expressions. The quantity to the left of the equals sign is called the left hand side (or lhs for short) and the quantity to the right the right hand side (rhs). To show p(k+1) is true means to show the lhs of p(k+1) is equal to the rhs of p(k+1). This is achieved by starting with one side and manipulating it until it becomes the other side. We usually start with the lhs but this is not always the case. Let’s proceed.

Table 4.6.1.

data={
{"1+2+3+...+k+(k+1)","write down lhs of p(k+1)"},
{"(1+...+k) + (k+1)","note that the expression contains lhs of p(k)"},
{"\!\(TraditionalForm\`\*FractionBox[\(k \((k\\  + 1)\)\), \(2\)]\) + (k+1)","since lhs of p(k) = rhs of p(k)"},
{"(k+1)(\!\(\*FractionBox[\(\(k\)\(\\ \)\), \(2\)]\)+1)","factor out k+1"},
{"(k+1)(\!\(\*FractionBox[\(k\\  + \\ 2\), \(2\)]\))","use common denominator"},
{"(k+1)(\!\(\*FractionBox[\(\((k\\  + 1)\) + \\ 1\), \(2\)]\))","the rhs of p(k+1)"}
};
makeTextTable[data]

We have now established that p(k+1) is true, assuming p(k) is true. In other words, p(k) ⇒ p(k+1) . The principle of mathematical induction now tells us that p(n) is true for all positive integers n.

There are several variations in this principle. The first variation covers statements that are true for all integers beyond a certain value (such as  (2^n)> (n^2) which is true for all n ⩾ 5 ).

	If p((Subscript[n, 0])) is true and, for any integer k ⩾ (Subscript[n, 0]) , p(k+1) is true whenever p(k) is true then p(n) is true for all n ⩾ (Subscript[n, 0]) .
	
Let’s use this to prove the statement p(n): (2^(n ))> (n^2), n⩾5 . Our base step this time is to establish p(5). Now lhs p(5) has value 32 and the rhs p(5) has value 25 showing p(5) is a true statement. Now we assume that p(k) is true for some k ⩾ 5 .

Table 4.6.2.

data={
{"(2^(k + 1))","start with lhs of p(k+1)"},
{"= 2 · (2^k)","using properties of exponents"},
{"> 2·(k^2)","assuming p(k) is true"},
{"= (k^2) + (k^2)",""},
{"> (k^2) + 2k + 1",Column[{"since (k^2) > 2k+1","ideally another induction proof required"}]},
{"= (k+1)^2","finally the rhs of p(k+1)"}
};
makeTextTable[data]

There is also a stronger form of mathematical induction which states the following:

	If p(1) is true and, for each integer k ⩾ 1 the statements p(1), p(2),...,p(k) imply the statement p(k+1) then p(n) is true for all n ⩾ 1 .
	
This principle of strong mathematical induction is used for example to prove the result that every positive integer is a prime number, a power of a prime or a product of primes.