Permutation Groups and Symmetric Groups | Abstract Algebra

Summary

This video script delves into the concept of permutations as a fundamental aspect of abstract algebra. It defines permutations as bijections from a set to itself and explains how they form groups under function composition. The script covers the properties of group operations, such as associativity, identity, and inverses, using the symmetric group notation S_a and S_n as examples. It also provides a detailed exploration of the symmetric group S3, illustrating the composition of permutations and identifying inverses through a comprehensive table.

Takeaways

• 🔄 A permutation is a reordering of elements in a set, which can be thought of as a bijection from a set to itself.
• 🔄 The operation between permutations is function composition, where one permutation is applied before another.
• 🔄 Function composition is associative, meaning the order in which compositions are performed does not affect the result.
• 🔄 The composition of permutations is closed, meaning that composing any two permutations results in another permutation.
• 🔄 There exists an identity element in permutation groups, which is the identity function that leaves all elements unchanged.
• 🔄 Every permutation has an inverse that, when composed with the original permutation, results in the identity permutation.
• 🔄 Permutations on a set form a group, with the set of all permutations of a set denoted as S_a, and specifically for the first n positive integers as S_n.
• 🔄 Symmetric groups, denoted by S_n, represent all possible permutations of a set and can be likened to the symmetries of an object.
• 🔄 A group of permutations may refer to a subgroup of a symmetric group, not necessarily containing all permutations.
• 🔄 The number of permutations for a set of n objects is n factorial, as demonstrated by the six permutations in the symmetric group S3.
• 🔄 The inverse of a permutation can be found using a composition table, which shows the result of composing any two permutations from the group.

Q & A

What is a permutation?

A permutation is a reordering of elements in a set, and more rigorously, it is a bijection from a set to itself, meaning it is a one-to-one and onto mapping that rearranges the elements of the set without changing their quantity.

Why are permutations considered groups in abstract algebra?

Permutations are considered groups because they satisfy the four group axioms: closure (composition of any two permutations results in another permutation), associativity (the composition of permutations is associative), identity (there exists an identity permutation that leaves all elements unchanged), and inverses (every permutation has an inverse that undoes its effect).

What is the operation between permutations?

The operation between permutations is function composition, where one permutation is applied after another, resulting in a new permutation.

What is the identity element in the group of permutations?

The identity element in the group of permutations is the identity function, denoted as Epsilon, which maps each element to itself, leaving the set unchanged.

How do you find the inverse of a permutation?

The inverse of a permutation is found by reversing the effect of the original permutation such that when composed with the original permutation, the result is the identity permutation. Each element is mapped to its original position before the permutation was applied.

What is the significance of the symmetric group notation S_a?

The notation S_a stands for the symmetric group on the set 'a', which is the set of all permutations of the elements in 'a'. It is called 'symmetric' because each permutation can be seen as a symmetry of the set.

What is the difference between a symmetric group and a group of permutations?

A symmetric group, denoted as S_a or S_n, contains all possible permutations of a set. A group of permutations, on the other hand, may refer to any group G that is a subgroup of a symmetric group, and does not necessarily include all permutations.

How many permutations are there in the symmetric group S3?

There are six permutations in the symmetric group S3, as the number of permutations of 'n' objects is n factorial, and for S3, n=3, so 3! = 6.

Can you provide an example of composing two permutations from the symmetric group S3?

Sure, if we take the permutations Beta and Gamma from S3 and compose them (Beta composed with Gamma), we first apply Gamma which swaps 1 with 2 and leaves 3 unchanged, and then apply Beta which swaps 1 with 3 and 2 with 2, resulting in a new permutation where 1 maps to 1, 2 maps to 3, and 3 maps to 2.

What does it mean for a permutation to be its own inverse?

A permutation is its own inverse if composing it with itself results in the identity permutation. This means that applying the permutation and then applying it again leaves the set unchanged, effectively undoing the first application.

How can you verify that the composition of two permutations results in another permutation?

You can verify this by applying the first permutation to the set, then applying the second permutation to the result of the first. If the final arrangement of elements is a bijection from the set to itself, then the composition is indeed another permutation.

Outlines

00:00

🔄 Introduction to Permutations and Groups

This paragraph introduces the concept of permutations as reorderings of elements and their mathematical definition as bijections from a set to itself. It explains the operation of function composition for combining permutations and highlights the properties that make permutations form a group, such as closure, associativity, and the existence of an identity element and inverses. The paragraph sets the stage for a deeper exploration of abstract algebra through the study of permutations.

05:00

🔄 Properties of Permutation Composition

The second paragraph delves into the properties of the operation used to combine permutations, which is function composition. It establishes that this operation is associative due to the nature of function composition and that the composition of permutations is closed, meaning that composing any two permutations results in another permutation on the same set. The paragraph also introduces the identity permutation, which leaves elements unchanged, and discusses the concept of inverse permutations, which when composed with their corresponding permutation, yield the identity permutation.

10:03

🔄 Symmetric Groups and Permutation Examples

This paragraph discusses symmetric groups, denoted as S_A or S_n, which are groups of all permutations on a set. It uses the example of the symmetric group S3, which contains all permutations of the set {1, 2, 3}, to illustrate how permutations can be combined through composition. The paragraph provides a detailed table showing the results of composing different permutations from S3, demonstrating the concept of inverse permutations and reinforcing the group properties of permutations.

15:06

🔄 Conclusion and Further Exploration

The final paragraph concludes the discussion on permutations and groups, emphasizing that permutations form groups due to the presence of an identity element, closure, associativity, and inverses. It clarifies the distinction between a symmetric group, which contains all permutations of a set, and a group of permutations, which could be a subgroup of a symmetric group. The paragraph invites the viewer to explore more examples of groups of permutations in future videos and encourages questions and video requests in the comments.

Keywords

💡Permutation

A permutation is a bijective function from a set to itself, essentially a reordering of elements within the set. In the context of the video, permutations are used to demonstrate the concept of a group in abstract algebra. For example, switching the positions of 'A' and 'B' in the sequence 'ABC' is a simple permutation. The video script uses permutations to illustrate the elements of a group and how they can be combined through function composition.

💡Bijection

A bijection is a one-to-one correspondence between the elements of two sets. In the video, a permutation is defined as a bijection from a set to itself, meaning each element is mapped to a unique element in the same set. The script provides examples of bijections, such as mapping the set {1, 2, 3} to itself in a way that each number is sent to a different element or to itself, which are both valid permutations.

💡Function Composition

Function composition is the process of applying one function to the result of another. In the script, it is the operation used to combine permutations. The notation 'Alpha of beta' means that permutation beta is applied first, followed by Alpha. The video demonstrates how function composition is used to create new permutations from existing ones, which is crucial for understanding the group structure of permutations.

💡Associativity

Associativity is a property of an operation that states that the way numbers are grouped does not change their sum or product. In the video, it is explained that function composition, and thus the composition of permutations, is associative. This property is fundamental to the group structure because it allows for the combination of permutations in any order without affecting the result, as shown in the script with the composition of permutations Alpha and Beta.

💡Closure

Closure refers to the property that the result of an operation within a set is also in that set. The video script explains that the composition of permutations is closed, meaning that composing any two permutations from a set results in another permutation from the same set. This is a key requirement for a set of elements to form a group in abstract algebra.

💡Identity Element

An identity element is an element that, when combined with another element through an operation, leaves the other element unchanged. In the context of permutations, the identity function is the permutation that leaves every element in the set unchanged. The script illustrates this with the function Epsilon, which is the identity for permutation composition and is crucial for the group structure.

💡Inverse

An inverse is an element that, when combined with another element through an operation, yields the identity element. The script explains that every permutation has an inverse that is also a permutation, and composing a permutation with its inverse results in the identity permutation. This concept is important for understanding the group structure of permutations, as it ensures that every element has a counterpart that 'undoes' its effect.

💡Symmetric Group

A symmetric group, denoted by S_A or S_n, is the group of all permutations of a set. The script introduces the concept of symmetric groups as a specific type of group in abstract algebra, where each permutation represents a symmetry of the set, similar to rotating a square back onto itself. The symmetric group on the set of the first n positive integers is particularly common and is denoted by S_n.

💡Group

In abstract algebra, a group is a set equipped with an operation that combines any two of its elements to form a third element in the set, satisfying four main properties: closure, associativity, identity, and invertibility. The script demonstrates that the set of all permutations of a set, with function composition as the operation, forms a group, satisfying all these properties.

💡S3

S3, or the symmetric group on three elements, is the group consisting of all possible permutations of the set {1, 2, 3}. The script uses S3 as an example to illustrate the composition of permutations, showing the six unique permutations and how they can be combined to form other permutations within the group. This example helps to concretely demonstrate the abstract concepts discussed in the video.

Highlights

A permutation is defined as a bijection from a set to itself, essentially a reordering of elements.

The operation between permutations is function composition, which is associative and closed.

The identity element in permutation composition is the identity function, which leaves elements unchanged.

Every permutation has an inverse that is also a permutation, ensuring the group structure.

The set of all permutations of a set, with function composition as the operation, forms a group.

The symmetric group on a set is denoted by S_A, representing all permutations of the set.

S_n specifically refers to the symmetric group on the first n positive integers.

A group of permutations can be a subgroup of a symmetric group, not necessarily containing all permutations.

The number of permutations of n objects is n factorial, demonstrated with S3 having six elements.

The composition of two permutations results in another permutation, as shown with beta and gamma in S3.

A full table of permutations in S3 and their compositions can be used to identify inverse permutations.

Alpha permutation is its own inverse, demonstrated through its composition with itself resulting in the identity.

The concept of function composition is applied from right to left when composing permutations.

The practical application of permutations is likened to the symmetries of geometric shapes, like rotating a square.

The video provides a detailed example of composing permutations in S3, illustrating group properties.

The video concludes with an invitation for viewers to engage with questions or video requests.

Transcripts

let's go over what a group of

permutations is will cover definitions

why these things are groups we'll also

cover symmetric groups and we'll see how

we combine permutations in a group this

will give us a whole array of new

examples of groups to study as we

continue learning abstract algebra now

what is a permutation you may just think

of it as a reordering of something we

might have ABC in this order and we

could permute it into this other order

maybe we switch A and B so in A's place

we now have B and in B's place we now

have a and we leave C unchanged that

would be an example of a permutation but

for our purposes we'll need a slightly

more rigorous definition this more

rigorous definition is actually quite

simple a permutation is just a bijection

from a set to itself I'll leave a link

in the description if you need a recap

of what by objections are but here are

two quick examples of bijections from a

set to itself so these are both

permutations these are both permutations

on the set containing one two and three

this permutation Alpha takes one as an

input and sends it to two it Maps two to

one and it Maps three to itself this

other permutation beta takes one and

Maps it to two it takes two and Maps it

to three and it Maps three to one these

are each bijections from this set one

two three back to itself they basically

just Shuffle the elements around we're

thinking about how groups are

constructed with permutations so what

would the operation be between

permutations well again a permutation is

just a special type of function so the

operation is function composition and it

works quite simply if we want to compose

the permutation Alpha with the

permutation beta we would write it like

this Alpha of beta just remember how the

notation works this means that the

permutation beta is applied first and

then Alpha is applied so we start with 1

2 3 and first we apply beta that sends

one to two two to three and three to one

and then we apply Alpha which takes 2

and sends it to one it takes three and

sends it to three and it takes one and

sends it to two so the net effect of

composing Alpha with beta was to send

one to one two to three and three to two

it gave us another permutation so we've

got this idea of permutations by

ejections from sets to themselves and

we've got this operation between them

composition now let's discuss some

properties that this operation has

firstly it is associative this is

because function composition is

associative so the composition of

permutations is associative as a result

to quickly prove it let's just recall

what function composition is its

notation is this F of G of some input X

and what it means is evaluate the

function f at the function G at X so F

of G of X is f of G of x to prove this

operation is associative we need to show

that F composed with G of H of X is

equal to F of G composed with h of X and

this is done through repeated

applications of the definition F

composed with G of H is by definition F

of G decomposed with h but then F of G

composed with h is by definition F of G

of H but then F of G evaluated at h of X

is just F composed with G evaluated at h

of X which by definition is f composed

with G of H of X and so indeed

composition between permutations more

generally function composition itself is

associative earlier we took the

composition of two permutations and got

another permutation this is of course

true in general that the composition of

permutations is closed this is because

if we compose by ejections from a set a

to itself we will get another bijection

from the set a to itself so if we just

have a bunch of permutations of this at

a and we compose any two of them we'll

just get another permutation on the set

a I'll leave a link in the description

to my lesson proving that the

composition of bijections is a bijection

which thus gives us this result of

closure for permutations but I hope

you'll agree it's a fairly easy result

to accept each permutation just shuffles

a set into some order and so if we

permute a set and then permute it again

which is composing permutations you're

just going to get the set shuffled in

some order so again you're going to get

a permutation on that same set moving on

let's quickly talk about the identity do

we have an identity element when it

comes to composing permutations we

certainly do for any set a the identity

function on a is this guy we could call

Epsilon it goes from a back to a and it

takes each input and leaves it unchanged

so the identity function Epsilon of x

equals X

certainly by definition this Epsilon is

a permutation it is a bijection from a

to itself and we see if we compose

Epsilon with any other permutation that

just gives us the permutation right back

this is fairly easily demonstrated as I

wrote out in these equations just

explaining this one for example if we

compose Epsilon with any permutation F

by definition that's taking F and

plugging it into Epsilon but Epsilon

doesn't change the input so we just get

F back out so Epsilon of f is f so

indeed Epsilon is our identity element

when it comes to composing permutations

if we compose any permutation with this

identity function the permutation is

left unchanged now that we have an

identity element we can start to think

about inverses recall that permutations

are just bijections from a set to itself

off hopefully you're familiar with the

fact that bijections have inverses and

I'll leave a link in the description to

my lesson proving it if you need to see

that but we know every bijection has an

inverse that is also a by ejection and

thus every permutation has an inverse

that is also a permutation now we need

to be careful we're talking specifically

about inverse functions this doesn't

necessarily mean that these inverse

functions are the inverses in the

context of the groups that we're trying

to create but we can quickly check that

in fact they are exactly what we're

looking for if we have an inverse

function f inverse composed with the

original function f by definition we get

the identity function and here's some of

the details of that written out in One

Direction if we take F inverse which

could just be the inverse of a

permutation and compose it with f itself

well by definition that means we're

plugging f of x into F inverse but by

definition of inverse functions and in

this context inverse permutations these

guys just undo each other leaving the

inside element X unchanged so indeed we

have inverse elements for our

permutations going back to the first

permutation Alpha that we saw at the

beginning of the video this would be

Alpha inverse Alpha sends one to two but

Alpha's inverse element sends two back

to one alpha sends two to one the alpha

inverse sends one back to two and they

both leave three unchanged if we

permuted a set with Alpha and then with

Alpha inverse the set would be unchanged

if we permuted it with Alpha inverse and

then Alpha it would also be unchanged if

you compose a permutation with its

inverse that ends up not changing

anything at all you get the identity so

we've got inverse elements we've got an

identity element we've got closure we've

got associativity we've got groups and

that's our big result for any set a the

set of all permutations of a the set of

all bijections from a to itself along

with the operation of function

composition is a group these are groups

of permutations here's some common

notation S Sub a stands for the

symmetric group on the set a this is

just the set of all permutations of a

it's called a symmetric group because

each permutation of a set is like one of

the sets symmetries very much like how

you could rotate a square and place the

square back onto itself you can permute

the elements of a set and place them

back onto the set that's like a

bijection in right and then S Sub n this

is the symmetric group specifically on

the set of the first n positive integers

so the group of all permutations of 1

through n and then generally if we say a

group of permutations we're referring to

any group essay or SN any of these

symmetric groups or any subgroup of one

of these two groups so a symmetric group

S A has all permutations on the set a

but a group of permutations doesn't

necessarily need to have all

permutations so when we say a group of

permutations we could be referring to a

subgroup of asymmetric group doesn't

necessarily have to be the whole

symmetric group let's dig more into

detail with an example here is the full

symmetric group S3 every permutation on

the set of positive integers one through

three as you might expect there are six

elements you may recall that the number

of permutations of three objects is

three factorial so unsurprisingly we

have six different permutations here the

notation I've used is a common notation

for permutations that I think you'll

agree is pretty straightforward here for

Epsilon what this notation means is that

the permutation Epsilon takes one and

sends it to one takes two sends it to

two it takes three and sends it to three

this is of course the identity

permutation meanwhile the permutation

gamma sends one to two two to one and

three to three if we come over to the

permutation Kappa it sends one to three

and so on so these are all six

permutations of one two and three we can

try taking two permutations from this

symmetric group S3 and composing them

let's look at beta composed with gamma

remember when doing function composition

the function on the right acts first so

first we would apply this permutation

gamma it sends one to two two to one and

three to three then we apply beta beta

sends two to one it sends one to three

and it sends three to two so the net

effect of this composition is that one

gets sent to let me make my highlighter

a little smaller one gets sent to one

because gamma sent it to two but beta

sent two back to one two gets sent to

three because gamma sends two to one but

beta sent one to three and three gets

sent to two because gamma sends three to

three but beta takes three and sends it

two if you look back at the list of

permutations of S3 it turns out that

when we compose beta with gamma what we

get is Alpha our composition sent one to

one just like Alpha does it sent two to

three just like Alpha and it sent three

to two which is also what Alpha does

this of course isn't a surprise that

composing the permutations would give us

another permutation let's now take a

look at the full table if we compose any

two permutations from S3 what

permutation do we get here's the full

results in this table the function that

would act first the one that would be on

the right if you did function

composition is in the top row and the

function that would act second the

function that would be on the left in

function composition is here on the

leftmost column so if we want to look

for example at what we get if we compose

beta with gamma we would would go to

gamma first as the function on the right

so look at Gamma in the column and then

go down to the beta row and what we get

no surprise is Alpha and this is the

Full Table showing us what we would get

if we composed any two of these

permutations together if we looked at

Gamma of Kappa for example we would

start at Kappa and go down to the gamma

row that turns out to be beta if we want

to see what beta of alpha would be we'd

start at the alpha column and go down to

the beta row we see that that gives us

Kappa these are the full results feel

free to check them yourself as a fun

exercise using this table we can also

pick out inverse permutations if we look

at Delta for example we see that we get

Epsilon the identity function when Delta

is composed with the beta so Delta and

beta are inverses if we go to the beta

column we get the identity function at

the Delta Row the inverse of alpha

interestingly is alpha alpha is its own

inverse let's quickly go through that

calculation Alpha is the permutation

that sends one to one two to three and

three to two it's inverse based on the

table is itself so let's try taking

Alpha inverse and composing it with

Alpha and see what we get when composing

permutations another way we can write

them is like this in this sort of

product notation and again it's function

composition so we want to go from right

to left starting with this permutation

and then going to that one so let's look

at where one would get sent Alpha

inverse sends one to one and then Alpha

sends one to one so one just goes to one

Alpha inverse sends two to three but

then Alpha sends three back to two so if

we put 2 in this composition it will

first get sent to three but then get

sent back to two and then three gets

sent to two by Alpha inverse and then

Alpha sends two back to three so no

surprise if we can pose Alpha with its

inverse which happens to be itself one

just gets sent to one two to two and

three to three there is just an identity

permutation of nothing being moved at

all this is of course what you'll get if

you take any permutation from this table

and try composing it with its inverse

and if you want to try doing a few more

of those on your own here again is the

complete list of the six permutations of

S3 and I think that's enough for now

remember a permutation is just a

bijection from a set to itself we can

combine permutations with function

composition this is a closed operation

if we compose permutations from a set to

itself we get another permutation on

that same set we also have an identity

permutation which doesn't move any

elements at all and each permutation has

an inverse Additionally the operation of

composition is associative so

permutations on a set form groups we

denote the group of permutations on a

set a as S A and if that set happens to

be the first and positive integers we

denote it as s n and when we talk about

a group of permutations we might be

referring to one of these full symmetric

groups with all the permutations on a

particular set or we may be talking

about a subgroup of one of the bigger

symmetric groups in the next video we'll

see some more interesting examples of

groups of permutations let me know in

the comment if you have any questions or

video requests

[Music]

[Music]