Set theory lecture-2
Recall: representation of sets
Roster form - all elements are listed.
Set-builder form
Note that, in general, for infinite sets like $\mathbb{R}$ it is not possible to use the roster form. So, we need set-builder form.
$\text{Intervals in } \mathbb{R}$
Let $a,b∈\mathbb{R}$ with $a < b$.
Open interval
Closed interval
$(a,b]=\{x: x∈\mathbb{R}, a<x≤b\}$
$[a, b)=\{x:x∈\mathbb{R}, a≤x<b\}$
$(a, \infty)=\{x:x∈\mathbb{R}, x>a\}$
$[a, \infty)=\{x:x∈\mathbb{R}, x≥a\}$
$(-\infty, b)=\{x:x∈\mathbb{R}, x<b\}$
$(-\infty, b]=\{x:x∈\mathbb{R}, x≤b\}$
$(-\infty,\infty)= \mathbb{R}$
All these intervals are subsets of $\mathbb{R}$.
Proper subset
We say $A$ is a proper subset of $X$ if $A$ is a subset of $X$ but $A≠X$.
e.g. $\{1,2\} ⫋ \{1,2,3\}$
Super set
We say $B$ is a superset of $A$ if $A$ is a subset of $B$.
Properties of union
$A ∪ B = B ∪ A$ (Commutative law)
$(A ∪ B )∪ C = A ∪ (B ∪ C) $ (Associative law)
$A ∪ \phi = A$ (Identity law)
$A ∪ A = A$ (Idempotent law)
If $A ⊆ U$ then $A ∪ U= U$.
Properties of intersection
$A ∩ B = B ∩ A$
$(A ∩ B)∩ C = A ∩ (B ∩ C)$
$A ∩ \phi = \phi$
$A ∩ A = A$
If $A ⊆ B$ then $A ∩ B= A$.
Distributive law
$A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)$
$A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)$
$A\cap B$
$A \cap C$
Properties of complement
$U$ : Universal set
$A’ = U-A$
$(A’)’= A \quad [(A’)’= U-A’=U-(U-A)=A]$
$\phi’= U; U’= \phi$
If $A ⊆ B ⊆ U,$ then $B’⊆ A’\\ [x∈B’ => x∉B => x∉A ∵(A⊆B) =>x∈A’]$
De morgan’s laws
i. $(AUB)’ = A’∩ B'$
ii. $(A∩B)’ = A’U B'$
Number of elements in the union
Let $A$ and $B$ are two finite sets such that $A∩B=\phi$. Then $n(AUB)=n(A)+n(B)$
$n(A)\rightarrow$ number of elements in $A$
$n(B)\rightarrow$ number of elements in $B$
Proof of number of elements in the union
$n(AUB)=n(A)+n(B)-n(A∩B)$
Proof:
$AUB = (A-B)U(A∩B)U(B-A)$ $\text{where} (A-B), A∩B \ \& \ (B-A) \text{are pairwise disjoint}.$
$∴ n(AUB)=n(A-B)+n(A∩B)+n(B-A)$
$n(AUB) =[n(A-B)+n(A∩B)]+[n(B-A)+n(A∩B)]-n(A∩B) …(i)$
But, $A=(A-B)U(A∩B) \leftarrow$ Disjoint union
$∴ n(A)=n(A-B)+n(A∩B)$
Similarly, $∴ n(B)=n(B-A)+n(A∩B)$
substitute in …(i), we get, $∴ n(AUB)=n(A)+n(B)-n(A∩B)$
What about $n(A \cup B \cup C)?$
$\text{Proof of ~ n } (A \cup B \cup C)$
$n(AU(BUC)) = n(A)+n(BUC)-n(A∩(BUC))$
$= n(A)+n(B)+n(C)-n(B∩C)-n(A∩(B∩C)) \cdots(i)$
By distributive property,
$A∩(BUC)=(A∩B)U(A∩C)$
$\text{So,} \ n(A∩(BUC))=n(A∩B)+n(A∩C)-n((A∩B)∩(A∩C))$
$=n(A∩B)+n(A∩C)-n(A∩B∩C) \cdots(ii)$
$\text{Proof of} \ n(A \cup B \cup C)$
By (ii) in (i),
$n(A∩B∩C)=n(A)+n(B)+n(C)-n(A∩B)-n(B∩C)-n(A∩C)+n(A∩B∩C)$
======
Example
$400$ People who speaks either English or Hindi or Both.
$250$ people : speak Hindi
$200$ people : speak English
How many speak both languages?
Solution
Let $H$ : set of people speaking Hindi.
$E$ : set of people speaking English.
Given: $n(H)=250, n(E)=200, n(HUE)=400$
To find : $n(H∩E)=?$
$n(HUE)=n(H)+n(E)-n(H∩E)$
$n(H∩E)=-n(HUE)+n(H)+n(E)$ $=-400+250+200$ $= 50$
Problem 1
Suppose $AUB=AUC \ \& \ A∩B=A∩C$. Prove that $B=C$.
Solution:
To show $B=C$ It is enough to show that $B⊆C$ & $C⊆B$
Let $x∈B ⊆ AUB=AUC$
$\Rightarrow \ x∈A \ \text{or} \ x∈C.$
If $x∈C$, then O.K.
Problem 1 (continue)
If $x∈A$ then $x∈A∩B$ $\ (∵x∈B \text{also})$
But $A∩B=A∩C$,
so, $x∈A∩C => x∈C$
so, we have $x∈B => x∈C$
$∴ B⊆C$
Similarly, $C⊆B$
$∴ B=C$
Problem 2
If $P(A)=P(B)$ then prove that $A=B$.
Recall: $P(A)={C:C⊆A}$.
Since, $A⊆A, A∈P(A)=P(B)$
$\Rightarrow \ A∈P(B) \ \Rightarrow \ A⊆B$.
Similarly, $B∈P(B)=P(A)=>B⊆A$.
Hence, $A=B$.
Notations
Statement 1 $\Rightarrow$ statement 2 means if statement 1 is true then statement 2 is true.
statement 1$\Longleftrightarrow$statement 2 means statement 1 is true if and only if statement 2 is true.
Short hand: iff $\equiv$ if and only if.
Problem 3
Suppose $A∩B \neq \phi, \ B∩C \neq \phi, \ A∩C \neq \phi$. Is it true that $A∩B∩C\neq \phi?$
Solution: No, Let $A=\{0,1\},B=\{1,2\},C=\{0,2\}$
$0∈A∩C, 1∈A∩B, 2∈B∩C$.
But $A∩B∩C= \phi$.
Thank you