TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Adjacent transpositions generate the finite symmetric group $S_{n}$

Statement

Let $S_{n} = Sym ({0, \dots, n - 1})$ with the composition convention of The finite symmetric group $S_{n}$ , one-line notation, and cycle notation. For $n \geq 2$ , $S_{n}$ is generated by the adjacent transpositions $τ_{i} = (i i + 1)$ , $0 \leq i < n - 1$ . Equivalently, let $κ_{n} : {0, \dots, n - 1} \to {1, \dots, n}$ be the increasing bijection $κ_{n} (i) = i + 1$ . Under $σ \mapsto κ_{n} σ κ_{n}^{- 1}$ , the generators are the one-based adjacent transpositions $s_{j} = (j j + 1)$ , $1 \leq j < n$ , whose preimages in $S_{n}$ are $τ_{j - 1}$ . For $n = 0, 1$ , the empty set generates the trivial group $S_{n}$ .

Facts & Assumptions

Given: The symmetric group $S_{n}$ on ${0, \dots, n - 1}$ and, for $n \geq 2$ , the increasing letter bijection $κ_{n}$ from the Statement.

[F1]

Every element of $S_{n}$ is a product of transpositions (Every finite permutation is a product of transpositions, so the transpositions generate $S_{n}$ ).

[F2]

The subgroup generated by a set is the smallest subgroup containing it; the empty set generates the trivial subgroup (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[F3]

Products of permutations act with the right factor first (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition).

Proof

technique · direct

1.1F3givenalgebra

For $0 \leq a < b < n$ , pointwise calculation using [F3] gives $(a b) = τ_{a} τ_{a + 1} \dots τ_{b - 2} τ_{b - 1} τ_{b - 2} \dots τ_{a + 1} τ_{a} .$ The product exchanges $a, b$ and fixes the other symbols; when $b = a + 1$ , it is just $τ_{a}$ . Every displayed index lies between $0$ and $n - 2$ .

2.1F1F2step 1.1

Thus every transposition lies in the subgroup generated by the adjacent ones, and [F1]--[F2] show that this subgroup is $S_{n}$ .

3.1F2F3step 2.1givenalgebra

Conjugation by the letter bijection $κ_{n}$ sends a permutation $σ$ of ${0, \dots, n - 1}$ to a permutation of ${1, \dots, n}$ . It preserves multiplication by [F3] and has inverse conjugation by $κ_{n}^{- 1}$ . It sends $τ_{j - 1}$ to $(j j + 1) = s_{j}$ . Transporting the adjacent-transposition product expressions from step 2.1 therefore proves that the $s_{j}$ , $1 \leq j < n$ , generate the one-based model, with precisely the stated preimages in $S_{n}$ .

4.1F2F3given∎

If $n = 0$ or $1$ , the underlying set admits only its identity permutation, so $S_{n}$ is trivial and [F2] says the empty set generates it. No letter transport or nonexistent generator is used in these cases.

Depends on

Used by

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Macauley, Math 4120 lecture notes: Generating sets for $S_n$ (standard reference, not scraped)

Adjacent transpositions generate the finite symmetric group SnSn​