Chapter - 3, Proofs

Section - 3.5 - Disjunctions


Summary

  • To use a given of the form :
    • Break proof into cases. For case 1, assume that is true and use this assumption to prove the goal. For case 2, assume is true and give another proof of the goal.
    • Another strategy can be: If it is also given , or it can also be proved that is false, then use this given to conclude that Q is true. Similarly, if it is given or it can be proved that is false, then it can be used to conclude that is true.
  • To prove a goal of the form :
    • Break the proof into cases. In each case, either prove P or prove Q.
    • Another strategy can be: If is true, then clearly the goal is true, so only need to worry about the case in which is false. Thus for the case is false, complete the proof by proving that is true. Point to note here is this strategy is same as proving the goal . Similarly it can be used instead of .

Soln1

Suppose . Thus and . Thus we have two cases:

Case 1: Suppose . Since , it follows that . Thus .

Case 2: Suppose . Thus .

Thus in all the cases, . Since is arbitrary, .


Soln2

Suppose . Thus either or . Thus we have two cases:

Case 1: Suppose . Thus . Since , it follows that .

Case 2: Suppose . Clearly it follows that .

Thus in all the possible cases, . Since is arbitrary, we can conclude that .


Soln3

Suppose . Thus we have:

.
.
.
.
.

Since is arbitrary, we can conclude that .


Soln4

Suppose A ∩ C ⊆ B ∩ C and A ∪ C ⊆ B ∪ C. Prove that A ⊆ B.

Suppose . Then . Since , it follows that . Thus either or, . So we have following cases:

Case 1: Suppose , then it follows .

Case 2: Suppose . Thus . Since , it follows that .

Thus from all the cases, if , then . Since is arbitrary, it follows that .


Soln5

We shall prove this using contra-positive. Suppose . Since , it follows that . Thus as well as . Since , then clearly . Thus we are left with . This can be simplified into which is equivalent to . Since , and , it follows that . Thus we have if then . By contra-positive, we can say if then . Since is arbitrary, we can conclude that .


Soln6

()Suppose . Suppose . Thus . Since , it follows that . And since , it follows that . Thus we have . Since is arbitrary, we can conclude that .

()Suppose . Suppose . Thus we have two cases:

Case 1: Suppose . Then clearly .

Case 2: Suppose . Then since , we have . Thus . Since , it follows that, . Since , it follows that . Thus we can say that .

Thus from all the possible cases, if then . Since is arbitrary, we can conclude that .


Soln7

Suppose . Thus we have two possible cases:

Case 1: Suppose . Then . Suppose , then . Since , then . Since is arbitrary, it follows that . Thus we have .

Case 2: Suppose . Then . Suppose , then . Since , then . Since is arbitrary, it follows that . Thus we have .

Thus from all cases, if , then . Since is arbitrary, it follows that .


Soln8

Suppose . Then . Since , it follows that . Thus we have following cases:

Case 1: Suppose . Then . It follows that .

Case 2: Suppose . Then . It follows that .

Thus we have either or .


Soln9

Suppose . It is equivalent to:






Soln10

Suppose . Then we have two cases:

Case 1: Suppose . Then . It follows that . Multiplying both sides by , we get .

Case 2: Suppose . Then . It follows that . Since , and . Thus .


Soln11

()Suppose . Then we have two cases:

Case 1: Suppose , then .
.
.
Since , it follows that \vert x - 4 \vert > 2 $$.

Case 2: Suppose , then




Since , it follows that \vert x - 4 \vert > 2.

()Suppose . Then we have two cases:

Case 1: Suppose , then .
.
.
.
Since , so .
Thus .

Case 2: Suppose , then .
.
.
.
.
.
.
Since , it follows that .
And since , it follows that , Or .


Soln12

(a)

()Suppose . Then we have two cases:

Case 1: Suppose , then .

Case 2: Suppose , then . Or .

Thus from both cases, .

()Suppose . Then we have following possible cases:

Case 1: Suppose , then . Since , it follows that .

Case 2: Suppose , then . Since , or , it follows that .

Thus form both cases, we have .

(b)

First lets prove , because:

  • if then , thus is true.
  • if then , thus is true, it follows is true.

Thus we have .

We know that(from (a)), . Suppose and . Since , it follows that, .

(c)

We have following all possible cases:

  • Case 1: .

As , .

Also since , .
Similarly since , .
Thus .

From above we can conclude .

  • Case 2: .

As , .

Also since , .
Similarly since , .
Thus .

We can conclude .

  • Case 3: : Here we have following further cases:

    • Case a: :
      LHS:
      Since , .
      As , it follows that .
      Thus we have .
      RHS:
      Since , .
      Also, since , .
      Thus . Since , it follows .
      Thus we have
      So,
      we can conclude that .

    • Case b: : LHS:
      Since , .
      As , it follows that or .
      Thus we have .
      RHS:
      Since , .
      Also, since , .
      Thus . Since , it follows .
      Thus we have
      So,
      we can conclude that .

  • Case 4: :
    This case is similar to Case 3. By swapping and , proof will be same as in Case 3.

Thus from all the cases above: .


Soln13

Suppose is an integer. Thus can either be even or odd. We have following cases:

  • Case 1: is even. Then , where is any integer. Thus . Since is integer, it follows that is also an integer. Thus is an even integer. Thus we can conclude if is even, then is also an even integer.

  • Case 2: is odd. Then , where is any integer. Thus . Since is integer, it follows that is also an integer. Thus is an even integer. Thus we can conclude if is odd, then is also an even integer.

Thus from both cases, is even integer.


Soln14

Suppose is an integer. We have following possible cases:

Case 1: is even, or where is even. . Thus is a multiple of and remainder is zero.

Case 2: is odd, or where is odd. . Thus is not a multiple of and clearly remainder is one.

From both cases above, we can conclude that when divided by , remainder will either be zero or one.


Soln15

(a)

Suppose is arbitrary element and .

.
.
.
.
.
.
.

Since is arbitrary, it follows that .

(b)

Suppose .










Thus we can conclude, .


Soln16

(a)

()Suppose . Suppose . Now we have two cases:

  • Case 1: . Since , It follows that exist in atleast one of the sets of . Or we can also say that exists in atleast one of the sets of . Thus it follows that , or .

  • Case 2: . It follows that exists in atleast one of the sets of . Or we can also say that exists in atleast one of the sets of . Thus it follows that , or .

From both cases above, since is arbitrary, we can conclude: .

()Suppose . It follows that exists in atleast one of the sets, say , of . Thus we have two cases:

  • Case 1: . Since and contains only one set , it follows . Thus .

  • Case 2: . Thus there exists atleast one set in such that . Thus we can say that .

Thus from above cases, we have . Since is arbitrary we can say that: .

Thus we can conclude that .

(b)

B ∪ (∩F) = ∩A∈F (B ∪ A)

()Suppose . Thus we have following possible cases:

  • Case 1: . Suppose . Since , it follows that . Also since is arbitrary, it follows that . Or .

  • Case 2: . Thus must exist in all the sets of . Thus we can also say that . Since , it follows that is also true. Thus we can say that .

Thus from both cases, .

()Suppose . Thus must exist in all sets: such that . It follows following two cases:

Case 1: . Then it follows that .

Case 2: . Since is arbitrary, it means exists in all the sets of . Or . It follows that .

Thus from both cases, .

Thus from both directions, we can conclude .

(c)

Suppose . It appears that belongs to all the sets of as well as belongs to . Thus it seems to be equivalent to . Lets try to prove it:

() Suppose . Thus must exist in . Suppose . Since must exist in all the sets of , it follows that . Thus we can also say that , or . Since is arbitrary, . It follows that .

(). Suppose . Since , must exist in . Also, since ,
must exist in all the sets, , of . Thus . Or .

Thus from both directions we have .


Soln17

Suppose . Suppose and suppose , then . Thus it follows that . So we have two cases:

Case 1: . Since is arbitrary, it follows that . Or .

Case 2: . Since is arbitrary, it follows that . Or .

Thus from both cases if , then .


Soln18

Suppose . Thus we have:




Now since is arbitrary, we can conclude that


Soln19

  • ():
    Suppose . Now we shall prove :

    • ()Suppose . Thus and . We will prove by contradiction. Suppose . Since , it follows that . Thus . Since , it contradicts the given that . Thus . Now since , it follows that .
    • ()Suppose . Thus and . We will prove by contradiction. Suppose . Since , it follows that . Thus . Since , it contradicts the given that . Thus . Now since , it follows that .

    Thus we can conclude that .

  • ():
    We will prove this by contra-positive. Suppose and lets say . Thus and . Since , we have following cases:

    • Case 1: If , then . Since , it follows . Also since , it follows that . Thus .

    • Case 2: If , then . Since , it follows . Also since , it follows that . Thus .

    Thus we can conclude from contra-positive that .

Thus from both directions, the condition is true. So we can conclude .


Soln20

  • ():
    Suppose . Now we will prove :

    • :
      Suppose . Thus we have two exhaustive cases:

      • Case 1: If , then .

      • Case 2: if . Since , it follows that . It follows that


        Since , then . Thus we can also say that .

      Thus from both cases above, we can conclude that .

    • :
      This proof is will be exactly similar to the proof above for by just swapping and .

    Thus from both directions above, we can conclude that if , then .

  • ():
    Suppose . Suppose , or . Thus we have two possible cases:

    • Case 1: if , then . Since , it follows . And since , it follows that . Since , it follows that .

    • Case 2: if , then . Since , it follows . And since , it follows that . Since , it follows that .

    Thus from both cases above, it follows that if , then . Since is arbitrary, it follows that .

    Thus from both directions above, we can conclude that .


Soln21

  • :
    Suppose .

    Proof of :

    Suppose . Since , it follows that . Thus . Thus we have two cases:

    • Case 1: if , then . Since , then .

    • Case 2: if , then . Since , then .

    Since is arbitrary, we can conclude from both the cases above that if .

    Proof of :

    Now, suppose . Suppose . Since , it follows . Thus . But it contradicts with assumption that . Thus .

  • : Suppose . Suppose . Since , we have following cases:

    • Case 1: if . Since and , it follows that . Thus , or . Since , it follows .

    • Case 2: if . Since and , it follows that . Thus , or . Since , it follows .

    Thus if , then . Since is arbitrary, we can conclude that .

Thus from both directions above, we can conclude that .


Soln22

(a)

A\C ⊆ (A\B) ∪ (B\C)

Suppose . Thus . Now we have following possible cases:

  • Case 1: . Since , it follows . Since , it follows .

  • Case 2: . Since , it follows . Since , it follows .

Thus from both cases above, .

(b)

Suppose . Thus . Thus we have two cases:

  • Case 1: . Using (a), since , then .
    Thus we have two cases:

    • Case a: , it follows that , or we can say .

    • Case b: , it follows that , or we can say .

    Thus from both cases, .

  • Case 2: . Using (a), since , then .
    Thus we have two cases:

    • Case a: , it follows that , or we can say .

    • Case b: , it follows that , or we can say .

    Thus from both cases, .

Thus from both cases above, we have if , then .


Soln 23

(a)

Suppose . Thus we have following cases:

  • Case 1: .
    Thus we have following cases:
    • Case a: . Thus , it follows that . Or we can also say that .

    • Case b: . Thus , it follows that . Or we can also say that .

  • Case 2: .
    Thus , or . Thus and . Thus and . It follows that .

Thus from both cases above, .

(b)

Lets say .

Then and .

And , and . Thus .

We can see that .


Soln24

(a)

Suppose . It is equivalent to:

Thus we have ffollowing cases:

Case 1: :
Thus and , it follows that .

Case 2: : Here , which is not possible. Thus this case is not possible.

Case 3: : Here also , which is not possible. Thus this case is not possible.

Case 4: : Here and . Or we can say . Since , it follows . Thus and . It follows that .

Thus from all the possible cases, .

(b)

Lets say .

Then .
And .


Soln25

We shall prove the conjecture .

Suppose . It follows that and .

Since , it follows:
.

Also, since , it follows that:
.

Thus we have following possible cases:

  • Case 1: and :
    This case is not possible as is not possible.

  • Case 2: and :
    Thus . Since , it follows: . Further since , it follows . Thus we can also say .

  • Case 3: and :
    Thus . Since , it follows: . Further since , it follows: . Thus we can also say .

  • Case 4: and :
    This case is also not possible as is not possible.

Thus from all the cases above, we can conclude that .

However is not correct.

One counter example is:
.
and .


Soln26

The proof is not correct as the proof actually shows . It can be corrected by changing the cases as follows:

  • Case 1. . Then . Plugging this into the assumption that , we get , so clearly x < 6. Also, since , it follows . Since , we can also say . Thus we have .

  • Case 2. . Then , so the assumption means that . Therefore , so . Also since , it follows . Or we can also say . Thus it follows that .

Thus from both the cases: . Thus we can conclude theorem is correct.


Soln27

Proof and theorem both are correct. The goal is of the form of .

Following strategies are used:

  • To prove goal of the form of , is assumed to be correct and then is proved.

  • Given is of the form of . Thus these two are taken as separate givens.

  • One of the given is of the form . Thus existential instantiation is used.


Soln28

Proof and theorem both are correct. Following strategies are used:

  • Strategy to prove a goal of the form of .
  • Strategy to prove a goal of the form of . Existential instantiation is used.
  • The goal is converted into and strategy to prove on case by case basis is used.

Soln29

Suppose . Thus we have:




Soln30

Proof and theorem both are not correct.

Counter example: . Thus niether and nor .

In the proof, both cases are wrong. For eg: In Case 1, is not true for all the elements of .


Soln31

For any statement , we can have following possible cases:

  • Case 1: P(x) is true for all values of . Or . Thus we can also say that .

  • Case 2: P(x) is false for atleast one value, say , of . Or is true. Thus we can also say .

Thus from both the cases, we can conclude that .