Unit II: Set Theory and Ordered Sets
Course: Discrete Mathematics
Code: CADSC102
Basic Concepts of Set Theory
Set theory is the fundamental language of mathematics. A set is a well-defined collection of distinct objects.
- Elements: The objects belonging to a set are called its members or elements.
- Notation: Sets are usually denoted by capital letters (A, B, C) and elements by small letters (a, b, x).
- Universal Set (U): The set containing all objects under consideration.
- Empty Set (Ø): A set with no elements.
Operations with Sets
Common operations used to manipulate sets include:
- Union (A ∪ B): Elements in A, or B, or both.
- Intersection (A ∩ B): Elements common to both A and B.
- Difference (A - B): Elements in A that are not in B.
- Complement (A'): Elements in the Universal set not in A.
- Cartesian Product (A × B): The set of all ordered pairs (a, b) where a is in A and b is in B.
Functions
A function is a special type of relation where every element in the domain is mapped to exactly one element in the codomain.
- Domain: The set of all possible inputs.
- Range: The set of all actual outputs.
- One-to-One (Injective): Every element in the range has only one pre-image.
- Onto (Surjective): Every element in the codomain is an image of at least one element in the domain.
Relations and Properties
A relation R from set A to B is a subset of A × B.
Properties of Relations
- Reflexive: (a, a) is in R for every a in A.
- Symmetric: If (a, b) is in R, then (b, a) must be in R.
- Transitive: If (a, b) and (b, c) are in R, then (a, c) must be in R.
- Anti-symmetric: If (a, b) and (b, a) are in R, then a = b.
Composition and Closures of Relations
- Representing Relations: Can be done via sets of pairs, matrices, or directed graphs (digraphs).
- Composition: If R is a relation from A to B and S is from B to C, S ∘ R is a relation from A to C.
- Closures: The smallest relation containing R that satisfies a specific property (Reflexive, Symmetric, or Transitive closure).
Ordered Sets and Hasse Diagrams
A set with a partial ordering relation is called a Partially Ordered Set or Poset.
Hasse Diagrams
A Hasse diagram is a simplified graphical representation of a finite partially ordered set.
- Eliminates reflexive loops.
- Eliminates transitive edges.
- Direction is understood to be upwards.
Exam Focus & Tips
- Exam Tip: Be prepared to draw a Hasse Diagram for a given set and relation (like "divides" or "subset of").
- Common Mistake: Confusing "Symmetric" and "Anti-symmetric". A relation can be neither, or even both (if it's empty).
- Derivation: To find the Reflexive Closure, add (a, a) pairs to the existing relation until all elements are covered.
Frequently Asked Questions
Q: What is a Power Set?
A: The set of all possible subsets of a set, including the empty set and the set itself.
Q: When is a relation called an Equivalence Relation?
A: When it is Reflexive, Symmetric, and Transitive.