Permutation and Group

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

A permutation of a permutation, is the product of the two permutations?
Right. The multiplication is not commutative, i.e in general ab≠ba. For example $$\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$$ but $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}.$$
What happens if I keep permuting using the same permutation?
If you keep permuting with same permutation, you will eventually return to the initial configuration. For example $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} =\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix} =\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}.$$ The identity permutation, usually denoted by (1), is the permutation that changes nothing. We know that, say, there are n objects, then applying the same permutation for n! times will always end up to be the identity permuation, i.e. $$\tau^{n!}=(1)$$
Can I say τ^n!-1=1/τ?
Not quite. But you can write τ^n!-1=τ^-1, meaning that it is the multiplicative inverse of τ in the permutation multiplication.

Muliplication with an identity element and inverses. It is a group!?
Right. It is a group.
For every element α of a group G, we define a function A_α(g)=αg. It is not hard to see that A_α is a bijection and so it is a permutation. Indeed we have A_αA_β=A_αβ. Hence if we identify α with A_α, we see that each element of a group is indeed a permutation of the group!

Permutations

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com. 

Permutation of n objects is just a bijection on the set of these n objects?
Right.  If we don't specify the set, we means a permutation on the set {1,2,3,...,n}.

How to present a permutation?
Of course, we can present it as a bijection, e.g.
$$f(x)=\begin{cases}1 & x=1\\3 & x=2\\2 & x=3\end{cases}$$ However, traditionally we have a simpler presentation
$$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)$$ which is, I believe, self-explanatory. The lower part is the new arrangement.

Why not just write (1 3 2)?
It is because we already use this symbol for a special type of permutations-the cycles. For instance (1 3 2) refers to the permutation f(1)=3, f(3)=2 and f(2)=1, i.e. $$\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right).$$
It is easy to see cycles are interesting, mathematically?
First, we have to understand the multiplication of two permutations. If we consider two permutations $f$ and $g$ as two bijections on {1,2,3,...,n}, then their product is just the permutation $(fg)(x)=f\circ g(x)=f(g(x))$, that means if $g(r)=s$ and $f(s)=t$ then $(fg)(r)=s$. For instance, $$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right)=\left(\begin{matrix}1&2&3\\2&1&3\end{matrix}\right).$$ It is known that every permutation is a product of cycles.

So cycles are the primes for permutations?
Not quite. The transpositions (i,j), i.e. the cycles of two elements, are the primes. Every permutation can be written as a product of transpositions. e.g. $$\left(\begin{matrix}1&2&3&4&5\\3&5&4&1&2\end{matrix}\right)=(1\, 3\, 4)(2\, 5)=(1\, 4)(1\, 3)(2\, 5).$$

1=0!?

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

(Growing lazy, not a good sign....)

I have seen a proof, saying that 1=0!?
Which one do you mean '"1=0!"?' or '"1=0"!?', uh?

You got the trick. Why do we use "!" for factorial?
I am not a historian, I don't know why Christian Kramp choose n! to represent factorial.

Why does 0!=1?
Lets first consider the definition of factorial. The n! is the number of ways to permute n objects. In the set theory language, n! is the size of the set of all bijective maps on a set of n elements.
Let A be a set. A bijective map or a bijection or a permutation is a subset F of A×A such that

1. For any elements a∈A, there exists a unique F(a)∈A such that (a,F(a))∈F.
2. For any elements a∈A, there exists a unique F^-1(a)∈A such that (a,F^-1(a)∈F.

For example the map on {x,y,z} such that F(x)=y, F(y)=z, F(z)=x is a bijection (and hence a permutation), but G(x)=y, G(y)=x, G(z)=x is not.

On {x,y,z}, we have six permutations, right?
Yes. They are

• (F(x), F(y), F(z))=(x, y, z)
• (F(x), F(y), F(z))=(x, z, y)
• (F(x), F(y), F(z))=(y, x, z)
• (F(x), F(y), F(z))=(y, z, x)
• (F(x), F(y), F(z))=(z, x, y)
• (F(x), F(y), F(z))=(z, y, x)

Hence 3!=6.

On empty set ∅, ...?
Note that ∅ equals to and is the only subset of ∅×∅. There is no way we can violate the two conditions, and so ∅ is the bijection on ∅. Therefore 0!=1.

Cardinal Numbers

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

(A blog a week, keep my lazy away.... sort of)

Ordinal numbers are about order. Cardinal numbers are about quantities. In the previous post, we know what is an ordinal number. What is a cardinal number?
A cardinal number is a set of sets such that whenever we pick two sets in it, we can pair up their elements.  If two sets lie inside the same cardinal number, we say that they are of the same cardinality.
For example,  {a,b,c} and {x,y,z} are of the same cardinality, as we can pair up their elements as (a,x), (b,y) and (c,z).

A natural number is a cardinal number. Isn't it?
Well, we use a natural number as the representative of its cardinal number.
For example, {a,b,c} and 3={0,1,2} are of the same cardinality, and so we say that {a,b,c} has 3 elements.

So, if the elements of a set can be labelled as 0,1,2,...,n-1, then the set has n elements. Right?
Exactly.  It is just our usual sense of numbers. However, we are used to label the elements with 1,2,3,...,n instead.

The first infinite cardinal number is still ω={0,1,2,3,...} ?
Yeah.  Unlike ordinal numbers, 1+ω=ω=ω+1.
The sum of cardinal numbers are defined by, #A+#B=#(A×{0} ∪ B×{1}).
For example, 3+4=#{a,b,c}+#{x,y,z,w}=#{(a,0),(b,0),(c,0),(x,1),(y,1),(z,1),(w,1)}=7.

So, m+n=n+m?
Right. It is easy to see that A×{0} ∪ B×{1} and A×{1} ∪ B×{0} should have the same cardinality.

I guess the product of two cardinal numbers is (#A)(#B)=#(A×B)?
Good. For example 
3×4
=(#{a,b,c})(#{x,y,z,w})
=#{(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z),(b,w),(c,x),(c,y),(c,z),(c,w)}
=12.
Again, we have m×n=n×m.

Ordinal numbers.

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Giuseppe Peano says 1 is the smallest natural number, while John von Neumann says that 0 is the smallest natural number?
Yes. In the past, or even nowadays, 0 as a number is not quite natural in many people's eyes. However, when mathematicians want to give a vigorous definition for ordinal numbers, they figure out that 0 should be the starting point.

What is the vigorous definition for ordinal numbers?
An ordinal number α is a set of ordinal numbers that are smaller then α.

So 3={0,1,2}, 5={0,1,2,3,4} are ordinal numbers?
True. All natural numbers are ordinal numbers. Indeed the set

ω={0,1,2,3,...}
is also an ordinal number. It is the smallest infinite ordinal number.

The second smallest infinite ordinal is {0,1,2,...,ω}?
Yes, it is ω+1. Note that it is different from 1+ω which equals to ω. The definition of addition is like this--
{0,1,2,...}+{0,1,2,...}={0,1,2,..., 0,1,2,...},
where the symbols with different colors are considered different, and that the elements are listed in the order.
By renaming the elements, we see that
3+2={0,1,2}+{0,1}={0,1,2}+{3,4}={0,1,2,3,4}=5.
The addition for finite ordinals is the usual addition of natural numbers.
However, we see that
ω+1={0,1,2,...}+{0}={0,1,2,...}+{ω}={0,1,2,...,ω} but
1+ω={0}+{0,1,2,3,...}={0}+{1,2,3,...}=ω.
The two are different as ω+1 has a largest element but ω does not.

I doubt we still ignore 0 with we deal with ordinal numbers in daily language?
Well, we have invented a word "zeroth", denote that something should come earlier before the first object in a series. For example, the zeroth chapter or the zeroth law of thermodynamics.

3={0,1,2}

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.


In the last post, we mentioned that sometimes we identify 2={0,1}. So 3={0,1,2}, 4={0,1,2,3}?
Yes. It is the construction of natural numbers by polymath John von Neumann:

• 0={ }, the empty set.
• n+1=n∪{n}.

Therefore we have: 0={ }, 1={0}, 2={0,1}, 3={0,1,2}, .... In general n={0,1,2,...,n-1} for n≥1.

I see, so n is a set of n elements, right?
This definition has many advantages:

1. n is a set of n elements.
2. The definition is recursive, it does not depend on anything outside the number system.
3. n> m if and only if n is an element of m.
4. n≥ m if and only if n is a subset of m.
5. This definition can be extended to infinite ordinals.

Are there any other definitions for natural numbers?
Yes. For instance, 0={ }, 1={0}, 2={1}, etc. As soon as the definition fits Peano axioms, that's okay.

What are Peano axioms?
Proposed by Giuseppe Peano, there are five axioms:

1. There is an initial number, called 0. (Peano indeed use 1 as the initial number)
2. There is a successor operation. If n is a natural number, its successor is denoted by n+1.
3. For all nonzero natural number m, there exists a unique n such that n+1=m.
4. There exists no natural number n such that n+1=0.
5. If 0 has Property P and that "if n has Property P then n+1 also have Property P", then all natural numbers have Property P.

The last property is the mathematical induction?
Well... the reason that mathematical induction works is that it is a property of the natural number system!

The power set of X

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Suppose X and Y are sets. What is Y^X?
Y^X is the set of all functions from X to Y. From the last post, we see that if X has n elements and Y has m elements, then Y^X has mⁿ elements.

What is 2^X?
If we write like that, we identify 2 with a set with two elements, in particular we can consider 2={0,1}. Therefore 2^X is simply a set of functions that for each x∈X, f(x) takes up values as 0 or 1.

How do we describe a function in 2^X?
Since f(x) can only have two values, we can describe the function f using the preimage of 0, i.e. f^-1(0)={x∈X   :   f(x)=0}. In other words, each function in 2^X corresponds to exactly one subset of X.

2^X is sometimes used to denote the power set of X, right?
A power set of X, usually denoted by P(X), is the set of all subsets of X. Because there exists a correspondence between the functions in 2^X and the subsets in P(X), so we sometimes really consider them identical.
For example, if X={a,b,c}, then P(X)={∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} and the eight functions in 2^X are
f(a)=f(b)=f(c)=1;
f(a)=0, f(b)=f(c)=1;
f(b)=0, f(a)=f(c)=1;
f(c)=0, f(a)=f(b)=1;
f(a)=f(b)=0, f(c)=1;
f(a)=f(c)=0, f(b)=1;
f(b)=f(c)=0, f(a)=1;
f(a)=f(b)=f(c)=0.