Algebraic Structures and Number Theory

• These notes cover mathematical concepts for computer scientists, focusing on algebraic structures and number theory, based on lectures from the summer semester of 2017
• The document was compiled by Janko Böhm on January 6, 2020

Foundational Constructions

• Sets are collections of distinct objects considered as a whole
• The membership of an element m in a set M is denoted by m ∈ M
• Sets can be defined by listing their elements: M = {m₁, m₂, ...}
• The empty set, denoted by Ø or {}, contains no elements

Set Operations

• The complement of N in M, M/N, contains elements in M but not in N
• The union of M and N, M ∪ N, combines all elements from both sets
• The intersection of M and N, M ∩ N, includes elements present in both sets

Quantifiers

• The universal quantifier ∀ means "for all"
• The existential quantifier ∃ means "there exists"

Set Size and Cartesian Products

• |M| denotes the number of elements in set M
• The Cartesian product M × N creates ordered pairs (m, n) with m from M and n from N
• Mⁿ represents the n-fold Cartesian product of M with itself

Power Set

• The power set of M, denoted 2Ṁ or P(M), includes all possible subsets of M

Mathematical Induction

• Induction is used to prove statements for all natural numbers by establishing a base case and an inductive step
• The base case validates the statement for an initial value like A(0)
• The inductive step proves that if A(n - 1) is true, then A(n) is also true

Relations Between Sets

• A relation R between sets M and N is defined as a subset of their Cartesian product, R ⊆ M × N
• A function f : M → N assigns a unique element f(m) in N to each element m in M
• M is referred to as the source, and N as the target

Function Terminology

• f(A) represents the image of subset A under function f
• Bild(f) denotes the image of the entire function
• f⁻¹(B) represents the preimage of subset B under function f.
• The graph of f, Graph(f), is the set of pairs {(m, f(m)) | m ∈ M}

Types of Functions

• A surjective function (onto) has its image equal to its codomain: f(M) = N
• An injective function (one-to-one) ensures that if f(m₁) = f(m₂), then m₁ = m₂
• A bijective function is both injective and surjective

Invertible Functions

• A bijective function f : M → N has an inverse function f⁻¹: N → M
• The inverse function satisfies f⁻¹(f(x)) = x and f(f⁻¹(y)) = y

Composition of Functions

• The composition of f : M → N and g : N → L is denoted as g ◦ f, mapping M to L by g(f(m))

Relations on Sets

• A relation R on set M is reflexive if (m, m) ∈ R for all m ∈ M
• A relation R is transitive if (l, m) ∈ R and (m, n) ∈ R implies (l, n) ∈ R
• A relation R is antisymmetric if (n, m) ∈ R and (m, n) ∈ R implies m = n
• A partial order satisfies reflexivity, transitivity, and antisymmetry
• A total order is a partial order where any two elements are comparable

Equivalence Relations

• Equivalence relations, denoted by ~, are reflexive, symmetric, and transitive
• Symmetry means if (m, n) ∈ R, then (n, m) ∈ R
• An equivalence class [m] contains all elements equivalent to m: [m] = {n ∈ M | m ~ n}
• Equivalence classes either coincide or are disjoint

Integers and Division

• Natural numbers N = {0, 1, 2, 3, ...} have addition and multiplication that are associative and commutative
• Integers Z include negative numbers, constructed from N by considering differences of natural numbers
• The division with remainder theorem states that for a, b ∈ Z, with b ≠ 0, there exist unique q, r ∈ Z such that a = bq + r and 0 ≤ r < |b|

Divisibility

• If a = bq for some q ∈ Z, then b divides a, denoted b | a
• Two integers a and b are coprime (relatively prime) if their greatest common divisor is 1
• a is congruent to b modulo m, written a ≡ b mod m, if m divides (a - b)

Prime Numbers

• An integer p is prime if p = ab implies a = ±1 or b = ±1
• The fundamental theorem of arithmetic states that every integer n > 1 has a unique prime factorization