Set Theory PDF

# Set Theory ## The Cardinality of Sets - The cardinality of Z is infinite. We also call the size of the set A, the **cardinality** of set A. - A set is called finite if its cardinality is an integer. - Otherwise, if it is infinite. ## Equality of Sets - Two sets are equal, if their elements are...

# Set Theory ## The Cardinality of Sets - The cardinality of Z is infinite. We also call the size of the set A, the **cardinality** of set A. - A set is called finite if its cardinality is an integer. - Otherwise, if it is infinite. ## Equality of Sets - Two sets are equal, if their elements are identical. - **Example:** - Suppose E = {x | x ∈ Z, 2 | x} - Suppose F = {z | z∈ Z, z = a+b, a, b are odd} - Is E = F? **Solution:** - For every x∈E, then x∈F. Also, x∈F then x∈E. - Therefore, E = F. ### Explanation - **Step 1:** Prove for every element in E, that it is also an element of F. - We know that x ∈ E implies x = 2y for some y ∈ Z. - From that, we can rewrite x as (2y +1) + (-1). - Note that 2y + 1 is odd and -1 is also odd. - So, x is in the form of z = (2y + 1) + (-1), where a, b are odd, and z is an element of F. - Therefore, we conclude that x ∈ E ⇒ x ∈ F. - **Step 2:** Now, prove for every element in F, that it is also an element of E. - We know that if z ∈ F, then there exists c ∈ Z such that z = 2c, which means z ∈ E. ## Subsets - Suppose A and B are sets. - **Subset:** A is a subset of B if every element of A is also an element of B. The notation ACB means this. - **Example:** A = {1, 2, 3} and B = {1, 2, 3, 4} - Therefore, ACB. ### Important Notes - For any set A, we have: - **A⊆A** because every element of A is of course in A. - **Φ⊆A** because the empty set is a subset of all sets. ## Proper Subsets - **Proper subset:** A is a proper subset of B if A is contained in B but not equal to B. The notation ACB, AB means this. - **Example:** Φ ⊂ {1, 2, 3} and {1, 2} ⊂, {1, 2, 3} ## Notation | Symbol | Meaning | |---|---| | x ∈ A | x is an element of A | | B ⊆ A | B is a subset of A | ## Counting Subsets - The family of all of the subsets of any set S is called the **power set** of S. We denote this by: 2^|S| - **Example:** How many subsets does A = {1, 2, 3} have? | Number of Elements | Subsets | Number | |---|---|---| | 0 | Φ | 1 | | 1 | {1}, {2}, {3} | 3 | | 2 | {1, 2}, {1, 3}, {2, 3} | 3 | | 3 | {1, 2, 3} | 1 | | | Total: | 8 | ## Disjoint Sets - Two sets are disjoint if they have no elements in common. - **Example:** - A ={1, 3, 7, 8} and B = {2, 4, 7, 9, 3}. - Then, A and B are not disjoint since they have the element 7 in common. - **Example:** - A = {x | x ∈ Z^-} and B = {x | x ∈ Z⁺} - A and B are disjoint because A contains only negative integers and B contains only positive integers. ## Venn-Euler Diagram - A Venn-Euler diagram is a pictorial representation of relationships between sets. ## Set Operations ### Union - The union of A and B is the set of elements that are in A or B. This is denoted by: A ∪ B. ### Intersection - The intersection of A and B is the set of elements that are in both A and B. This is denoted by: A ∩ B. ### Set Operations In Symbols - A ∪ B = { x | x ∈ A or x ∈ B}. - A ∩ B = { x | x ∈ A and x ∈ B }. ### Example - Suppose A = {1, 2 ,3, 4} and B = {3, 4, 5, 6}. - A ∪ B = {1, 2, 3 ,4, 5, 6} - A ∩ B = {3, 4} ## Comparability of Two Sets - Two sets A and B are comparable if A ⊆ B or B ⊆ A. ## Set Operations Properties - **Commutative Properties** - A ∪ B = B ∪ A and A ∩ B = B ∩ A - **Associative Properties** - A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C - **Distributive Properties** - A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) - A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) - **Identities** - A ∪ Φ = A and A ∩ Φ = Φ ## Set Difference - The **difference** of A and B is the set of elements that are in A but not in B. - This is denoted by : A - B. - A - B = {x | x ∈ A and x ∉ B} ## Symmetric Difference - The **symmetric difference** is the set of all elements that are in A but not B or in B but not A. - This is denoted by: A△B. - A△B = (A - B) ∪ (B - A). ## Complement - The complement of a set A is the set of elements that do not belong to A. - This is the difference of the universal set U and A. - We denote the complement by A’ or A^c. ## Properties of Complement - 1. A ∪ A’ = U - 2. A ∩ A’ = Φ - 3. (A’)’ = A ## Set Operations Visualized - **Example:** - Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6}, and C = {1, 3, 4}. - Visualize these sets using a Venn Diagram. | Description | Set | |---|---| | **(A ∪ B) ∩ C** |{2, 3, 4, 5, 6} ∩ {1, 3, 4} = {3, 4} | | **A ∩ C** | {1, 2, 3, 4} ∩ {1, 3, 4} = {1, 3, 4} | | **(A ∩ C) ∩ B** |{1, 3, 4} ∩ {3, 4, 5, 6} = {3, 4} | | **(A ∪ B) ∩ (B ∪ C)** | {1, 2, 3, 4, 5, 6} ∩ {1, 2 ,3, 4, 5, 6, 7, 8, 9} = {1, 2, 3, 4, 5, 6} | | **(A ∩ C) ∪ (B ∩ C)** | {1, 3, 4} ∪ {3, 4, 5, 6} = {1, 3, 4, 5, 6}| ## De Morgan’s Laws - **De Morgan's Law:** - _A - (B ∪ C) = (A - B) ∩ (A - C)_ - _A - (B ∩ C) = (A - B) ∪ (A - C)_ **Example:** - Let A = {2, 3, 4, 5, 6}, B = {2, 7, 8, 9, 6}, C = {1, 2, 3, 5, 7} - A - (B ∪ C) = (A - B) ∩ (A - C) - A - (B ∩ C) = (A - B) ∪ (A - C) ## Complement of a Set - B - (C ∩ A) = (B - C) ∪ (B - A) ## Venn Diagram Example - **Represent two sets using a Venn diagram. Identify the regions:** - A - B - A ∩ B - (A ∪ B) ∩ C ## Properties of Complement - **The union of any set A and its complement A’ is the universal set: A ∪ A’ = U** - **The complement of the universal set U is the null set Φ: U’ = Φ, Φ’ = U** - **Set A and its complement are disjoint: A ∩ A’ = Φ** - **The complement of the complement of set A is the set A itself: (A’)’ = A** - **A - B = A ∩ B’** - **A - B = {x | x∈A, x∉B}** - **A ∩ B = {x | x ∈ A, x ∈ B}**