Chapter - 3, Proofs

Section - 3.4 - Proofs Involving Conjunctions and Biconditionals


Summary

  • To prove a goal of the form :
    Prove and separately.
  • To use a given of the form :
    Treat this given as two separate givens: , and .
  • To prove a goal of the form :
    Prove and separately.
  • To use a given of the form :
    Treat this as two separate givens: , and .
  • Sometimes in a proof of a goal of the form the steps in the proof of are the same as the steps used to prove , but in reverse order. These two directions can be summed up by proving equivalences(biconditional) in the steps involved. For eg: If such proof involves R, then it can be summed up as: P ↔ R ↔ Q.
  • To prove equivalences of sets, say , most of the proofs involve either of the following approaches:
    • .
    • .

Soln1

() Suppose is arbitrary. Since , it follows that . Now since , and is arbitrary, it follows that . Similarly since , and is arbitrary, it follows that . Thus we can conclude that .

) Suppose is arbitrary. Since , it follows that . Similarly, since , it follows that . Thus we have . Now as is arbitrary, we can conclude that .


Soln2

Suppose . Since , it follows that . Also since , it follows that . Now since and , it follows that . As is arbitrary, we can conclude that .


Soln3

Suppose . Thus we have . Since and , it follows that . Thus we have . Thus we can say . As is arbitrary, we can conclude that .


Soln4

Given that and . Since , suppose is an arbitrary variable such that . Since , it follows that . Thus . As is arbitrary, we can conclude that .


Soln5

Given that . Suppose . Then . Thus there exists an element such that , so we can conclude that .


Soln6

Suppose . Thus we have:





Since is arbitrary, we can say that .


Soln7

()Suppose . Then we have . Suppose , then . Or we can say that and . Since is arbitrary, .
Since , then . Similarly, since , then
Thus we can conclude that .

()Suppose . Since , it follows that . Similarly it can be seen that . Now suppose . Then we have and . Or we can say . As is arbitrary, we can say that . Thus we can conclude .


Soln8

()Suppose , then . Since , it follows that . Now since , then . Thus if then . We can conclude that .

( )Suppose . Suppose is a set in such that . Since , it follows that . Thus . Now since , it follows that . Thus we can conclude . As is arbitrary, thus we have .


Soln9

Suppose and where are integers. Then . Suppose , then is an integer. Thus , is odd.


Soln10

()Suppose is even. Then , where . Thus . Suppose , then . Since , it follows that is even.

( )As an integer can either be even or odd but not both, we shall prove this by contrapositive. Thus we shall prove that If is not even(odd) then is also not even(odd). Suppose is odd, then . Thus . Suppose , then . Thus is odd. Thus we can conclude that if is even then is also even.


Soln11

(a)

The problem with the proof is with the usage of variable in and . Value of may not be same.

(b)

For and , then while . Thus .


Soln12

() Suppose is arbitrary. Suppose , then



Thus the equation: is correct for . Now since , it follows that .

( ). We shall prove contra-positive. Suppose . Now and . Since , it follows that is not correct. Thus if , then .


Soln13

()Suppose . Suppose . Suppose , then . Now is defined only if . Thus there exists a such that . Now since is arbitrary, it follows that .

( ). Suppose . Suppose and . Since , we can assume . Then is correct(can be verified by putting the value of ). Thus there exists a for which and is correct. We can conclude .


Soln14

Suppose . Thus there exists a set, say , in such that . Since , it follows that . Since , then . Thus we have . Since , it follows that . Since is arbitrary, we can conclude .


Soln15

Suppose and are not disjoint. Then there must be an element, say , such that and . Since , then there must exist a set, say , in such that . Also since , it follows that must exist in all the sets of . Thus there exist a set such that it is not disjoint with any of the sets of . But this contradicts the given that there is no such set. Thus we can conclude that and are disjoint.


Soln16

()Suppose . Then exists in atleast one of the subsets of . Thus must exists in all subsets of . It follows that . Since is arbitrary, we can conclude that .

( ). Suppose . Thus exists in atleast one of the subsets of . It follows that . Since is arbitrary, we can conclude that .

Thus we can say that .


Soln17

(a)

Suppose that . Thus there exist a set, say , such that and and . Since , it follows that . Similarly since , it follows that . Thus . It follows that . Since is arbitrary, we can conclude that .

(b)

The issue is that set may not be same in and .

(c)

where and

where , and

.

.


Soln18

()Suppose . Suppose . Thus there exist some set, say such that . Similarly there exist some set, say , such that . Thus . As and , then . It follows that if , then . Since is arbitrary, . Thus we can conclude that: .

() Suppose . Suppose that where and . Since and , it follows that . Similarly, since and , it follows that . Thus . Since , it follows that . Since is arbitrary, it follows that . Thus we can conclude that .


Soln19

()Suppose and are not disjoint. Then there must exist an element, say , such that and . Since , it follows that . Similarly since , it follows that . Thus . But it is a contradiction to the given that . Thus .

()Suppose and are not disjoint. Then there must exist an element, say , such that and . Thus there must exist a set, say in such that . Similarly there must exist a set, say , in such that . Thus . This contradicts to the given that . Thus and .


Soln20

(a)

Suppose . Thus is in and is not in . Since , there must exist a set, say , in such that . Also since not in , there is no set, say , in , such that . It follows that can exist in only those sets in which are not present in . Or we can say that exists in atleast one of the sets in . It follows that . Since is arbitrary, we can conclude that .

(b)

Statement and , then is wrong. It is possible that belongs to some other set() of .

(c)

Lets first prove direction :

.

Suppose . Suppose . Thus there exist a set, say , such that and , and . As , there may exist some other set, say , such that , and . Thus if such set exists, then , because exists in both and . But since it follows that . Thus there is no such set . It follows that does not exist in any of the sets of . Or we can say that . Since , it follows that . Thus it follows that , or we can say that .

Now proof for direction :

.

Here we shall prove by contra-positive. Suppose that . Suppose that , where and . Thus there exist a set() in such that belongs to that set. It follows that . Also, since and , it follows that . Since , it follows that . Thus .Thus by contrapositive we can conclude that if , then .

(d)

, where and .

, where and .

.

.


Soln21

Suppose . Suppose , then . Since , it follows that there exist a set, say , in such that . Also since , it follows that does not belong to any of the sets of . Thus .


Soln22

(a)

  • Strategy to prove a goal of the form .
  • Strategy to prove .
  • Strategy to prove .
  • Strategy for .

(b)

Suppose
It is equivalent to:


(Note that )


Since is arbitrary, it follows that .

(c)

Suppose
It is equivalent to:




Since is arbitrary, it follows that .


Soln23

(a)

Suppose . Thus there must exist a set, say , in such that . Thus . Now suppose exist in some set where . Now if also contain then , which is clearly not possible as then can not exist in . Else if does not contain , then clearly can not exist in . Thus does not exist in any set . It follows that . Thus we can conclude that , or . Since is arbitrary, we can conclude that .

(b)

,
,



Soln24

(a)

Suppose . Then there must exist atleast an , such that . Since , it follows that . Similarly, since , it follows that . Thus we have , or . Since is arbitrary, it follows that .

(b)

,
,



Soln25

Suppose , then both and are true.


Soln26

(a)

()Suppose . Then where . It follows that , thus . Similarly, , thus .

()Suppose and . Thus and , where . Thus . Since are natural numbers and and does not divide, it follows that and . Or we can say that and , where . Thus we have as well as . Thus and . Thus we can conclude .

(b)

Suppose , then as well as are true, but is not true.