Abstract Algebra Notes

  • Abstract Algebra: Study of algebraic structures like groups, rings, and fields.
  • Applications have grown with computing, benefiting science, engineering, and computer science students.
  • Theory remains central, emphasizing proofs alongside applications like coding theory and cryptography.
  • Rigorous Proofs:
    • Abstract mathematics uses logical arguments to derive information from axioms.
    • Axioms should be consistent and not overly restrictive.
    • A mathematical proof is a convincing argument about a statement's accuracy.
    • Proof detail level depends on the audience's mathematical maturity.
    • Counterexamples disprove theorems; examples illustrate them.
    • Quantifiers (e.g., only, for all) are crucial.
    • Avoid unstated assumptions.
    • To prove uniqueness, assume multiple objects exist and show they are equal.
    • Proving the contrapositive is equivalent to proving the original statement.
  • Sets and Equivalence Relations:
    • Set Theory: Sets are well-defined collections of objects.
    • Notation: a ∈ A (a is an element of A), a ∈/ A (a is not an element of A).
    • Important Sets: N, Z, Q, R, C.
    • Set Relations and Operations:
    • Subset: A ⊂ B if every element of A is in B.
    • Proper Subset: B ⊂ A and B != A.
    • Equality: A = B if A ⊂ B and B ⊂ A.
    • Empty Set: ∅ (subset of every set).
    • Union: A ∪ B = {x : x ∈ A or x ∈ B}.
    • Intersection: A ∩ B = {x : x ∈ A and x ∈ B}.
    • Disjoint Sets: A ∩ B = ∅.
    • Universal Set: U (fixed set for complements).
    • Complement: A' = {x : x ∈ U and x ∈/ A}.
    • Difference: A \ B = A ∩ B' = {x : x ∈ A and x ∈/ B}.
    • Proposition 1.1: Properties of set operations (e.g., A ∪ A = A, A ∩ ∅ = ∅).
    • Theorem 1.2 (De Morgan's Laws):
      • (A∪B)′=A′∩B′(A ∪ B)' = A' ∩ B'
      • (A∩B)′=A′∪B′(A ∩ B)' = A' ∪ B'
    • Cartesian Products and Mappings:
    • Cartesian Product: A × B = {(a, b) : a ∈ A and b ∈ B}.
    • Relation: Subset of A × B.
    • Mapping (Function): f ⊂ A × B assigns a unique b ∈ B to each a ∈ A.
      • Notation: f : A → B, f(a) = b, f : a ↦ b.
      • Domain: A
      • Range/Image: f(A) = {f(a) : a ∈ A} ⊂ B
    • Well-defined: Each element in the domain maps to a unique element in the range.
    • Surjective (Onto): f(A) = B; for every b ∈ B, there exists an a ∈ A such that f(a) = b.
    • Injective (One-to-one): a1 != a2 implies f(a1) != f(a2); equivalently, f(a1) = f(a2) implies a1 = a2.
    • Bijective: Both one-to-one and onto.
    • Composition: (g ◦ f)(x) = g(f(x)).
    • Theorem 1.3: Associativity of composition; properties of one-to-one and onto maps under composition.
    • Identity Mapping: id(s) = s.
    • Inverse Mapping: g ◦ f = idA and f ◦ g = idB.
    • Invertible: Possesses an inverse.
    • Theorem 1.4: A mapping is invertible if and only if it is bijective.
    • Equivalence Relations and Partitions:
    • Equivalence Relation: A relation R ⊂ X × X that is reflexive, symmetric, and transitive.
    • Equivalence Class: [x] = {y ∈ X : y ∼ x}.
    • Partition: Collection of nonempty sets X1, X2, . . . such that Xi ∩ Xj = ∅ for i != j and ∪k Xk = X.
    • Theorem 1.5: Equivalence classes form a partition; partitions induce equivalence relations.
    • Corollary 1.6: Equivalence classes are either disjoint or equal.
    • Congruence Modulo n: r ≡ s (mod n) if r − s = nk for some k ∈ Z.
  • Mathematical Induction:
    • First Principle: If S(n0) is true and S(k) implies S(k+1), then S(n) is true for all n ≥ n0.
    • Second Principle: If S(n0), . . . , S(k) imply S(k+1), then S(n) is true for all n ≥ n0.
    • Well-Ordering Principle: Every nonempty subset of natural numbers is well-ordered (has a least element).
  • Division Algorithm:
    • Theorem 2.3: For integers a and b > 0, there exist unique integers q and r such that a=bq+ra = bq + r, where 0 ≤ r < b.
    • Divisibility: a | b if b = ak for some integer k.
    • Common Divisor: d is a common divisor of a and b if d | a and d | b.
    • Greatest Common Divisor (gcd): d = gcd(a, b) is the largest positive integer dividing both a and b.
    • Relatively Prime: gcd(a, b) = 1.
    • Theorem 2.4: There exist integers r and s such that gcd(a,b)=ar+bsgcd(a, b) = ar + bs; the gcd is unique.
    • Corollary 2.5: If a and b are relatively prime, there exist integers r and s such that ar+bs=1ar + bs = 1.
  • Euclidean Algorithm: Systematic method to compute gcd(a, b) and express it as ar + bs.
  • Prime Numbers:
    • Definition: Integer p > 1 divisible only by 1 and p.
    • Composite: Integer n > 1 that is not prime.
    • Lemma 2.6 (Euclid): If p | ab, then p | a or p | b.
    • Theorem 2.7 (Euclid): There are infinitely many primes.
    • Theorem 2.8 (Fundamental Theorem of Arithmetic): Every integer n > 1 has a unique prime factorization n=p1p2⋅⋅⋅pkn = p1p2 · · · pk.