Proof and definition of some basic laws of the set analysis:

1.Commutative law

Ø(i) A U B = B U A

(ii) A ∩ B = B ∩ A

2.Associative Laws:

For any three finite sets A, B and C;

(i) (A U B) U C = A U (B U C)

(ii) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Thus, union and intersection are associative.

3.Idempotent Laws:

For any finite set A;

(i) A U A = A

(ii) A ∩ A = A

4.Identity law:

For any finite set A, Null set Ø and universal set U:

(i) A U Ø  = A

(ii) A ∩ U = A

5.Distributive Laws

For any three finite sets A, B and C;

(i) A U (B ∩ C) = (A U B) ∩ (A U C)

(ii) A ∩ (B U C) = (A ∩ B) U (A ∩ C)

Thus, unions and intersections are distributive over intersections and union respectively.

6.De Morgan’s Laws:

For any three finite sets A and B;

(i) A – (B U C) = (A – B) ∩ (A – C)

(ii) A – (B ∩ C) = (A – B) U (A – C)

De Morgan’s Laws can also we written as:

(i) (A U B)’ = A’ ∩ B’

(ii) (A ∩ B)’ = A’ U B’

 

More laws of the algebra of sets:

7.For any two finite sets A and B;

(i) A – B = A ∩ B’

(ii) B – A = B ∩ A’

(iii) A – B = A ⇔ A ∩ B = ∅

(iv) (A – B) U B = A U B

(v) (A – B) ∩ B = ∅

(vi) A ⊆ B ⇔ B’ ⊆ A’

(vii) (A – B) U (B – A) = (A U B) – (A ∩ B)

8.For any three finite sets A, B and C;

(i) A – (B ∩ C) = (A – B) U (A – C)

(ii) A – (B U C) = (A – B) ∩ (A – C)

(iii) A ∩ (B – C) = (A ∩ B) – (A ∩ C)

(iv) A ∩ (B △ C) = (A ∩ B) △ (A ∩ C)

Proof of De-Morgan’s law:

De Morgan’s Laws can be we written as:

(i) (A U B)’ = A’ ∩ B’

(ii) (A ∩ B)’ = A’ U B’

Definition of De Morgan’s law:

The complement of the union of two sets is equal to the intersection of their complements and the complement of the intersection of two sets is equal to the union of their complements. These are called De Morgan’s laws.

For any two finite sets A and B;

(i) (A U B)’ = A’ ∩ B’ (which is a De Morgan’s law of union).

(ii) (A ∩ B)’ = A’ U B’ (which is a De Morgan’s law of intersection).

 

Proof of De Morgan’s law: (A U B)’ = A’ ∩ B’

Let P = (A U B)’ and Q = A’ ∩ B’

Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)’

⇒ x ∉ (A U B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A’ and x ∈ B’

⇒ x ∈ A’ ∩ B’

⇒ x ∈ Q

Therefore, P ⊂ Q …………….. (i)

Again, let y be an arbitrary element of Q then y ∈ Q ⇒ y ∈ A’ ∩ B’

⇒ y ∈ A’ and y ∈ B’

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A U B)

⇒ y ∈ (A U B)’

⇒ y ∈ P

Therefore, Q ⊂ P …………….. (ii)

Now combine (i) and (ii) we get; P = Q i.e. (A U B)’ = A’ ∩ B’

 

Proof of De Morgan’s law: (A ∩ B)’ = A’ U B’

Let M = (A ∩ B)’ and N = A’ U B’

Let x be an arbitrary element of M then x ∈ M ⇒ x ∈ (A ∩ B)’

⇒ x ∉ (A ∩ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A’ or x ∈ B’

⇒ x ∈ A’ U B’

⇒ x ∈ N

Therefore, M ⊂ N …………….. (i)

Again, let y be an arbitrary element of N then y ∈ N ⇒ y ∈ A’ U B’

⇒ y ∈ A’ or y ∈ B’

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)’

⇒ y ∈ M

Therefore, N ⊂ M …………….. (ii)

Now combine (i) and (ii) we get; M = N i.e. (A ∩ B)’ = A’ U B’

`

Examples on De Morgan’s law:

  1. If U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}.

Proof of De Morgan’s law: (X ∩ Y)’ = X’ U Y’.

Solution: 

We know,  U = {j, k, l, m, n}

X = {j, k, m}

Y = {k, m, n}

(X ∩ Y) = {j, k, m} ∩ {k, m, n}

= {k, m}

Therefore, (X ∩ Y)’ = {j, l, n}  ……………….. (i)

Again, X = {j, k, m} so, X’ = {l, n}

and    Y = {k, m, n} so, Y’ = {j, l}

X’ ∪ Y’ = {l, n} ∪ {j, l}

Therefore,  X’ ∪ Y’ = {j, l, n}   ……………….. (ii)

Combining  (i)and (ii) we get;

(X ∩ Y)’ = X’ U Y’.          Proved

  1. Let U = {1, 2, 3, 4, 5, 6, 7, 8}, P = {4, 5, 6} and Q = {5, 6, 8}.
    Show that (P ∪ Q)’= P’ ∩ Q’.Solution:

We know, U = {1, 2, 3, 4, 5, 6, 7, 8}

P = {4, 5, 6}

Q = {5, 6, 8}

P ∪ Q = {4, 5, 6} ∪ {5, 6, 8}

= {4, 5, 6, 8}

Therefore, (P ∪ Q)’ = {1, 2, 3, 7}   ……………….. (i)

Now P = {4, 5, 6} so, P’ = {1, 2, 3, 7, 8}

and Q = {5, 6, 8} so, Q’ = {1, 2, 3, 4, 7}

P’ ∩ Q’ = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7}

Therefore, P’ ∩ Q’ = {1, 2, 3, 7}   ……………….. (ii)

Combining  (i)and (ii) we get;

(P ∪ Q)’ = P’ ∩ Q’.          Proved

Proof:  The Identity Law A U Ø = A

Solution:

Both A and B are always subsets of AUB, that is,

A⊂(AUB) and B⊂(AUB). From this law, we can write

A ⊂ (A U Ø).

Now let x ɛ (A U Ø); Then x ɛ A or x ɛ Ø. By definition of the null set, x ∉ Ø; hence x ɛ A;

So x ɛ (A U Ø) implies x ɛ A, i.e. (AUØ) ⊂ A. By the definition, two sets A and B are equal, if and only if A ꞇ B and B ꞇ A. Here (AUØ)ꞇA and Aꞇ(AUØ).

Proof: The Idempotent law  A U A = A

Solution: By the definition, two sets A and B are equal, if and only if A ꞇ B and B ꞇ A. From this definition we must show that (AUA)ꞇA and Aꞇ(AUA). By the rules, both A and B are always a subset of the union of two sets Aꞇ(AUA).

Now let x ɛ (A U A); Then by the definition of union x ɛ A or x ɛ A. Thus x belongs to A.

Hence (AUA)ꞇA and we can write A = ( A U A )

Definition and proof of Distributive Law

Distributive Law states that, the sum and product remain the same value even when the order of the elements is altered.

First Law: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Second Law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

First Law :
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
 
The first law states that taking the union of a set to the intersection of two other sets is the same as taking the union of the original set and both the other two sets separately and then taking the intersection of the results.
 
Proof :
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Let x ∈ A ∪ (B ∩ C). If x ∈ A ∪ (B ∩ C) then x is either in A or in (B and C).
x ∈ A or x ∈ (B and C)
x ∈ A or {x ∈ B and x ∈ C}
{x ∈ A or x ∈ B} and {x ∈ A or x ∈ C}
x ∈ (A or B) and x ∈ (A or C)
x ∈ (A ∪ B) ∩ x ∈ (A ∩ C)
x ∈ (A ∪ B) ∩ (A ∪ C)
x ∈ A ∪ (B ∩ C) => x ∈ (A ∪ B) ∩ (A ∪ C)
 
Therefore,
A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C)— 1
 
Let x ∈ (A ∪ B) ∩ (A ∪ C). If x ∈ (A ∪ B) ∩ (A ∪ C) then x is in (A or B) and x is in (A or C).
x ∈ (A or B) and x ∈ (A or C)
{x ∈ A or x ∈ B} and {x ∈ A or x ∈ C}
x ∈ A or {x ∈ B and x ∈ C}
x ∈ A or {x ∈ (B and C)}
x ∈ A ∪ {x ∈ (B ∩ C)}
x ∈ A ∪ (B ∩ C)
x ∈ (A ∪ B) ∩ (A ∪ C) => x ∈ A ∪ (B ∩ C)
 
Therefore,
(A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C)— 2
 
From equation 1 and 2
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
 
Second Law :
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
 
The second law states that taking the intersection of a set to the union of two other sets is the same as taking the intersection of the original set and both the other two sets separately and then taking the union of the results.
 
Proof :
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Let x ∈ A ∩ (B ∪ C). If x ∈ A ∩ (B ∪ C) then x ∈ A and x ∈ (B or C).
x ∈ A and {x ∈ B or x ∈ C}
{x ∈ A and x ∈ B} or {x ∈ A and x ∈ C}
x ∈ (A ∩ B) or x ∈ (A ∩ C)
x ∈ (A ∩ B) ∪ (A ∩ C)
x ∈ A ∩ (B ∪ C) => x ∈ (A ∩B) ∪ (A ∩ C)
 
Therefore,
A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∩ C)— 3
 
Let x ∈ (A ∩ B) ∪ (A ∩ C). If x ∈ (A ∩ B) ∪ (A ∩ C) then x ∈ (A ∩ B) or x ∈ (A ∩ C).
x ∈ (A and B) or (A and C)
{x ∈ A and x ∈ B} or {x ∈ A and x ∈ C}
x ∈ A and {x ∈ B or x ∈ C}
x ∈ A and x ∈ (B or C)
x ∈ A ∩ (B ∪ C)
x ∈ (A ∩ B) ∪ (A ∩ C) => x ∈ A ∩ (B ∪ C)
 
Therefore,
(A ∩ B) ∪ (A ∩ C) ⊂ A ∩ (B ∪ C)— 4
 
From equation 3 and 4
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Hence, the distributive law property of sets theory has been proved.

Associative Law of Set Theory Proof

Associative Law states that the grouping of set operation does not change the result of the next grouping of sets. It is one of the important concepts of set theory. If we have three sets A, B, and C, then,

1. Associative Law of Intersection: (A ∩ B) ∩ C = A ∩ (B ∩ C)
2. Associative Law of Union: (A U B) U C = A U (B U C)

Associative Law of Set Theory Proof – Definition

Statement:
 
First Law:
The first law states that the intersection of a set to the intersection of two other sets is the same.
(A ∩ B) ∩ C = A ∩ (B ∩ C)
 
Proof :
In the first law (A ∩ B) ∩ C = A ∩ (B ∩ C)
Step 1:
Let us take the L.H.S, (A ∩ B) ∩ C
Let x ∈ (A ∩ B) ∩ C. If x ∈ (A ∩ B) ∩ C then x ∈ (A and B) and x ∈ C
x ∈ (A and B) and x ∈ C
x ∈ (A and B) implies x ∈ A and x ∈ B
So, we have
x ∈ A, x ∈ B and x ∈ C
x ∈ A and x ∈ (B and C)
x ∈ A and (B and C)
x ∈ A ∩ (B ∩ C)
x ∈ (A ∩ B) ∩ C => x ∈ A ∩ (B ∩ C)
(A ∩ B) ∩ C ⊂ A ∩ (B ∩ C)— 1
 
Step 2:
Let us take the R.H.S, (A ∩ B) ∩ C
Let x ∈ A ∩ (B ∩ C). If x ∈ A ∩ (B ∩ C) then x ∈ A and x ∈ (B and C)
x ∈ A and x ∈ (B and C)
x ∈ (B and C) implies x ∈ B and x ∈ C
So, we have
x ∈ A, x ∈ B and x ∈ C
x ∈ (A and B) and x ∈ C
x ∈ (A and B) and C
x ∈ (A ∩ B) ∩ C
x ∈ A ∩ (B ∩ C) => x ∈ (A ∩ B) ∩ C
A ∩ (B ∩ C) ⊂ (A ∩ B) ∩ C— 2
 
From equation 1 and 2
(A ∩ B) ∩ C = A ∩ (B ∩ C)
Hence, associative law of sets for intersection has been proved.
 
Second Law:
Second law states that the union of a set to the union of two other sets is the same.
(A ∪ B) ∪ C = A ∪ (B ∪ C)
 
Proof :
In the second law (A ∪ B) ∪ C = A ∪ (B ∪ C)
Step 1:
Let us take the L.H.S, (A ∪ B) ∪ C
Let x ∈ (A ∪ B) ∪ C. If x ∈ (A ∪ B) ∪ C then x ∈ (A or B) or x ∈ C
x ∈ (A or B) or x ∈ C
x ∈ (A or B) implies x ∈ A or x ∈ B
So, we have
x ∈ A or x ∈ B or x ∈ C
x ∈ A or x ∈ (B or C)
x ∈ A or (B or C)
x ∈ A ∪ (B ∪ C)
x ∈ (A ∪ B) ∪ C => x ∈ A ∪ (B ∪ C)
(A ∪ B) ∪ C ⊂ A ∪ (B ∪ C)— 3
 
Step 2:
Let us take the R.H.S, (A ∪ B) ∪ C
Let x ∈ A ∪ (B ∪ C). If x ∈ A ∪ (B ∪ C) then x ∈ A or x ∈ (B or C)
x ∈ A or x ∈ (B or C)
x ∈ (B or C) implies x ∈ B or x ∈ C
So, we have
x ∈ A or x ∈ B or x ∈ C
x ∈ (A or B) or x ∈ C
x ∈ (A or B) or C
x ∈ (A ∪ B) ∪ C
x ∈ A ∪ (B ∪ C) => x ∈ (A ∪ B) ∪ C
A ∪ (B ∪ C) ⊂ (A ∪ B) ∪ C— 4
 
From equation 3 and 4
(A ∪ B) ∪ C = A ∪ (B ∪ C)
Hence, the associative law of sets for the union has been proved.

Commutative Laws of Sets

We will now look at the commutative laws between two sets. These proofs are relatively straightforward.

Theorem 1 (Commutative Law for the Union of Two Sets): If A and B set

then AB=BA.

  • Proof: Suppose that xAB. Then xA or xB or xAB to which we write that xBA. Therefore AB=BA. ■

Theorem 2 (Commutative Law for the Intersection of Two Sets): If A and

 B are sets then AB=BA.

  • Proof: Suppose that xAB. If x is both in A and B, then we can also say that x is in both B and A or rather xBA. Therefore AB=BA. ■

Partition of a set:

Definition. A partition of a set A is a set of nonempty subsets of A such that every element x in A is in exactly one of these subsets (i.e., A is a disjoint union of the subsets). The intersection of any two distinct sets in P is empty. The elements of P are said to be pairwise disjoint.

Let { A¡ } ¡ ɛ I  be a family of non-empty subsets of A where I ={ 1,2,3,4—-} .Then

{A¡} ¡ ɛ I   is called a partition of A if

1.A1UA2UA3UA4=A

2.A¡=Aⱼ or A¡∩Aⱼ =Ø

Furthermore, each Ai is then called the equivalence class of A.

 

Examples of partition set

1.A collection of disjoint subsets of a given set. The union of the subsets must equal the entire original set. For example, one possible partition of {1, 2, 3, 4, 5, 6} is {1, 3}, {2}, {4, 5, 6}.

2.Let T={1,2,3,———–8,9,10}

And let A={1,3,5},  B={2,6,10} C={4,8,9}

Then {A,B,C} is not a partition of T since T҂AUBUC

i.e.7ɛT but 7҂(AUBUC).

3.Let T={1,2,3,———–8,9,10}

And let A={1,3,5,7,9},  B={2,4,10}  and C={3,5,6,8}

Then {A,B,C} is not a partition of T since

A∩C҂ Ø, A ҂ C

 

 

 

 

 

`

 

 

Related Posts

5 thoughts on “Proof and definition of some basic laws of the set analysis:

মন্তব্য করুন

আপনার ই-মেইল এ্যাড্রেস প্রকাশিত হবে না। * চিহ্নিত বিষয়গুলো আবশ্যক।

bn_BDBengali
en_USEnglish bn_BDBengali