This video tutorial covers the first unit of Discrete Mathematics, focusing on sets, relations, and functions. The speaker emphasizes key concepts and question types likely to appear on exams, providing examples and explanations throughout.
This lecture covers sets, relations, and functions, focusing on concepts and question types relevant for examinations. The notes are based on the provided transcript and include examples.
I. Sets
A. Definition: A set is an unordered collection of distinct objects. Objects are called elements or members of the set.
B. Set Notation:
1. **Roster Form:** Listing elements within curly braces. Example: A = {1, 2, 3, 4}
2. **Set-Builder Form:** Defining elements based on a property. Example: B = {x | x is a natural number and x < 5} (This reads as "B is the set of all x such that x is a natural number and x is less than 5")
C. Types of Sets:
1. **Null Set (Empty Set):** A set containing no elements. Represented by {} or Ø. Example: C = {x | x is a real number and x² + 1 = 0} (There are no real numbers that satisfy this condition).
2. **Singleton Set:** A set containing only one element. Example: D = {5}
3. **Finite Set:** A set with a finite number of elements. Example: E = {1, 3, 5, 7, 9}
4. **Infinite Set:** A set with an infinite number of elements. Example: F = {x | x is a natural number}
D. Set Operations:
1. **Union (∪):** The set of all elements in either set A or set B or both. Example: A = {1, 2, 3}, B = {3, 4, 5}, A ∪ B = {1, 2, 3, 4, 5}
2. **Intersection (∩):** The set of all elements common to both sets A and B. Example: A = {1, 2, 3}, B = {3, 4, 5}, A ∩ B = {3}
3. **Complement (A'):** The set of all elements in the universal set (U) that are not in set A. Example: U = {1, 2, 3, 4, 5}, A = {1, 2, 3}, A' = {4, 5}
4. **Difference (A - B):** The set of all elements in set A that are not in set B. Example: A = {1, 2, 3}, B = {2, 3, 4}, A - B = {1}
5. **Symmetric Difference (A Δ B):** The set of elements that are in either A or B, but not both. (A - B) ∪ (B - A). Example: A = {1, 2, 3}, B = {3, 4, 5}, A Δ B = {1, 2, 4, 5}
E. Subsets:
1. **Subset (⊆):** Set A is a subset of set B if all elements of A are also elements of B. Example: A = {1, 2}, B = {1, 2, 3}; A ⊆ B
2. **Proper Subset (⊂):** Set A is a proper subset of set B if A is a subset of B, and A ≠ B. Example: A = {1, 2}, B = {1, 2, 3}; A ⊂ B
3. **Improper Subset:** A set is an improper subset of itself. Example: A = {1,2,3}; A ⊆ A
F. Power Set (P(A)): The set of all subsets of set A. Example: A = {1, 2}, P(A) = { {}, {1}, {2}, {1, 2} }
II. Relations
A. Definition: A relation R from a set A to a set B is a subset of the Cartesian product A × B. A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
B. Representing Relations:
1. **Set Notation:** Listing the ordered pairs. Example: R = {(1, 2), (2, 3), (3, 1)}
2. **Matrix Representation:** A matrix where rows represent elements of A, columns represent elements of B, and entry (i, j) is 1 if (aᵢ, bⱼ) ∈ R, and 0 otherwise.
3. **Directed Graph (Digraph):** Nodes represent elements of A and B, and a directed edge from a to b indicates (a, b) ∈ R.
C. Types of Relations (assuming relation R is on a single set A):
1. **Universal Relation:** R = A × A
2. **Null (Empty) Relation:** R = {}
3. **Identity Relation:** R = {(a, a) | a ∈ A}
4. **Inverse Relation (R⁻¹):** {(b, a) | (a, b) ∈ R}
5. **Reflexive:** For all a ∈ A, (a, a) ∈ R. Example: R = {(1,1), (2,2), (3,3), (1,2)} is reflexive on {1,2,3} because (1,1), (2,2), (3,3) are present.
6. **Symmetric:** If (a, b) ∈ R, then (b, a) ∈ R. Example: R = {(1, 2), (2, 1)} is symmetric.
7. **Antisymmetric:** If (a, b) ∈ R and (b, a) ∈ R, then a = b. Example: R = {(1, 1), (2, 2), (3,3)} is antisymmetric.
8. **Transitive:** If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. Example: R = {(1, 2), (2, 3), (1, 3)} is transitive.
9. **Equivalence Relation:** A relation that is reflexive, symmetric, and transitive.
10. **Partial Order Relation:** A relation that is reflexive, antisymmetric, and transitive.
III. Functions
(This section is not explicitly detailed in the transcript, but is mentioned as part of the unit's scope.)
A. Definition: A function is a special type of relation where each element in the domain maps to exactly one element in the codomain.
B. Notation: f: A → B (f is a function from set A to set B)
C. Types of Functions: (One-to-one, onto, bijection, etc. - details would need a separate explanation.)
Example Problem (from the transcript):
Prove that (A - C) ∩ (C - B) = Ø
This detailed lecture note expands upon the provided transcript, offering a structured overview with definitions, examples, and explanations to facilitate understanding of the core concepts. Further examples and detailed explanations of functions and more complex proof techniques would enhance these notes.
The transcript mentions power set questions in two key ways:
Calculating the size of a power set: The speaker explains that the number of elements (subsets) in the power set of a set A with 'n' elements is 2<sup>n</sup>. This is presented as a formula to remember for multiple-choice questions (MCQs). An example is given: if A = {a, b, c}, then the power set P(A) has 2³ = 8 elements.
Listing elements of a power set: The speaker demonstrates how to construct the power set for a given set. For instance, the example of A = {a, b, c} is used to show how to systematically list all possible subsets, from the empty set {} to the set itself {a, b, c}, resulting in the power set P(A) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }. This process is described as straightforward: list all combinations of elements.
In essence, the transcript highlights that power set questions on exams will likely involve either calculating the number of subsets in a power set (using the 2<sup>n</sup> formula) or listing the actual subsets within a power set for a relatively small initial set.