Chapter  6, Mathematical Induction
Section  6.5  Closures Again
Summary
 Suppose is a relation on set . (n times).
 Suppose is a relation on set . Then .
 Transitive closure of relation on set is .
Soln1
(a)
We need to prove the following:
 .
 is closed under . Or .
 .
 is the closure of under .
Now we will prove them one by one:

Proof for: .
Since , it follows that . Thus is closed under . Also since , it follows that . Thus .

Proof for: is closed under .
Suppose . Suppose is an arbitrary set in . Since , it follows that . Since is closed under and , it follows that . Since was arbitrary element of , it follows that . It follows that . Since is arbitrary, it follows that .

Proof for: .
Suppose . Suppose is an arbitrary set in . Since , it follows . Since , it follows . Since is arbitrary, thus .
Suppose . Suppose is an arbitrary set in . Since , it follows . Since is an arbitrary set, it follows . It follows that . Since is arbitrary, it follows that .

Proof for: is the closure of under .
Thus we need to prove that the smallest set closed under such that .
Suppose is a set such that and is closed under . Thus . It follows that . Since is closed under and and , it follows that is the smallest set closed under such that .
(b)
Suppose
We need to prove the following:
 .
 is closed under .
 is the smallest set closed under such that .
Now we shall prove each as follows:

:
It directly follows that . Also since and , if follows that . Thus .

is closed under :
Suppose . Thus for some , . It follows that . But . Thus . Since was arbitrary, it follows that . Thus is closed under .

is the smallest set closed under such that :
Suppose there is a set closed under such that . Thus we need to prove that . Thus we need to prove that . We shall prove this using induction:
Base Case:
For . Thus by assumption for our set , .
Induction Step:
Suppose for , .
Suppose . Thus by the definition of , it follows that there exists some such that . But by our hypothesis, , thus . Since is a closed set and , it follows that , or . Since is arbitrary, it follows that .
Thus , or . Thus .
Soln2
Closure of set under is : .
Soln3
This can be proved in a similar way like in Ex1 part(a).
Suppose .
We shall now prove that and is closure of on . We will prove this by proving the following:
 .
 .
 .
 is the smallest set such that and .
Lets prove each of them:

.
We know that . Also . Thus . It follows that .

.
Suppose . Suppose . Suppose is an arbitrary element of . Since , it follows that . Since , it follows that . Since was arbitrary, it follows that . Thus . Since was arbitrary, it follows that is closed on . Since is arbitrary, it follows that .

.
Suppose . Suppose is an arbitrary element of . Since , it follows that . Since , it follows . Since is arbitrary, it follows that .
Suppose . Suppose is an arbitrary element of . Since , it follows that . Since was arbitrary, it follows that . Thus . Since is arbitrary, it follows .

is the smallest set such that and .
Suppose is a set such that and . Thus . It follows that . Thus is the smallest set such that and .
Soln4
We shall follow the proof from Ex1(b).
Suppose and . Suppose .
Note that is different from in Ex1 part(b).
Now we shall prove that is the closure of on .
We need to prove the following:
 .
 is closed under .
 is the smallest set closed under such that .
Now we shall prove each as follows:

:
It directly follows that . Also since and , if follows that . Thus .

is closed under :
Suppose . Suppose . Thus for some , . Similarly for some , . Now consider following cases:

Case
Then by definition of , it follows that . Thus .

Case
Then by definition of , it follows that . Thus .
Thus in all possible cases. Since and are arbitrary, it follows that . Thus is closed on .


is the smallest set closed under such that :
Suppose there is a set closed under such that . Thus we need to prove that . Thus we need to prove that . We shall prove this using strong induction:
Suppose is an arbitrary natural number. Suppose (induction hypothesis). Consider the following cases:

Case
For . Thus by assumption for our set , . 
Case
Suppose . Since , it follows that where and such that . Since and , then by our induction hypothesis and . It follows that as well as . Since is closed under , it follows that . Thus . Since was arbitrary, it follows that .
Thus , or . Thus .

Soln5
Using Soln4, we have:
.
.
As we can see, will consists of all possible products of prime numbers. Since every natural number greater than 1 can be expressed as a product of primes, it follows that contains all natural numbers other than one. Thus .
Soln6
(a)
Suppose is defined as follows:
For , .
For ,
Suppose . Now we will prove that is closure of under . We shall prove this by proving the following:
 .
 .
 is the smallest set closed under such that .
Lets prove each of the above:

.
Clearly . Since , it follows that .
Since , We can clearly see that . Since , it follows that .

.
Or we may also say that we need to prove .
Suppose . Suppose . Since , it follows that for some and such that and . Consider the following cases:

Case
Then by definition of , it follows that . Since , it follows that .

Case
Then by definition of , it follows that . Since , it follows that .
Thus from both cases . Since and are arbitrary, it follows that .


is the smallest set closed under such that .
Suppose there is a set closed under such that . Thus we need to prove that . Thus we need to prove that . We shall prove this using strong induction:
Suppose is an arbitrary natural number. Suppose (induction hypothesis). Consider the following cases:

Case
For . Thus by assumption for our set , . 
Case
Suppose . Since , it follows that for some function , where and such that . Since and , then by our induction hypothesis and , it follows that as well as . Since is closed under , it follows that . Since is arbitrary, it follows that .
Thus , or . Thus .

(b)
We know from part(a), that closure of on is , where is defined as:
For , .
For ,
We are given that set . Also, it is given .
We need to prove: . Thus we shall prove:
 .
 .
Now we shall prove both statements:

.
Suppose . Thus for some and , . Since , it follows that . Also since , we can also say that .
Since , then by the definition of it follows that . Thus . Similarly since and , it follows that . Thus . Since , it follows that . Thus . Since was arbitrary, it follows that . 
.
Thus we need to prove that . We can prove this by proving that . We shall prove this using strong induction. Suppose is a natural number. Suppose our induction hypothesis is .
We have following possible cases:

Case .
Thus . Suppose . Thus . Thus . It follows that . Also , it follows that . Thus . Or .

Case .
Suppose . Since and by the definition of , there exist and such that either or where and .
Since and , then it follows from induction hypothesis that and . Thus and . Since , it follows that where . Similarly where .Consider the following possible cases:

Thus . Thus . 
Thus
.
Thus .
Thus in both cases .
Since is arbitrary, it follows that .

Thus in both cases .
It follows that .

Since and , it follows that .
(c)
Required set will be .
Soln7
We will prove this by ordinary induction.
Base Case:
For , R^1 = R S^1 = S R \subseteq S R^1 \subseteq S^1 n = 1 R^n \subseteq S^n $$.
Induction step:
Suppose theorem is correct for . Thus for .
Now consider .
Suppose . Since , it follows that there exists an element such that and . By our hypothesis, , it follows that and . Since , it follows that . Since is arbitrary, it follows that .
Soln8
(a)
.
Since and , it follows from Ex7, that and . Thus we can conclude that .
However . Example:
Suppose . Thus . Thus . But . Thus .
(b)
.
Since and , it follows from Ex7, that and . Thus we can conclude that .
However . Example:
Suppose . Thus . Thus . But . Thus .
Soln9
(a)
Suppose , and and suppose .
Thus and . Thus . Thus .
Since . it follows that .
Suppose . Since and is the smallest positive integer such that , it follows that . But this contradicts with our assumption that . Thus .
(b)
We are given that .
Also we can directly see . Thus we need to prove:
We need to prove: .
We will prove this using ordinary induction.

Base Case
Suppose . Suppose , thus . Thus , or we can also say . Since , it follows that there must exist an element such that and .
Since , it follows .
Clearly by the definition of , we can say that .
We will prove by contradiction that . Suppose . Thus . Since and , it follows that . Since , it follows that . But this contradicts with the assumption that . It follows that . Thus and . 
Induction Step:
Suppose theorem is true for . Thus if , it follows that .
Now consider for .
Suppose . Since , it follows . Thus by induction hypothesis there exists an element such that and . Suppose .
Clearly and and .
Since , it follows that . Thus . Since , it follows that there exists an element such that and .
Since , it follows .Also by the definition of , we can say that . We will prove by contradiction that . Suppose . Since and , it follows . Since , it follows , or . Thus we have a contradiction. It follows that .
Since and , it follows that . Thus . We shall prove by contradiction that . Suppose . Thus . Since and , it follows that . Since , it follows , or . Thus we have a contradiction. It follows that .
Thus we have an element such that and .
Soln10
(a)
Suppose .
Thus we need to prove . We can prove this by proving and .
We shall prove this by induction.

Base Case:
For , we need to prove and .
() Suppose . Thus . Suppose that . It follows that . Thus , and . Thus there is an path from to of length . Thus . Since is arbitrary, it follows that .
() Suppose . Thus , and . Thus , or . Since is arbitrary, it follows that .

Induction Step:
Suppose for , .
Now lets consider of .
() Suppose . Thus there exist an element such that and . Since , then by induction hypothesis, . Thus there is an path from to of length . It follows that , and . Suppose . Since and , it follows that . Thus . Thus . Thus .
() Suppose . It follows that , and . Suppose . Since , it follows that .
Since , we can also say . Since and , it follows that . Thus by induction hypothesis, it follows .
Since and , it follows that . Thus .
(b)
We know from theorem 6.5.2, .
Suppose .
Thus we need to prove .
Suppose .
Clearly .
Suppose is arbitrary positive integer. Thus from part(a) . Since was arbitrary, it follows that . Thus .
Soln11
(a)
Suppose .
We will prove this by induction.

Base Case:
For .
Suppose . Thus and . It follows that . Suppose . Thus , and and . Since , it follows . Thus is onetoone. Thus . It follows that , or .

Induction Step:
Suppose theorem is correct for . Thus .
Now consider for .
Suppose . Thus . Also it follows that there exist some element such that and and and $$ b \ne c $.
Note: It can be easily proved by contradiction that and . I skipped it.
Thus and . Thus by induction hypothesis, it follows . Thus there is a function such that for some , and and .
We have following possible cases:
 Case :
Suppose . Suppose is a function such that . Since is onetoone, it follows that is path from to of length less than equal . Thus .
 Case :
We have and where . Suppose is a function such that and . Thus and . Since , it follows that . Since is onetoone, we can say that is a onetoone function from to of length . Since , it follows that . It follows that .
Thus from both cases . Thus if .
Thus .
(b)
We know from theorem 6.5.2, .
Suppose .
We need to prove .
() Suppose . Thus for some natural number , such that . Thus it follows from part(a) of this solution that . Thus .
() Suppose . Thus there exist a onetoone function such that for some natural number , , and . Thus from Ex10 part(a), it follows that . Thus . Since is onetoone, it follows , or . Thus . Thus we can conclude .
Soln12
(a)
Suppose and . It follows that . Thus from Ex11 part(a), it follows that there exist a simple path of length at most .
We will prove by contradiction that length of path is . Suppose length of path is such that . It follows that there is a onetoone function such that and , and . Thus from Ex10 part(a), it follows that . Since , it follows that . But it contradicts with assumption that . Thus .
Thus there is a simple path from to of length .
(b)
Suppose . We have following possible cases:

Case .
Thus . Suppose . Thus . Also the statementt is vacuously true.

Case .
Thus . Suppose . Since , it follows from Ex9 (b), there exist an element such that and . Thus . It follows that .
Now we shall prove that by contradiction. Suppose . Since , it follows . But . Thus we have a contradiction. It follows that . Thus we have and . Thus by part(a) of this solution it follows that there is a simple path from to of length . Thus there is a onetoone function such that .
Suppose . Since , it follows Since is simple path, it follows that and .Thus is a simple path except .
Soln13
Suppose is a simple path from to of length , where .
Clearly length of path is and contains elements.(using the same definition as defined in book).
Since contains elements and is onetoone, it follows that can contain at max elements.
It follows that maximum length of is .
Suppose . Suppose that . Consider the following cases:

Case
Since maximum length of a simple path is , then from Ex12 part(a), it follows that . Thus where . It follows that .

Case
Using the result of Ex12(b), it follows maximum length of such path is . Thus where . It follows that .
Thus combining both cases, it follows that .
It follows that .
Also since , it follows that .
Thus .
Soln14
Earlier I tried this using induction on and not able to do it. Later it seems like it was wrong to apply induction on as value of is dependent on .
We have to prove , where .
We shall use induction on .

Base Case:
For . Thus the only possible value of . Thus . And . Thus .

Induction Step:
Suppose for , . Thus for some integer , .
Now consider for ,
Thus for :
Value of will be . Thus . And .Consider the following cases:

Case :
Thus . Thus divides .

Case :
Since , thus by induction hypothesis, it follows that . Thus .
Thus . Thus . Thus .
Thus in both cases .
