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 Ex-1 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 Ex-1(b).

Suppose and . Suppose .

Note that is different from in Ex-1 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 Ex-7, that and . Thus we can conclude that .

However . Example:

Suppose . Thus . Thus . But . Thus .

(b)

.

Since and , it follows from Ex-7, 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 one-to-one. 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 one-to-one, 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 one-to-one, we can say that is a one-to-one 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 one-to-one function such that for some natural number , , and . Thus from Ex-10 part(a), it follows that . Thus . Since is one-to-one, it follows , or . Thus . Thus we can conclude .


Soln12

(a)

Suppose and . It follows that . Thus from Ex-11 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 one-to-one function such that and , and . Thus from Ex-10 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 Ex-9 (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 one-to-one 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 one-to-one, 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 Ex-12 part(a), it follows that . Thus where . It follows that .

  • Case

    Using the result of Ex-12(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 .