Binary Operations And Groups

Binary Operation

Let

S

be a set, a binary operation on

S

is a function

⋆ : S \times S \to S

where we denote

⋆ (a, b)

a ⋆ 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 ⋆ b = b ⋆ a

is called commutative

Associative Binary Operation

A binary operation on a set

S

such that for any

a, b, c \in S

, then

(a ⋆ b) ⋆ c = a ⋆ (b ⋆ c)

is called associative

Left Fold

Suppose that

⋆ : S \times S \to S

is a binary operation, and

(x_{1}, x_{2}, \dots x_{k})

be a tuple in

ℕ_{0}

for some

k \in ℕ_{1}

then

foldl (⋆, (x_{1}, x_{2}, \dots x_{k})) : = {\begin{matrix} (foldl (⋆, (x_{1}, x_{2}, \dots x_{k - 1}))) ⋆ x_{k} & a m p; if k \geq 2 \\ x_{1} & a m p; if k = 1 \end{matrix}

Left fold formalizes the idea that we want to look at objects of the form $(((x_{0} ⋆ x_{1}) ⋆ x_{2}) ⋆ \dots ⋆ x_{k})$ , we also have a right fold:

Right Fold

Suppose that

⋆ : S \times S \to S

is a binary operation, and

(x_{1}, x_{2}, \dots x_{k})

be a tuple in

ℕ_{0}

for some

k \in ℕ_{1}

then

foldr (⋆, (x_{1}, x_{2}, \dots x_{k})) : = {\begin{matrix} x_{1} ⋆ (foldr (⋆, (x_{2}, \dots x_{k}))) & a m p; if k \geq 2 \\ x_{1} & a m p; if k = 1 \end{matrix}

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 (a \oplus︎ b) = (c \otimes a) \oplus︎ (c \otimes b)

Bracket Placement Doesn't Matter for Associative Binary Operations

Suppose that

⋆

is an associative binary operation, then for any

n \in ℤ^{\geq 3}

, then no matter how one places the brackets in the product

x_{1} ⋆ x_{2} ⋆ \dots ⋆ 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 $((x_{1} ⋆ x_{2}) ⋆ x_{3} ⋆ \dots) ⋆ x_{k}$

Therefore the statement we are trying to prove is equivalent to that of: for any $k \in ℕ^{\geq 3}$ given the syntactically incorrect $x_{1} ⋆ x_{2} ⋆ \dots ⋆ 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 ℕ^{\geq 3}$ and lets show that it holds true for $k + 1$ , suppose we have a product $x_{1} ⋆ \dots ⋆ x_{k + 1}$ and then an arbitrary bracketing of the product which is syntactically valid, it must have the form $(e_{a}) ⋆ (e_{b})$ where $a + b = k + 1$ where without loss of generality $a \geq 2$ and $b \geq 1$ , due to this we also know that $a, b \leq 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 $(e_{a}) ⋆ (e_{b}) = (((x_{1} ⋆ x_{2}) ⋆ \dots) ⋆ x_{a}) ⋆ (((x_{a + 1} ⋆ x_{a + 2}) ⋆ \dots) ⋆ x_{a + b})$ 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 $⋆$ . Closing our left eye, we can observe that: $(e_{a}) ⋆ (e_{b - 1} ⋆ x_{a + b}) = (e_{a} ⋆ e_{b - 1}) ⋆ x_{a + b}$ Now $(e_{a} ⋆ e_{b - 1})$ is a arbitrarily bracketed expression of using $a + b - 1 < 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 $(e_{a} ⋆ e_{b - 1}) ⋆ x_{a + b} = (((x_{1} ⋆ x_{2}) ⋆ \dots) ⋆ x_{b - 1}) ⋆ x_{a + b}$

Chaining equalities, we've proven that $(e_{a}) ⋆ (e_{b}) = (((x_{1} ⋆ x_{2}) ⋆ \dots) ⋆ x_{b - 1}) ⋆ 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

⋆ : S \times S \to S

is associative, and

(x_{1}, \dots x_{k})

is a tuple in

ℕ_{1}

, then

foldl (⋆, (x_{1}, \dots x_{k})) = foldr (⋆, (x_{1}, \dots, x_{k}))

Since all bracketings are equal, then specifically these bracketing are equal

Fold of a Composition Law

Suppose that

⋆ : S \times S \to S

is a composition law, and

(x_{1}, \dots x_{k})

a tuple in

ℕ_{0}

for

k \in ℕ_{1}

fold (⋆, (x_{0}, x_{1}, \dots, x_{k})) : = foldl (⋆, (x_{0}, x_{1}, \dots, x_{k}))

Sum Fold

Suppose we have

+ : ℝ \times ℝ \to ℝ

then and

R \subseteq ℝ

a finite tuple, then we define

\sum R = fold (+, R)

in terms of the sum fold

Ellipses Notation

Suppose that

⋆ : S \times S \to S

is a composition law, and

(x_{1}, \dots x_{k})

a tuple in

ℕ_{0}

for

k \in ℕ_{1}

x_{1} ⋆ x_{2} ⋆ \dots ⋆ x_{k} : = fold (⋆, (x_{0}, x_{1}, \dots, x_{k}))

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 $fold (+, (a_{0}, \dots, a_{k}))$

Composition Law

A composition law is an associative binary operation

Identity Element

Given a set

S

and a binary relation

⋆

, we say that an element

e \in S

is an identity element on

S

when for every

s \in S, e ⋆ s = s ⋆ e = s

Binary Operation has Inverses For an Identity

Given a set

S

and a binary operation

⋆

S

, that has an identity element

e

, then we say that $⋆$ has inverses for $e$ if for every

s \in S

, there exists some

r \in S

such that

s ⋆ r = e

Group

We say that

(G, ⋆)

where

G

is a set and

⋆

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 ⋆ b = b ⋆ 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

ℤ, +

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 + \dots + 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

⋆

is a constant composition law, then

(T, ⋆)

forms a group

Let $t$ be the only element of $T$ , we claim this is the identity, which we can verify by checking $t ⋆ t = t$ , because $⋆$ 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 ⋆ 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 ⋆ g = g ⋆ f = f

since

g

is an identity element, but also

g ⋆ f = f ⋆ 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 ⋆ b = b ⋆ a = e

Suppose that

b

and

c

are both inverses to

a

, thus

a ⋆ b = e = c ⋆ a

, then

c = c ⋆ e = c ⋆ (a ⋆ b) = (c ⋆ a) ⋆ b = e ⋆ b = b

so then

c = b

Inverse

Given a group

G

and

a \in G

, we denote the unique element

b

such that

a ⋆ b = b ⋆ a = e

a^{- 1}

and call it the inverse of

a

two inverses cancel

{(a^{- 1})}^{- 1} = a

To show this is true we want to show that

a^{- 1} ⋆ a = a ⋆ a^{- 1} = e

, though the definition of

a^{- 1}

is such that

a ⋆ a^{- 1} = a^{- 1} ⋆ 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

{(a ⋆ b)}^{- 1} = b^{- 1} ⋆ a^{- 1}

For ease let

c = {(a ⋆ b)}^{- 1}

, so that

(a ⋆ b) ⋆ c = c ⋆ (a ⋆ b) = e

since we know

(a ⋆ b) ⋆ c = a ⋆ (b ⋆ c) = e

, and thus

a^{- 1} ⋆ (a ⋆ (b ⋆ c)) = a^{- 1} ⋆ e

, thus

(a^{- 1} ⋆ a) ⋆ (b ⋆ c) = a^{- 1} e

, which simplifies to

e ⋆ (b ⋆ c) = a^{- 1}

, so we can see that

a^{- 1} = b ⋆ c

, as needed

Cancellation

Suppose

G

is a group and

a, b, c \in G

, then

a ⋆ c = b ⋆ c ⟹ a = b

and

c ⋆ a = c ⋆ b ⟹ a = b

, in other words, we can cancel common elements on right and left

Suppose that

a ⋆ c = b ⋆ c

, let

c^{- 1}

be the inverse of

c

, then we have the following

\begin{matrix} a ⋆ c = b ⋆ c & a m p; ⟺ \\ (a ⋆ c) ⋆ c^{- 1} = (b ⋆ c) ⋆ c^{- 1} & a m p; ⟺ \\ a ⋆ (c ⋆ c^{- 1}) = b ⋆ (c ⋆ c^{- 1}) & a m p; ⟺ \\ a ⋆ e = b ⋆ e & a m p; ⟺ \\ a = b \end{matrix}

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

| G |

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

ℤ, +

where

+

is defined in the usual sense form an abelian group

Cartesian Product of Abelian Groups is Abelian

Let

(G, ⋆)

be an abelian group, then

G^{n}

forms an abelian group with the operation

\oplus︎

defined for

a, b \in G^{n}

a \oplus︎ b : = (a_{1} ⋆ b_{1}, \dots, a_{n} ⋆ b_{n})

Can the above be generalized for any extra group properties?

Multiplicative Notation

Given a group $(G, ⋆)$ 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 ⋆ b$ to reduce visual clutter

note: since $\cdot$ is also a simple thing to write, we may also use it in place of $⋆$

Power of an Element

Given a group

G

and

a \in G

, then we define

a^{n} : = \overset{n times}{\overset{⏞}{a a \dots a}}

for any

n \in ℤ^{> 0}

and

a^{0} : = e

, when

n \in ℤ^{< 0}

then

a^{n} : = {(a^{- 1})}^{n}

, thus we've defined

a^{n}

for all

n \in ℤ

Power Properties

For all

a, b \in G

a^{n} a^{m} = a^{n + m}

and

{(a^{n})}^{m} = a^{n m}

for any

m, n \in ℤ

TODO

Order of a Group Element

The order of an element

a \in G

, denoted

| a |

, is the smallest

n \in ℕ_{1}

such that

a^{n} = e

Suppose

G

is a group and that

a \in G

a

has finite order given by

n \in ℕ_{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 | k

We know that

a^{k} = e = a^{0}

therefore

k % n = 0 % n = 0

therefore

n | k

as needed.

Subgroup

Suppose that

(G, ⋆)

is a group, then if

H \subseteq G

is a group under

⋆

, then we say that

H

is a subgroup of

G

and write

H ⩽ G

Let

G

be a group. Given a non-empty

H \subseteq G

a b^{- 1} \in H

for any

a, b \in H

, then

H ⩽ 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 ⋆ s = s ⋆ 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 $⋆$ we know that it was composition law meaning that this operation is closed for elements in $G$ , so we also need to verify that $⋆$ is closed in $H$ , that is to say that $⋆$ 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 {(y^{- 1})}^{- 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 $| a | = 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

ℚ, ℝ, ℂ

are groups under multiplicaiton

TODO

Generator

The notation

⟨ a ⟩

denotes the set

{a^{n} : n \in ℤ}

. Then

a \in G

is said to be a generator of

g

if and only if

G = ⟨ a ⟩

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 = ⟨ a ⟩

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

| a | = n

, then

⟨ a^{k} ⟩ = ⟨ a^{\gcd (n, k)} ⟩

and

| a^{k} | = \frac{n}{\gcd (n, k)}

TODO

For a group

G

and

a \in G

, then

| a |

divides

| G |

TODO