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.