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:
- 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
- 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 A∪B=B∪A. |
- Proof: Suppose that x∈A∪B. Then x∈A or x∈B or x∈A∩B to which we write that x∈B∪A. Therefore A∪B=B∪A. ■
Theorem 2 (Commutative Law for the Intersection of Two Sets): If A and B are sets then A∩B=B∩A. |
- Proof: Suppose that x∈A∩B. If x is both in A and B, then we can also say that x is in both B and A or rather x∈B∩A. Therefore A∩B=B∩A. ■
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
`
There is visibly a bundle to realize about this. I think you made various nice points in features also.
Great post, you have pointed out some great details , I besides conceive this s a very fantastic website.
I needed to thank you for this excellent read!!
I certainly enjoyed every bit of it. I have got you
saved as a favorite to check out new stuff you post…
I simply want to mention I am newbie to blogs and certainly loved your blog site. Likely I’m want to bookmark your website . You surely have superb posts. Cheers for sharing your web-site. cialis at walmart
I genuinely enjoy looking at on this web site, it holds wonderful blog posts. В«The living is a species of the dead and not a very attractive one.В» by Friedrich Wilhelm Nietzsche. pharmacie de garde.