Chapter - 3, Proofs

Section - 3.6 - Existence and Uniqueness Proofs


Summary

  • means there exists only one value of for which is true.
  • is equivalent to all of the following:
    • .
    • .
    • .
  • To prove a goal of the form of :
    • Strategy 1: Prove and . The first of these goals shows that there exists an such that P(x) is true, and the second shows that it is unique. The two parts of the proof are therefore sometimes labeled existence and uniqueness.
    • Strategy 2: Prove , using strategies from previous sections.
  • To use a given of the form of :
    Consider it as two given statements, and . To use the first statement you should probably choose a name, say , to stand for some object such that is true. The second tells you that if you ever come across two objects and such that and are both true, you can conclude that .

Soln1

Suppose is arbitrary. Lets say . Thus we have to prove :

Existence:

Suppose . Then . Also . Thus we have . Since is arbitrary, we can say that for all values of , there exists a such that . Thus we can conclude .

Uniqueness:

Suppose , then , which give . Similarly suppose , gives . Thus . Thus we can conclude that $$.

Thus we can say . Thus we can conclude . Since is arbitrary, we can conclude that for every value of , is true.


Soln2

Update(20th-May-2018)

Earlier solution was incorrect as pointed out by William. Here is the fixed version:


Suppose . Then we have to prove .

Existence:

There are two possible cases:

  • Case 1: Suppose . Suppose . Then , and . Thus LHS = RHS, or .

  • Case 2: Suppose . Suppose . Then . Thus LHS = RHS, or .

Thus from both cases we have for any arbitrary , is true.

Uniqueness:

Suppose for a value z , then , or . Also suppose for a value , .

For , We have two possible cases:

  • Case 1: . Then we have , which says that for any value of , is true.

  • Case 2: . Then we have , or .

Thus, case-1 and case-2 together, for every value of , is true when .

Similarly, we can see that, for , when , is true.

Thus we have, for any arbitrary , .

It follows that is true.


Earlier Solution(with mistakes)

Suppose . Then we have to prove .

Existence:

There are two possible cases:

  • Case 1: Suppose . Suppose . Then , and . Thus LHS = RHS, or .

  • Case 2: Suppose . Suppose . Then . Thus LHS = RHS, or .

Thus from both cases we have for any arbitrary , is true.

Uniqueness:

Suppose for a value z , then , or . Also suppose for a value , . We have two possible cases:

  • Case 1: . Then we have , which says that for any value of , is true. Similarly, it can be shown that for is true for any value of .

  • Case 2: . Then we have , or . Similarly it can be proved that, if , then . Or we can say that .

Thus from both cases, if , then is true.


Soln3

Suppose is arbitrary. Suppose .

Existence:

Suppose . Thus . Since , we get . Also . Thus . It follows that .

Uniqueness:

Suppose for values and respectively. Since , then . Since , it can be simplified to .
Similarly, since , we can get .

Thus we have . It follows that .

Thus we can conclude that for all , .


Soln4

Existence:

Suppose , then is defined. Suppose . Suppose is arbitrary, then . Thus there exists a such that for all and for all , we have .

Uniqueness:

Suppose , such that . Multiplying each side by , we get . Thus . Thus we can say that is a unique value of for the given statement is to be correct.


Soln5

(a)

Suppose . Then there exists a set such that . Thus we can also say that . Since is arbitrary, it follows that .

(b)

()

This is already proved in first part.

()

Suppose . Thus there atleast exists one set, say , in such that . Now suppose there is one more set, say , such that and . Since , it follows that . But it contradicts with the given that all sets of are disjoint. Thus . Or we can say that only one set exists such that . It follows that . Now since is arbitrary, it follows .

Thus from both directions, we can say that .


Soln6

(a)

Existence:
Suppose . Clearly . Also . Thus there exist a set, such that for every set , .

Uniqueness:
Suppose there is another set say, . Now for , . Thus we can say that . Thus is unique set such that .

(b)

Existence:
Suppose . Clearly . Also . Thus there exist a set, such that for every set , we have .

Uniqueness:
Suppose there is another set say, . Now for , . Since , it follows . Thus it follows that . Since , it follows that , or . Thus is unique set such that .


Soln7

(a)

Existence:
Suppose is arbitrary and , or . Suppose . Clearly . Also since , it follows that . Thus there exist a set, such that for every set , and .

Uniqueness:
Suppose such that . Now for , we have . But since , . It follows that . Thus .

(b)

Existence:

Suppose . Suppose . Clearly . Also . Thus there exist a set, such that for every set , .

Uniqueness:
Suppose there is another set say, . Now for , . But , it follows that . Thus we can conclude that is unique.


Soln8

(a)

Existence:

Suppose is arbitrary and . Also suppose . Suppose . Suppose . Then:






Since ,

Since is arbitrary, we have .

Thus there exists a set such that .

Uniqueness:

Now for uniqueness proof. Lets assume such that . Suppose , it follows that . But since , , it follows that . Thus we have .

(b)

Existence:

Suppose is arbitrary and . Also suppose . Suppose . Suppose . Then:





Since is always false as we assumed :


Since is arbitrary, we have .

Uniqueness:

Now for uniqueness proof. Lets assume such that . Suppose , it follows that . Since , it follows . Thus we have . Thus if if , then . Thus contains all the elements which are not in , or . Thus .


Soln9

(a)

Existence:

Suppose . Now suppose , then it follows that . Similarly if , then . Since is arbitrary, .

Uniqueness:

Suppose is a set such that . Now for , we have . But . It follows that . Or we can say that is unique.

(b)

Suppose is arbitrary. From last part we know that .

Existence:

Suppose . Then . Since contains all element which exists in . But clearly . Thus . Thus there exists a set such that .

Uniqueness:

Suppose is a set such that . Now for , we have . But since , it follows that . Or we can conclude that is unique.

(c)

Existence:

Suppose . Then we have :


Uniqueness:

Suppose is a set such that . Suppose . Thus we have :


Thus we have . Or we can say that is unique.


(d)

Suppose is arbitrary.

Existence:

Suppose . Suppose . Then we have : .
.
Since , :
.
.

Thus there exists a , such that .

Uniqueness:

Suppose is a set such that . Since this is true for all sets and all sets such that , this must be true for . Thus , which is equivalent to . Thus we can conclude that is unique.


Soln10

We can have following cases:

Case 1: .
Suppose does not contain any set. Thus . But since is empty, is false. Thus if then is false. Or by contra-positive, we can conclude that if then .

Case 2: contains more than one element:
Suppose . Suppose such that sets and . Thus . Or we can say that . But clearly . Or is false. Thus by contrapositive we can say that if then does not contains more then one element.

Thus combining both cases 1 and 2, there is only one possibility that contains only one element.


Soln11

Existence:
Suppose . Since , it follows that . Suppose , then if , it follows that . Thus . Since is arbitrary, .

Uniqueness:

Suppose and are two different sets such that and . Since , we can replace with in and with in . Thus we get and . It follows that .


Soln12

(a)

Required statement: .

(b)

We shall prove it in two steps:

Existence Proof: First prove two such value exists so that is true.

Uniqueness Proof: Prove if there is any value, say so that is true, then this value must be equal to any of the two values find in previous step.

(c)

Existence:

Suppose , then we have .

Also suppose , then we have .

Uniqueness:

Suppose for a value such that , and . Thus . Since , multiplying both sides by , we get . Thus it contradicts with the assumption . So we can conclude that and are the only possible values for .