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]

]

1. Notes on symbolic logic

1.1. Statements, truth values and truth tables

Definition 1.1.1. A statement is an assertion that can be determined to be true or false. 

Definition 1.1.2. The truth value of a statement is T if it is true and F if it is false. 

For example, the statement “2 + 3 = 5” has truth value T. 

Definition 1.1.3 Statements that involve one or more of the connectives “and”, “or”, “not”, “if ... then’’ and “... if and only if ...” are compound statements (otherwise they are simple statements). 

For example, “It is not the case that 2 + 3 = 5” is the negation of the statement above. Of course, it is stated more simply as “2 + 3 ≠ 5’’. Other examples of compound statements are:

If you finish your homework then you can watch T.V.
This is a question if and only if this is an answer.
I have read this and I understand the concept.

In symbolic logic, we often use letters, such as p, q and r to represent statements and the following symbols to represent the connectives.

Table 1.1.4.

data={{"Connective","Symbol", "Formal Name"},
{"not","¬","negation"},
{"and","∧","conjunction"},
{"or","∨","disconjunction"},
{"if ... then","→","conditional"},
{"...if and only if...","↔","bicconditional"}
};
makeTextTable[data]

Note that the connective “or” in logic is used in the inclusive sense (not the exclusive sense as in English). Thus, the logical statement “It is raining or the sun is shining” means it is raining, or the sun is shining or it is raining and the sun is shining.

If p is the statement “The wall is red” and q is the statement “The lamp is on”, then p ∨ q is the statement “The wall is red or the lamp is on (or both)” whereas q → p is the statement “If the lamp is on then the wall is red”. The statement ¬ p ∧ q translates to “The wall isn’t red and the lamp is on”.

Statements given symbolically have easy translations into English but it should be noted that there are several ways to write a statement in English. For example, with the examples above, the statement   p → q directly translates as “If the wall is red then the lamp is on”. It can also be stated as “The wall is red only if the lamp is on” or  “The lamp is on if the wall is red’’. Similarly,  p ∧ ¬ q directly translates as “The wall is red and the lamp is not on” but it would be preferable to say “The wall is red but the the lamp is off”. Below more extensive list of English equivalents.

1.1.a. ENGLISH TRANSLATIONS OF LOGICAL STATEMENTS

Let p and q be statements. We give here some common ways to translate from symbolic logic into English.

Table 1.1.a.1.

data={{"Symbolic Form","English Equivalent"},
{"p→q",Column[{"If p then q", "p only if q", "q, if p","p is a sufficient condition for q","q is a necessary condition for p","All p are q"}]},
{"p↔q",Column[{"p if and only if q","p is a necessary and sufficient condition for q"}]},
{"(p ∨ q) ∧ ¬(p ∧ q)","Either p or q"}
};
makeTextTable[data]

The truth value of a compound statement is determined from the truth values of its simple components under certain rules. For example, if p is a true statement then the truth value of ¬ p is F. Similarly, if p has truth value F, then the statement ¬ p has truth value T. These rules are summarized in the following truth table.

Table 1.1.5.

Clear[p];
makeTruthTable[{p,¬p},{p}]

If p and q are statements, then the truth value of the statement p ∨ q is T except when both p and q have truth value F. The truth value of p ∧ q is F except if both p and q are true. These and the truth values for the other connectives appear in the truth tables below.

Table 1.1.6.

(*data={{"p","q","p∨q","p∧q","p → q","p ↔ q"},
{"T","T","T","T","T","T"},
{"T","F","T","F","F","F"},
{"F","T","T","F","T","F"},
{"F","F","F","F","T","T"}
};
makeTextTable[data]*)

Clear[p,q];
makeTruthTable[{p,q,p∨q,p∧q,p\[Implies]q,p⧦q},{p,q}]

From these elementary truth tables, we can determine the truth value of more complicated statments. For example, what is the truth value of  p ∧ ¬q given that p and q are true? In this case, ¬q has truth value F and from the second line of the tables above, we see the truth value of the compound statement is F. Had it been the case that p was false and q true, then again ¬q would be false and from the fourth row of the above table we see that p ∧ ¬q is a false statement. To consider all the possible truth values, we construct a truth table.

Table 1.1.7.

data={{"p","q" ,"p ∧ ¬q"},
{"T","T","t F f"},
{"T","F","t F t"},
{"F","T","f F f"},
{"F","F","f F f"}
};
makeTextTable[data]

The lower case t and f were used to record truth values in intermediate steps.

1.1.b. COMPLETING A TRUTH TABLE

A truth table involving n statements has  (2^n) rows. So a table for a statement involving p and q has 4 rows and a table involving p, q and r has 8 rows etc. Here we give an example of completing a truth table with 8 rows. Typically, the table is set up as follows. We hold the first two statements true and consider the two cases of the last statement being true or false giving the first two rows of the table. Next we let the second statement be false and again consider both possible truth values of the last statement (giving the first 4 rows of the table). Finally, we let the first statement be false and consider the possible truth values of the last two statements, first with the second statement true and the last statement taking on both possible values and then the second statement being false and the last statement taking both values. We complete the truth table for the statement  (p → q) → (q ∨ r) will have eight rows.

Table 1.1.b.1.

data={{"p","q" ,"r","(p → q) → (q ∨ r)"},
{"T","T","T",""},
{"T","T","F",""},
{"T","F","T",""},
{"T","F","F",""},
{"F","T","T",""},
{"F","T","F",""},
{"F","F","T",""},
{"F","F","F",""}
};
makeTextTable[data]

As in algebra, we find the truth values of parenthesized expressions first. So to complete this example we’ll first find the truth value of  p → q . Second, we’ll find the truth value of q ∨ r and finally find the truth value of the complete statement.

  We look up the truth values for the conditional involving two statements to find the truth values p → q . These values are now entered in the table. Note that it is important to know the elementary truth tables. Also, it is probably better to memorize in the form “T → T is T, T→ F is F” etc., rather than think in terms of p and q.

Table 1.1.b.2.

data={{"p","q" ,"r","(p → q) → (q ∨ r)"},
{"T","T","T","T                "},
{"T","T","F","T                "},
{"T","F","T","F                "},
{"T","F","F","F                "},
{"F","T","T","T                "},
{"F","T","F","T                "},
{"F","F","T","T                "},
{"F","F","F","T                "}
};
makeTextTable[data]

Note that whenever p is false that p → ? is true. In fact, it is only false when the first statement is true and the second is false. Next we fill in the truth values of q ∨ r .

We look up the truth values for the conjunction involving two statements to find the truth values of  q ∨ r . These values are now entered in the table. Again, think of the conjunction of two statements is T except when both statements are false.

Table 1.1.b.3.

data={{"p","q" ,"r","(p → q) → (q ∨ r)"},
{"T","T","T","T               T"},
{"T","T","F","T               T"},
{"T","F","T","F               T"},
{"T","F","F","F               T"},
{"F","T","T","T               F"},
{"F","T","F","T               T"},
{"F","F","T","T               T"},
{"F","F","F","T               F"}
};
makeTextTable[data]

Finally, we use the truth values we have entered to fill in the truth values of the complete statement (p → q) → (q ∨ r).

We look up the truth values for the conjunction involving two statements to find the truth values of  q ∨ r . These values are now entered in the table.

Table 1.1.b.4.

data={{"p","q" ,"r","(p → q) → (q ∨ r)"},
{"T","T","T","T       T        T"},
{"T","T","F","T       T        T"},
{"T","F","T","F       T        T"},
{"T","F","F","F       T        T"},
{"F","T","T","T       T        F"},
{"F","T","F","T       T        T"},
{"F","F","T","T       T        T"},
{"F","F","F","T       F        F"}
};
makeTextTable[data]

Finally, we use the truth values we have entered to fill in the truth values of the complete statement (p → q) → (q ∨ r).

Note that while a truth table involving statements p and q has 4 rows to cover the possibility of each statement being true or false, if we have additional information about either statement this will reduce the number of rows in the truth table. If, for example, the statement p is known to be true, then in constructing the truth table of ¬p=>¬q we will only have 2 rows. Truth tables involving n statements will have (2^n) rows unless additional information about the truth values of some of these statements is known.

Definition 1.1.8. A statement that is always true is called logically true or a tautology. 

Definition 1.1.9. A statement that is always false is called logically false or a contradiction. 

Symbolically, we denote a tautology by 1 and a contradiction by 0.

1.2. Logical equivalence and implication

We cannot construct any more than 16 truth tables involving two statements. This is because such a truth table has 4 rows and the truth value of each row is T or F. Below there is a list of 16 inequivalent truth tables.

Table 1.2.1.

(*data={{"p","q","p∨¬p","p∨q","q→p","p→q","¬(p∧q)","p","q","¬(p↔q)","p↔q","¬q","¬p","p∧q","¬(p→q)","¬(q→p)","¬(p∨q)","p ∧ ¬p"},
{"T","T","T","T","T","T","F","T","T","F","T","F","F","T","F","F","F","F"},
{"T","F","T","T","T","F","T","T","F","T","F","T","F","F","T","F","F","F"},
{"F","T","T","T","F","T","T","F","T","T","F","F","T","F","F","T","F","F"},
{"F","F","T","F","T","T","T","F","F","F","T","T","T","F","F","F","T","F"}
};
makeTextTable[data]*)
makeTruthTable[{p,q,p∨¬p,p∨q,q\[Implies]p,p\[Implies]q,¬(p∧q),p,q,¬(p⧦q),p⧦q,¬q,¬p,p∧q,¬(p\[Implies]q),¬(q\[Implies]p),¬(p∨q),p ∧ ¬p},{p,q}] (*TO Do !!!*)

However, we can certainly construct more than 16 statements involving two statements. What happens is that many (in fact infinitely many) statements have identical truth tables.

Definition 1.2.2. We say that the statements r and s are logically equivalent if their truth tables are identical. For example the truth table of ¬p ∨ q :

Table 1.2.3.

makeTruthTable[{p,q,¬p∨q},{p,q}]

shows that  ¬p ∨ q is equivalent to  p → q . It is easily shown that the statements r and s are equivalent if and only if  r ↔ s is a tautology.

If statements r and s are equivalent we write r ↔ s . For statements involving three statements, r, s and t, there are 64 different truth tables that can be constructed. In general, there are (2^(2^n)) truth tables that can be constructed from n statements.

One common error is think that the statements p → q and its converse  q → p are equivalent, but they are not. The conditional statement  p → q is equivalent to its contrapositive statement ¬q → ¬p .

Definition 1.2.4.  We say that r implies s if s is true whenever r is true. If r implies s then we write  r → s. Alternatively, r implies s if and only if the statement r → s is a tautology. 

Definition 1.2.5. We say that s is logically deducible from r.

For example, in a mathematical theorem the hypothesis implies the conclusion or the conclusion is deducible from the hypothesis.

1.2.a. Common Logical equivalences and implications

Table 1.2.a.1.

data={{"Basic statement","Equivalent"},
{"p∨q","q∨p"},
{"p∧q","q∧p"},
{"¬(p∧q)","-p∨¬q"},
{"¬(p∨q)","-p∧¬q"},
{"p→q",Column[{"¬p∨q","¬q→¬p"}]},
{"p↔q",Column[{"(p→q)∧(q→p)","(¬p∨q)∧(¬q∨p)"}]},
{"p∧(q∧r)","(p∧q)∧r"},
{"p∨(q∨r)","(p∨q)∨r"},
{"p∧(q∨r)","(p∧q)∨(p∧r)"},
{"p∨(q∧r)","(p∨q)∧(p∨r)"},
{"p→(q∨r)","(p∧¬q)→r"}
};
makeTextTable[data]

Table 1.2.a.2.

data={{"Basic statement","Equivalent"},
{"p∧q",Column[{"p","p∨q"}]},
{"p↔q","p→q"},
{"p∧(p→q)","q"},
{"(p→q)∧¬q","¬p"},
{"(p→q)∧(q→r)","p→r"},
{"(p↔q)∧(q↔r)","p↔r"}
};
makeTextTable[data]

It is also important to spot equivalent statements when written in English and not just symbollically.

1.2.1. Statements involving variables

The sentence “x + 2 = 5” cannot be assigned a truth value and so it is technically not a statement. However, if we knew the value of x we could determine its truth value. We say that it is a statement involving a variable, namely x. If we allow x to have value 3 then we get a true statement whereas, if we let x have value 1 we get a false statement. Symbolically, we might represent the above statement as p(x). We see that p(3) is true while p(1) is false. Similarly, the statement xy = 4 could be represented symbolically as q(x,y) since it is a statement involving two variables. Again, to assign a truth value to q(x,y) we would have to know the values of both x and y. If x had value 2 and y had value 5 then q(2,5) would have truth value F. Note that q(2,2) has truth value T.

Another way to be able to assign truth values to statements involving variables is through the use of quantifiers. 

Definition 1.2.1.1. The universal quantifier, ∀ , in English means “For all possible values of the variable”. 

Definition 1.2.1.2. The existential quantifier, ∃ , in English means “There is a value of the variable”. 

Thus, with the examples above, the following are statements: (Subscript[∀, x]) p(x); (Subscript[∃, x]) p(x). The first states that for all possible values of the variable x that x + 2 = 5. The second states that there is a value of x for which x + 2 = 5. Clearly, we have made each of these a statement (and we might believe the first to be false and the second to be true). The problem we are left with is what do we mean by the possible values of the variable? 

Definition 1.2.1.3. We assume that the variable in our statement may be replaced by a quantity from a set of known objects. This set of objects is called the universal set of discourse, or more briefly, the universal set.

Usually, this universal set will be understood from the context. However, if necessary, we shall define the universal set for each variable in the statement and write something like (Subscript[∀, x∈U]) p(x). Here, the notation x∈U translates into English as “x an element of the set U”. Note that for quantified statements involving more than one variable, the universal set for each variable may be different.

Alternatively, we may think about a statement involving variables as a statement about the universal set U. 

Definition 1.2.1.4. The truth set of the statement consists of those elements of U for which the statement is true. 

For example, if the universal set is the set of integers then the truth set of the statement “(x^2)=4” is -2,2 . A statement about U is a tautology if and only if its truth set is U and a contradiction if its truth set is the empty set. Thus a statement such as (Subscript[∀, x∈U]) p(x) is true if its truth set is U. If its truth set is a proper subset of U then it is a false statement. A statement of the form (Subscript[∃, x∈U]) p(x) is true if its truth set is non empty and false if its truth set is the empty set.

1.2.2. Negation of statements involving variables

Consider the statement (Subscript[∀, x∈U])p(x) . If this statement is true then its truth set is U. Its negation must be false and have truth set the empty set. Alternatively, if the statement is false (i.e. its truth set is a proper subset of U) then its negation has to be true. We claim that the negation is the statement (Subscript[∃, x∈U]) ¬p(x) . Clearly this is the negation if the original statement is true. If the original is false then there must have been some x for which p(x) was false. We conclude that the statement  ¬((Subscript[∀, x]) p(x)) is equivalent to (Subscript[∃, x]) ¬p(x) . Similarly, ¬((Subscript[∃, x]) p(x)) is equivalent to (Subscript[∀, x]) ¬p(x) .

For statements involving more than one variable we have a similar situation. We give below a table of statements involving two quantifiers along with its negation.

Table 1.2.2.1.

data={{"Statement","Negation"},
{"\!\(TraditionalForm\`\*SubscriptBox[\(∀\), \(x\)]\(\*SubscriptBox[\(∀\), \(y\)]\\ p(x, y)\)\)","\!\(TraditionalForm\`\*SubscriptBox[\(∃\), \(x\)]\(\*SubscriptBox[\(∃\), \(y\)]\\ \(¬ p(x, y)\)\)\)"},
{"(Subscript[∀, x])(Subscript[∃, y]) p(x,y)","\!\(TraditionalForm\`\*SubscriptBox[\(∃\), \(x\)]\(\*SubscriptBox[\(∀\), \(y\)]\\ \(¬ p(x, y)\)\)\)"},
{"(Subscript[∃, x])(Subscript[∀, y]) p(x,y)","\!\(TraditionalForm\`\*SubscriptBox[\(∀\), \(x\)]\(\*SubscriptBox[\(∃\), \(y\)]\\ \(¬ p(x, y)\)\)\)"},
{"(Subscript[∃, x])(Subscript[∃, y]) p(x,y)","(Subscript[∃, x])(Subscript[∃, y]) ¬p(x,y)"}
};
makeTextTable[data]

1.2.2.a. Negation

We illustrate why the negation of (Subscript[∃, x∈X])(Subscript[∀, y∈Y]) p(x,y) is (Subscript[∀, x∈X])(Subscript[∃, y∈Y])  ¬p(x,y)  using two sets X and Y, each having two elements. In the diagrams below, if p(x,y) is true we mark the square red and if it is false then we leave it white. There are of course 16 such diagrams.

Now consider the statement  (Subscript[∃, x∈X])(Subscript[∀, y∈Y]) p(x,y). For this to be true we must have one of the following diagrams. This is because for at least one fixed x and every element of Y the statement is true. Thus there must be at least one red row.

Fig. 1.2.2.a.1.

GraphicsRow[{RegionPlot[x≥0 || y<0,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[y≥0 || y<0,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x<0 || y<0,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[ y≤ 0,{x,-2,2},{y,-2,2}, Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[y≥0 || x<0,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[y≥0 ,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[y≥0 || x≥0,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None]}]

It is false for the remaining nine diagrams shown below (since no row is all red).

Fig. 1.2.2.a.2.

GraphicsRow[{RegionPlot[False,{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x≥ 0 && y≥  0,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[(x≥ 0 && y≥  0)||(x< 0 && y<  0),{x,-2,2},{y,-2,2},Mesh->1,Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x< 0 && y<  0,{x,-2,2},{y,-2,2}, Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x≤ 0 && y≥ 0,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x≥0 ,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x≥ 0 && y<  0,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[(x< 0 && y≥  0)||(x≥ 0 && y<  0),{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None],
RegionPlot[x<0,{x,-2,2},{y,-2,2},Frame->True,FrameLabel->{"Y","X"},ImageSize->120,FrameTicks->None,PlotStyle->Red,BoundaryStyle->None]}]

The situation is reversed for the statement (Subscript[∀, x∈X])(Subscript[∃, y∈Y])¬p(x,y) . In this case, the statement is true if there is no completely red row and false when there is.

2. Notes on methods of proof

2.1. Introduction

In mathematics we make assertions about a system whether it be a number system or something more abstract such as a group or linear space. 

Definition 2.1.1. An assertion not known to be true or false is called a hypothesis or conjecture. 

Prior to 1995, a famous conjecture was Fermat’s Last Theorem. It stated that for an integer n ⩾ 3  there are no positive integer solutions to the equation (x^n) + (y^n) = (z^n) . 

Definition 2.1.2. The process of establishing the truth of an assertion is called a proof.

Once a conjecture has been shown to be a true statement we label it as a lemma, theorem or corollary. We think of a lemma as a result which is used primarily to prove a more important result (i.e. a theorem), and a corollary as a special case or consequence of a theorem. For example in calculus, we could think of Maclaurin’s Theorem as a corollary to Taylor’s Theorem.

In these notes we are concerned with techniques that may be used to prove a result and provide a tonic to the student’s malady on proofs namely “I don’t know where to start”. It is probably impossible to teach how to prove something and the best one can offer is a catalog of types of proof along with examples. By reading proofs, the student can often gain insight as to how to prove their own particular result. Once they have gained some experience, they might then be ready for more complicated proofs. What is certain is that there is no cook book solution to obtaining a proof. We recommend that you read the notes on logic

Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","logic"}]

before proceeding.

2.2. Definitions and Theorems

In many math text books you will see definitions and theorems. The definitions are defining technical words and give a name to a special subclass of objects. For example, when we study the integers we have a special subset of positive integers greater than 1 which are called primes. In calculus we deal mainly with continuous functions or differentiable functions which are special subsets of functions. Quite often it is these definitions that lead to proofs of elementary results. In understanding mathematics, it is important to have a solid grasp of these definitions. Without that, comprehending a theorem is limited and attempting to prove a theorem is useless. Definitions have the form “X is a blob if and only if condition”. This biconditional form is used in two ways. First, suppose we have an object Y and want to know if it is a blob. We see if Y satisfies the condition. If it does then Y is a blob, otherwise it is not. Secondly, suppose we have an object Y that is a blob. Then we know that Y does satisfy the condition and may make use of this fact, in a proof say.

The majority of theorem statements have two forms. The first is a conditional statement “If condition then conclusion”. This form is an implication and it means that the conclusion is true whenever the condition is true. If the condition is denoted by p and the conclusion by q then the statement of the theorem is written as p ⇒ q. Consequently, p ⇒ q if and only if the logical statement p → q is a tautology. Often you will see the phrase “For all” in statements of theorems. A statement such as “For all x in X, conclusion” is really a conditional form “If x is an element of X then conclusion”. It happens to be true no matter which element x we consider.

The second common form of a theorem statement is the biconditional. This has the form “p if and only if q” or symbollically p ⇔ q . It is equivalent to the two implications p ⇒ q and q ⇒ p . Indeed, this is how many of these theorems are proved (by proving the two implications). Logically,  p ⇔ q if and only if p ↔ q is a tautology.

One important aspect of statements is that they do have equivalent forms. Often, it might be difficult to prove a result as it is stated but it could be easier to prove an equivalent statement. The following table gives a list of common equivalent forms.

Table 2.2.1.

data={{"Basic statement","Equivalent"},
{"p ⇒ q","¬q ⇒ ¬p"},
{"p ⇔ q",Column[{"(p ⇒ q)∧(q ⇒ p)","(¬q ⇒ ¬p)∧(¬p ⇒ ¬q)","(p ⇒ q)∧(¬p ⇒ ¬q)"}]},
{"p ⇒ (q∨r)","(p∧¬q) ⇒ r"}
};
makeTextTable[data]

We also list some of the English equivalents of the conditional.

Table 2.2.2.

data={{"Symbolic Form","English Equivalent"},
{"p\[Implies]q",Column[{"If p then q", "p only if q", "q, if p","q whenever p","p is a sufficient codntition for q","q is a necessary condition for p"}]},
{"p⧦q",Column[{"p if and only if q","p is a necessary and sufficient condition for q"}]}
};
makeTextTable[data]

Other phrases that appear in theorems are “There exists” and “unique”. A theorem statement such as “There exists an x in X such that conclusion” is know as an existence theorem. It says that the conclusion statement is satsfied by something (or the truth set is non empty). However, the conclusion may be satisfied by many elements of the set. If there is precisely one element of the set that satisfies the conclusion then the theorem statement would state “There exists a unique x in X such that conclusion”. Such theorems are referred to as uniqeness theorems. Our previous statement is an existence and uniqeness theorem. It is possible to have a theorem which asserts uniqeness but not existence.

2.3. Disproving Statements

Some conjectures are false. Verifying that a conjecture is false is often easier than proving a conjecture is true. Despite that, showing a conjecture is false may have its own challenges and usually requires a deep knowledge of the subject.

Some statements are often shown to be false by a counter examples. Such statements have the form “For all x in X conclusion”. This is shown to be false by finding one element of X which does not satisfy the conclusion. As an example, consider the statement “For all prime numbers p, 2p+1 is prime”. This statement is true for the primes 2, 3 and 5. It is also true for the primes 11 and 23. However, the statement is an assertion for all primes. Clearly the statement is not true for the prime 7 (since 15 = 3 × 5) and we have obtained a counter example to the statement.

For finite sets, statements of the form such as “There exists an x such that conclusion” can be refuted by example. By testing each element of the set and showing no element satisfies the conclusion we have shown the statement is false through an exhaustive search. This would also refute the statement “There exists a unique x such that conclusion”. However, a statement of this form might be false for another reason, namely that there are two or more elements of the set that satisfy the conclusion. Again, this statement could be refuted through a counter example. For example consider the statement “The equation (x^2)=1 has a unique solution”. This statement is false in the integers since both 1 and -1 satisfy the equation and we have disproved it using a counter example. Note that the statement is true in the positive integers.

As we noted above, some statements remain conjectures for many years (or even centuries) due to the fact that a proof cannot be constructed (or discovered) or that a counter example cannot be found. There are many famous conjectures and famous theorems that were conjectures for many years (The 4 color theorem and Fermat’s Last Theorem, for example).

2.4. Types of Proof

We discuss some approaches to proofs in this section. We focus our attention on proof by mathematical induction, direct proofs, and indirect proofs (by contrapositive, equivalence and proofs using contradiction). We assume that the theorem statement is a conditional form ( p ⇒ q ) since the biconditional form is equivalent to two conditional implications.

2.4.1 Direct Proofs

In a direct proof of the statement p ⇒ q we employ the transitive nature of implication. That is to say that if p ⇒ r and r ⇒ q then it follows that p ⇒ q . To start off the proof we assume that p is a true statement. From this we deduce an implied statement (Subscript[p, 1]) . From (Subscript[p, 1]) we deduce an implied statement (Subscript[p, 2]) and so on until we obtain an implication (Subscript[p, k]) ⇒ q . Using the transitive property of implication we then deduce the validity of the theorem statement. The idea is very simple but the problem is what are these implied statements (Subscript[p, 1]),(Subscript[p, 2]),...,(Subscript[p, k]) ? These are results in their own right and may be obtained from other theorems, corollaries or lemmas. In other words, they are known true statements. Alternatively, they may be obtained from definitions. Undoubtedly, then, we have to know some of the implications of the statement (Subscript[p, i]) . In other words, what does a given piece of information tell us. The bad news is that a given statement might make us think of several consequences and only a few of those facts might be used in the proof. The worst case is that a given statement means absolutely nothing. So the difficulty in a direct proof is finding these connections between certain facts. For example, suppose we know that x is a prime number. What does that tell us? Here are some possible connections:

	• Only positive divisors are 1 and itself
	• If x is not two then it is an odd integer
	• If x is odd then it is of the form 4k+1 or 4k-1 for some integer k.
	
Essentially we need to build in our memory a list of facts and implications. This comes down to knowing as much information as possible. One might compare a direct proof to crossing a river using stepping stones. Standing on the river bank is knowing the statement p. Getting across the river is deducing the statement q. The stepping stones are the intermediate statements each of which is a consequence of the other. From each stone, you may have a choice of several stones to reach next and you have to decide which one is best for you. The worst scenario is to have no stones on which to step!

The skill of knowing which implications to use gets better with practice and experience. However, one cannot over emphasize the fact that it is necessary to have knowledge of other results.

There is one particular warning we should give here. In knowing the answer to a problem we were unable to solve by ourselves, we sometimes work backwards to see how we could have derived that answer. This often gives us more insight into the problem. In a direct proof of a conditional statement p ⇒ q we do know the answer (namely q). This time, assuming the answer and working backwards does not work and certainly is not a proof. In first attempts at proofs, students often assume q and derive a true statement such as “1 = 1” and conclude that q is true. This is incorrect from many points of view. First of all, their “proof” may never use the statement p. What they have proved is q ⇒ 1 = 1 . Secondly, the statement “1=1” is true (in fact a tautology) and so is true whenever q is true but is also true if q is false. Thirdly, at best the student has proved the converse statement which is not equivalent to the original. Think about the statement “If x is odd then 2x is even” and why 2x being even does not imply that x is odd.

2.4.2. Proof by Contradiction and Reductio ad Absurdum

A common method to establish  p ⇒ q is through proof by contradiction. As in direct proofs, we assume p is true but we also assume the negation of q is true. From these facts, we deduce that the negation of p is also true (or that p is false and hence the contradiction). Our conclusion is that the original statement q must be true. Logically we have (p∧ ¬q)  →  ¬p  is equivalent to p → q .

A similar technique is known as reductio ad absurdum. Again, we wish to establish p ⇒ q . Suppose that we know r is a true statement. As with proof by contradiction we assume p and the negation of q to be true. Suppose we can now show that these imply that the negation of r is true (or that r is false). We now have that r is both true and false which is absurd. Our conclusion is that q is true.

2.4.3. The Contrapositive and Equivalent Forms

The contrapositive of the implication p ⇒ q is the implication ¬q ⇒ ¬p . These are equivalent forms. Sometimes it is easier to prove a result in the contrapositive form rather than in the original conditional form. Proving the contrapositive might also be done as a direct proof, by induction or by contradiction. The only care that one need take is that the contrapositive is formed correctly. For example the contrapositive of the statement “If x is odd then 5x is odd” is the statement “If 5x is not odd then x is not odd” or better still, “If 5x is even then x is even”. Some statements become more difficult to put in the contrapositive form when they involve several connectives. The contrapositive of the statement “If x is odd and y is even then xy is even” is “If xy is odd then x is even or y is odd”. From our table of equivalents in section 2, we see this is equivalent to “If xy is odd and x is odd then y is odd”.

Let’s realize that in a direct proof of this result, our assumed true statement would change depending on which form we chose. For the statement “If x is odd and y is even then xy is even” we would assume that x is and odd integer and y an even integer. For the statement “If xy is odd then x is even or y is odd” we would assume that the product xy is an odd integer. Finally, for the statement “If xy is odd and x is odd then y is odd” we would assume that xy is odd and x is odd.

Whether it is better to prove a statement in the original form or to rewrite it to an equivalent form is difficult to answer. Certainly when answering problems from a text, it would be prudent to keep to the original form of the statement in the majority of cases. However, if you get stuck on a proof it might be beneficial to consider alternative phrasings.

2.4.4. Existence Proofs

Theorems which state “There exists an x such that conclusion” are known as existence theorems. Many, but not all, theorems of this type are proved using a constructive proof so named because one finds an element x that does satisfy the conclusion. 

As a simple example consider the statement “Let a be a real number. There exists a real number x that is a solution to the equation 5x+3 = a”. A proof of this statement would construct such a real number x. Using the rules of arithmetic in the real number system, we know that if a is a real number then so too is ((a - 3)/5). This is a value of x that is a solution to the equation since 5x +3 = 5(((a - 3)/5)) + 3 = a - 3 +3 = a as required. Of course not all proofs are this simple and to produce an element x that will work may require ingenuity.

2.4.5. Uniqueness Proofs

Theorem statements that involve the word “unique” are known as uniqueness theorems. Typically the proof of such a statement follows the idea that we assume there are two elements that satisfy the conclusion of the statement and then show that these elements are identical. 

As an example, consider the statement “If the real number equation 5x + 3 = a has a solution then it is unique”. A proof would look something like the following. Suppose that y and z are both solutions to the equation. Then 5y + 3 = a and 5z + 3 = a. Thus 5y +3 = 5z +3 from which we deduce that y = z. While this is a very simple example, the skeleton of the proof is the same for many uniqueness theorems.

2.4.6. Mathematical Induction

A type of proof that deserves special attention is 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).

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

	If p(1) is true and, for each integer  k ⩾ 1 , p(k+1) is true whenever p(k) is true then p(n) is true for all n ⩾ 1.
	
This principle is often compared to an infinite line of dominos. The inductive part of the principle (for each integer n ⩾ 1 , p(n+1) is true whenever p(n) is true) would say that the domino in the (n+1)st position falls whenever the nth domino falls. However, at that stage we still don’t know if the line of dominos has fallen or is still upright. The base step in the principle (If p(1) is true) is analogous to saying the first domino has fallen. We would now realize that the complete line of dominos will fall. It is important to show that the base step and the inductive step in the principle are satisfied.

There are several variations in this principle. The first 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 each 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]) .
	
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. As with the principle of mathematical induction, there is a variation on this to cover those statements that are true for all integers beyond a certain value (Subscript[n, 0]) .

3. Notes in set theory

3.1. Notation and Terminology

Definition 3.1.1. A set is a collection of objects called elements of the set. 

Why not use the word “collection” and eliminate the word “set”, thereby having fewer words to worry about? “Collection” is a common word whose generic meaning is understood by most people. The use of the word “set” means that there is also a method to determine whether or not a particular object belongs in the set. We then say that the set is well-defined. 

For example, it is easy to decide that the number 8 is not in the set consisting of the integers 1 through 5. After all, there are only five objects to consider and it is clear that 8 is not one of them by simply checking all five.

A basic problem here is now to indicate sets on paper and verbally. As seen above, a set could be described with a phrase such as “the integers 1 through 5” and the speaker hopes that it is understood. Symbollically, we use two common methods to write sets. 

Definition 3.1.2. The roster notation is a complete or implied listing of all the elements of the set. 

So A={a,b,c,d} and  B={2,4,6,8,...,40} are examples of roster notation defining sets with 4 and 20 elements respectively. The ellipsis, “...”, is used to mean you fill in the missing elements in the obvious manner or pattern, as there are too many to actually list out on paper. 

Definition 3.1.3. The set-builder notation is used when the roster method is cumbersome or impossible. 

The set B above could be described by {x| 2 ⩽x≤40 and x is even} . The vertical bar, “|’”, is read as “such that” so this notation is read aloud as “the set of x such that x is between 2 and 40 (inclusive) and x is even.’’ (Sometimes a colon is used instead of |.) In set-builder notation, whatever comes after the bar describes the rule for determining whether or not an object is in the set. For the set {x| x is real number} the roster notation would be impossible since there are too many reals to actually list out, explicitly or implicitly.

To discuss and manipulate sets we need a short list of symbols commonly used in print. We start with five symbols summarized in the following table.

Table 3.1.4.

data={{"Symbol","Meaning", "Example","Read as:"},
{"∈","element of","x∈A","'x an element of A'or 'x in A'"},
{"⊂","subset","A⊂B","'A os a subset of B' or 'A contained in B'"},
{"⋃","union","A ⋃ B","A union B"},
{"⋂","intersection","A ⋂ B","A intersect B"},
{"'","complement","A'","A complement"}
};
makeTextTable[data]

The first symbol, ∈ , indicates membership of an object in a particular set. The negation of this, or nonmembership is often indicated by “x ∉ A” (“x is not in A”). The subset relation, A⊂B , states that every element of A is also an element of B. Logically, this would be: if x ∈ A then x∈B. The union and intersection operators form new sets by the following rules.

3.1.a Set union and set intersection examples

Let A = {1,3,5,7,9} and  B = {2,3,4,5,6}.

A ⋃ B consists of the elements in A or B so  A ⋃ B = {1,2,3,4,5,6,7,9}.

A ⋂ B consists of the elements in both A and B so A ⋂ B = {3,5}.

The set A ⋃ B is defined to be { x| x ∈ A or x ∈ B } while A ⋂ B is defined to be { x| x ∈ A and x ∈ B } . Finally, the complement of a set consists of those objects that are not in the given set. This presents a minor problem. If A = { -3, π , (Sqrt[2])} then clearly I am not in A so should I be considered an element of  A’ ? Normally not, I think. Underlying a discussion or argument involving sets is usually a large set called the universal set or universe of the discourse and is commonly denoted by U. This universe may be implied or stated explicitly. Operations involving union, intersection or complement are understood to be contained in this universe. 

For example, if we were discussing real numbers (so that our universe would be the set of reals) and mentioned the set A above with 3 elements, it is understood that  A’ consists of those real numbers not in A. This conveniently excludes me from the set  A’ .

3.2. More on set operations

3.2.1. Arbitrary unions and intersections

The notions of union and intersection can be easily extended to more than two sets.

For finitely many sets, say (Subscript[A, 1]), (Subscript[A, 2]),..., (Subscript[A, 10]) we write (Subscript[A, 1]) ⋃ (Subscript[A, 2]) ⋃ ... ⋃ (Subscript[A, 10])  or (Underoverscript[ ⋃, (n=1), 10])(Subscript[A, n])  and (Subscript[A, 1]) ⋂ (Subscript[A, 2]) ⋂ ... ⋂ (Subscript[A, 10])  or (Underoverscript[ ⋂, (n=1), 10])(Subscript[A, n]). If we have a sequence of sets ((Subscript[A, n]))_(n=1)^∞ we write  (Underoverscript[ ⋃, (n=1), ∞])(Subscript[A, n]) and (Underoverscript[ ⋂, (n=1), ∞])(Subscript[A, n]). 

Perhaps the most general form of this notation is a collection of sets with subscripts in some general index set Γ, ((Subscript[A, γ])| γ ∈ Γ) . Here Γ could be finite or infinite. We then write (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) and (Underscript[ ⋂, γ∈Γ])(Subscript[A, γ]) . So an alternate way to write (Underoverscript[ ⋂, (n=1), ∞])(Subscript[A, n]) would be (Underscript[ ⋂, n∈N])(Subscript[A, n]) where N is the set of natural numbers.

Exactly what these symbols mean is as follows.

By (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) we mean {x| (Subscript[∃, γ∈Γ]) x ∈ (Subscript[A, γ])} and by (Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])  we mean  {x| (Subscript[∀, γ∈Γ]) x ∈ (Subscript[A, γ])}.

Check that these become our original definitions of set union and intersection when the indexing set has just two elements, and then we can just call the two sets A and B. An example of a large indexing set would be the set of reals R. If  (Subscript[A, x])={(x,y)| y real} then (Underscript[ ⋃, x∈R])(Subscript[A, x]) would be the entire Cartesian plane  R x R written as a union of all vertical lines in the plane.

Some care must be taken when dealing with negations involving union and intersections. Since x∈ (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) means there is at least one  γ so that  x ∈ (Subscript[A, γ]) , then x∉ (Underscript[ ⋃, γ∈Γ])(Subscript[A, γ]) means x is not in any (Subscript[A, γ]). (Logically we have ¬ ((Subscript[∃, γ∈Γ])x∈(Subscript[A, γ])) ≈ (Subscript[∀, γ∈Γ]) x ∉ (Subscript[A, γ]).) Similarly, Since  x ∈(Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])  means  x∈(Subscript[A, γ]) for every γ, then x ∉(Underscript[ ⋂, γ∈Γ])(Subscript[A, γ])means there is at least one γ with x ∉ (Subscript[A, γ]) . (Logically we have ¬((Subscript[∀, γ∈Γ])x∈(Subscript[A, γ])) ≈ (Subscript[∃, γ∈Γ]) x ∉ (Subscript[A, γ]).)

3.2.2. Manipulating Unions and Intersections

3.2.2.a Boolean Algebra

Definition 3.2.2.a.1. A Boolean algebra is a set with two binary operations, ⋃ and ⋂ , that are commutative, associative and each distributes over the other, plus a unary operation ‘ . Also required are identity elements ϕ and U for the binary operations that satisfy A ⋃ ϕ = A , A ⋂ U = A , A ⋃ A’ = U  and A ⋂ A’ = ϕ for all elements A in the set.

One interpretation of Boolean algebra is the collection of subsets of a fixed set X. We take ⋃ , ⋂ , ‘ , ϕ and U to be set union, set intersection, complementation, the empty set and the set X respectively. Equality here means the usual equality of sets.

Another interpretation is the calculus of propositions in symbolic logic. Here we take  ⋃ , ⋂ , ‘ , ϕ  and U to be disjunction, conjunction, negation, a fixed contradiction and a fixed tautology respectively. In this setting equality means logical equivalence.

It is not surprising then that we find analogous properties and rules appearing in these two areas. For example, the axiom of the distributive properties says that for sets we have A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C) while p ∨ (q ∧ r) ↔( p ∨ q) ∧ (p ∨ r) is a familiar equivalence in logic.

From the axioms above one can prove DeMorgan’s Laws (in some axiom sets this is included as an axiom). The following table contains just a few rules that hold in a Boolean algebra, written in both set and logic notation. Rows 3 and 4 are DeMorgan’s Laws. Note that the two versions of these rules are identical in structure, differing only in the choice of symbols.

Table 3.2.2.a.2.

data={{"Set vesion","Logic version"},
{"A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C)","p ∨ (q ∧ r) ↔( p ∨ q) ∧ (p ∨ r)"},
{"A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C)","p ∧ (q ∨ r) ↔( p ∧ q) ∨ (p ∧ r)"},
{"(A ⋃ B)' = A' ⋂ B'","¬(p ∨ q)↔ ¬p ∧ ¬q"},
{"(A ⋂ B)' = A' ⋃ B'","¬(p ∧ q)↔ ¬p ∨ ¬q"},
{"A ⋃ A = A","p ∨ q ↔ p"}
};
makeTextTable[data]

The important rules (A ⋃ B)’ = A’ ⋂ B’ and (A ⋂ B)’ = A’ ⋃ B’ are known as DeMorgan’s Laws.

3.2.2.b. De Morgan’s law

Example using DeMorgan’s Law: Let A = {a,d,e,g} and B = {c,d,f,g} in the universe U = {a,b,c,d,e,f,g,h,i } To verify that  (A ⋃ B)’ = A’ ⋂ B’  find each of these two sets independently to find that they are indeed the same.

First:  (A ⋃ B)’ ={a,c,d,e,f,g}’ = {b,h,i}

Second:  A’ ⋂ B’ ={b,c,f,h,i} ⋂ {a,b,e,h,i} = {b,h,i}

As predicted, {b,h,i} = {b,h,i} !

These rules also extend to arbitrary unions and intersections as ( (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ]) ())' = (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ])' and  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' =  (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])'

3.2.2.c. Set equality

DeMorgan’s Law:    ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' =  (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' .

If we are given specific sets (Subscript[A, γ]) then we could probably calculate the two sets equated in DeMorgan’s Law and see that they are in fact equal. To prove this law in general we can use a technique often used to prove the equality of two sets. The idea is simply this: to prove that A=B we could show that A ⊂ B and  B ⊂ A. This works very nicely on DeMorgan’s Law as follows.

First, assume x ∈ ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' . This says x ∉  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) )  so there exists a γ with   x ∉ (Subscript[A, γ]) . Thus  x ∈ (Subscript[A, γ])' (for this particular ) and we have x ∈ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' . This short argument establishes the fact that  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' ⊂ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' by showing that an arbitrary element of the first set must be an element of the second.

Second, assume that x ∈ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' . This says that there exists a γ with  x ∈ (Subscript[A, γ])'. Thus  x ∉ (Subscript[A, γ]) (for this particular γ ) and we have  x ∉  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) )   so  x ∈ ((Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ])())' . This establishes the fact that  ( (Underscript[ ⋂, γ∈Γ]) (Subscript[A, γ]) ())' ⊃ (Underscript[ ⋃, γ∈Γ]) (Subscript[A, γ])' .

Putting these two results together verifies DeMorgan’s Law. Note that the second argument is essentially the first argument in reverse. This is quite often the case when showing two sets are equal by this method and you can see that most of the work is done when the first argument is complete. That’s what makes this approach nice to use in many situations.

In manipulating expressions involving set operations it is often convenient to distribute one set operation over another.Specifically we have   A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C) and  A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C)

3.2.2.d. Set equality by Venn Diagram

http://www.math.csusb.edu/notes/sets/setsex2/setsex2.html

Here is a demonstration of  A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C) using Venn diagrams.

In the left image we form ( B ⋃ C ) and then intersect that with A to form the purple region which is  A ⋂ (B ⋃ C) .

In the right image we alternately display the sets  (A ⋂ B) and (A ⋂ C). Their union is then displaye d as the purple region (A ⋂ B) ⋃ (A ⋂ C) .

3.3. Venn Diagrams

Row[{Import["C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/venn.png"],
Import["C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/venn1.png"],
Import["C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/venn2.png"],
Import["C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/venn3.png"]}]

http://www.math.csusb.edu/notes/sets/node5.html#SECTION00030000000000000000

To visualize relationships between 2, 3 or 4 sets we quite often use pictures called Venn diagrams. The standard way to draw these diagrams for 1, 2 and 3 sets is illustrated here. The enclosing rectangle represents the universe.

Observe that the Venn diagram with n sets partitions the universe into (2^n) pieces. Here is a picture of the 4 set Venn diagram.

3.3.a. Regions in a Venn diagram

Fig. 3.3.a.1.

Import["C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/plot.png"]

Why does a Venn diagram with n sets divide the universe into (2^n) regions? The number (2^n) comes from the fact that each region can be written as an intersection of n sets. Consider this Venn diagram with n = 3. There are (2^3)=8 regions as predicted. Each region consists of those points in some of the subsets and not in others. 

For example, region 3 contains points in A and in B but not in C. That’s the set A ⋂ B ⋂ C’ . Region 8 is A’ ⋂ B’ ⋂ C since it contains points not in A, not in B and in C. So any triple intersection involving A or A’ , B or B’ and C or C’ corresponds to one of the regions. How many such triple intersections are there? We have 2 choices for the first set (A or A’), 2 choices for the second and 2 for the third. That makes a total of  2 · 2 · 2 = (2^3) triple intersections. Here is the list of all 8.

Table 3.3.a.2.

data={{"Region","Triple intersections"},
{"1","A' ⋂ B' ⋂ C'"},
{"2","A ⋂ B' ⋂ C'"},
{"3","A ⋂ B ⋂ C'"},
{"4","A' ⋂ B ⋂ C'"},
{"5","A ⋂ B ⋂ C"},
{"6","A ⋂ B' ⋂ C"},
{"7","A' ⋂ B ⋂ C"},
{"8","A' ⋂ B' ⋂ C"}
};
makeTextTable[data]

There is nothing special about using 3 sets. The same reasoning applies to n sets. If we have n sets (Subscript[A, 1]),(Subscript[A, 2]),..., (Subscript[A, n]) and form intersections of n sets by picking  (Subscript[A, 1]) or  (Subscript[A, 1])',(Subscript[A, 2]) or (Subscript[A, 2])' and so on up to (Subscript[A, n]) or (Subscript[A, n])' we will (2^n) such intersections.

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. Use these links to get to the relevant set of notes: logic, sets, methods of proof, functions.

logic

Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","logic"}]

sets

Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","set"}]

methods of proofs

Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","methods"}]

functions

(*Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","functions"}]*)

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 methods of the previous section apply here: Set equality.

Hyperlink[{"C:/mathematica/z_Projects/BostonUniversity/1. MET CS 248/MET CS 248.nb","Set equality"}]

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).

4.6.a Proof by picture

http://www.math.csusb.edu/notes/proofs/bpf/sum/sum.html

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) istrue"},
{"= (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.