Week 06 Set Theory Discrete Structures.pptx

Week 06 Set Theory Discrete Structures

1. ( MA-216) - Discrete Structures (Discrete Mathematics) Spring 2025 Set Theory Week- 06

2. Outline Set Application of Sets Sets Notation Set Membership Cardinality of a Set Types of Sets

3. Databases Data-type or type in computer programming Constructing discrete structures Finite state machine Modeling computing machine Representing computational complexity of algorithms Application of Sets

4. A set is an unordered collection of different elements. A set is usually denoted by a capital letter, and its elements are listed within curly braces { } Some Example of Sets A set of all positive integers A set of all the planets in the solar system A set of all the states in USA A set of all the lowercase letters of the alphabet Sets

5. Set notation is a mathematical way to define and represent sets . Roster Notation: The elements of a set are explicitly listed inside curly braces { }. Elements are separated by commas. Example : Set of odd positive integer less than 10 O = {1,3,5,7,9 } Sets Notation

6. Set Builder Notation: Instead of listing elements, it describes a property that all elements must satisfy. Uses the format: O = {x ∈ 𝒁 + | x is odd and x<10 } where | (or : ) means " such that ." Sets Notation (Cont.)

7. If an element is in a set, written as : Example 1 − V = { a , e , i , o , u } A = { x | x is a vowel in English alphabet } a is an element of the set V , denoted by a ∈ V . a is not an element of the set V , denoted by a ∉ V . Set Membership

8. Example: I : {0 , 1, 2, …,99} 50 ∈ I 100 ∉ I S: { a, 2, class} 2 ∈ S room ∉ S Set Membership (Cont.)

9. Set of natural numbers 𝐍 = {1,2,3,…} Set of integers 𝐙 = {…,-2,-1,0,1,2,…} Set of positive integers 𝐙 + = {1,2,3,…} Set of rational numbers 𝐐 = {p/q | p ∈ 𝐙 , q ∈ 𝐙 , and q ≠ 0} Set of real numbers 𝐑 Set of Whole Numbers W ={0,1,2,3,4,5,…} Important Sets

10. Cardinality of a set S, is the number of elements of the set and denoted by | S | . The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞ . Example : S = {1,4,3,5} W = {1,2,3,4,5,…} Cardinality:  | S | = 4,| W | = ∞ Cardinality of a Set

11. Find cardinality of following sets . A = {x | x ∈ 𝐙 + , x is odd and x<10} A = {1,3,5,7,9} |A| = 5 B = Ø |B| = C = {Ø} |C| = 1 R R is infinite. Cardinality of a Set (Cont.)

12. Two sets A and B are equal if and only if they contain exactly the same elements, regardless of the order. This is written as: A=B A and B are equal if and only if ∀ x (x ∈ A ↔ x ∈ B ). "for every element x , if x is in A , then x must also be in B , and vice versa." Equality of Sets

13. Example 1: Let: A = { 1,2,3 }, B = { 3,1,2 } Since both sets contain exactly the same elements . we say: A=B Equality of Sets (Cont.) Example 2: Unequal Sets A = { 1,2,3 }, B = { 1,2,4 } Here: A contains 3, but B contains 4 instead. Since they have different elements we say: A ≠ B

14. Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc . Finite Set A set which contains a definite number of elements is called a finite set . Example : S = { X | X ∈ N and 70 > X > 50 } Types of Sets

15. Infinite Set A set which contains infinite number of elements is called an infinite set . Example − S ={ x | x ∈ N and x >10} Types of Sets (Cont.)

16. It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set . Universal sets are represented as U . Universal Set

17. Example − We may define U as: The set of all animals on earth. In this case, set of all mammals is a subset of U , set of all fishes is a subset of U , set of all insects is a subset of U , and so on . U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}  A = {2, 4, 6, 8, 10}, B = {1, 3, 5, 7, 9 } For the set of the vowels of the alphabet, U would be all the letters of the alphabet Universal Set (Cont.)

18. An empty set contains no elements. It is denoted by ∅ . As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero . Example : S = ∅ S = { x | x ∈ N and 7< x <8}=∅ Empty Set or Null Set

19. Example : S = {x | x ∈ 𝑍 + and x < } S = { } = Ø A set that has no elements called empty set , or null set . Ø and { Ø} Ø ≠ { Ø} Empty Set or Null Set (Cont.)

20. Singleton set or unit set contains only one element. A singleton set is denoted by { s }. Example : S = {8 } S ={ x | x ∈ N ,  7 < X < 9 } Singleton Set or Unit Set

21. Set can contain other sets S = { {1}, {2}, {3} } T = { {1}, {{2}}, {{{3}}} } V = { { {1}, {{2}} }, { {{3}} }, { {1}, {{2}}, {{{3}}} } } V has only 3 elements! Note that 1 ≠ {1} ≠ {{1}} ≠ {{{1}}} They are all different Set Of Sets

22. Let A and B be sets . A is a subset of B if and only if every element of A is also an element of B . D enoted by A ⊆ B . A ⊆ B if and only if ∀ x (x ∈ A → x ∈ B ). A is a subset of B if and only if, for all x, if x is an element of A, then x is an element of B ∀ set S, Ø ⊆ S , S ⊆ S Subset

23. A ⊆ B, ∀ x (x ∈ A → x ∈ B) and B ⊆ A, ∀ x (x ∈ B → x ∈ A) then A = B, ∀ x (x ∈ A ↔ x ∈ B) Subset and Equality

24. Example Q and R Q ⊆ R N and Z N ⊆ Z A = {x | x ∈ 𝐙 + and x<10} B = {x | x ∈ 𝐙 + , x is even and x<10} B ⊆ A Subset (Cont.)

25. Let A and B be sets. A is a proper subset of B if and only if A ⊆ B but A ≠ B, denoted A ⊂ B. A ⊂ B if and only if ∀ x (x ∈ A  x ∈ B) ˄  x (x ∈ B ˄ x ∉ A). Proper Subset

26. If S is a subset of T , and S is not equal to T , then S is a proper subset of T Let : T = {0, 1, 2, 3, 4, 5} and S = {1, 2, 3} S is not equal to T , and S is a subset of T Let Q = {4, 5, 6}. Q is neither a subset of T nor a proper subset of T The difference between “subset” and “proper subset” is like the difference between “less than or equal to” and “less than” for numbers Proper Subset (Cont.)

27. Let S be a set . The power set of S is the set of all subsets of S, denoted by P(S ). Example: S = {a, b} P(s)  P ({ a ,b }) = {Ø ,{a} ,{b} ,{ a ,b }} Using:   The Power Set

28. What is P({1,2,3})? Solution: P({1,2,3}) = { Ø, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} } P(Ø) = ? P({Ø}) = ? The Power Set (Cont.)

29. Assume A is finite. |P(A)| = ? Solution: A = {a} A = {a,b} A = {a,b,c} P(A) = {Ø, {a}} P(A) = {Ø, {a}, {b}, {a,b}} |P(A)| = 2 |P(A)| = 4 P(A)={Ø,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} |P(A)| = 8 |P(A)| = 2 |A| The Cardinality of the Power Set

30. Two sets that have at least one common element are called overlapping sets. In case of overlapping sets . Example − Let, A ={1,2,6} and B ={6,12,42 }. There is a common element ‘6’, hence these sets are overlapping sets. Overlapping Set

31. Two sets A and B are called disjoint sets if they do not have even one element in common . Example − Let, A ={1,2,6} and B ={7,9,14 } There is not a single common element, hence these sets are disjoint sets . Disjoint Set

32. Venn diagram, invented in 1880 by John Venn, is a schematic diagram that shows all possible logical relations between different mathematical sets. Venn Diagrams

33. Chapter Reading Chapter # 2 , Kenneth H. Rosen, Discrete Mathematics and Its Applications, Section 2.1 Exercise Questions Question # 1,3,5,6,7,9,12,19,20,23,32,43,44

34. Thanks ...?