M4S1 - Introduction to Sets PDF

# M4S1 - Introduction to Sets ## Set - It is an unordered collection of objects, called elements or member of the set. - Capital letters (A, B, C) specifies a set. ### Examples: - A = Set of all the planets in the solar system - L = Set of all the lowercase letters of the alphabet - D = {1,2,3,4,5...

# M4S1 - Introduction to Sets ## Set - It is an unordered collection of objects, called elements or member of the set. - Capital letters (A, B, C) specifies a set. ### Examples: - A = Set of all the planets in the solar system - L = Set of all the lowercase letters of the alphabet - D = {1,2,3,4,5} - J = 0 - F = {F,A,N,N,Y} - J= {} - J = {0} ### Note: - Ø ≠ {0} - Sets do not have duplicate elements. - In a set, order does not matter. ## Cardinality of Set - The number of elements of the set. - Example: Let C = {yellow, blue, red}. - The cardinality of C is 3. |C| = 3 ## Types of Set - **Finite set:** Contains a definite number of elements. - Example: A = {1,2,3,4,5,6,7,8,9} - **Infinite set:** Contains infinite number of elements. - Example: Z*= {1,2,3,4,...} - **Empty set or null set:** An empty set contains no elements. Ø = {} - **Universal set:** U set of all animals on earth - **Singleton or unit set:** is a set that has only one element. - **Equal set:** If two sets contain the same elements they are said to be equal. - **Equivalent set:** If the cardinalities of two sets are same, they are called equivalent sets. - **Subset:** A set X is a subset of set Y if every element of X is an element of set Y. - "C" is the symbol of subset. - Example: A ⊆ B - **Proper subset:** A Set X is a proper subset of set Y if every element of X is an element of set Y. But Set X is not equal Set Y. - "C" is the symbol of proper subset - **Overlapping set:** Two sets that have at least one common element are called overlapping sets. - **Disjoint set:** Two sets A and B are called disjoint sets if they do not have even one element in common. ## Two methods of Set representation: 1. **Roster / Tabular form** - All the elements of a set are listed, the elements are separated by commas and are enclosed within braces { }. - Example: - F= {Abe, LotLot, Dolor, Anne, Ethel} - Z= {...,-3,-2,-1,0,1,2,3,...} - N = {1,2,3,4,5} 2. **Set Builder Notation** - The set is defined by specifying a property that elements of the set have in common. - All the elements of the set, must possess a single property to become the member of that set. - General form: {x|P(x)} - | - read as "such that", - P(x) - properties of x - Example: {x | x > 0} - It says "the set of all x's, such that x is greater than 0". - In other words any value greater than 0 - **Notes:** - The "x" is just a place-holder, it could be anything, such as {q|q>0} - Some people use ":" instead of "I", so they write {x: x > 0} ## Set Builder Notation Symbols - **E** is an element of - **-** is not an element of - **N** - set of all natural numbers - **Z** - set of all integers - **Z*** - set of all positive integers - **Q** - set of all rational numbers, {p/q | p ∈ ℤ, q ∈ ℤ, and q ≠ 0} - **R** - set of all real numbers, include both rational and irrational numbers - **R*** - set of all positive real numbers - **W** -the set of all whole numbers ## Examples: - **a.** Even integers {x|x=twice the integer} - **b.** Numbers whose square root is an integer. {x| √x ∈ ℤ} - **c.** Set A is the set of all 'x' such that 'x' is a natural number between 5 and 10. A = {x | x ∈ ℕ, 5 < x < 10} - **d.** Set A is a set of odd positive integers below 11. A = {x ∈ ℕ | x < 11, x is odd} - **e.** Set of letters in the word "California". A = {x | x is a letter of the word "California"} - **f.** Any value greater than 0. A = {y|y>0} - **g.** Any value except 15. A = {y|y ≠ 15} - **h.** Any value less than 7. A = {y|y<7} - **i.** All integers greater than 4. A = {y ∈ ℤ | y>4} ## Ordered Pairs - The pair of elements that occur in a particular order and are enclosed in brackets is known as a set of ordered pairs. - If 'a' and 'b' are two elements, then the two different pairs are (a, b), (b, a). - In an ordered pair (a, b), a is called the first element, and b is called the second element. - If we change the position of the elements in the ordered pair, then the ordered pair also get changed, i.e., it becomes (b, a) but (a, b) ≠ (b, a). ## Cartesian Product - Cartesian product of sets A and B (A X B) is defined as the set of all ordered pairs (x, y) such that x belongs to A and y belongs to B. - **Example:** - A = {1, 2} and B = {3, 4, 5} - A X B = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)} # M4S3 - Proving Set Identities ## SET Identities - [https://calcworkshop.com/set-theory/set-identities/](https://calcworkshop.com/set-theory/set-identities/) ### Properties for Subset Relations | Identity | Name | |---|---| | (A∩B)⊆A | Inclusion for Intersection | | (A∩B)⊆B | | | A⊆(AUB) | Inclusion for Union | | B⊆(AUB) | | | (A⊆B)(B⊆C)(A⊆C) | Transitive Property of Subsets | ### Properties of Universal Set and Empty Set | Identity | Name | |---|---| | AUØ=A | Domination Laws | | A∩Ø=Ø | | | A∩A'=Ø | Complementation Laws | | AUA'=U | | | U'=Ø | | | Ø' = U | | ### Set Identities | Identity | Name | |---|---| | A∩B=B∩A | Commutative Laws | | A∪B=B∪A | | | (A∩B)∩C=A∩(B∩C) | Associative Laws | | (A∪B)∪C=A∪(B∪C) | | | A∪(B∩C)=(A∪B)∩(A∪C) | Distributive Laws | | A∩(B∪C)=(A∩B)∪(A∩C) | | | A∩U=A | Identity Law | | A∪U=U | (Intersection and Unition with Universal Set) | | (A')'= A | Double Complement Laws | | A∩A=A | Idempotent Laws | | A∪A=A | | | (A∩B)'=A'∪B' | De Morgan's Laws | | (A∪B)'=A'∩B' | | | A∪(A∩B)= A | Absorption Laws | | A∩(A∪B) = A | | | A-B=A∩B' | Set Difference Law | - The basic method to prove a set identity is the element method or the method of double inclusion. It is based on the set equality definition: two sets A and B are said to be equal if A⊆B and B⊆A. In this method, we need to prove that the left-hand side (LHS) of a set identity is a subset of the right-hand side (RHS) and vice versa. - There are styles of proofs for sets that we will look at: - **Venn Diagram** - **Membership Table** - **Proofs For Set Relations** - **Proofs For Set Identities** ## Venn Diagram - Proofs using Venn diagrams are visual and typically quick to complete. However, there are some drawbacks. Venn diagrams are only practical for a small number of sets under consideration and are not considered robust or readily accepted in some academic circles. - **Example** - In this problem, we will use Venn diagrams for both the left-hand side and the right-hand side to demonstrate equivalence. - **Prove (AUB)-B = A-B** ## Membership Table - A proof by membership table is just like a proof by truth table in propositional logic, except we use 1s and Os in place of T and F, respectively. Again, this proof style is straightforward to create, but it loses effectiveness as the number of sets increases. - **Example** - In this question, we will use a membership table, similar to a truth table, to verify equivalence. Notice that the red column is exactly the same as the blue column, showing the left-side is equivalent to the right side. - **Prove (AUB) - B = A- B** ## Proofs For Set Relations - When proving set relations, we wish to show that one set is a subset of another. We will use a direct proof style that involves what some textbooks refer to as the element method or the double inclusion method. The process is simple in nature as we seek to prove the left-hand side is a subset of the right-hand side or vice versa. - In other words, we want to show that a given object is an element of the set. ### Example-1 - In this problem, let's prove the transitive property of subsets. Suppose A is a subset of B and B is a subset of C, show that A is a subset of C. - **Claim:** - If A⊆B and B⊆C, then A⊆C - **Proof:** - Assume A⊆B and B⊆C is given - Let x ∈ A be true. - Since A⊆B, if follows that x∈B - And since B⊆C it follows that x∈C - Therefore, for every x, if x ∈ A then x∈C ### Example-2. - Show that (A UB') = Α' ∩ B', Let x ∈ U - x∈ (AUB') = x∈A U B - = x ∈ A and x ∈ B - = x ∈ A' and x ∈ B' - = x ∈ (Α' ∩ B') ## Proofs For Set Identities - And for proving set identities, we will utilize a style that is sometimes called proof by definition. For these types of proofs, we will again employ all of our proof strategies like direct, indirect (contraposition and contradiction), and cases along with our set identities and definitions and either write our proof in paragraph form or as a two-column proof with justifications. ### E.g. - **Claim:** (A∩B) - (B-C) = A-B | (A∩B)-(B-C) = A - B | Prove using the Laws of Set | |---|---| | | Definition of set difference: A-B = A∩B' | | (A∩B') - (B∩C') | Definition of set difference | | (A∩B') ∩ (B∩C')' | Definition of set difference | | (A∩B') ∩ (B'∪C) | De Morgan's, Double complement | | (A∩B') ∩ (B'∪C) | apply Distributive (A∩B) ∪ (A∩C)) | | ((A∩B') ∩ B') ∪ ((A∩B') ∩ C) | Distributive | | (A∩(B'∩B')) ∪ (A∩(B'∩C)) | Associative | | (A∩B') ∪ (A∩(B'∩C)) | Idempotent | | (A∩B') ∪ (A∩(B'∩C)) | this format is similar to Distributive (A∩B) ∪ (A∩C)) = A∩(B∪C) | | A∩(B'∪(B'∩C)) | Distributive | | A∩B' | Absorption AU (A∩B)= A | | A∩B'=A-B | Definition of set difference | ## Example: Simplify the following sets using the Law of Sets 1. [AU (A' ∩ B)] U (AUB') | | | |---|---| | [(AUA') ∩ (AUB)] U (AUB') | Distributive | | [ Un (AUB)] U (AUB') | Inverse : AUA' = U | | (AUB) U (AUB') | Identity : UOA=A | | AU (BUA) U B' | Associative | | AU (AUB) U B' | Commutative | | (AUA) U (BU B') | Associative | | AU (BUB') | Idempotent: AUA=A | | AUU | Inverse : BUB' = U | | U | Domination : AUU=U | 2. [BU (AUB') U (A' ∩ B)] ∩ Β' | | | |---|---| | [BU (AUB) U (A' ∩ B)] ∩ B' | | | [BU (B'UA) U (A' ∩ B)] ∩ B' | Commutative | | [(BUB') UAU (A'∩ B)] ∩ B' | Associative | | [UUAU (A'∩ B)] ∩ Β' | Inverse : BUB' = U | | [(UUA) U (A'∩ B)] ∩ B' | Associative | | [UU (A'∩ B)] ∩ Β' | Domination : UUA= U | | U∩B' | Domination | | B' | Identity : AQUA |