Chapter - 3, Proofs

Section - 3.7 - More Examples of Proofs


Summary

It contains few more examples to outline proofs which may contain multiple strategies.


Soln1

Existence:

Suppose .

Proof for: :

Suppose . Suppose , then . Since is arbitrary, we can say . Since , it follows that . Thus we have, if , then . Since is arbitrary, it follows that .

Proof for: :

Suppose is arbitrary. Suppose . Suppose , or . Then there must exist some set, say such that . Since , it follows that . Thus . Thus we have . Since is arbitrary, we can conclude .

Uniqueness:

Suppose is a set such that and are true. Now since this is true for all possible values of and we know that if then is true. Thus if , it follows that , or . Now suppose . Then there exists some set, say such that . But since , it follows that , or . Thus . Since is arbitrary, it follows that . Thus we have . It follows that .


Soln2

Existence:

Suppose . Thus we have:

We know that every power set contains a set with empty element, or . Thus one possible value of and it clearly satisfies the above statement.

Uniqueness:

Suppose if , then,

is equivalent to:

This can be true only in following cases:

  • :
    Clearly this is not possible.

  • : Clearly this is also not possible.

Thus it contradicts the assumption that such set exists.

Thus there is only one such set .


Soln3

We shall prove this as follows :

  1. if (a) then (b).
  2. if (b) then (c).
  3. if (c) then (a).

where (a), (b) and (c) are the parts given in the problem.

- if (a) then (b).

Suppose (a), is true. Thus is true.

We will prove this part : by contradiction. Suppose . Suppose . Since , it follows that . Similarly, since , it follows . Thus . But this contradicts with the assumption . Thus we have if , then . Since is arbitrary, we can conclude .

Now we will prove part : by contradiction. Suppose . Suppose . It follows that , which is equivalent to . Since , it follows that . Similarly, since , it follows that . Thus , which contradicts our assumption. Thus if , then . Since is arbitrary, we can say that .

- if (b) then (c).

Suppose (b) is true. Thus is true. Suppose , then we have following possible cases:

  • Case 1: , , : This case is not possible because we know that if , then .

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

  • Case 3: , , : Thus . It follows that .

  • Case 4: , , : This case is not possible because we know that if , then .

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

- if (c) then (a).

Suppose (c) is true. Thus is true. Suppose . It follows that . Thus we have following cases:

  • Case 1: , : In this case . It follows that .

  • Case 2: , : This case is not possible as is not possible.

  • Case 3: , : This case is also not possible as is not possible.

  • Case 4: , : Since , it follows that .

Thus from all the cases we have, . Since is arbitrary, we can conclude that .


Soln4

Suppose . Thus if , then . Since , it follows that . Thus exists in at-least one of the sets, say in . Thus we have . Now suppose , then . And since , we can conclude that . Since is arbitrary, we can conclude that .


Soln5

(a)

Suppose . Thus we have:


Since ,









Since is arbitrary, we can conclude .

(b)

Suppose . Thus we have:


Since ,













Since is arbitrary, we can conclude .

(c)

Suppose . Thus exist in atleast one of the sets, say , such that . Thus exist in all the sets of . Thus for any set, say , we have . Thus if , then because . Since can be any set such that , it follows that exists in all the sets such that . Thus also exists in . Since is arbitrary, we can conclude that .

Counterexample for: :

Suppose

Suppose , , .

Thus
And .

Thus .

(d)

We shall prove the theorem .

Suppose . Thus must exist in atleast one of the set, , such that . Since , and , it follows that must exist in . Thus we can conclude that if , then .

Suppose

Suppose , , .

Thus
And .

Thus .


Soln6

Suppose is arbitrary. Suppose . Suppose is an arbitrary real number and . Then we have: , is equivalent to:



Since , thus

Since :


Thus,


Soln7

Suppose that . Thus for all , there exists a such that for all , if , then

.
Since , if , then:
.
.
.

Thus .


Soln8

Suppose that . Thus for all , there exists a such that for all , if , then

.
.
.

Since , .

Thus, if , then , where .

Thus .


Soln9

The proof and theorem both are correct. Following strategies are used:

  1. To prove a goal of the form of . Here existential instantiation is used.
  2. To prove a goal of the form of , all possible cases are considered.