Linked Reduction Systems for Permutations

Abstract

For any \(n \geq 2\) we let \(S_n\) be the set of permutations of the set \(\{1,2,\ldots,n\}\). A reduction \(\overline{f}\) on \(S_n\) is a set of functions \(\{f_i : 1 \leq i \leq n\}\) such that \(f_n\) is the identity function on \(\{1,2,\ldots,n-1\}\) and for \(i n_0\), such that \(\phi(n) \leq n\) for all \(n \geq n_0\), and for which \(p \downarrow \phi(n) \downarrow i = p \downarrow i \downarrow n-1\) for all \(n > n_0\), for all \(i \leq n-1\) and for all \(p \in S_n\). And the system is said to be amenable if for every \(n > n_0\) there is an integer \(k < n\) such that, for all \(p \in S_n\), \(p \downarrow k \downarrow n-1 = p \downarrow n-1\). The purpose of this paper is to study faithful reductions and linked reduction systems. We characterize amenable, linked reduction systems by means of two types of liftings by which a reduction on \(S_{n+1}\) can be formed from one on \(S_n\). And we obtain conditions for a reduction system to be faithful. One interesting consequence is that any amenable, linked reduction system which begins with a simple reduction is faithful.