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

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

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

TODO

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.

One Point sets are Form Trivial Groups

Suppose that \( T \) is a set such that \( | T | = 1 \), and \( \star \) is a constant composition law, then \( \left( T, \star \right) \) forms a group

Let \( t \) be the only element of \( T \), we claim this is the identity, which we can verify by checking \( t \star t = t \), because \( \star \) is constant, thus it is an identity element.

Now we can also show that we have inversion as well, because for every element in \( T \) (which is just \( t \)) we have an element (which is also \( t \)) such that \( t \star t = t \), where the \( t \) on the right hand side is the identity.

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

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 \)

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

TODO

For a group \( G \) and \( a \in G \), then \( \left | a \right | \) divides \( \left | G \right | \)

TODO