Mastering Proofs, Sets, Functions, and Relations
Proofs by Induction
Purpose: To prove statements or properties that are true for all natural numbers.
Steps:
- Base Case: Verify the statement for the initial value (usually n=1).
- Inductive Hypothesis: Assume the statement is true for some arbitrary natural number n.
- Inductive Step: Prove the statement for n+1, based on the assumption that it’s true for n.
Examples:
- Summation: To prove 1 + 2 + … + n = n(n+1)/2, show it holds for n=1 and then prove n+1 case using the hypothesis.
- Divisibility: For 4^(2n) – 1 is divisible by 5, check base case n=1, then use algebra to demonstrate divisibility for n+1.
- Inequality: To show 2n + 1 ≤ 2^n for n ≥ 3, establish base case and apply algebraic manipulation in the inductive step.
Set Operations and Venn Diagrams
Operations:
- Union (A ∪ B): Set of elements in A, B, or both.
- Intersection (A ∩ B): Set of elements common to A and B.
- Difference (A – B): Set of elements in A but not in B.
- Complement (Aᶜ): Set of all elements not in A, relative to a universal set.
Venn Diagrams: Illustrate the relationships between different sets, visually representing operations.
Definitions and Properties of Sets, Functions, and Relations
Sets:
- Subset (⊆): A is a subset of B if every element of A is also an element of B.
- Partition: Splitting a set into exclusive and exhaustive subsets.
Functions:
- Injective (One-to-One): No two different elements of the domain map to the same element in the codomain.
- Surjective (Onto): Every element of the codomain is the image of at least one element from the domain.
- Bijective: A function that is both injective and surjective. It establishes a perfect “pairing” between elements of the domain and codomain.
Relations:
- Reflexive: Every element is related to itself.
- Symmetric: If a is related to b, then b is necessarily related to a.
- Transitive: If a is related to b, and b is related to c, then a is related to c.
- Antisymmetric: If a is related to b and b to a, then a must be equal to b.
- Equivalence Relation: A relation that is reflexive, symmetric, and transitive. It divides the set into equivalence classes.
- Partial Order Relation: A relation that is reflexive, antisymmetric, and transitive. Not all elements are comparable.
- Total Order Relation: A partial order in which every pair of elements is comparable.
Hasse Diagrams and Directed Graphs
Hasse Diagrams:
Simplified way of representing a partial order relation on a set.
Elements are represented by dots, and the order is indicated by lines without arrows, omitting reflexive, transitive links.
Directed Graphs (Digraphs):
Represent relations with vertices (nodes) for elements and directed edges (arrows) showing relationships.
Key Elements:
- Maximal Elements: Elements that no other element exceeds.
- Minimal Elements: Elements that do not precede any other element.
- Greatest Element: A unique maximal element that exceeds all others.
- Least Element: A unique minimal element that all other elements precede.
Equivalence Classes and Order Relations
Equivalence Classes: Sets of elements that are equivalent to each other under an equivalence relation, partitioning the set into non-overlapping classes.
Order Relations: Describe how elements of a set are ordered or related in terms of “greater than”, “less than” or “equal to”.
Function Inverses
One-to-One but Not Onto Function:
The inverse relation is not a function because not every element in the codomain maps back to the domain.
Onto but Not One-to-One Function:
The inverse relation is not a function because a single element in the codomain may correspond to multiple elements in the domain, violating the definition of a function.