Discrete Structures 1 - Module 6: Sets - PDF

Module 6 **DISCRETE STRUCTURE 1** Sets **I. INTRODUCTION** This module contains a review of the fundamental theories of sets. They are important in mathematics since every mathematics field uses or in some way refers to sets. It is also considered an important building block of more complex math...

Module 6 **DISCRETE STRUCTURE 1** Sets **I. INTRODUCTION** This module contains a review of the fundamental theories of sets. They are important in mathematics since every mathematics field uses or in some way refers to sets. It is also considered an important building block of more complex mathematical structures. **II. OBJECTIVES** **III. LESSON PROPER** **Sets** A set is a well-defined collection of objects; the objects are called the elements of members of the set. - It can be represented by the upper case letters A, B, C \... - element- An object which belongs to or is a member of or is contained in a set - a member of set A is denoted by an [ ∈ *A*]{.math.inline} - does not belong to set A is denoted by a **∉**[ *A*]{.math.inline}. - ∅ The empty set is the set that contains no elements. - *U* The universe set is the set of all elements. - **ℕ** The set of natural numbers. That is, N {0, 1, 2, 3...}. - ℤ  The set of integers. That is, Z {... , −2, −1, 0, 1, 2, 3,...}. - ℚ The set of rational numbers. - **ℝ** The set of real numbers. - P(A) The power set of any set A is the set of all subsets of A. **Example** 1. Set of vowels in the English alphabet **Finite and Infinite Sets** ***Examples*** 1. A = {banana, quava, guyabano, papaya} 2. Z={x\|x is a set of integers} **Specifying Sets** - Roster method -- the elements of the set are enumerated and separated by a comma. - Set-builder notation -- a descriptive phrase is used to describe the elements or members of the set. Uses {x \|P(x)} notation. 1. 2. 1. 2. 3. Set builder example 1, - read " Q is a set of those elements x such that x is a rational number. vertical bar means "such that" - symbol x denotes any one element of a set. - Universal set a set of all elements related to a condition under consideration denoted by [∪]{.math.inline}. ***More Examples*** 1. 2. Let *R* be the set of all real numbers; let A be the set of numbers that satisfy the equation x^2^ + 4 = 0. Then the set Has no elements since the square of any real number is nonnegative. Thus, set A is an empty or null set [⌀]{.math.inline}. **Set Equality** - *if and only if every element of set A is also an element of set B and every element of set B is in A.* ***Example*** 1. Let the sets **Subsets** *denoted by A*[⊆]{.math.inline}*B, if every element of A is also an element of B* **Example** 1. Let set B represent the students enrolled in JAVA at PDM, and let Then A [⊆]{.math.inline} [ ] B, that is, set A is a subset of B 2. Consider the sets And, **ℝ** = {x\|x is a real number} Then, A [⊆]{.math.inline} [ ] A and **ℝ** [⊆]{.math.inline} [ ] **ℝ**. - Every element of set A is naturally an element of the same set; set A is a subset of itself, A [⊆]{.math.inline}A. - The null set [⌀]{.math.inline} is a subset of every set. - A and R are non-empty sets, then [⌀]{.math.inline} [⊆]{.math.inline} [ ] *A and* [⌀]{.math.inline} [⊆]{.math.inline} [ ] *R.* A [⊆]{.math.inline} [ ] B then *B* is a superset of A, this relationship is denoted by the symbol B[ ⊇ *A*.]{.math.inline} ***Example*** The set of real numbers **ℝ** is the superset of the set of rational numbers ℚ, In turn, ℚ is the superset of the set of integers ℤ. These relationships are written in symbols below. **ℝ**[⊇]{.math.inline} ℚ [ ⊇ ℤ ]{.math.inline} Set Relationship can be represented graphically by a *Venn Diagram* ***Example*** *A* [ ⊆ *B*]{.math.inline} **Theorem.** Two sets A and B are equal if and only if A[⊆]{.math.inline}B and B [⊆]{.math.inline} A. **Set Inclusion** - a set is a subset of another set, - much broader concept than set equality - two sets A and B may be unequal, yet set A may be a subset of B **Examples** 1. 2. Consider the following sets: C={v,x,y,z} D={w,x,y,z} Then [*C* ≠ *D*]{.math.inline} since v is an element of C only and w is an element of set D only. In such a case of set inequality, neither [*C* ⊆ *D*]{.math.inline} nor [*D* ⊆ *C*]{.math.inline} is true. **Subset Formation** - All set which can be formed from the element of a given set are subsets of the given set. - The total number of all possible subsets depends on the number of elements of the given set. Consider the universal set [*U*]{.math.inline} with none, one, two, and three elements if [*U*]{.math.inline} has no elements so that n([*U*]{.math.inline}*)* =0, then [*U*]{.math.inline} =[⌀]{.math.inline} and the only subset of [⌀]{.math.inline} is the empty itself. Hence, [*U*]{.math.inline} has one (1) subset, which can be written 2^0^. Let [*U*]{.math.inline} *=*{x} so that n([*U*]{.math.inline}*)*=1. The subset of [*U*]{.math.inline} now are [⌀]{.math.inline} and {x}. Hence, [*U*]{.math.inline} has two (2) subsets, which can be written 2^1^. See the table below. Table 1: Subset Formation +-----------------+-----------------+-----------------+-----------------+ | Line [𝒰]{.math | n([𝒰]{.math | Subsets of | Number of | |.inline} |.inline}) | [𝒰]{.math | subsets | | | |.inline} | | | | | | Of [𝒰]{.math | | | | |.inline} | +=================+=================+=================+=================+ | 1. [⌀]{.math | 0 | \ | 1=2^0^ | |.inline} | | [⌀]{.math | | | | 1 |.display}\ | 2=2^1^ | | 2. *{x}* | | | | | | 2 | \ | 4=2^2^ | | 3. *{x,y}* | | [⌀, {*x*}]{.mat | | | | 3 | h | 8=2^3^ | | 4. *{x,y,z}* | |.display}\ | | | | | | | | | | \ | | | | | [⌀, {*x*}, {*y* | | | | | }, {*x*,*y*}]{. | | | | | math | | | | |.display}\ | | | | | | | | | | [⌀, {*x*}, {*y* | | | | | }, {*z*}, {*x*, | | | | | *y*}]{.math | | | | |.inline},{x,z}, | | | | | {y,z}, | | | | | | | | | | {x,y,z} | | +-----------------+-----------------+-----------------+-----------------+ Let U={x ,y} so that n(U) =2. Set U has 2² or 4 subsets. Let U = {x ,y ,z} so that n(U)=3. By the same reasoning, set U has 2³ or 8 subsets. In general, if U has n element, then the number of subsets of U is 2ⁿ. **Set Operation** The most common set operations are complement, union, intersection, difference, symmetric difference, product, and power sets. **Complement** Let A be any subset of a universal set U. Then the complement of A, denoted by A', is the set of Elements of U which are not members of A. In symbols, the definition of the complement is A'= {x ∈ U \| x ∉ A} Read "not A is a set of that element x of U for which x is not an element of A." The set A' is represented by the shaded region. ***Example*** **Let** *U* = { 1, 2, 3, 4, 5, 6, 7 } and consider its subset *A* = { 1, 2, 3} then the set *A'* = { 4, 5, 6, 7 } is the set that contains that element of *U* which are not elements of *A.* **IV. ADDITIONAL RESOURCES** **V. PRACTICE EXERCISES/ACTIVITIES** Let A {1, 2, 3, 4, 5, 6}, B {2, 4, 6}, C {1, 2, 3} and D {7, 8, 9}. Determine which of the following are true, false, or meaningless. 1\. A ⊂ B 2. B ⊂ A 3. B ∈ C 4. ∅ ∈ A 5. ∅ ⊂ A 6\. A \< D 7. 3 ∈ C 8. 3 ⊂ C 9. {3} ⊂ C 10. C ⊂ B **Subset** A {1, 2, 3, 4, 5, 6} B {1, 2, 3} **VI. ASSESSMENT** The instructions for the assessment will be posted in the LMS or to be given in a separate worksheet. **VII. REFERENCES** - Icutan, S.L., Baquiran M.D., Cayabyab S., Cenas P., Parrone J., Patacsil F. 2013. **[Simplified Discrete Mathematics]**. Jimczyville Publications - Stein C., Drysdale R., Bogart K.,2012. **[Discrete Mathematics for Computer Scientists]**. Pearson Education South Asia PTE. LTD. - Sirug, W.2012.**[Fundamentals of Discrete Mathematics.]** Mindshapers Intramuros Manila - Fernadez M. 2010. **[Discrete Mathematics].** Mindshapers Intramuros Manila - Haggard G., Schipt J., Whitesides S. 2009. **[Discrete Mathematics for Engineers and Scientists]**. Cengage Learning Asia Pasig City - http://discrete.openmathbooks.org/dmoi3.html