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.
Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering and cyclic rotation
Statement
Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering the factors and cyclically rotating the entries within each cycle. The identity permutation has the empty disjoint-cycle decomposition.
Facts & Assumptions
Given: A finite set and a permutation ; the cyclic subgroup acts on by evaluation.
A disjoint-cycle decomposition is a product of pairwise disjoint cycles of length at least ; its omitted one-cycles are the fixed points (Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type).
For a left action, the distinct orbits partition the acted-on set (The orbits of a group action are the equivalence classes of iff for some , and hence partition the acted-on set).
The cyclic subgroup is exactly the set of integer powers (, and every cyclic group is abelian).
Cycles with disjoint supports commute (Cycles with disjoint supports commute).
Proof
The evaluation rule is an action by the Given, and [L3] identifies its orbit at as ; by [L2] these orbits partition .
Fix an orbit . Since is finite, the sequence first repeats; bijectivity of makes the first repeated value . If the least positive return time is , then and restricts to the cycle ; when , is fixed.
The cycles obtained from the non-singleton orbits have pairwise disjoint supports, and their product agrees with on each orbit and fixes every singleton orbit. Their product is therefore ; if every orbit is a singleton, this is the empty product.
In any disjoint-cycle decomposition of , [L4] allows powers to be taken factor by factor, while every factor except the unique one supporting a given point fixes that point. Thus successive powers of move the point exactly around that factor's support, so the support is the point's intrinsic -orbit. Hence the factor supports are forced, and the cycle on each support is forced up to its starting point, which is cyclic rotation; only the order of the disjoint factors remains free.
Depends on
- Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type
- Cycles with disjoint supports commute
- Left group actions, transitive actions, and faithful actions
- The orbit $G\cdot x$ and stabilizer $G_x$ of a point in a group action
- The orbits of a group action are the equivalence classes of $x\sim y$ iff $y=g\cdot x$ for some $g$, and hence partition the acted-on set
- The subgroup $\langle S \rangle$ generated by a subset, the cyclic subgroup $\langle g \rangle$, and cyclic groups
- $\langle g \rangle = \{\, g^{n} : n \in \mathbb{Z} \,\}$, and every cyclic group is abelian
Used by
- A k-cycle has sign (-1)ᵏ⁻¹, and sgn(σ)=(-1)^n-c(σ) when fixed points are counted as cycles Corollary
- The order of a permutation is the least positive common multiple of its nontrivial cycle lengths, with value 1 for the identity Corollary
- A₄ consists of the identity, eight 3-cycles, and three products of disjoint transpositions Example
- From one-line notation to a disjoint-cycle decomposition, with the right-hand factor acting first Example
- Every finite permutation is a product of transpositions, so the transpositions generate Sₙ Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 65 results over 18 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- T. W. Judson, Abstract Algebra: Theory and Applications, §5.1, Theorem 5.3 (standard reference, not scraped)
- J. S. Milne, Group Theory, Proposition 4.26 (standard reference, not scraped)