Binary Operation
Let \( S \) be a set, a binary operation on \( S \) is a function \( \star : S \times S
\to S \) where we denote \( \star \left ( a , b \right ) \) as \( a \star b \) using infix notation
Note the distinction between binary operation and binary relation, a binary operation is a function, which
is a binary relation with some extra conditions.
Commutative Binary Operation
A binary
operation on a set \( S \) such that for any \( a , b \in S \), then \( a \star b = b \star a
\) is called commutative
Associative Binary Operation
A binary
operation on a set \( S \) such that for any \( a , b , c \in S \), then \( \left ( a \star b
\right ) \star c = a \star \left ( b \star c \right ) \) is called associative
Left Fold
Suppose that \( \star : S \times S \to S \) is a binary operation, and \( \left( x _ 1, x _ 2, \ldots x _ k \right) \) be a tuple in \( \mathbb{ N } _ 0 \) for some \( k \in \mathbb{ N } _ 1 \) then
\[
\operatorname{ foldl } \left( \star, \left( x _ 1, x _ 2, \ldots x _ k \right) \right) :=
\begin{cases}
\left( \operatorname{ foldl } \left( \star, \left( x _ 1, x _ 2, \ldots x _ { k - 1 } \right) \right) \right) \star x _ k &\text{ if } k \ge 2 \\
x _ 1 &\text{ if } k = 1
\end{cases}
\]
Left fold formalizes the idea that we want to look at objects of the form \( \left( \left( \left( x _ 0 \star x _ 1 \right) \star x _ 2 \right) \star \cdots \star x _ k \right) \), we also have a right fold:
Right Fold
Suppose that \( \star : S \times S \to S \) is a binary operation, and \( \left( x _ 1, x _ 2, \ldots x _ k \right) \) be a tuple in \( \mathbb{ N } _ 0 \) for some \( k \in \mathbb{ N } _ 1 \) then
\[
\operatorname{ foldr } \left( \star, \left( x _ 1, x _ 2, \ldots x _ k \right) \right) :=
\begin{cases}
x _ 1 \star \left( \operatorname{ foldr } \left( \star, \left( x _ 2, \ldots x _ { k } \right) \right) \right) &\text{ if } k \ge 2 \\
x _ 1 &\text{ if } k = 1
\end{cases}
\]
Distributivity
Let \( \oplus \) be a
binary
operation on a set \( S \), and let \( \otimes : X \times S \to S \) be a
binary function for some set \( X \) then we say that
\( \otimes \) distributes into \( \oplus \)
whenever we have for any \( a, b \in S \) and \( c \in X \)
\[
c \otimes \left( a \oplus b \right) = \left( c \otimes a \right) \oplus \left( c \otimes b \right)
\]
Bracket Placement Doesn't Matter for Associative Binary Operations
Suppose that \( \star \) is an associative
binary operation, then for any \( n \in \mathbb{Z}^{\ge 3} \), then no matter how one places
the brackets in the product \( x_{1} \star x_{2} \star \ldots \star x_{n} \) it always evaluates to the
same value
In order to prove this statement we have to prove that no matter the bracketing we get the same
value, but what exactly is this value? It must be the result of some bracketing so to make
our life easier let's select a left-most bracketing of the form
\[
\left( \left( x _ 1 \star x _ 2 \right) \star x _ 3 \star \cdots \right) \star x _ k
\]
Therefore the statement we are trying to prove is equivalent to that of: for any \( k \in \mathbb{ N
} ^ { \ge 3 } \) given the syntactically incorrect
\[
x _ 1 \star x _ 2 \star \cdots \star x _ k
\]
then given any syntactically valid version (obtained by inserting brackets), the value of the
expression is equal to the value of the version where it is bracketed in the left-most manner. We'll
prove this by strong induction or induction, which we will determine as the proof continues.
For the base case this holds true because of associativity. Now for the induction step assume it
holds true for \( k \in \mathbb{ N } ^ { \ge 3 } \) and lets show that it holds true for \( k + 1
\), suppose we have a product \( x _ 1 \star \cdots \star x _ { k + 1 } \) and then an arbitrary
bracketing of the product which is syntactically valid, it must have the form
\[
\left( e _ a \right) \star \left( e _ b \right)
\]
where \( a + b = k + 1 \) where without loss of generality \( a \ge 2 \) and \( b \ge 1 \), due to
this we also know that \( a, b \le k \)
Since we are (now) using strong induction then we know that the property holds true on \( e _ a, e _
b \) as they are arbitrarily bracketed expressions, each of which have the same value as their
left-most bracketed counterparts, and therefore since they have the same value, they can be
substituted so that
\[
\left( e _ a \right) \star \left( e _ b \right) = \left( \left( \left( x _ 1 \star x _ 2 \right)
\star \cdots \right) \star x _ a \right) \star \left( \left( \left( x _ { a + 1 } \star x _ { a + 2
} \right) \star \cdots \right) \star x _ { a + b } \right)
\]
at this point we've done some work, now if we can re-arrange this to be fully left-bracketed which
would prove the statement true, recall that one of the properties we haven't used yet is
associativity of \( \star \) . Closing our left eye, we can observe that:
\[
\left( e _ a \right) \star \left( e _ { b - 1 } \star x _ { a + b } \right) = \left( e _ a \star e _
{ b - 1 } \right) \star x _ { a + b }
\]
Now \( \left( e _ a \star e _ { b - 1 } \right) \) is a arbitrarily bracketed expression of using \(
a + b - 1 \lt k + 1\) elements and so by our strong induction hypothesis we know that it's value is
equal to the leftmost bracketed version of itself, so we have
\[
\left( e _ a \star e _ { b - 1 } \right) \star x _ { a + b } = \left( \left( \left( x _ 1 \star x _
2 \right) \star \cdots\right) \star x _ { b - 1 } \right) \star x _ { a + b }
\]
Chaining equalities, we've proven that \( \left( e _ a \right) \star \left( e _ b \right) = \left(
\left( \left( x _ 1 \star x _ 2 \right) \star \cdots\right) \star x _ { b - 1 } \right) \star x _ b
\), which is exactly what we wanted to show, therefore by induction this shows that the property
holds for every expression.
Associativity Implies Folds are Equal
Suppose that \( \star : S \times S \to S \) is associative, and \( \left( x _ 1, \ldots x _ k \right) \) is a tuple in \( \mathbb{ N } _ 1 \), then
\[
\operatorname{ foldl } \left( \star, \left( x _ 1, \ldots x _ k \right) \right) = \operatorname{ foldr } \left( \star, \left( x _ 1, \ldots, x _ k \right) \right)
\]
Fold of a Composition Law
Suppose that \( \star : S \times S \to S \) is a composition law, and \( \left( x _ 1, \ldots x _ k \right) \) a tuple in \( \mathbb{ N } _ 0 \) for \( k \in \mathbb{ N } _ 1 \)
\[
\operatorname{ fold } \left( \star, \left( x_0 , x_1 , \ldots , x_k \right) \right) := \operatorname{ foldl } \left( \star, \left( x_0 , x_1 , \ldots , x_k \right) \right)
\]
Sum Fold
Suppose we have \( + : \mathbb{ R } \times \mathbb{ R } \to \mathbb{ R } \) then and \( R \subseteq \mathbb{ R } \) a finite tuple, then we define
\[
\sum R = \operatorname{ fold } \left( +, R \right)
\]
in terms of the
sum fold
Ellipses Notation
Suppose that \( \star : S \times S \to S \) is a composition law, and \( \left( x _ 1, \ldots x _ k \right) \) a tuple in \( \mathbb{ N } _ 0 \) for \( k \in \mathbb{ N } _ 1 \)
\[
x _ 1 \star x _ 2 \star \cdots \star x _ k := \operatorname{ fold } \left( \star, \left( x_0 , x_1 , \ldots , x_k \right) \right)
\]
Since all bracketings yield the same value, our definition of fold to be the left fold was quite arbitrary. We can also now look at previous things under simpler lights, recall a definition of \( \sum _ { i = 0 } ^ k a _ i \) that you're familiar with, this is simply just \( \operatorname{ fold } \left( +, \left( a _ 0, \ldots , a _ k \right) \right) \)
Composition Law
A composition law is an associative
binary operation
Identity Element
Given a set \( S \) and a
binary relation \( \star \), we
say that an element \( e \in S \) is an identity element on \( S \) when for every \( s \in S, e \star s
= s \star e = s\)
Binary Operation has Inverses For an Identity
Given a set \( S \) and a binary operation \( \star \) on \( S \), that has an
identity
element \( e \),
then we say that
\( \star \) has inverses for \( e \) if for every \( s \in S \), there exists
some \( r \in S \) such that
\[
s \star r = e
\]
Group
We say that \( \left( G, \star \right) \) where \( G \) is a set and \( \star \) is a
composition
law on \( G \), when there exists an element \( e \in G \) satisfying the following
properties:
- \( e \) is an identity
element on \( G \)
- inversion: for every \( a \in G \) we have some \( b \in G \) such that \( a \star b = b \star a
= e \)
note: informally this says that you can do nothing, and you can also undo anything
Trivial Group
A trivial group is a group that has one element
The Integers are a Group
\( \mathbb{ Z } , + \) form a group
Note that at this point in time we can write things like \( a + b \) and that makes sense, if we were to
write something like \( x a + b \) this should not make sense because at this point we only have one
operator, and not a multiplication operator yet, but we can think of \( x a \) as "syntactic sugar" for \( a
+ a + \ldots + a \) (with \( x \) repetitions) and it's alright.
It should be clear by now that \( \emptyset \) is not a group since it cannot have an identity element
because there are no elements as candidate for this position. At this point in time we know that in a group
there is at least one element \( e \) with the above properties, we will now find out that there is exactly
one such element.
identity element is unique in a group
Suppose \( G \) is a group, then the identity element \( e \) is unique
Suppose that \( f \) and \( g \) are both identity elements, then by the identity property of a group,
we know that \( f{\star} g{=} g{\star} f{=} f \) since \( g \) is an identity element, but also \(
g{\star} f{=} f{\star} g{=} g \) since \( f \) is the identity, as well. Relating the equalities yields
that \( f{=} g \) and therefore the identity element is unique.
inverse element is unique
Suppose \( G \) is a group, and \( a \in G \), then there is a unique element \( b \) such that \( a
\star b = b \star a = e \)
Suppose that \( b \) and \( c \) are both inverses to \( a \), thus \( a \star b = e = c \star a \),
then \( c = c \star e = c \star \left ( a \star b \right ) = \left ( c \star a \right ) \star b = e
\star b = b \) so then \( c = b \)
Inverse
Given a group \( G \) and \( a \in G \), we denote the unique element \( b \) such that \( a \star b = b
\star a = e \) as \( a^{- 1} \) and call it the inverse of \( a \)
two inverses cancel
\( \left ( a^{- 1} \right )^{- 1} = a \)
To show this is true we want to show that \( a^{- 1} \star a = a \star a^{- 1} = e \), though the
definition of \( a^{- 1} \) is such that \( a \star a^{- 1} = a^{- 1} \star a = e \) and since the
equality symbol is a reflexive relation, this proves what we needed to show
inverse of ab
Given a group \( G \) and \( a , b \in G \), then \( \left ( a \star b \right )^{- 1} = b^{- 1} \star
a^{- 1} \)
For ease let \( c = \left ( a \star b \right )^{- 1} \), so that \(
\left ( a \star b \right ) \star c = c \star \left ( a \star b \right ) = e \) since we
know \( \left ( a \star b \right ) \star c = a \star \left ( b \star c \right ) = e \) , and
thus \( a^{- 1} \star \left ( a \star \left ( b \star c \right ) \right ) = a^{- 1} \star e \), thus \(
\left ( a^{- 1} \star a \right ) \star \left ( b \star c \right ) = a^{- 1} e \), which simplifies to \(
e \star \left ( b \star c \right ) = a^{- 1} \), so we can see that \( a^{- 1} = b \star c \), as needed
Cancellation
Suppose \( G \) is a group and \( a , b , c \in G \), then \( a \star c = b \star c \implies a = b \)
and \( c \star a = c \star b \implies a = b \), in other words, we can cancel common elements on right
and left
Suppose that \( a \star c = b \star c \), let \( c ^ { -1 } \) be the inverse of \( c \) , then we have
the following
\[
\begin{gather}
a \star c = b \star c &\iff \\
\left( a \star c \right) \star c ^ { -1 } = \left( b \star c \right) \star c ^ { -1 } &\iff \\
a \star \left( c \star c ^ { -1 } \right) = b \star \left( c \star c ^ { -1 } \right) &\iff \\
a \star e = b \star e &\iff \\
a = b
\end{gather}
\]
Where we've used associativity followed by the definition of inverse and then the identity element. The
proof for right cancellation can be obtained by placing a mirror on the left of the above chain of
equalities and reversing individual elements, so that if you see ɘ you interpret it as e.
Order of a group
The order of a group \( G \) denoted by \( \left | G \right | \) is the cardinality of \( G \)
Abelian
Given a
group, if it's
composition
law is
commutative,
then we say that the group is
abelian
The Integers with Addition are Abelian
\( \mathbb{ Z } , + \) where \( + \) is defined in the usual sense form an abelian group
Cartesian Product of Abelian Groups is Abelian
Let \( \left( G, \star \right) \) be an abelian group, then \( G ^ n \) forms an abelian group with the
operation \( \oplus \) defined for \( a, b \in G ^ n \) as
\[
a \oplus b := \left( a _ 1 \star b _ 1, \ldots , a _ n \star b _ n \right)
\]
Can the above be generalized for any extra group properties?
Multiplicative Notation
Given a group \( \left ( G , \star \right ) \) then since there is only one operation in question,
instead of writing the operator between every two pairs of elements we may limit it to \( a b \), to
refer to \( a \star b \) to reduce visual clutter
note: since \( \cdot \) is also a simple thing to write, we may also use it in place of \( \star
\)
Power of an Element
Given a group \( G \) and \( a \in G \), then we define \( a^{n} := \overbrace{a a \ldots a}^{\text{n
times}} \) for any \( n \in \mathbb{Z}^{\gt 0} \) and \( a^{0} := e \), when \( n \in \mathbb{Z}^{\lt 0}
\) then \( a^{n} := \left ( a^{- 1} \right )^{n} \), thus we've defined \( a^{n} \) for all \( n \in
\mathbb{Z} \)
Power Properties
For all \( a , b \in G \), \( a^{n} a^{m} = a^{n + m} \) and \( \left ( a^{n} \right )^{m} = a^{n m} \)
for any \( m , n \in \mathbb{Z} \)
TODO
Order of a Group Element
The order of an element \( a \in G \), denoted \( \left | a \right | \), is the smallest \( n \in
\mathbb{N}_{1} \) such that \( a^{n} = e \)
Suppose \( G \) is a group and that \( a \in G \) if \( a \) has finite order given by \( n \in \mathbb{
N } _ 0 \), then \( a ^ i = a ^ j \) iff \( i ~\%~ n = j ~\%~ n \)
If the power of an element with finite order yields the identity then the order divides
the power
Let \( G \) be a group and suppose \( a \in G \) has order \( n \) then if \( a ^ k = e \) then \( n
\mid k \)
We know that \( a ^ k = e = a ^ 0 \) therefore \( k ~\%~ n = 0 ~\%~ n = 0\) therefore \( n \mid k \) as
needed.
Subgroup
Suppose that \( \left( G, \star \right) \) is a
group, then if \( H
\subseteq G \) is a group under \( \star \), then we say that \( H \) is a subgroup of \( G \) and write
\( H \leqslant G \)
Let \( G \) be a group. Given a non-empty \( H \subseteq G \) if \( a b ^ { -1 } \in H \) for any \( a,
b \in H \), then \( H \leqslant G \)
Since \( H \) is non-empty then there is some element \( h \in H \), thus we know that \( h h ^ { -1
} \in H \), since \( h \in H \), since \( H \subseteq G \), then we know that \( h \in G \), and
therefore in \( G \) we have an inverse \( h ^ { -1 } \) such that \( h h ^ { -1 } = e \), where \(
e \in G \) but by assumption this is also an element of \( H \), thus \( e \in H \).
So now we know that \( e \in H \), how can we be sure this is the identity in \( H \)? Perhaps it is
not, but given any \( s \in H \), since \( H \subseteq G \), we know \( s \in G \) then using the
fact that \( G \) is a group we see \( e \star s = s \star e \), since \( e \) is also in \( H \)
this confirms that it is \( H \)'s identity.
Now we'll show that \( H \) has inverses, so let \( a \in H \), at the same time we know we have \(
e \in H \), thus \( e a ^ { -1 } \in H \) and thus \( a ^ { -1 } \in H \) as needed.
At this point it may seem like we've verified all the requirements for \( H \) to be a group, but
there's something a little subtle, when we were working with \( \star \) we know that it was
composition law meaning that this operation is closed for elements in \( G \), so we also need to
verify that \( \star \) is closed in \( H \), that is to say that \( \star \) is a composition law
in \( H \), so let \( x, y \in H \), then from the previous paragraph we know that \( y ^ { -1 } \)
is a member of \( H \), thus \( x \left( y ^ { -1 } \right) ^ { -1 } \in H \)
Notice that the equation stated above is special, firstly given two elements in \( a, b \in H \) it combines
\( a \) and \( b ^ { -1 } \), the special thing here is the \( b ^ { -1 } \), originally we don't know if
this element is a member of \( H \) because in the proof we verify if indeed it is a group, and we don't
know that inverses exists until we verify them, but we do know when it's combined with \( b ^ { -1 } \) it
produces an element of \( H \).
Note that we need \( H \) to be non-empty otherwise the empty set would satisfy the above, and we know that
the empty set is not a group. It also helps us bootstrap the proof.
TODO
An element of a group has order \( 1 \) if and only if \( x = e \)
Suppose that \( a \in G \), then \( \left | a \right | = 1 \) if and only if \( a^{1} = e \) note
that \( a^{1} = a \), so \( a = e \) as needed
For the reverse direction, follow the above proof backwards, noting that each connection is a
bi-implication
TODO
Show that \( \mathbb{Q} , \mathbb{R} , \mathbb{C} \) are groups under multiplicaiton
TODO
Generator
The notation \( \left \langle a \right \rangle \) denotes the set \( \left \lbrace a^{n} : n \in
\mathbb{Z} \right \rbrace \). Then \( a \in G \) is said to be a generator of \( g \) if and only if \(
G = \left \langle a \right \rangle \)
For a positive integer n, all groups of order n are cyclic iff GCD(n, phi(n)) = 1
cyclic group
A group \( G \) is considered a cyclic group if and only iff there exists some \( a \in G \) such that
\( G = \left \langle a \right \rangle \)
cyclic implies abelian
If a group \( G \) is cyclic, then it is abelian
TODO
power equivalence
For a group \( G \) with \( a \in G \), if \( G \) has infinite order, then \( a^{i} = a^{j} \) if and
only if \( i = j \) otherwise if \( G \) has finite order \( n \) then \( a^{i} = a^{j} \) if and only
if \( i \% n = j \% n \)
TODO
gcd generates the same
Suppose \( G \) is a group. Let \( a \in G \) so that \( \left | a \right | = n \), then \( \left
\langle a^{k} \right \rangle = \left \langle a^{\gcd{\left ( n , k \right )}} \right \rangle \) and \(
\left | a^{k} \right | = \frac{n}{\gcd{\left ( n , k \right )}} \)
TODO
For a group \( G \) and \( a \in G \), then \( \left | a \right | \) divides \( \left | G \right | \)
TODO