Isomorphism between $M$ and $S_3$: Finding the Corresponding Function

[mathmari]

Hey!

I want to show that $M=\{\tau \in S_4\mid \tau (4)=4\}$ is isomorphic to $S_3$.

To do that we have to consider a function $f(x)$ that gives the isomorphism of $M$ with $S_3$, i.e., we have to describe what $f(x)$ is in $S_3$ for each $x\in M$, right?

We have that $f(\tau)\in \{1,2,3\}$ for $\tau \in S_3$ and $f(\tau (4))=4$, right?

How can we define that function? Which is the formula? (Wondering)

 

[I like Serena]

Hey!

I want to show that $M=\{\tau \in S_4\mid \tau (4)=4\}$ is isomorphic to $S_3$.

To do that we have to consider a function $f(x)$ that gives the isomorphism of $M$ with $S_3$, i.e., we have to describe what $f(x)$ is in $S_3$ for each $x\in M$, right?

We have that $f(\tau)\in \{1,2,3\}$ for $\tau \in S_3$ and $f(\tau (4))=4$, right?

How can we define that function? Which is the formula? (Wondering)

Hi mathmari! (Smile)

Not quite.
Let's reserve $\tau$ to be an element of $M \subseteq S_4$ and let's consider $\sigma \in S_3$.
Then $\sigma \in S_3 = \{ (1), (1 2), ..., (1 2 3) \}$.
And $\tau = f(\sigma) \in M \subseteq S_4 = \{ (1), (1 2), ..., (1 2 3 4) \}$.

We can pick $f: S_3 \to M$ given by $\tau = f(\sigma)$ such that $\tau(1) = \sigma(1), \tau(2) = \sigma(2), \tau(3) = \sigma(3), \tau(4) = 4$. (Nerd)

 

[mathmari]

Let's reserve $\tau$ to be an element of $M \subseteq S_4$ and let's consider $\sigma \in S_3$.
Then $\sigma \in S_3 = \{ (1), (1 2), ..., (1 2 3) \}$.
And $\tau = f(\sigma) \in M \subseteq S_4 = \{ (1), (1 2), ..., (1 2 3 4) \}$.

We can pick $f: S_3 \to M$ given by $\tau = f(\sigma)$ such that $\tau(1) = \sigma(1), \tau(2) = \sigma(2), \tau(3) = \sigma(3), \tau(4) = 4$. (Nerd)

(Thinking)

We have to show that this function is bijective, right? (Wondering)

For each $\tau$ there is a $x$ such that $\tau (i)=x, i=1,2,3,4$, so $f$ is onto.

For $\tau (i)= \tau (j)$ we have that $i=j$, so $f$ is 1-1.

Is this correct? (Wondering)

 

[I like Serena]

We can pick $f: S_3 \to M$ given by $\tau = f(\sigma)$ such that $\tau(1) = \sigma(1), \tau(2) = \sigma(2), \tau(3) = \sigma(3), \tau(4) = 4$. (Nerd)

Btw, we can shorten this by saying: let $f: S_3 \to M$ be the canonical function (that is, the "obvious" or "trivial" function). (Nerd)

We have to show that this function is bijective, right? (Wondering)

For each $\tau$ there is a $x$ such that $\tau (i)=x, i=1,2,3,4$, so $f$ is onto.

For $\tau (i)= \tau (j)$ we have that $i=j$, so $f$ is 1-1.

Is this correct? (Wondering)

To show bijectivity, we typically need to show surjectivity and injectivity.
That is, each element in the codomain has at least one original and at most one original.
Sometimes we can immediately see that there is exactly one original.

In this case we might say that any $\tau \in M$ has $\tau(4)=4$, which means that its original in $S_3$ is uniquely defined.
That is, $f$ is 1-1 and onto, and is therefore bijective.

More formally, to show surjectivity, we would need to suppose that $f$ is not surjective, and then prove this leads to a contradiction. The same for injectivity.

Btw, we also need to show that $f$ is homomorphic. (Nerd)

 

[mathmari]

Btw, we can shorten this by saying: let $f: S_3 \to M$ be the canonical function (that is, the "obvious" or "trivial function). (Nerd)

Why is this the obvious function? (Wondering)

In this case we might say that any $\tau \in M$ has $\tau(4)=4$, which means that its original in $S_3$ is uniquely defined.
That is, $f$ is 1-1 and onto, and is therefore bijective.

Could you explain it further to me? Why do we look only at $\tau (4)$ ? (Wondering)

More formally, to show surjectivity, we would need to suppose that $f$ is not surjective, and then prove this leads to a contradiction. The same for injectivity.

Suppose that $f$ is not surjective, that means that one element of $M$ has no corresponding element in $S_3$, right? (Wondering)
But the function is defined as follows:
$\tau(1) = \sigma(1), \tau(2) = \sigma(2), \tau(3) = \sigma(3), \tau(4) = 4$
So, in each case, except $\tau (4)=4$, we have a $\sigma (i)$ that is equal to $\tau (i)$, right? (Wondering)
But what about $\tau (4)=4$ ? (Wondering)

Suppose that $f$ is not injective, that means that one element of $S_3$ has no corresponding element in $M$.
The element of $S_3$ are $\sigma (1), \sigma (2), \sigma (3)$, or not? (Wondering)
From the definition of the function we have that each of them is equal to a $\tau (i) \in M$.
Is this correct? (Wondering)

Btw, we also need to show that $f$ is homomorphic. (Nerd)

To do that do we have to show that $f(\sigma_1 \circ \sigma_2)=f(\sigma_1)\circ f(\sigma_2)$ ? (Wondering)

 

[Deveno]

The function you are looking for is:

$\phi:S_3 \to S_4$, where given $\sigma \in S_3$, $\phi(\sigma) = \tau$ is the function $\{1,2,3,4\} \to \{1,2,3,4\}$

$\tau(1) = \sigma(1)$
$\tau(2) = \sigma(2)$
$\tau(3) = \sigma(3)$
$\tau(4) = 4$.

Given $\tau \in M$, define:

$\psi(\tau) = \mu$ to be the element of $S_3$ such that:

$\mu(1) = \tau(1)$
$\mu(2) = \tau(2)$
$\mu(3) = \tau(3)$

that is $\mu = \tau|_{\{1,2,3\}}$ ($\tau$ *restricted* to the subset $\{1,2,3\} \subseteq \{1,2,3,4\}$).

Since $S_3$ and $M$ are FINITE (both have $6$ elements, which I urge you to find explicitly), either surjectivity or injectivity is sufficient to show bijectivity of $\phi$.

One can also show that $\psi\circ\phi = \text{id}_{S_3}$, the identity automorphism of $S_3$, and that $\phi\circ\psi = 1_M$, the identity automorphism of $M$, although this might be a bit confusing to "keep straight".

The idea involved here is that an element of $S_3$ permutes three objects (which we label "1", "2" and "3"). The elements of $M$ ALSO permute three objects, since $M$ leaves "4" unchanged (fixed).

You have to be careful about what you call "elements", here.

The elements of $S_3$ and $M$ are FUNCTIONS, whereas the elements of $\{1,2,3\}$ and $\{1,2,3,4\}$ are NUMBERS.

Our isomorphism is thus a "function between functions", introducing a third layer, which you need to keep distinct from the first two.

(As an aside, although the inclusion of $\{1,2,3\}$ into $\{1,2,3,4\}$ may seem "canonical", there are, in fact, four copies of $S_3$ in $S_4$, and from an algebraic standpoint, there is no reason to single out anyone of them as "the" inclusion", just as there is no reason to single out any any basis of a (finite-dimensional) vector space as "the" basis).

 

[mathmari]

The function you are looking for is:

$\phi:S_3 \to S_4$, where given $\sigma \in S_3$, $\phi(\sigma) = \tau$ is the function $\{1,2,3,4\} \to \{1,2,3,4\}$

$\tau(1) = \sigma(1)$
$\tau(2) = \sigma(2)$
$\tau(3) = \sigma(3)$
$\tau(4) = 4$.

I got stuck right now... Why is the function $\{1,2,3,4\} \to \{1,2,3,4\}$ and not $\{1,2,3\} \to \{1,2,3,4\}$ ? (Wondering)

 

[I like Serena]

Why is this the obvious function? (Wondering)

Because it's as close to the identity function as we can get. (Nerd)

(As an aside, although the inclusion of $\{1,2,3\}$ into $\{1,2,3,4\}$ may seem "canonical", there are, in fact, four copies of $S_3$ in $S_4$, and from an algebraic standpoint, there is no reason to single out anyone of them as "the" inclusion", just as there is no reason to single out any any basis of a (finite-dimensional) vector space as "the" basis).

For a function $S_3 \to M$ I think it is canonical, since it is given in $M$ that $\tau(4)=4$.

Could you explain it further to me? Why do we look only at $\tau (4)$ ?

Since we know that $\tau(4)=4$ that excludes $4$ from all further considerations.
That is, $\tau(1),\tau(2),\tau(3)$ are all elements of $\{1,2,3\}$, which identifies a permutation in $S_3$ uniquely.

Suppose that $f$ is not surjective, that means that one element of $M$ has no corresponding element in $S_3$, right?
But the function is defined as follows:
$\tau(1) = \sigma(1), \tau(2) = \sigma(2), \tau(3) = \sigma(3), \tau(4) = 4$
So, in each case, except $\tau (4)=4$, we have a $\sigma (i)$ that is equal to $\tau (i)$, right?
But what about $\tau (4)=4$ ?

The question is, if we can find an element in $M$ that is not mapped to an element in $S_3$.
Since $\tau(4)=4$, that means that $\tau(1), \tau(2), \tau(3) \in \{1,2,3\}$, so that the original is always an element in $S_3$. (Thinking)

Suppose that $f$ is not injective, that means that one element of $S_3$ has no corresponding element in $M$.
The element of $S_3$ are $\sigma (1), \sigma (2), \sigma (3)$, or not? (Wondering)
From the definition of the function we have that each of them is equal to a $\tau (i) \in M$.
Is this correct?

Not quite.
Not injective means that there is an element $\tau \in M$ that has at least 2 originals, say distinct $\sigma_1$ and $\sigma_2$.
So $f(\sigma_1) = f(\sigma_2) = \tau$.
Now we need to prove that $\sigma_1 = \sigma_2$. (Thinking)

To do that do we have to show that $f(\sigma_1 \circ \sigma_2)=f(\sigma_1)\circ f(\sigma_2)$ ? (Wondering)

Yep. (Nod)

 

[mathmari]

Since we know that $\tau(4)=4$ that excludes $4$ from all further considerations.
That is, $\tau(1),\tau(2),\tau(3)$ are all elements of $\{1,2,3\}$, which identifies a permutation in $S_3$ uniquely.

Ah ok... (Thinking)

The question is, if we can find an element in $M$ that is not mapped to an element in $S_3$.
Since $\tau(4)=4$, that means that $\tau(1), \tau(2), \tau(3) \in \{1,2,3\}$, so that the original is always an element in $S_3$. (Thinking)

I don't understand why $\tau(4)=4$ is mapped to an element in $S_3$. Could you explain it to me? (Wondering)

Not quite.
Not injective means that there is an element $\tau \in M$ that has at least 2 originals, say distinct $\sigma_1$ and $\sigma_2$.
So $f(\sigma_1) = f(\sigma_2) = \tau$.
Now we need to prove that $\sigma_1 = \sigma_2$. (Thinking)

We have that $$\tau (i)=\tau (j) \Rightarrow \sigma (i)=\sigma (j) , i,j\in \{1,2,3\} \\ \tau (i)=\tau (4) \Rightarrow \sigma (i)=4$$

What about $\sigma (i)=4$ ? (Wondering)

Yep. (Nod)

$$f(\sigma_1 \circ \sigma_2) \\ f(\sigma_1)\circ f(\sigma_2)$$ Do we take all the permutations? $\sigma_1(1), \sigma_1(2), \sigma_1(3)$, or do we calculate that? (Wondering)

 

[I like Serena]

I don't understand why $\tau(4)=4$ is mapped to an element in $S_3$. Could you explain it to me?

It isn't. (Shake)

Instead $\tau$ is mapped to an element in $S_3$.
It is given that $\tau(4)=4$ and the mapping of $\tau$ is such that $\sigma(i)=\tau(i)$ for $i=1,2,3$.

We have that $$\tau (i)=\tau (j) \Rightarrow \sigma (i)=\sigma (j) , i,j\in \{1,2,3\} \\ \tau (i)=\tau (4) \Rightarrow \sigma (i)=4$$

What about $\sigma (i)=4$ ? (Wondering)

Hold on. (Wait)
Suppose we pick $i=1,j=2$.
Are you saying that $\tau(1)=\tau(2)$?
That can't be right. They are different by definition. (Worried)

$\sigma(i) \ne 4$ by definition as well, since $\sigma \in S_3$.

$$f(\sigma_1 \circ \sigma_2) \\ f(\sigma_1)\circ f(\sigma_2)$$ Do we take all the permutations? $\sigma_1(1), \sigma_1(2), \sigma_1(3)$, or do we calculate that? (Wondering)

We should be a bit smart here.
Let's start with $i=1$.
Then the question is whether $f(\sigma_1 \circ \sigma_2)(1) = (f(\sigma_1)\circ f(\sigma_2))(1)$. (Wondering)
We do know that $\tau(1) = f(\sigma)(1) = \sigma(1)$, because that's how we defined $f$.

 

[mathmari]

Instead $\tau$ is mapped to an element in $S_3$.
It is given that $\tau(4)=4$ and the mapping of $\tau$ is such that $\sigma(i)=\tau(i)$ for $i=1,2,3$.

It's not really clear to me why we consider $\tau(4)=4$ seperately from the mapping. Is it because $\tau(4)=4$ is fixed? (Wondering)

Suppose we pick $i=1,j=2$.
Are you saying that $\tau(1)=\tau(2)$?
That can't be right. They are different by definition. (Worried)

How can we check if there is an element $\tau\in M$ that has at least $2$ originals? (Wondering)

Let's start with $i=1$.
Then the question is whether $f(\sigma_1 \circ \sigma_2)(1) = (f(\sigma_1)\circ f(\sigma_2))(1)$. (Wondering)
We do know that $\tau(1) = f(\sigma)(1) = \sigma(1)$, because that's how we defined $f$.

We have that $$f(\sigma_1 \circ \sigma_2)(1)=f(\sigma_1(\sigma_2(1)))=f(\sigma_1(f(\sigma_2)(1)))=(f(\sigma_1)\circ f(\sigma_2))(1)$$ right? (Wondering)

 

[I like Serena]

It's not really clear to me why we consider $\tau(4)=4$ seperately from the mapping. Is it because $\tau(4)=4$ is fixed? (Wondering)

The mapping is between 2 functions: $S_3 \to M$, or $(\{1,2,3\} \to \{1,2,3\}) \to (\{1,2,3,4\} \to \{1,2,3,4\})$.

How can we check if there is an element $\tau\in M$ that has at least $2$ originals? (Wondering)

That's what we have to figure out.
The point is that there isn't one.
That's because we know that for any $\tau \in M$ we have that $\tau(4)=4$ and that $\tau(i) \in \{1,2,3\}$ for $i=1,2,3$.
That means that if $\sigma_1$ and $\sigma_2$ are supposedly distinct originals, we have that $\sigma_1(i)=\sigma_2(i)=\tau(i)$ for $i=1,2,3$.
In other words, $\sigma_1 = \sigma_2$, which is the required contradiction. (Nerd)

We have that $$f(\sigma_1 \circ \sigma_2)(1)=f(\sigma_1(\sigma_2(1)))=f(\sigma_1(f(\sigma_2)(1)))=(f(\sigma_1)\circ f(\sigma_2))(1)$$ right? (Wondering)

Yup! (Nod)

 

[Deveno]

For a function $S_3 \to M$ I think it is canonical, since it is given in $M$ that $\tau(4)=4$.

Well, yes, that's true. I suppose the whole point of this could be summed up as "forget about 4".

However, that wasn't quite my point. Part of the point of the "abstract" in "abstract algebra" is to forget about the PARTICULARS of a given group, and focus on the PROPERTIES. For example, suppose we wanted to find an isomorphism from $S_3 \to N$, where:

$N = \{\rho \in S_4: \rho(3) = 3\}$.

Now, an "almost identity *function*" won't quite do the trick. It's convenient for this exercise to think of $S_3$ embedded in $S_4$ by "leaving out the last element of $\{1,2,3,4\}$".

But such an approach doesn't involve any *symmetry*, the order of 1,2,3 and 4 in the set $\{1,2,3,4\}$ is an artifact of our counting system, the group $S_4$ doesn't care if the four things it is permuting are numbers, or letters, or any set of four elements. Put another way, as far as $S_4$ is concerned "4" isn't special. The key idea is that if anyone element is fixed by a set of permutations, any product of permutations in that set ALSO fix that element.

I don't mean to sound critical of your posts, because "you're not wrong". Everything you posted is true, and well-presented. I just can't seem to help pointing out that a more abstract approach is more useful in the long run, where we may not have "the accident of natural numbers" to help out.

I worry, of course, that this may just confuse mathmari, which is counter-productive.

I got stuck right now... Why is the function $\{1,2,3,4\} \to \{1,2,3,4\}$ and not $\{1,2,3\} \to \{1,2,3,4\}$ ? (Wondering)

All the elements of $M$ are in $S_4$, and all of these are bijective mappings from $\{1,2,3,4\} \to \{1,2,3,4\}$.

$M$ is the subset of such mappings that map 4 to 4. The point of this exercise is to show that we can IDENTIFY (via an isomorphism) any such mapping with a unique element of $S_3$ that "does the same thing" (essentially). The elements of the group $S_3$ have a different domain and co-domain that the elements of $M$, but the only difference between these domains/co-domains is that 4 is in the domain = co-domain of everything in $M$, but not for the elements of $S_3$.

So in one direction we do this:

Extend $S_3$ to an action on the four-element set $\{1,2,3,4\}$ by taking $\sigma \in S_3$ and having $\sigma$ "do what it normally does" on 1,2, and 3, and having $\sigma$ "do nothing" to 4 (leave it fixed).

In the reverse direction, we take an element of $M$, and "forget about 4" (since it stays fixed), and just consider the bijective action of $M$ on "what's left" (1,2 and 3).

 

[mathmari]

The mapping is between 2 functions: $S_3 \to M$, or $(\{1,2,3\} \to \{1,2,3\}) \to (\{1,2,3,4\} \to \{1,2,3,4\})$.

(Thinking)

Is this a mapping between functions because $S_3$ and $M$ are already functions? (Wondering)

That means that if $\sigma_1$ and $\sigma_2$ are supposedly distinct originals, we have that $\sigma_1(i)=\sigma_2(i)=\tau(i)$ for $i=1,2,3$.

I haven't understood that... Could you explain it to me? (Wondering)

 

[I like Serena]

Is this a mapping between functions because $S_3$ and $M$ are already functions?

Elements of $S_3$ and $M$ are functions. (Nerd)

I haven't understood that... Could you explain it to me?

Suppose $f$ is not injective, then there must be an element $\tau \in M$ and distinct $\sigma_1, \sigma_2 \in S_3$ such that $f(\sigma_1)=f(\sigma_2)=\tau$.
We have defined $f$ such that if $f(\sigma)=\tau$, that then $\sigma(i)=\tau(i)$ for $i=1,2,3$.
That means that if $f(\sigma_1)=f(\sigma_2)=\tau$, that we have $\sigma_1(i)=\sigma_2(i)=\tau(i)$ for $i=1,2,3$.
And that in turn means that $\sigma_1 = \sigma_2$. (Thinking)

Is it enough to show that for $i=1$, or do we have to show that it holds for a general $i$ ?

We have to show it for general $i$.
In particular for $i=1,2,3$ and separately for $i=4$.
You knew that, didn't you? (Wondering)

 

[mathmari]

Suppose $f$ is not injective, then there must be an element $\tau \in M$ and distinct $\sigma_1, \sigma_2 \in S_3$ such that $f(\sigma_1)=f(\sigma_2)=\tau$.
We have defined $f$ such that if $f(\sigma)=\tau$, that then $\sigma(i)=\tau(i)$ for $i=1,2,3$.
That means that if $f(\sigma_1)=f(\sigma_2)=\tau$, that we have $\sigma_1(i)=\sigma_2(i)=\tau(i)$ for $i=1,2,3$.
And that in turn means that $\sigma_1 = \sigma_2$. (Thinking)

I got it now! (Bow)
I am reading again the part about the surjectivity of the function but I still don't understand the part about $\tau (4)=4$. (Sweating)

Could you explain it further to me? (Wondering)

We have to show it for general $i$.
In particular for $i=1,2,3$ and separately for $i=4$.
You knew that, didn't you? (Wondering)

For $i=1,2,3$ we have the following:

$$f(\sigma_1 \circ \sigma_2)(i)=(\sigma_1\circ\sigma_2)(i)=(f(\sigma_1)\circ f(\sigma_2))(i)$$

Is this correct? (Wondering) For $i=4$ we have the following:

$$f(\sigma_1 \circ \sigma_2)(4)=4$$ Or not? (Wondering)

How is this equal to $(f(\sigma_1)\circ f(\sigma_2))(4)$ ? (Wondering)

 

[Deveno]

I got it now! (Bow)
I am reading again the part about the surjectivity of the function but I still don't understand the part about $\tau (4)=4$. (Sweating)

Could you explain it further to me? (Wondering)


For $i=1,2,3$ we have the following:

$$f(\sigma_1 \circ \sigma_2)(i)=(\sigma_1\circ\sigma_2)(i)=(f(\sigma_1)\circ f(\sigma_2))(i)$$

Is this correct? (Wondering)

It is correct, although you *could* (if you wanted to,) put in some extra steps:

$f(\sigma_1 \circ \sigma_2))(i) = (\sigma_1\circ \sigma_2)(i) = \sigma_1(\sigma_2(i)) = \sigma_1(f(\sigma_2)(i))$

(here we are using the fact that $\sigma_2(i) \neq 4$, so that $f(\sigma_2)(i) = \sigma_2(i)$)

$= f(\sigma_1)(f(\sigma_2)(i))$

(here, we are using the fact that $f(\sigma_2)(i) \neq 4$, since elements of $S_4$ are bijective, and $4$ already has the pre-image $4$, so no other element can map to it)

$= f(\sigma_1)\circ f(\sigma_2)(i)$.

For $i=4$ we have the following:

$$f(\sigma_1 \circ \sigma_2)(4)=4$$ Or not? (Wondering)

Yes.

How is this equal to $(f(\sigma_1)\circ f(\sigma_2))(4)$ ? (Wondering)

By definition (of $M$) we have:

$f(\sigma_1)\circ f(\sigma_2)(4) = f(\sigma_1)(f(\sigma_2)(4)) = f(\sigma_1)(4) = 4$, since *every* element of $M$ takes $4 \mapsto 4$.

**************************

As regards your question on surjectivity, we can show this a number of ways. One way is to argue that since $S_3$ is finite, and $f$ is injective, we must have that $f$ is surjective since $|S_3| = |M| = 6$ (this is true of ANY function between two finite sets of equal size).

Another way is to exhibit, explicitly, a pre-image under $f$ in $S_3$, for any $\tau \in M$, that is: display some $\sigma \in S_3$ such that $f(\sigma) = \tau$.

So suppose $\tau \in M$. Say:

$\tau(1) = a$
$\tau(2) = b$
$\tau(3) = c$
$\tau(4) = 4$.

Since $\tau$ is a bijective mapping we have: $\{a,b,c\} = \{1,2,3\}$ (I am *not* claiming $a =1,b = 2, c= 3$, but just that $\{a,b,c\}$ is the same SET as $\{1,2,3\}$, perhaps listed in a different order).

Define $\sigma \in S_3$ as:

$\sigma(1) = a$
$\sigma(2) = b$
$\sigma(3) = c$.

Then $f(\sigma) = \tau$, as desired.

 

[mathmari]

One way is to argue that since $S_3$ is finite, and $f$ is injective, we must have that $f$ is surjective since $|S_3| = |M| = 6$ (this is true of ANY function between two finite sets of equal size).

Could you explain to me why this holds, in general? (Wondering)

Another way is to exhibit, explicitly, a pre-image under $f$ in $S_3$, for any $\tau \in M$, that is: display some $\sigma \in S_3$ such that $f(\sigma) = \tau$.

So suppose $\tau \in M$. Say:

$\tau(1) = a$
$\tau(2) = b$
$\tau(3) = c$
$\tau(4) = 4$.

Since $\tau$ is a bijective mapping we have: $\{a,b,c\} = \{1,2,3\}$ (I am *not* claiming $a =1,b = 2, c= 3$, but just that $\{a,b,c\}$ is the same SET as $\{1,2,3\}$, perhaps listed in a different order).

Define $\sigma \in S_3$ as:

$\sigma(1) = a$
$\sigma(2) = b$
$\sigma(3) = c$.

Then $f(\sigma) = \tau$, as desired.

Why is $\tau$ a bijective mappring? (Wondering)

 

[mathmari]

It is correct, although you *could* (if you wanted to,) put in some extra steps:

$f(\sigma_1 \circ \sigma_2))(i) = (\sigma_1\circ \sigma_2)(i) = \sigma_1(\sigma_2(i)) = \sigma_1(f(\sigma_2)(i))$

(here we are using the fact that $\sigma_2(i) \neq 4$, so that $f(\sigma_2)(i) = \sigma_2(i)$)

$= f(\sigma_1)(f(\sigma_2)(i))$

(here, we are using the fact that $f(\sigma_2)(i) \neq 4$, since elements of $S_4$ are bijective, and $4$ already has the pre-image $4$, so no other element can map to it)

$= f(\sigma_1)\circ f(\sigma_2)(i)$.
By definition (of $M$) we have:

$f(\sigma_1)\circ f(\sigma_2)(4) = f(\sigma_1)(f(\sigma_2)(4)) = f(\sigma_1)(4) = 4$, since *every* element of $M$ takes $4 \mapsto 4$.

Is it $f((\sigma_1 \circ \sigma_2))(i)$ or $f(\sigma_1 \circ \sigma_2)(i)$ ? (Wondering)

And is it $(f(\sigma_1)\circ f(\sigma_2))(i)$ or $f(\sigma_1)\circ f(\sigma_2)(i)$ ? (Wondering)

 

[Deveno]

Could you explain to me why this holds, in general? (Wondering)

Suppose $A,B$ are two finite sets with $|A| = |B|$ and $f:A \to B$ a function. Then:

$f$ is injective $\iff$ $f$ is surjective.

Suppose $f$ is injective. Thus $f(a_1) = f(a_2) \implies a_1 = a_2$.

Now if $f$ were not surjective, we have some $b \in B$, such that there is no $a \in A$ with $f(a) = b$. Now we have $|A|$ domain elements, and only $|B| - 1 = |A| - 1$ images to send them to (since nothing maps to $b$). So some element of $B$ has more than one pre-image, say $b_1$, with two distinct pre-images $a_1$ and $a_2$. But this means:

$f(a_1) = b_1 = f(a_2)$, but $a_1 \neq a_2$. Since $f$ is injective, this is a contradiction. So $f$ must be surjective.

On the other hand, suppose $f$ is surjective. Consider the $|B|$ sets, $f^{-1}(b)$. Since $f$ is a function, if $b_1 \neq b_2$, then $f^{-1}(b_1) \cap f^{-1}(b_2) = \emptyset$. Since we have $|B| = |A|$ such sets, and we have at least one element in each of them, it must be that the union of such pre-images (which is a disjoint union) has at least $|B| = |A|$ elements, which therefore includes all of $A$. Thus the pre-image sets form a partition of $A$, and we have $|A| = |B|$ such pre-image sets (one for each $b \in B$).

I claim that for each $b \in B$, we have: $|f^{-1}(b)| = 1$ (we know it is at LEAST $1$).

Since we have $|B|$ such sets, we have $|A| = \sum\limits_{b\in B} |f^{-1}(b)| \geq |B|\cdot 1 = |B|$.

Since $|A| = |B|$ if any pre-image has size >1, we get $|A| > |B|$, a contradiction. We thus conclude that every $b \in B$, has a UNIQUE pre-image in $A$, so $f$ is injective.

Why is $\tau$ a bijective mappring? (Wondering)

$S_4$ is, by definition, the set of all bijective mappings from the set $\{1,2,3,4\}$ to itself. $M$ is a subset of $S_4$, and as such all its elements are bijections.

 

[mathmari]

Suppose $A,B$ are two finite sets with $|A| = |B|$ and $f:A \to B$ a function. Then:

$f$ is injective $\iff$ $f$ is surjective.

Suppose $f$ is injective. Thus $f(a_1) = f(a_2) \implies a_1 = a_2$.

Now if $f$ were not surjective, we have some $b \in B$, such that there is no $a \in A$ with $f(a) = b$. Now we have $|A|$ domain elements, and only $|B| - 1 = |A| - 1$ images to send them to (since nothing maps to $b$). So some element of $B$ has more than one pre-image, say $b_1$, with two distinct pre-images $a_1$ and $a_2$. But this means:

$f(a_1) = b_1 = f(a_2)$, but $a_1 \neq a_2$. Since $f$ is injective, this is a contradiction. So $f$ must be surjective.

On the other hand, suppose $f$ is surjective. Consider the $|B|$ sets, $f^{-1}(b)$. Since $f$ is a function, if $b_1 \neq b_2$, then $f^{-1}(b_1) \cap f^{-1}(b_2) = \emptyset$. Since we have $|B| = |A|$ such sets, and we have at least one element in each of them, it must be that the union of such pre-images (which is a disjoint union) has at least $|B| = |A|$ elements, which therefore includes all of $A$. Thus the pre-image sets form a partition of $A$, and we have $|A| = |B|$ such pre-image sets (one for each $b \in B$).

I claim that for each $b \in B$, we have: $|f^{-1}(b)| = 1$ (we know it is at LEAST $1$).

Since we have $|B|$ such sets, we have $|A| = \sum\limits_{b\in B} |f^{-1}(b)| \geq |B|\cdot 1 = |B|$.

Since $|A| = |B|$ if any pre-image has size >1, we get $|A| > |B|$, a contradiction. We thus conclude that every $b \in B$, has a UNIQUE pre-image in $A$, so $f$ is injective.
$S_4$ is, by definition, the set of all bijective mappings from the set $\{1,2,3,4\}$ to itself. $M$ is a subset of $S_4$, and as such all its elements are bijections.

I understand! Thanks for explaining! (Mmm)

Is it $(f(\sigma_1 \circ \sigma_2))(i)$ or $f(\sigma_1 \circ \sigma_2)(i)$ ? (Wondering)

And is it $(f(\sigma_1)\circ f(\sigma_2))(i)$ or $f(\sigma_1)\circ f(\sigma_2)(i)$ ? (Wondering)

Is there a difference between the above notations? (Wondering)

 

[I like Serena]

I understand! Thanks for explaining! (Mmm)

Is it $(f(\sigma_1 \circ \sigma_2))(i)$ or $f(\sigma_1 \circ \sigma_2)(i)$ ? (Wondering)

And is it $(f(\sigma_1)\circ f(\sigma_2))(i)$ or $f(\sigma_1)\circ f(\sigma_2)(i)$ ? (Wondering)

Is there a difference between the above notations? (Wondering)

$f(\sigma_1 \circ \sigma_2)(i)$ could mean either $(f(\sigma_1 \circ \sigma_2))(i)$ or $f((\sigma_1 \circ \sigma_2)(i))$.
However, the latter interpretation is undefined, since $f$ is only defined for permutations and not for numbers.
So we can assume it means the first interpretation.
This is also the natural interpretation, reading from left to right.
In other words $(f(\sigma_1 \circ \sigma_2))(i)$ and $f(\sigma_1 \circ \sigma_2)(i)$ mean the same thing.
The choice depends on whether you want to be explicit or want to keep things short. (Nerd)The same thing applies to $(f(\sigma_1)\circ f(\sigma_2))(i)$ and $f(\sigma_1)\circ f(\sigma_2)(i)$.
In this case I prefer the first notation, since my natural inclination is to read $f(\sigma_1)\circ f(\sigma_2)(i)$ as $f(\sigma_1)\circ (f(\sigma_2)(i))$, making it confusing. (Thinking)

 

[mathmari]

I see... Thank you very much! (Mmm)