Permutation Ontology

FLOW ALGEBRA
TITLE: Permutation Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/permutation-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
SOURCE_STATUS: Mathematical synthesis; live source page not independently verified.

1. ONTOLOGY DEFINITION
A permutation is a bijection from a finite set to itself; equivalently, an arrangement of distinct elements in which order matters. Distinguish full permutations from ordered selections without replacement (k-permutations).

2. TYPED ENTITIES
Set<T>: finite collection of distinct elements of type T
Element<T>: member of Set<T>
Permutation<T>: bijection Set<T> -> Set<T>
OrderedSequence<T>: finite indexed sequence
SymmetricGroup(n): group of permutations of {1,...,n}
Cycle: cyclic orbit of a permutation
Transposition: permutation swapping exactly two elements
Parity: EVEN | ODD
Inversion: pair (i,j), i<j and pi(i)>pi(j), for a permutation of an ordered set
Factorial(n): product of integers 1 through n, with 0! = 1
KPermutation(n,k): ordered choice of k distinct objects from n

3. TYPE AND DOMAIN CONSTRAINTS
n: Integer where n >= 0
k: Integer where 0 <= k <= n
S: finite Set<T> with |S|=n
pi, sigma, tau: Permutation<T> on the same S
Each permutation maps every element of S to exactly one element and has a unique preimage for every element.

4. FORMAL OPERATIONS
PERMUTE(S) -> Set<Permutation<T>>
COUNT_PERMUTATIONS(n) -> n!
COUNT_K_PERMUTATIONS(n,k) -> n!/(n-k)!
APPLY(pi,x) -> pi(x)
COMPOSE(sigma,pi)(x) -> sigma(pi(x))
IDENTITY(S)(x) -> x
INVERSE(pi)(pi(x)) -> x
CYCLE_DECOMPOSITION(pi) -> disjoint cycles, unique up to cycle rotation and cycle order
SIGN(pi) -> (-1)^(number of inversions) for S={1,...,n}

5. AXIOMS AND ALGEBRAIC LAWS
Closure: sigma o pi is a permutation of S.
Associativity: tau o (sigma o pi) = (tau o sigma) o pi.
Identity: id o pi = pi o id = pi.
Inverse: pi^-1 o pi = pi o pi^-1 = id.
Composition is generally noncommutative for n >= 3.
|SymmetricGroup(n)| = n!.
Every permutation decomposes into disjoint cycles.
Every permutation can be expressed as a product of transpositions.
Parity of a permutation is independent of the chosen transposition decomposition.
SIGN(sigma o pi) = SIGN(sigma) * SIGN(pi).

6. COUNTING IDENTITIES
P(n,k) = n(n-1)...(n-k+1) = n!/(n-k)!.
P(n,0)=1; P(n,n)=n!.
C(n,k)=P(n,k)/k!.
For a multiset of n labelled positions with indistinguishable groups of multiplicities m1,...,mr (sum mi=n), the number of distinct arrangements is n!/(m1!...mr!).
For n >= 1, the number of cyclic arrangements of n distinct objects up to rotation is (n-1)!; reflection is NOT identified.

7. SEMANTIC RELATIONSHIPS
Permutation IS_A Bijection.
Permutation ACTS_ON FiniteSet.
Permutation HAS_PROPERTY Invertibility.
Permutation HAS_REPRESENTATION OneLineNotation | TwoLineNotation | CycleNotation.
Permutation BELONGS_TO SymmetricGroup.
Transposition IS_A Permutation.
KPermutation IS_A OrderedSelectionWithoutReplacement.
Combination DIFFERS_FROM KPermutation BY OrderSensitivity.

8. INFERENCE RULES
IF f:S->S is bijective AND S is finite THEN f is a permutation of S.
IF pi and sigma are permutations of S THEN sigma o pi is a permutation of S.
IF pi is a permutation of S THEN pi^-1 exists and is unique.
IF pi is a product of an even number of transpositions THEN SIGN(pi)=+1.
IF two full arrangements differ only by order THEN they are distinct permutations, unless the elements are indistinguishable under the declared equivalence.

9. VALIDATION
CHECK all domain/codomain elements belong to S.
CHECK each element of S has exactly one image and exactly one preimage.
CHECK composition operands share a compatible underlying set.
CHECK 0 <= k <= n for ordered selections.
CHECK factorial counts use exact integer arithmetic.
CHECK cycle decompositions cover each element exactly once, including fixed points when required.
CHECK parity from inversion count equals parity from any transposition decomposition.

10. EXAMPLE
S={1,2,3}; pi=(1 2 3) maps 1->2, 2->3, 3->1.
pi^-1=(1 3 2).
|PERMUTE(S)|=3!=6.
P(3,2)=3!/1!=6.
SIGN(pi)=+1 because a 3-cycle is a product of two transpositions.

11. SEMANTIC_EQUIVALENCE
"permutation" ~ "bijective rearrangement of a finite set" (mathematical context).
"k-permutation" ~ "ordered selection of k distinct elements without replacement".
"arrangement" is context-dependent and not universally equivalent to permutation.

12. CONFIDENCE
Mathematical definitions and standard identities: HIGH.
Claims about source-page wording or structure: UNVERIFIED.

13. FLOW_HASH
METHOD: SHA-256 over canonical UTF-8 flow content, excluding the FLOW_HASH value itself.
VALUE: COMPUTE_ON_PUBLICATION

14. UPDATE_MODEL
Trigger: correction to definitions, notation, mathematical examples, or ontology cross-links.
Process: review -> validate -> version increment -> regenerate FLOW_HASH -> publish.
Preserve provenance and previous versions.

15. AI_CONSUMPTION
Interpret a permutation as a bijection, not an arbitrary sequence with repetition.
Preserve composition order explicitly: (sigma o pi)(x)=sigma(pi(x)).
Distinguish permutation counts from combination counts.
Apply assumptions before using cyclic or multiset counting formulas.
Return symbolic formula, assumptions, and exact count when inputs are provided.