Chapter - 3, Proofs

Section - 3.3 - Proofs Involving Quantifiers


Summary

  • To prove a goal of the form :
    • Let stand for an arbitrary object and prove . If x is already being used in the proof for something, then choose an unused variable, say , for the arbitrary object, and prove .
    • Scratch work will look as:
      Given:
      Goal:
      It will be transformed to:
      Given:
      Goal:
    • Formal proof will look as:
      Let x be arbitrary.
      [Proof of goes here.]
      Since was arbitrary, we can conclude that .
  • To prove a goal of the form :
    • Try to find a value of for which will be true. Then start the proof with “Let x = (the value decided)” and proceed to prove for this value of .
    • Scratch work will look as:
      Given:
      Goal:
      It will be transformed to:
      Given:
      Goal:
      x = (the value decided)
    • Formal proof will look as:
      Let x = (the value decided).
      [Proof of goes here.]
      Thus .
  • To use a given of the form :
    • Introduce a new variable, say , into the proof for which is true. Thus it can be assumed that P(x_0) is true. This rule of inference is called existential instantiation.
    • Using a given of the form is very different from proving a goal of the form , because when using a given of the form , there is no choosing for the value of .
  • To use a given of the form :
    • Plug in any value, say a, for x and use this given to conclude that P(a) is true. This rule is called universal instantiation.
    • It will be useful for cases when particular value, say , of is already known or considered and thus it can be assumed that is true.

Soln1

Suppose is true at . Thus we have . Suppose . Then is true. Since and then is true. Thus is true. If follows that is true.


Soln2

Suppose is arbitrary and , then and . Suppose . Since and , it follows that . Now since and , it follows that . But . Thus the assumption is not correct. It follows that if , then . As is arbitrary, we have .


Soln3

Suppose and . Since , it follows . Thus and . This contradicts the assumptions that . As is artibrary, .


Soln4

Suppose . Then . Since it is given that , it follows that . Thus if then . As is arbitrary, we get .


Soln5

(a) Empty set: .

(b) No. there is no other such set.


Soln6

(a)

Suppose . Putting the value of in . We get:

Thus

(b)

Given that . Solving this for , we get . Since is a real number, then is real. Thus .


Soln7

Suppose and . Putting this value of in , we get:



Thus .


Soln8

Suppose . Since , then must belongs to . Thus we have . Since is arbitrary, we have .


Soln9

Suppose . Since , then must belongs to all the set of . Now since , it follows that . Thus we have . Since is arbitrary, we have .


Soln10

Suppose . Since , it follows that . Thus belongs to all the sets of . Or we can say that . It follows that . Now since is arbitrary, .


Soln11

Suppose that . Thus belongs to all the sets of . Since , then . But there is no such element that . Thus such does not exist. Or .


Soln12

Suppose . Thus must exist in atleast one of the sets of . Suppose that and . Since , then . Thus x also exist in atleast one of the sets of . Or . Since is arbitrary, .


Soln13

Suppose , then belongs to all the sets of . Since , it follows that must belongs to all the sets of . Thus . Since is arbitrary, it follows that .


Soln14

Suppose . Suppose exists in where . Thus . It follows that . Now since , it follows that . Thus . Or we can say that if then . Since is arbitrary, we can conclude that .


Soln15

Suppose , then . Thus is a subset of all the sets of where . Or we can say that . Thus .


Soln16

Given that . Thus all the sets of A are subset of . Suppose , then belongs to atleast one of the set of . Since all the sets of are subsets of , it follows that . Thus if , then . Since is arbitrary, it can be concluded that .


Soln17

Suppose , then belongs to atleast one of the sets of . Since it is given that all the sets of are subsets of every set of , it follows that exists in all the sets of . Or we can say that . Thus if , then . Since is arbitrary, we can conclude that .


Soln18

(a)

It is given that and , where are integers. Adding the equations, we have . Since is also integer, it can be concluded that .

(b)

Given that . Since , it can be simplified to . Thus .


Soln19

(a)

Suppose . Then . Similarly . Thus for , then . Since is real, the equation is correct.

(b)

No, statement will not be correct as is not an integer.


Soln20

The problem is negation of is . In the given proof, its negation is taken as .


Soln21

(a) The issue with the proof is it started with but in conclusion it is assumed that .

(b) , .


Soln22

The issue with the proof is that is fixed for the value of . But for the goal of the theorem it should be arbitrary.


Soln23

(a)

It looks like theorem is correct except for only boundary case for empty set. If then and . Thus for this case, we have no contradiction.

(b)

As seen above we can have only boundary case examples:


Thus , are not disjoint.

But . Thus they are disjoint.


Soln24

(a)

Problem with the proof is and are considered equal, which may not be the case always.

(b)

Taking and , the theorem is not correct.


Soln25

Let be an arbitrary real number. Let . Now let be an arbitrary real number. Simplifying

Now taking , we have . Thus we can conclude that .


Soln26

(a)

  • Goal: and Given: :
    For goal , we introduce an arbitrary variable and move forward.
    For given , we introduce a new variable, say for which is true and move forward for the proof.
    Thus in both cases we move forward in the proof by introducing a variable.

  • Goal: and Given: :
    For goal , we move forward by finding a value for which is true.
    For given , we move forward by finding a value that can help further in proof as will be true for that value.
    Thus in both cases we work on finding specific value to move forward with the proof.

(b) Not sure about the reason for these similarities.