Coordinates and block notation
Finite blocks. If 0=b0<b1<⋯ tends to infinity, put Ik={bk,…,bk+1−1}, with length ℓk. Any choice of finite permutations πk of {0,…,ℓk−1} gives
g(bk+r)=bk+πk(r).
The inverse replaces each πk by πk−1. If the boundaries and local rules are computable uniformly, this gives a computable permutation. Every orbit remains within one finite block. Its order is the least common multiple of all local cycle lengths, interpreted as infinite when no finite common multiple exists.
Transport. If e:X→N is a specified bijection and f is a bijection of X, then efe−1 is a permutation of N. Its inverse is ef−1e−1. This carries orbit structure intact while changing the numerical layout.
For integers, use
η(k)={2k−1−2kk>0,k≤0.
Thus Z is listed as 0,1,−1,2,−2,…. For pairs, use the Cantor bijection
C(a,b)=2(a+b)(a+b+1)+b,a,b∈N.
Its inverse is obtained by finding the unique s with
2s(s+1)≤n<2(s+1)(s+2),
then taking b=n−s(s+1)/2 and a=s−b. For Z2 use E(a,b)=C(η(a),η(b)).
For rationals, fix an enumeration q0,q1,… of reduced fractions a/b with b>0, ordered first by ∣a∣+b, then by a. Each height contains finitely many fractions, so both enumeration and finding the index of a given reduced fraction are computable. Write ι(q) for that index.
Why cycles describe every permutation
For g∈S∞, consider the orbit {gk(n):k∈Z}. If some positive iterate returns to n, the orbit is a finite cycle. Otherwise k↦gk(n) is a bijection from Z onto the orbit. Thus an infinite cycle is two-sided, not a one-way ray.
Consequently every permutation decomposes into disjoint finite cycles and two-sided infinite cycles. Its cycle type records
(c1,c2,c3,…;c∞),
where each count is a nonnegative integer or ℵ0, and the total number of points is countably infinite. Two permutations of N are conjugate in S∞ exactly when these counts agree: a conjugacy matches cycles of equal length and matches successive positions within them. Conversely, a conjugacy carries each orbit to an orbit of the same type.
This classifies all permutations up to relabeling. It does not classify their appearance in the usual numerical ordering: conjugating can turn short jumps into arbitrarily long jumps.
What “definable” means here
The main catalog, P01–P39, consists of formulas and constructive families with computable forward and inverse maps, subject to the parameter conditions stated. A parameter such as an arbitrary permutation must itself be supplied by a computable rule with computable inverse when it is used to obtain a computable example.
Formal definability depends on a language and permitted parameters. Every computable permutation is definable in first-order arithmetic, but the converse fails. P40 is an explicit illustration of that distinction. It belongs in a mathematical reference, but not among examples whose values a visualization can always calculate.
There are only countably many finite descriptions in a fixed countable language, whereas S∞ has cardinality 2ℵ0. Accordingly, this catalog supplies broad families and a complete description of possible orbit shapes, rather than an enumeration of every individual element of S∞. The families overlap: a transposition can also appear as a particular block or bit permutation.