Definition and Notation
Set Concept
Set: well-defined collection of distinct objects called elements or members. Elements: unordered, unique. Notation: uppercase letters (e.g., A, B).
Set-Builder and Roster Notation
Roster notation: explicit listing {1, 2, 3}. Set-builder: descriptive {x | x satisfies property P}.
Membership
Symbol ∈ denotes membership: a ∈ A means "a is an element of A". a ∉ A means "a is not an element of A".
Empty Set
Empty (null) set: contains no elements, denoted ∅ or {}. Unique by definition.
Examples
Set of natural numbers: ℕ = {0, 1, 2, 3, ...}. Set of vowels: V = {a, e, i, o, u}.
Types of Sets
Finite and Infinite Sets
Finite: countable number of elements. Infinite: unbounded elements (e.g., ℕ, ℝ).
Equal Sets
Sets A and B equal if they have exactly the same elements: A = B ⇔ ∀x (x ∈ A ⇔ x ∈ B).
Subset and Proper Subset
Subset: A ⊆ B if every element of A is in B. Proper subset: A ⊂ B if A ⊆ B and A ≠ B.
Singleton Sets
Singleton: set with exactly one element, e.g., {a}.
Disjoint Sets
Disjoint: sets with no common elements, A ∩ B = ∅.
Set Operations
Union
Union (A ∪ B): set of elements in A or B or both. Definition: A ∪ B = {x | x ∈ A or x ∈ B}.
Intersection
Intersection (A ∩ B): elements in both A and B. A ∩ B = {x | x ∈ A and x ∈ B}.
Difference
Difference (A \ B): elements in A not in B. A \ B = {x | x ∈ A and x ∉ B}.
Complement
Complement (A'): elements not in A relative to universal set U. A' = U \ A.
Symmetric Difference
Symmetric difference (A △ B): elements in A or B but not both. A △ B = (A \ B) ∪ (B \ A).
Subsets and Power Set
Subsets
Definition: A ⊆ B if ∀x (x ∈ A ⇒ x ∈ B). Includes empty set and the set itself.
Proper Subsets
A ⊂ B if A ⊆ B and A ≠ B.
Power Set
Power set P(A): set of all subsets of A. |P(A)| = 2^|A|.
Example
A = {1,2}, P(A) = {∅, {1}, {2}, {1,2}}.
Properties
Power set always contains ∅ and A itself. Used in combinatorics and logic.
Cardinality
Definition
Cardinality |A|: number of elements in set A. For finite sets, count elements.
Infinite Cardinality
Infinite sets: cardinality corresponds to sizes of infinite sets (countable, uncountable).
Countable Sets
Countable: elements can be put in one-to-one correspondence with ℕ.
Uncountable Sets
Uncountable: cannot be matched with ℕ (e.g., real numbers ℝ).
Cardinality of Power Set
|P(A)| = 2^|A| (exponential growth).
Universal Set and Complement
Universal Set
Universal set U: set containing all objects under consideration.
Complement
Complement A' = U \ A: elements in U not in A.
Properties of Complement
A ∪ A' = U; A ∩ A' = ∅; (A')' = A.
Relation with Difference
A' = U \ A.
Example
If U = {1,2,3,4}, A = {1,3}, then A' = {2,4}.
Ordered Pairs and Cartesian Product
Ordered Pair
Ordered pair (a, b): pair of elements with order significant. (a, b) ≠ (b, a) unless a = b.
Cartesian Product
Definition: A × B = {(a, b) | a ∈ A, b ∈ B}.
Properties
|A × B| = |A| × |B| for finite sets.
Higher-Dimensional Products
Cartesian product extended to tuples: A1 × A2 × ... × An.
Application
Used to define relations, functions, coordinate systems.
Venn Diagrams
Purpose
Visual representation of sets and their relationships.
Basic Diagrams
Two or three overlapping circles representing sets.
Set Operations Visualization
Union, intersection, difference illustrated via shaded regions.
Limitations
Complex for more than three sets; alternative diagrams used (e.g., Euler diagrams).
Example
Two sets A and B: overlapping region is A ∩ B, total shaded area A ∪ B.
Set Identities and Laws
Commutative Laws
A ∪ B = B ∪ A; A ∩ B = B ∩ A.
Associative Laws
(A ∪ B) ∪ C = A ∪ (B ∪ C); (A ∩ B) ∩ C = A ∩ (B ∩ C).
Distributive Laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
Identity Laws
A ∪ ∅ = A; A ∩ U = A.
De Morgan's Laws
(A ∪ B)' = A' ∩ B'; (A ∩ B)' = A' ∪ B'.
| Identity | Expression |
|---|---|
| Commutative | A ∪ B = B ∪ A, A ∩ B = B ∩ A |
| Associative | (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C) |
| Distributive | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
| De Morgan's | (A ∪ B)' = A' ∩ B', (A ∩ B)' = A' ∪ B' |
Applications of Sets
Mathematics
Foundation for functions, relations, algebra, topology.
Computer Science
Data structures (sets, hash tables), databases, logic programming.
Logic and Proofs
Formalizing propositions, predicates, quantifiers.
Probability Theory
Events modeled as sets, operations for event combinations.
Information Retrieval
Search engines use sets for indexing and query results.
Common Misconceptions
Order Matters
Sets: order irrelevant. Confusion with tuples or lists.
Duplicates Allowed
Sets exclude duplicates. Multiple occurrences count once.
Subset vs. Proper Subset
Subset includes equality; proper subset excludes it.
Empty Set is Null
Empty set ≠ null value; empty set is a valid set with no elements.
Universal Set Context
Universal set depends on context; not fixed globally.
Summary
Core Concepts
Sets: fundamental building blocks. Elements distinct, unordered. Operations define relations between sets.
Key Properties
Subset relations, cardinality, complements, power sets crucial for mathematical reasoning.
Notation and Language
Symbols ∈, ⊆, ∪, ∩ standard. Mastery essential for discrete math.
Applications
Wide use in math, CS, logic, probability. Essential for theoretical and practical problems.
Final Note
Sets underpin discrete mathematics structure, facilitate abstraction, and formal definitions.
Example: Set operations on A={1,2,3}, B={2,3,4}Union: A ∪ B = {1,2,3,4}Intersection: A ∩ B = {2,3}Difference: A \ B = {1}Symmetric Difference: A △ B = {1,4}References
- Halmos, P.R., "Naive Set Theory," Springer, 1974, pp. 1–96.
- Rosen, K.H., "Discrete Mathematics and Its Applications," McGraw-Hill, 7th ed., 2012, pp. 50–120.
- Enderton, H.B., "Elements of Set Theory," Academic Press, 1977, pp. 10–85.
- Grimaldi, R.P., "Discrete and Combinatorial Mathematics," Pearson, 5th ed., 2003, pp. 30–78.
- Jech, T., "Set Theory," Springer Monographs in Mathematics, 2003, pp. 5–150.