Sets and Set Operations
SCC121 Fundamentals of Computer Science
Professor Corina Sas
School of Computing and Communications
Recap: Sets and Membership
Definition of Sets:
A set is a collection of distinct objects.
Example: A = {a, b, c}
A is the set, and a, b, c are its elements.
Curly braces { } are markers for the beginning and the end of the set.
Membership Notation:
a ∈ A: Indicates that element a belongs to (or is in) set A.
m ∉ A: Indicates that element m does not belong to (or is not in) set A.
Defining Sets Through Properties:
Example: The set of natural numbers x such that x < 10 can be defined as:
{x | x ∈ N ext{ and } x < 10}
Recap: Set Operations
Operations on Sets:
Union (A ∪ B):
The set of elements in A, or B, or both.
Intersection (A ∩ B):
The set of elements common to both A and B.
Difference (A - B):
The set of elements in A that are not in B.
Cartesian Product (A × B):
The set of all possible ordered pairs where the first element comes from set A and the second comes from set B.
Specific Examples of Set Operations
Example Calculations:
Given: A = {a, b, c, y}, B = {b, c, d, e, y}, C = {x, a}
Calculation of Union and Intersection:
Union: A ∪ (B ∩ C)
Calculation:
A ∪ (B ∩ C) = A ∪ empty set = A = {a, b, c, y}
Intersection: (A ∪ B) ∩ C
Calculation:
(A ∪ B) ∩ C = {a, b, c, d, e, y} ∩ C = {y}
Summary of Set Operations
Set Operations Notation and Meaning:
A ∪ B: Union - objects that belong to set A or set B.
A ∩ B: Intersection - objects that belong to both sets A and B.
A - B: Difference - objects that belong to set A but not set B.
A × B: Cartesian Product - all ordered pairs with the first element from A and the second from B.
Types of Sets
Overview and Objectives
Topics Covered:
Defining sets
Set operations
Types of sets
Objectives:
Understanding the different types of sets and the relationships among them.
Categories of Sets
Empty Set
Disjoint Sets
Equal Sets
Sets of Sets
Subsets and Proper Subsets
Supersets and Proper Supersets
Universal Sets
Complement Sets
Empty Set
Definition:
The empty set is a set that contains no objects.
Also known as the null set or void set.
Notation for empty set: { } or the symbol ∅.
Example:
A = { } is an empty set.
A = ∅.
Disjoint Sets
Definition:
Two sets are disjoint if they have no elements in common.
Formally, two sets are disjoint if their intersection is the empty set.
Examples:
Sets {New York, Washington} and {3, 4} are disjoint.
Sets {1, 2} and ∅ are disjoint.
Sets {1, 2, 3} and {3, 4, 5} are not disjoint since they share element 3.
Equal Sets
Definition:
Two sets are equal if they have the same elements.
Written as: A = B
For equality, every element of set A must also be in set B, and vice versa.
Example:
A = {a, b, c, d, e}; B = {d, b, c, e, a}
Conclusion: A = B
Not Equal Sets
Definition:
Two sets are not equal if there is at least one element in one of the sets that is not present in the other.
Written as: A ≠ B
Examples:
A = {a, b, c, d, e}; B = {d, b, c, e} are not equal sets since a ∈ A but a ∉ B.
C = {1, 2} and D = {2, 1, 3} are not equal sets because 3 ∈ D but 3 ∉ C.
Sets of Sets
Definition:
Sets can contain atomic elements (letters, numbers) or other sets.
Examples:
A = {a, {b, c}} is a set containing element a and another set consisting of elements b and c.
B = {{a}}.
C = {∅} where {∅} ≠ ∅.
Cardinality of Sets
Definition:
Cardinality of a set is the number of its elements, written as |A|.
Examples:
Let A = {1, 2, 3, 4, 5}. Then |A| = 5.
|∅| = 0.
Let B = {∅, {a}, {b}, {a, b}}. Then |B| = 4.
Singleton set: A set with one element, e.g., A = {a} or B = {{a}}.
Subsets
Definition:
Set A is a subset of set B if every element of set A is also an element of B.
Written as: A ⊆ B.
The sets may also be equal: A = B.
Example:
A = {a, b, c} and B = {a, b, c, d, e}.
Verification: a ∈ B, b ∈ B, c ∈ B ⇒ A ⊆ B.
Non-Subset Example: A ⊈ B if there is at least one element in A not in B.
Example: A = {1, 2, 3}, B = {4, 5} ⇒ 1 ∉ B, thus A ⊈ B.
Proper Subsets
Definition:
A is a proper subset of set B if A is a subset of B and A is not equal to B.
Written as: A ⊂ B.
Example:
If A = {a,b,c} and B = {a,b,c,d,e}, then A ⊂ B.
Proper Subset Verification:
{1, 2} ⊂ {1, 2, 3} since the latter contains at least one additional element.
Supersets
Definition:
Set B is a superset of set A if every element of A is also an element of B.
Written as: B ⊇ A.
Verification:
If B is a superset of A, A ⊆ B holds.
Example:
If A = {a, b, c}, then it can be stated B = {a, b, c, d, e} means B ⊇ A.
Proper Supersets
Definition:
B is a proper superset of A if there is at least one element in B that is not in A.
Written as: B ⊃ A.
Verification:
For B ⊃ A, A must also be a proper subset of B, meaning A ⊂ B.
Universal Sets
Definition:
A universal set is a non-empty set that contains all possible elements relevant to a specific problem. Denoted by U.
Examples:
Set of natural numbers N for counting.
Set of alphabet letters for spelling.
Example universal set:
Complement Sets
Definition:
The complement set is the difference between the universe and a given set.
Denoted as: comp(A) = U - A.
Example:
If U = {red, orange, yellow, green, blue, indigo, violet} and A = {red, yellow, blue}, then:
Summary of Set Properties
Symbol | Symbol Name | Meaning
∅ | Empty set | A set with no elements.
Disjoint sets | Sets whose intersection is the empty set.
A = B | Equal sets | Sets with the same elements.
A ≠ B | Not equal sets | Sets that do not have the same elements.
|A| | Set cardinality | Number of elements in a set A.
A ⊆ B | Subset | Elements of set A are also in set B.
A ⊂ B | Proper subset | A is a subset, and there is at least one element in set B that is not in set A.
B ⊇ A | Superset | Elements of A are also in B.
B ⊃ A | Proper superset | B is a superset and has at least one element not in A.
U | Universal set | Set of all possible elements relevant to a specific problem.
comp(A) | Complement set | Difference between the universe and set A.