Definitions

Number Systems:

• $\mathbb{N}$: The set of all natural numbers, i.e., $\mathbb{N}=\left\{0, 1, 2, 3, \ldots\right\}$.
• $\mathbb{Z}$: The set of all integers (whole numbers: positive, negative, and zero), i.e., $\mathbb{Z}=\left\{\ldots , -3, -2, -1, 0, 1, 2, 3, \ldots\right\}$
• $\mathbb{Q}$: The set of all rational numbers (numbers that can be expressed as quotients $m/n$ of integers, where $n \neq 0$), i.e., $\mathbb{Q}=\left\{\displaystyle\frac{a}{b}\in\mathbb{R}:a,b\in\mathbb{Z},\ b\ne 0\right\}$
• $\mathbb{R}$: The set of all real numbers, i.e., the numbers representing all points on the real number line.
• $\mathbb{C}$: The set of all complex numbers, i.e., $\mathbb{C}=\left\{a + bi:a\in\mathbb{R},\ b\in\mathbb{R}\right\}$.

Relation: Let $A$ and $B$ be sets. A relation $\mathcal{R}$ between $A$ and $B$ is a subset of the Cartesian product $A\times B$.

Function: A function $f$ mapping A to B is a relation from A to B that satisfies the following property,
"$\forall a \in A, a$ appears as the first member of exactly one ordered pair in $f$."

Injective (1-1): A function ($f$: $A\to B$) is injective if $\forall x \in A\forall y \in A(f(x) = f(y) \to x = y)$.

Surjective (onto): A function ($f$: $A\to B$) is surjective if $\forall y \in B\exists x \in A (f(x) = y)$.

Bijective: A function $f$ is said to be bijective if it is both injective and surjective.

Cardinality: The number of elements in a set $A$ is the cardinality of $A$, denoted by $|A|$. Two sets $A$ and $B$ have the same cardinality if there exists a bijective function from $A$ to $B$.

Partition: A partition of a set $S$ is a collection of nonempty subsets of $S$ such that every element of $S$ is in exactly one of the subsets of the partition. The subsets are the cells of the partition.

Equivalence Relation: A relation $\mathcal{R}$ on a set $\mathbf{A}$ is called an equivalence relation if the following hold:

1. $\forall x\in\mathbf{A}$ $(x\mathcal{R}x)$ (Reflexive Property)
2. $\forall x \in\mathbf{A}\forall y \in \mathbf{A}$ $(x\mathcal{R}y \to y\mathcal{R}x)$ (Symmetric Property)
3. $\forall x \in\mathbf{A} \forall y \in\mathbf{A} \forall z\in\mathbf{A}$ $(x\mathcal{R}y$ and $y\mathcal{R}z \to x\mathcal{R}z)$ (Transitive Property)

Binary Operation: Let $\mathbf{S}$ be a set. A binary operation on $\mathbf{S}$ is a function $f$ taking pairs of $\mathbf{S}$ to one element of $\mathbf{S}$. ($f$: $\mathbf{S}$ x $\mathbf{S} \to \mathbf{S}$)

Commutative: A binary operation * on a set $\mathbf{S}$ is commutative if (and only if) a*b=b*a for all $a, b\in\mathbf{S}$.

Associative: A binary operation * on a set $\mathbf{S}$ is associative $\iff \forall \mathbf{a} \in \mathbf{S} \forall \mathbf{b} \in \mathbf{S} \forall \mathbf{c} \in \mathbf{S},$ $\mathbf{(a*b)*c = a*(b*c)}$.

Isomorphism: An isomorphism is a one-to-one (injective) and onto (surjective) function $\gamma$: F $\rightarrow$ G for the binary structures (F, $\ast$) and (G, $\star$), and it satisfies the homomorphism property $\gamma$(a$\ast$b) = $\gamma$(a) $\star$ $\gamma$(b) for all a,b $\in$ F.

Structural Property: We say a property of $(\mathbf{S},*)$ is a structural property if and only if the property is unchanged when passed through isomorphism.

Identity Element: Let $(\mathbf{S},*)$ be a binary structure. An element $e$ of $\mathbf{S}$ is an identity element for $*$ if $e*s=s*e=s$ for all $s \in \mathbf{S}$.
i.e., $\exists e \in \mathbf{S} \forall s \in \mathbf{S}(e*s=s*e=s).$

Inverse: Let $(\mathbf{S},*)$ be a binary structure with identity element $e$. If for all $s \in \mathbf{S}$ there is an element $s^{-1} \in \mathbf{S}$ such that $s*s^{-1}=s^{-1}*s=e$, then $s^{-1}$ is the inverse of $s.$ i.e., $\forall s \in \mathbf{S} \exists s^{-1} \in \mathbf{S} (s*s^{-1}=s^{-1}*s=e).$

Group: A group $\langle \textit{G}, * \rangle$ is a set $\textit{G}$, closed under a binary operation *, such that the following axioms are satisfied:

$\mathcal{G}_1$: For all $\textit{a, b, c,} \in \textit{G}$, we have

$(\textit{a}*\textit{b})*\textit{c}=\textit{a}*(\textit{b}*\textit{c}).$$\textbf{associativity of *}$

$\mathcal{G}_2$: There is an element $\textit{e}$ in $\textit{G}$ such that for all x $\in \textit{G}$.

$\textit{e} *\textit{x} = \textit {x} * \textit {e}=\textit {x}$. $\textbf{identity element} \textit {e} for *.$

$\mathcal{G}_3$: Corresponding to each $\textit{a}\in\textit{G}$, there is an element $\textit {a} ^\prime$ in$\textit{G}$ such that
$\textit{a}*\textit{a} ^\prime=\textit{a} ^\prime*\textit{a}=\textit{e}. \textbf{inverse} \textit{a} ^\prime of \textit{a}$.

Abelian: A group G is abelian if its binary operation is commutative.

$GL(n,\mathbb{R})$: The general linear group of degree n is the set of n×n invertible matrices with real coefficient values. This forms a group under matrix multiplication.

Subgroup: Let $\mathbf{G}$ be a group. We say a subset $\mathbf{H} \subseteq \mathbf{G}$ is a subgroup if $\mathbf{H}$ is closed under the binary operation from $\mathbf{G}$ and $\mathbf{H}$ is also a group.

Proper Subgroup: a proper subgroup of a group $G$ is a subgroup $H$ of $G$ $|$ $H\neq G$ written $H\subset G$.

Order of a group: The order $|G|$ of a group $G$ is the number of elements in $G$.

Order of an element: Let $G$ be a group. The order of an element $c \in G$ is $|<c>|$. If it is of finite order $m$, then $m$ is the smallest integer such that $c^m=e$. Otherwise it is of infinite order.

Cyclic group:Let $\textit{G}$ be a group. We say $\textit{G}$ is $\mathbf{cyclic}$ if there exists an element $\textit{a} \in \textit{G}$ with $\langle \textit{a}\rangle$ = $\textit{G}$ where $\langle a\rangle$ = {$a^n | \textit{n} \in \mathbb{Z}$}. Since $\langle \textit{a}\rangle$ = $\textit{G}$, we say $\textit{a}$ generates G.

Generator: Let $\textit{G}$ be a group. If $\langle \textit{a}\rangle$ = $\textit{G}$, we say $\textit{a}$ generates $\textit{G}$, or $\textit{a}$ is a generator for $\textit{G}$. Note: $\langle \textit{a}\rangle$ := {$a^n | \textit{n} \in \mathbb{Z}$} is called the cyclic subgroup generated by $\textit{a}$.

Division Algorithm:Let $n\in\mathbb{Z}$ and $m\in\mathbb{Z}^+$. Then $n=mq+r$ where $q\in\mathbb{Z}$ is unique, and $0\leq r<m$ is unique.

Greatest Common Divisor:Let $r$ and $s$ be two positive integers. The positive generator $d$ of the cyclic group
$H=\left\{nr+ms|n,m\in \mathbb{Z}\right\}$
under addition is the greatest common divisor (abbreviated gcd) of $r$ and $s$. We write $d=$gcd$(r,s)$.

Relatively Prime: Two positive integers are relatively prime if their greatest common divisor is 1.

Permutation: A Permutation of a set A is a function $\phi : A \rightarrow A$ that is both one to one and onto.

Orbit of Permutation: Define an equivalence relation $\sim$ such that for $a,b \in A$, let $a \sim b$ if and only if $b=\sigma^n(a)$ for some $n \in \mathbb{Z}.$ Let $\sigma$ be a permutation of a set $A$. The equivalence classes in $A$ determined by the equivalence relation $\sim$ are the orbits of $\sigma$.

Cycle Permutation: A permutation $\sigma \in S_n$ is a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit.

Transposition: A cycle of length 2 is called a transposition.

Even Permutation: A permutation is an Even Permutation iff it can be expressed as the composition of an even number of transpositions.

Left Coset: Let $H$ be a subgroup of a group $G$. The subset $aH = \left\{ah|h \in H\right\}$ of $G$ is the left coset of $H$ containing $a$.

Index: Let H be a subgroup of a group G. The number of left cosets of H in G is the index (G:H) of H in G.

Direct Product of Groups: If $(G, \ast)$ and $(K, \star)$ are both groups, we can create a new group called the direct product of $G$ and $K$ by using $(G \times K, (\ast, \star))$. So $G \times K$ is a group with "component-wise operation."

Homomorphism: Let $(G, \ast)$ and $(G\prime, \star)$ be groups. We say a function $\varphi: G \rightarrow G\prime$ is a homomorphism if and only if $\varphi(a \ast b) = \varphi(a) \star \varphi(b)$ for all a $\in G$ and b \in G$. Kernel: Let$\phi : G \rightarrow G'$be a homomorphism of groups. The subgroup$\phi^{-1}[\left\{e'\right\}] = \left\{ x \in G | \phi(x) = e'\right\}$is the kernel of$\phi$, denoted by$Ker(\phi)$Image: Let$\varphi : X \rightarrow Y$be a function and$A \subseteq X$and$B \subseteq Y$. The image of$A$is$\varphi[A] = \{y \in Y | \varphi(a) = y$for some$a \in A\}$. Normal Subgroup:A subgroup$H$of a group$G$is normal if its left and right cosets coincide, that is, if$gH=Hg$for all$g \in G$Factor Group (or Quotient Group): Let$G$be a group and$H \triangleleft G$. Then the left cosets of$H$in$G$(denoted$G/H\$) is a group under coset multiplication and is called the factor or quotient group.

page revision: 137, last edited: 13 Jan 2012 00:04