1.9 KiB
Preliminaries
Sets and Equivalence Relations
Cartesian Product
A_1 * A_2 * … * A_n is all possible tuples (a_1, a_2, …, a_n).
Relation
A subset of A * B.
Function (Mapping)
For each a in A, there is a unique value b in B such that f(a) = b.
Surjective Function (Onto Function)
For each b in B, there is an a in A such that (a, b)
Injective Function (One-to-One Function)
For each b in B, there is at most an a in A such that f(a) = b
Bijective Function (One-to-One Correspondence)
A function that is both surjective and injective.
The Integers
Mathematical Induction
Well-Ordered Set
A subset of Z which has a smallest element.
Well-Ordering Principle
Every nonempty subset of natural numbers is well-ordered.
The Division Algorithm
For integer a, b, b != 0, there exists unique integers r and q where 0 <= r < b, such that:
a = bq + r
Groups
Integer Equivalence Classes and Symmetrics
Rigid Transformation
A transformation of an Euclidean space where the distance of every two points preserves.
Rigid Motion
A rigid transformation that preserve the shape of an object.
Definition
Group
(G, *) such that * is a function from G * G to G, and:
Associative
(a * b) * c = a * (b * c)
Identity Element
a * e = e * a = a
Inverse Element
a * a^-1 = a^-1 * a = e
Commutative Group (Abelian Group)
a * b = b * a
Finite Group (with Finite Order)
A group with finite elements.
Subgroup
A subset of G, which happens to be a group.
Trivial Subgroup
{e}
Proper Subgroup
Not G itself
Cyclic Group
Cyclic Subgroup
Cyclic Subgroup
A subgroup generated by an element a, <a>.
Cyclic Group
A group has a cyclic subgroup being itself.
Every cyclic group is abelian.
Order
The smallest positive integer such that a^n = e. n = |a|. If a does not exist, we write |a| = infinity.