DISCRETE 1 (NOTE)
Set Defined
A set is a well-defined and unordered collection/aggregate of objects of any kind.
The objects in a set are referred to as elements or members of the set.
Sets are denoted by upper-case/capital letters.
Example of Well-Defined Sets
1) The set of all official James Bond films made by EON Productions.
2) The set of best TV shows of all time.
3) The 10 top-selling recording artists of 2016.
4) The set of great rap artists.
Set Notation
Roster Method (Listing Method)
Example:
S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Descriptive or Set Builder Method
Example:
S = {whole numbers less than 10}
Universal Set
The universal set, denoted as U, contains all elements relevant to a particular discussion or problem.
Example:
U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Element Notation
If x ∈ S, then x is an element of S.
If x ∉ S, then x is NOT an element of S.
Example:
If E is the set of even numbers:
2 ∈ E: 2 is an element of set E.
3 ∉ E: 3 is NOT an element of set E.
Finite Set
A finite set is one where the number of elements in the set is countable.
Example:
A = {whole numbers less than 5} = {4, 3, 2, 1, 0}
There are 5 elements in this set.
B = {letters of the alphabet}
There are 26 elements in this set.
Infinite Set
An infinite set is one where the number of elements in the set is NOT countable.
Example:
X = {even whole numbers} = {2, 4, 6, 8, …}
Y = {multiples of 100} = {100, 200, 300, …}
The three dots (…) indicate that the list goes on, hence the elements are infinite.
Set Equality
Two given sets are equal if and only if they contain exactly the same elements.
Example:
Are the following sets equal?
1) A = {9, 2, 7, -3}, B = {7, 9, -3, 2}
2) A = {a, b, c}, B = {c, a, b}
3) A = {1, 2, 3}, B = {1, 3, 5}
4) A = {dog, cat, horse}, B = {cat, horse, squirrel, dog}
5) A = {dog, cat, horse}, B = {cat, horse, dog, dog}
6) A = {1, 2}, B = {1, 1, 1, 2, 2, 2}
7) {3} = {x | x is a counting number between 2 and 5}
8) {11, 12, 13…} = {x | x is a natural number greater than 10}
Subset
A subset is defined as a set contained within a larger set or equal to it.
Given U as the universal set of all numbers:
Symbolically: A ⊆ U if ∀x [x ∈ A → x ∈ U]
This means A is a subset of U if for every x: if x is an element of A, then x is an element of U.
Example to Determine if Set A is a Subset of Set U:
1) A = {4, 5, 6}
The elements 4, 5, 6 of set A are in Set U, hence A ⊆ U.
2) A = {…, -8, -4, 0, 4, 8, …}
The elements of set A (multiples of 4) are in Set U, hence A ⊆ U.
3) A = {3, a, 5, b, 7, c}
The elements a, b, c are not numbers and not in set U, hence A ⊄ U.
Practice Exercise
Determine whether set A is a subset of set U:
1) A = {rain, snow, sleet}
2) A = {1.5, 20%, 33, π}
3) A = {x | x is a rational number}
4) A = {3a, 2x, -1y}
Proper Subset
A proper subset is a subset that is not equal to the set it belongs to.
Symbolically: A ⊂ B if A ⊆ B and A ≠ B.
This means A is a proper subset of B.
A ⊂ B: A is a proper subset of B.
A ⊆ B: A is a subset of B.
A ≠ B: A is not equal to B.
A is a proper subset of B if A is a subset of B and A is not equal to B.
Example to Determine if Set A is a Proper Subset of Set B:
1) A = {dog, cat}, B = {dog, cat, bird, fish}
2) A = {dog, bird, fish, cat}, B = {dog, cat, bird, fish}
3) A = {red, blue, yellow}, B = {red, orange, yellow, green, blue, violet}
4) A = {jazz, pop, hip hop}, B = {classical, jazz, pop, rap, hip hop}
Practice Exercise
Determine whether set A is a proper subset of set B:
1) A = {car, bus, train}, B = {train, car, bus}
2) A = {a, b, c, d}, B = {a, c, b, d}
Number of Subsets
The number of subsets of a set with n elements is given by the formula .
Example to Determine the Number of Subsets:
1) A = {dog, cat}
2) B = {dog, cat, bird, fish}
Number of Proper Subsets
The number of proper subsets of a set with n elements is given by the formula .
Example to Determine the Number of Proper Subsets:
1) A = {dog, cat}
2) B = {dog, cat, bird, fish}
Example
Determine the number and list all distinct subsets and proper subsets of the set {t, a, p, e}.
Practice Exercise
Determine the number and list all distinct subsets and proper subsets of the following sets:
{S, L, E, D}
{1, 2}
{a, b, c}
Venn Diagram
A Venn diagram visually represents sets of items or numbers by using their logical relationships to decide how they should be grouped together.
The universal set is usually depicted as a large rectangle, while other sets are represented by circles within this rectangle.
Example:
Let the universal set U be the set of the letters of the alphabet and subset V be the set of all vowels.
Algebra of Sets
The algebra of sets encompasses the fundamental properties of set operations and set relations.
It is analogous to the algebra of numbers with respect to theories.
Fundamental laws of set algebra include:
Complement
Union
Intersection
Set Complement
The complement of a set S is the set of all elements of U that are not in S.
Denoted as S' or Sc.
Example:
If U = {letters of the alphabet} and V = {vowels}, then V' = {not vowels or consonants}.
Set Intersection (∩)
The intersection of two sets A and B consists of all elements belonging to both A and B.
This is written as A ∩ B.
Example:
If A = {girls} and B = {adults}, then A ∩ B = {adults who are girls}.
If C = {0, 1, 2, 3, …, 98, 99, 100} and D = {50, 100, 150, 200, 250, …}, then C ∩ D = {50, 100}.
Set Union (∪)
The union of two sets A and B consists of all elements belonging to either A or B.
This is written as A ∪ B.
Example:
If A = {even numbers} and B = {odd numbers}, then A ∪ B = {even and odd numbers}.
If C = {1, 2, 3, 4, 5} and D = {6, 7, 8, 9, 10}, then C ∪ D = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Set Difference (-)
The difference of set A and set B, denoted A – B, consists of elements of set A that are not in set B.
The difference of set B and set A, denoted B – A, consists of elements of set B that are not in set A.
Example:
If A = {1, 2, 3, …, 9, 10} and B = {2, 4, 6, 8, 10}, then:
A – B = {1, 3, 5, 7, 9}
B – A = {} (null set), since all elements of set B are in set A.
Symmetric Difference (⊕)
The symmetric difference between any two sets contains all elements present in either of the sets but not in their intersection.
It is the complement of the intersection of the sets.
Example:
If A = {3, 6, 9} and B = {2, 4, 6, 8, 10}, then A ⊕ B = {2, 3, 4, 8, 9, 10}.
The element {6} is in both sets A and B, hence not included in their symmetric difference. Also, A ∩ B = {6} and therefore (A ∩ B)’ = A ⊕ B = {2, 3, 4, 8, 9, 10}.
Sample Problem
A set of students were asked which sports they played in school: Football, Basketball, and Volleyball.
The tally of the results is as follows:
Name | Football | Basketball | Volleyball
Alex | ✓ | ✓ | -
Daniel | ✓ | ✓ | -
Debbie | - | - | -
Ellen | ✓ | - | -
James | ✓ | - | -
Jane | - | ✓ | -
Jenny | - | - | ✓
Jessica | - | ✓ | -
John | ✓ | - | ✓
Luisa | - | ✓ | ✓
Mary | - | ✓ | ✓
Ruben | ✓ | - | -
William | ✓ | ✓ | ✓
Use a Venn Diagram to Illustrate the Results
Answer Questions:
a. Who plays all three sports?
(B ∩ V ∩ F) = Mary and William
b. Who plays both volleyball and basketball?
V ∪ B = Daniel and Luisa
c. Who plays none of the three sports?
A’ U B’ U C’ = Debbie
Practice Exercise
Let U = {1, 2, 3, 4, 5, 6, 7, 8} and subset A = {1, 3, 4}. Find A’.
Let A = {±, ↑, ⇑, |, ⊕, ≠, ⟩, •, ◈} and B = {↑, }. Determine A ∩ B.
Let A = {², ù, õ, ½, §, d} and B = {ù, b, ½, @, d, Ó}. Determine A ∪ B.
Let A = {1, 2, 3, 4, 5, 6, 7} and B = {2, 4, 6, 8, 10}. Determine A – B.
Let A = {a, e, i, o, u} and B = {e, o, n, s}. Determine A ⊕ B.
Reference
Busby, R., Kolman, B., & Ross, S. (2022). Discrete Mathematical Structures: Pearson New International (6th ed). Pearson Education Limited.