CSC 203 - Discrete Structures Sets PDF

CSC 203 - Discrete Structures Sets Properties of Sets Professor Nwojo A. Nnanna [email protected] Nile University of Nigeria, Abuja October 10, 2024 Table of Contents Outline Table of Contents Outline Sets and Subsets Table of C...

CSC 203 - Discrete Structures Sets Properties of Sets Professor Nwojo A. Nnanna [email protected] Nile University of Nigeria, Abuja October 10, 2024 Table of Contents Outline Table of Contents Outline Sets and Subsets Table of Contents Outline Sets and Subsets Operations on Sets Sets and Subsets Sets and Subsets Definition A set is an unordered collection of distinct objects. The objects in a set are called the elements, or members, of the set. A set is said to contain its elements. Clearly, in a set, order is unimportant. Thus, {a, b, c, d} ≡ {d, a, c, b}. Definition The set of natural numbers, denoted by N, is defined as {1, 2, 3,... }1. 1 Some authors include the number 0 in this set while others strictly regard the set of natural numbers as the numbers used in counting. The set of integers, denoted by Z, is given by Z = {... , −3, −2, −1, 0, 1, 2, 3,... }. In set builder notation, we have Z+ = {x : x ∈ Z and x > 0}. { } p Q= : p, q ∈ Z, q ̸= 0. q Equality of Sets Definition (Equality of Sets) Two sets are equal if and only if they have the same elements. More formally, for sets A and B, A = B if and only if ∀x[x ∈ A ⇒ x ∈ B and x ∈ B ⇒ x ∈ A]. Example {a, b, c} = {b, c, a}, that is the order of the objects does not matter. Moreover, duplications of the elements of a set do not make any difference; thus, {a, b, c} = {b, c, a, a, b}. (1) Definition A set A is called finite if it has n distinct elements, where n ∈ N. In this case, n is called the cardinality of A and is denoted by |A|. A set is called infinite if it is not finite. Suppose A is a set. Then the set of all subsets of A is called the power set of A and is denoted by P(A). Example Consider the set A = {a, b, c, d}. The power set of A is P(A) = {∅, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {b, c, d}, {a, b, c, d}}. Operations on sets Sets can be combined in a number of different ways to produce another set. Here five basic operations are introduced and their properties are discussed. Definition (Union) The union of sets A and B, denoted by A ∪ B, is the set defined as A ∪ B = {x|x ∈ A or x ∈ B} Example If A = {1, 2, 3} and B = {4, 5}, then A ∪ B = {1, 2, 3, 4, 5}. Example If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A ∪ B = {1, 2, 3, 4, 5}. Note that elements are not repeated in a set. Definition (Intersection) The intersection of sets A and B, denoted by A ∩ B, is the set defined as A ∩ B = {x|x ∈ A and x ∈ B} Example If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A ∩ B = {1, 2}. Example If A = {1, 2, 3} and B = {4, 5}, then A ∩ B = ∅. Definition (Difference) The difference of sets A from B, denoted by A − B, is the set defined as A − B = {x|x ∈ A and x ∈/ B} Example If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A − B = {3}. Example If A = {1, 2, 3} and B = {4, 5}, then A − B = {1, 2, 3}. Note that in general A − B ̸= B − A. Complement Definition (Complement) For a set A, the difference U − A, where U is the universe, is called the complement of A and it is denoted by A. Thus A is the set of everything that is not in A. Definition (Symmetric Difference) If A and B are sets, then the symmetric difference of the two sets is defined as the set of all the elements that are in A or in B, but not in both A and B. This difference denoted by A ⊕ B, hence A ⊕ B = {x|(x ∈ A and x ∈ / B) or (x ∈ B and x ∈ / A)}. The fifth set operation is the Cartesian product We first define an ordered pair and Cartesian product of two sets using it. Then the Cartesian product of multiple sets is defined using the concept of n-tuple. Definition (Ordered pair) An ordered pair is a pair of objects with an order associated with them. If objects are represented by x and y, then we write the ordered pair as < x, y >. Two ordered pairs < a, b > and < c, d > are equal if and only if a = c and b = d. For example the ordered pair < 1, 2 > is not equal to the ordered pair < 2, 1 >. Cartesian product Definition (Cartesian product) The set of all ordered pairs < a, b >, where a is an element of A and b is an element of B, is called the Cartesian product of A and B and is denoted by A × B. Example Let A = {1, 2, 3} and B = {a, b}. Then A × B = {< 1, a >, < 1, b >, < 2, a >, < 2, b >, < 3, a >, < 3, b >}. Example For the same A and B as in Example 20, B × A = {< a, 1 >, < a, 2 >, < a, 3 >, < b, 1 >, < b, 2 >, < b, 3 >}. As you can see in these examples, in general, A × B ̸= B × A unless A = ∅, B = ∅ or A = B. Note that A × ∅ = ∅ × A = ∅ because there is no element in ∅ to form ordered pairs with elements of A. The concept of Cartesian product can be extended to that of more than two sets. First we are going to define the concept of ordered n-tuple. Definition (ordered n-tuple) An ordered n-tuple is a set of n objects with an order associated with them. If n objects are represented by x1 , x2 ,... , xn , then we write the ordered n-tuple as < x1 , x2 ,..., xn >. Definition (Cartesian product) Let A1 ,... , An be n sets. Then the set of all ordered n-tuples < x1 ,..., xn >, where xi ∈ Ai for all i, 1 ≤ i ≤ n, is called the Cartesian product of A1 ,... , An , and is denoted by A1 × A2 ×... × An. Example Let A = {1, 2}, B = {a, b} and C = {5, 6}. Then A × B × C = {< 1, a, 5 >, < 1, a, 6 >, < 1, b, 5 >, < 1, b, 6 >, < 2, a, 5 >, < 2, a, 6 >, < 2, b, 5 >, < 2, b, 6 >}. Definition (equality of n-tuples) Two ordered n-tuples < x1 ,... , xn > and < y1 ,... , yn > are equal if and only if xi = yi for all i, 1 ≤ i ≤ n. For example the ordered 3-tuple < 1, 2, 3 > is not equal to the ordered n-tuple < 2, 3, 1 >. Theorem The operations on sets satisfy the following properties: Commutative Properties: 1. A ∪ B = B ∪ A 2. A ∩ B = B ∩ A Associative Properties: 3. A ∪ (B ∪ C) = (A ∪ B) ∪ C 4. A ∩ (B ∩ C) = (A ∩ B) ∩ C Distributive Properties: 5. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 6. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Commutative Properties: 7. A ∪ A = A 8. A ∩ A = A Theorem The operations on sets satisfy the following properties: Properties of Complement: 9. (A) = A 10. A ∪ A = U 11. A ∩ A = ∅ 12. ∅ = U 13. U = ∅ 14. A ∪ B = A ∩ B Properties 14 and 15 are known as 15. A ∩ B = A ∪ B De Morgan’s laws. Properties of a Universal Set: 16. A ∪ U = U 17. A ∩ U = A Properties of the Empty Set: 18. A ∪ ∅ = A or A ∪ {} = A 19 A ∩ ∅ = ∅ or A ∩ {} = {} The Addition Principle Theorem If A and B are finite sets, then |A ∪ B| = |A| + |B|.