# Proof of normalization of permutations

Proposition (Normalization of permutations). For any permutation p : X1,X,X2 Y we can find Y1,X,Y2 = Y and q : X1,X2 Y1,Y2 such that:

=

Proof. Induction on p.

- If p = id then let q = id, and:

  =
- If p = p1 ; p2 then by induction we can find appropriate q1 ; q2 such that:
  = =
- If p = p1 p2 then either:

  - we can induct on p1, and:
    = = = =
  - or we can induct on p2, and:
    =

Back