Chapter - 2, Quantificational Logic

Section - 2.3 - More Operations on Sets


Summary

  • Sets can be defined in following ways:
    • Listing all elements of the set. Eg: .
    • Element-hood Test Notation: . Or sometimes replacing by an expression eg: .
    • A set can also be defined using indexed family notation. For eg: , where .
  • An indexed family can also be defined as . Thus means the same thing as .
  • Sets whose elements are all sets are called families of sets. Eg: .
  • Power Set: .
  • If is a family of sets, then:
    • Intersection of all sets in .
    • Union of all sets in .
  • Some useful logical forms:
    • is equivalent to .
    • is equivalent to which is equivalent to .
    • is equivalent to , or equivalently,.
    • is equivalent to .
  • An alternative notation of union or intersection. If , where each is a set. Then would be the set of all elements common to all the ’s, for , and this can also be written as .

Soln1

(a)


(b)

(c)


This is equivalent to:
.

(d)







Soln2

(a)



(b)


(c)

(d)


Soln3


Soln4


Soln5


Soln6

Given: where






Soln8

Given: and where

(a)



(b)


(c) No. The given statements are not equivalent.


Soln9





Thus


Soln10









Hence Proved.


Soln11

, and



And
Clearly


Soln12

(a)




Existential quantifier distributes over interjection:



This is equivalent to RHS.

(b)





Using reverse of, Universal Quantifier distributes over conjunction:

Using inverse of law of distribution:

Using Demorgan’s Law:




= RHS.

(c)








= RHS.


Soln13

Given: where and

(a)

(b)

Putting values from (a) :

(c)

To find , lets first compute


Thus we have:
No, expression of (b) and (c) parts are not equal.

(d)

LHS:

RHS:

Clearly LHS and RHS are not equal. We already saw this that if order of quantifiers are changed, expressions are also changed.


Soln14

(a)




If , will always be false.
Thus whole statement will be false. Thus , irrespective of the value of x.
which means .

(b)



If , will always be false.
Thus will always be true.
That means , irrespective of the value of x.
That means .


Soln15

(a)

  • According to the definition, R is the set of all sets that does not contains themselves.
  • R itself should also be a set that does not contain itself, as if it contains itself it will contradict its own definition.
  • Now if R does not contain itself, then again it contradicts with its definition which says it is a set that contains all the sets that does not contain themselves.
  • Thus such set R can not exist.

(b) It follows that there is no universal set of sets.