Discrete Structures - Set Theory and Set Operations
Fundamentals of Set Theory
Definition of a Set:
A set is the fundamental discrete structure upon which all other discrete structures are built.
Sets are used to group objects together. Frequently, the objects grouped within a set share similar properties.
Formally, a set is defined as an unordered collection of objects.
The objects contained within a set are designated as the elements or members of the set.
Fundamental Membership Notation:
Uppercase letters (e.g., , , ) are used to represent sets.
Lowercase letters (e.g., , , ) are used to represent elements.
The expression denotes that is an element of set (read as " is a member of " or " is in ").
The expression denotes that is not an element of set .
Important Numerical Sets
The Set of Natural Numbers:
The Set of Integers:
The Set of Positive Integers:
The Set of Rational Numbers (Fractions):
Expressed in set-builder notation:
The Set of Real Numbers:
Set Equality and Description Methods
Set Equality:
Two sets are equal if and only if they contain precisely the same elements.
Logical notation: .
Alternative criterion: Two sets and are equal if and only if and .
To formally prove that set equals set , one must demonstrate two sub-proofs:
Order independence: The set is equal to .
Repetition invariance: The set is equal to because both sets contain the exact same distinct elements.
Methods for Describing Sets:
Roster or Listing Notation:
Explicitly listing all members between curly braces .
Example:
Example: The set of odd positive integers less than is represented as .
Ellipsis Notation:
Used when a set contains many elements or is infinite, provided the underlying pattern is clear.
Example: The set of positive integers less than is denoted as .
Set-Builder Notation:
Characterizes elements by specifying the precise condition or property required for membership.
Example:
Example specifying the universal domain:
Summary of Set Characterization Approaches:
Explicitly:
Implicitly: or
Set-builder: , , or generally where represents a predicate statement.
Special Sets and Computer Science Applications
The Empty Set (Null Set):
The unique set containing no elements, denoted by or .
Example: The set of all positive integers that are strictly greater than their squares is the null set .
Singleton Set:
Any set that contains exactly one element.
Set Concepts in Computer Science:
The concept of a data type (or type) in computer programming and computer science is constructed directly upon the set concept.
A data type is defined as the name of a set together with a set of operations that can be performed on objects from that set.
Example: The Boolean data type is the name of the set combined with logical operators defined on elements of this set, such as , , and .
Venn Diagrams
Graphical Representation:
Sets can be depicted visually using Venn diagrams.
The Universal Set () encompasses all objects under consideration and is depicted as a rectangle.
Individual sets within the universal set are depicted as circles or closed geometric shapes inside the rectangle.
Individual elements inside sets may be represented as labeled points.
Example: A Venn diagram representing , the set of vowels in the English alphabet, positioned within the universal set .

Subsets and Proper Subsets
Subsets:
A set is a subset of set if and only if every element of is also an element of
Notation:
Predicate logic representation:
Example: The set of odd positive integers less than is a subset of the set of all positive integers.
Example: The set of rational numbers is a subset of the set of real numbers .

Universal Subset Theorems:
For any arbitrary set :
(The empty set is a subset of every set)
(Every set is a subset of itself)
Proper Subsets:
Set is a proper subset of set if is a subset of but .
Notation:
Predicate logic representation:
Subset Evaluation Examples:
is True.
is True.
Is ? Yes.
Is ? No.
Is ? Yes.
Is ? Yes.
Is ? Yes.
Is ? Yes.
Is ? Yes.
Is ? No.
Finite Sets, Infinite Sets, and Cardinality
Finite Sets:
Let be a set. If there are exactly distinct elements in , where is a nonnegative integer, is a finite set.
The integer is called the cardinality of .
Symbol for cardinality:
Infinite Sets:
A set is infinite if it is not finite (e.g., the set of positive integers ).
Cardinality Rules and Formulas:
When evaluating cardinality, only distinct, unrepeated elements are counted.
Inclusion-Exclusion Principle for two finite sets:
Cardinality Evaluation Examples:
For ,
For ,
For ,
For ,
For , is infinite
Power Sets
Definition and Purpose:
Many computational problems require evaluating all combinations of elements of a set to test if they satisfy specific conditions.
Given a set , the power set of is the set of all subsets of .
Notation: or .
Cardinality of a Power Set: If a set has elements (), its power set contains elements.
Minimal cardinality property: The power set of any set contains at least two elements (the empty set and the set itself), except when , in which case containing element ().
Worked Power Set Examples:
Power set of :
(total of subsets)
Power set of empty set ,
Power set of ,
Quick Quiz Exercises:
If ,
If ,
If ,
If ,
Ordered Tuples and Cartesian Products
Ordered -tuples:
Because sets are unordered, a distinct structure is necessary to represent ordered collections.
An ordered -tuple is an ordered collection having as its first element, as its second element, …, and as its -th element.
Two ordered -tuples are equal if and only if each corresponding pair of elements is equal: for all .
Cartesian Product:
Let and be sets. The Cartesian product of and , denoted by , is the set of all ordered pairs such that and
Set-builder definition:
Extension to sets:
Non-commutativity: In general, unless or one of the sets is empty.
Cartesian Product Examples:
Let and :
Let , , and , find :
Set Operations
Union:
The union of sets and is the set containing elements in , in , or in both.
Definition:
Example: If and , then .
Intersection:
The intersection of sets and is the set containing elements present in both and B$.\n - Definition: A \cap B = {x \mid x \in A \land x \in B}\n - Example 1: If A = {\text{Charlie}, \text{Lucy}, \text{Linus}}B = {\text{Lucy}, \text{Desi}}$, then .
Example 2: If and B = \{x \mid x \text{ is deceased}\}$, then A \cap B = {x \mid x \text{ is a deceased US president}}.\n\n- Disjoint Sets:\n - Two sets ABA \cap B = \emptyset.\n - Example: If A = {x \mid x \text{ is a US president}}B = {x \mid x \text{ is in this room}}$, then .
Complement:
The complement of a set consists of all elements in the universal set that are not in A$.\n - Definition: \bar{A} = A' = {x \mid x otin A}\n - Example: If A = {x \mid x \text{ is bored}}$, then .
Properties of Complements:
Difference (Relative Complement):
The set difference consists of elements in that are not in B$.\n - Definition: A - B = {x \mid x \in A \land x otin B}\n - Identity relationship: A - B = A \cap \bar{B}\n\n- Symmetric Difference:\n - The symmetric difference A \oplus BAB, but not both.\n - Definition: A \oplus B = {x \mid (x \in A \land x otin B) \lor (x \in B \land x otin A)}\n - Alternative formulation: A \oplus B = (A - B) \cup (B - A)\n - Behavior: Operates identically to logical "exclusive or" (XOR).\n - Example: Let A = {1, 2, 3, 4, 5, 6, 7}B = {3, 4, p, q, r, s}.\n - A \cup B = {1, 2, 3, 4, 5, 6, 7, p, q, r, s}\n - A \cap B = {3, 4}\n - A \oplus B = {1, 2, 5, 6, 7, p, q, r, s}\n\n# Set Identities and Proofs\n\n- Important Set Identities:\n - Identity Laws: A \cup \emptyset = AA \cap U = A\n - Domination Laws: A \cup U = UA \cap \emptyset = \emptyset\n - Idempotent Laws: A \cup A = AA \cap A = A\n - Complementation Law: \overline{(\bar{A})} = A\n - Commutative Laws: A \cup B = B \cup AA \cap B = B \cap A\n - Associative Laws: A \cup (B \cup C) = (A \cup B) \cup CA \cap (B \cap C) = (A \cap B) \cap C\n - Distributive Laws:\n - A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\n - A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\n - De Morgan's Laws:\n - \overline{A \cup B} = \bar{A} \cap \bar{B}\n - \overline{A \cap B} = \bar{A} \cup \bar{B}\n - Absorption Laws: A \cup (A \cap B) = AA \cap (A \cup B) = A\n - Complement Laws: A \cup \bar{A} = UA \cap \bar{A} = \emptyset\n\n- Proving Set Identities Using Membership Tables:\n - A membership table records a 10 if it does not.\n - Proof of Distributive Property A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\n\n\n\n - Detailed Truth Table Values:\n - Row 1 (A=1, B=1, C=1B \cup C = 1A \cap (B \cup C) = 1A \cap B = 1A \cap C = 1(A \cap B) \cup (A \cap C) = 1\n - Row 2 (A=1, B=1, C=0B \cup C = 1A \cap (B \cup C) = 1A \cap B = 1A \cap C = 0(A \cap B) \cup (A \cap C) = 1\n - Row 3 (A=1, B=0, C=1B \cup C = 1A \cap (B \cup C) = 1A \cap B = 0A \cap C = 1(A \cap B) \cup (A \cap C) = 1\n - Row 4 (A=1, B=0, C=0B \cup C = 0A \cap (B \cup C) = 0A \cap B = 0A \cap C = 0(A \cap B) \cup (A \cap C) = 0\n - Row 5 (A=0, B=1, C=1B \cup C = 1A \cap (B \cup C) = 0A \cap B = 0A \cap C = 0(A \cap B) \cup (A \cap C) = 0\n - Row 6 (A=0, B=1, C=0B \cup C = 1A \cap (B \cup C) = 0A \cap B = 0A \cap C = 0(A \cap B) \cup (A \cap C) = 0\n - Row 7 (A=0, B=0, C=1B \cup C = 1A \cap (B \cup C) = 0A \cap B = 0A \cap C = 0(A \cap B) \cup (A \cap C) = 0\n - Row 8 (A=0, B=0, C=0B \cup C = 0A \cap (B \cup C) = 0A \cap B = 0A \cap C = 0(A \cap B) \cup (A \cap C) = 0\n - Conclusion: Since the column for A \cap (B \cup C)(A \cap B) \cup (A \cap C) identically across all 8 possible combinations, the identity is verified.\n\n# Practice Exercises and Complete Solutions\n\n- Exercise 1: List the members of these sets:\n - a) {x \mid x \text{ is a real number such that } x^2 = 1}\n - Solution: {-1, 1}\n - b) {x \mid x \text{ is a positive integer less than } 12}\n - Solution: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}\n - c) {x \mid x \text{ is the square of an integer and } x < 100}\n - Solution: {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}\n - d) {x \mid x \text{ is an integer such that } x^2 = 2}\n - Solution: \emptyset\sqrt{2} is irrational)\n\n- Exercise 2: Determine whether each pair of sets is equal:\n - a) {4, 3, 3, 7, 4, 7, 7, 3}{4, 3, 7}\n - Solution: Equal (repetition of elements does not alter set equality).\n - b) {{1}}{1, {2}}\n - Solution: Not equal (the first set contains one element: the set {1}1{2}).\n - c) \emptyset{\emptyset}\n - Solution: Not equal (\emptyset{\emptyset} is a singleton set containing 1 element).\n\n- Exercise 3: Determine whether these statements are true or false:\n - a) 0 \in \emptyset: False\n - b) \emptyset \in {0}: False\n - c) {0} \subset \emptyset: False\n - d) \emptyset \subset {0}: True\n - e) {0} \in {0}: False\n - f) {0} \subset {0}\subseteq\subset)\n - g) {\emptyset} \subseteq {\emptyset}: True\n\n- Exercise 4: Use a Venn diagram to illustrate the relationships A \subset BB \subset C\n - Solution: Draw universal set UABC.\n\n- Exercise 5: What is the cardinality of each of these sets?\n - a) {a}1\n - b) {{a}}1\n - c) {\emptyset, {\emptyset}}2\n - d) {a, {a}, {a, {a}}}3\n\n- Exercise 6: Let A = {1, 2, 3, 4, 5}B = {0, 3, 6}. Find:\n - a) A \cup B = {0, 1, 2, 3, 4, 5, 6}\n - b) A \cap B = {3}\n - c) A - B = {1, 2, 4, 5}\n - d) B - A = {0, 6}\n\n- Exercise 7: For U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}A = {1, 2, 3, 4, 5}B = {1, 2, 4, 8}C = {1, 2, 3, 5, 7}D = {2, 4, 6, 8}. Determine:\n - a) (A \cup B) \cap C:\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - (A \cup B) \cap C = {1, 2, 3, 5}\n - b) A \cup (B \cap C):\n - B \cap C = {1, 2}\n - A \cup (B \cap C) = {1, 2, 3, 4, 5}\n - c) C \cup D = {1, 2, 3, 4, 5, 6, 7, 8}\n - d) (A \cup B) - C:\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - (A \cup B) - C = {4, 8}\n - e) A \cup (B - C):\n - B - C = {4, 8}\n - A \cup (B - C) = {1, 2, 3, 4, 5, 8}\n - f) (B - C) - D:\n - B - C = {4, 8}\n - (B - C) - D = \emptyset\n - g) B - (C - D):\n - C - D = {1, 3, 5, 7}\n - B - (C - D) = {2, 4, 8}\n - h) (A \cup B) - (C \cap D):\n - A \cup B = {1, 2, 3, 4, 5, 8}\n - C \cap D = {2}\n - (A \cup B) - (C \cap D) = {1, 3, 4, 5, 8}\n - i) A \oplus B:\n - A \oplus B = (A - B) \cup (B - A) = {3, 5} \cup {8} = {3, 5, 8}\n\n- Exercise 8: Draw the Venn diagram of these sets and find (A \cup B) - CB'\n - Solution: In a three-set Venn diagram (A, B, CU):\n - (A \cup B) - CABC\n - B'\bar{B}B\n\n- Exercise 9: Given Universal set U = {\text{positive integers not larger than } 12} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}A = {\text{positive integers not more than } 6} = {1, 2, 3, 4, 5, 6}B = {3, 4, 6, 7}C = {5, 6, 7, 8, 9, 10}. Find:\n - i) A \cup B = {1, 2, 3, 4, 5, 6, 7}\n - ii) |A - B|:\n - A - B = {1, 2, 5}\n - |A - B| = 3\n - iii) \mathcal{P}(A - B)A - B):\n - Since A - B = {1, 2, 5}\mathcal{P}(A - B) = {\emptyset, {1}, {2}, {5}, {1, 2}, {1, 5}, {2, 5}, {1, 2, 5}}ℳ(S)S = {a, b}{\emptyset, {a}, {b}}{{a}, {b}, {a, b}}{\emptyset, {a}, {b}, {a, b}}{\emptyset, {a, b}}A = {1, 2, 3, 4, 5, 6, 7}B = {3, 4, p, q, r, s}A \cap BA \cup BA \oplus BA = {1, 2}B = {3, 4}A \times BB \times A\emptyset \subseteq {1, 2, 3}{0} \in \emptyset{1, 3, 5} = {3, 5, 1}Sn = 416U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}A = {1, 2, 3, 4, 5}B = {1, 2, 4, 8}A - B{\emptyset, {a}, {b}, {a, b}}A \cap B = {3, 4}A \cup B = {1, 2, 3, 4, 5, 6, 7, p, q, r, s}A \oplus B = {1, 2, 5, 6, 7, p, q, r, s}A \times B = {(1, 3), (1, 4), (2, 3), (2, 4)}B \times A = {(3, 1), (3, 2), (4, 1), (4, 2)}A - B = {3, 5}$$