A proper permutation group transitive on countable sections

Problem

For a countably infinite set $\Omega$ , does there exist a proper subgroup of $\operatorname{Sym}(\Omega)$ transitive both on $\Omega$ and on its partitions into countably many infinite parts?

G<\operatorname{Sym}(\Omega),\qquad \forall\mathcal P,\mathcal Q,\quad\exists g\in G:\ g\mathcal P=\mathcal Q.

The construction realizes every prescribed matching between the parts.

Setup and result

An $\aleph_0$ -section of a countably infinite set $\Omega$ is a partition of $\Omega$ into countably many infinite subsets. In Problem 9.41(c) of the Kourovka Notebook, P. M. Neumann asks whether there is a proper subgroup of $\mathrm{Sym}(\Omega)$ which is transitive both on $\Omega$ and on its $\aleph_0$ -sections (4). We prove a labelled version of this assertion.

Theorem 1. There is a proper transitive subgroup $P<\mathrm{Sym}(\mathbb N)$ with the following property. If

\mathbb N=\coprod_{i\in\mathbb N}A_i=\coprod_{i\in\mathbb N}B_i, \qquad |A_i|=|B_i|=\aleph_0\quad(i\in\mathbb N),

then there exist $g\in P$ and $S\subseteq\mathbb N$ such that

g(A_i)=B_i\quad(i\in\mathbb N), \qquad g|_S\text{ and }g|_{\mathbb N\setminus S}\text{ are strictly increasing}.

Consequently, every countably infinite set admits a proper transitive permutation group which is transitive on $\aleph_0$ -sections.

Corson and Shelah (2, Corollary 10) obtain the countable-section conclusion under Martin’s Axiom for $\sigma$ -centered partial orders. Their result is a consequence of a more general construction concerning actions on collections of structures. Theorem 1 concerns the countable-section conclusion and requires no such additional hypothesis.

The subgroup used here is the group of permutations that are increasing on finitely many pieces. Cornulier (1) describes this group and its transitivity on infinite subsets with infinite complements. The matching argument uses a classical form of the Schröder–Bernstein theorem: the resulting bijection chooses, at each point, either one of the given embeddings or the inverse of the other. Halmos (3) applies this method to increasing embeddings of sequences. Here the embeddings preserve the labels of the parts exactly. This gives a matching on two increasing pieces even when infinitely many parts must be matched simultaneously.

Throughout, $\mathbb N=\{0,1,2,\ldots\}$ . Increasing means strictly increasing. A piece of a partition need not be an interval.

Increasing embeddings and exact matchings

We first record the order-theoretic form of the matching argument.

Lemma 2. Let $X,Y$ be linearly ordered sets, let $R\subseteq X\times Y$ , and suppose that $u:X\to Y$ and $v:Y\to X$ are increasing maps satisfying

(x,u(x))\in R\quad(x\in X), \qquad (v(y),y)\in R\quad(y\in Y).

Then there are a bijection $h:X\to Y$ and a subset $S\subseteq X$ such that $h|_S$ and $h|_{X\setminus S}$ are increasing and

(x,h(x))\in R\qquad(x\in X).

Proof. The maps $u$ and $v$ are injective. The relational Schröder–Bernstein theorem gives a bijection $h:X\to Y$ for which

\tag{5} h(x)=u(x)\quad\text{or}\quad v(h(x))=x \qquad(x\in X).

Put $S=\{x\in X:h(x)=u(x)\}$ . On $S$ , the map $h$ agrees with the increasing map $u$ . If $x<x'$ lie outside $S$ , then

v(h(x))=x<x'=v(h(x')),

and strict monotonicity of $v$ implies $h(x)<h(x')$ . Finally, either alternative in (5) implies $(x,h(x))\in R$ by the corresponding hypothesis. ◻

Lemma 3. Let $I$ be a set and let $p,q:\mathbb N\to I$ . If every fiber of $q$ is infinite, then there is an increasing map $u:\mathbb N\to\mathbb N$ such that

q(u(n))=p(n)\qquad(n\in\mathbb N).

Proof. Every infinite subset of $\mathbb N$ is unbounded. Choose $u(0)>0$ in $q^{-1}(\{p(0)\})$ . Having chosen $u(n)$ , choose

u(n+1)>u(n),\qquad q(u(n+1))=p(n+1).

The recursion gives the required map. ◻

Proposition 4. Let $p,q:\mathbb N\to I$ have infinite fibers. There are $g\in\mathrm{Sym}(\mathbb N)$ and $S\subseteq\mathbb N$ such that $g$ is increasing on $S$ and on its complement, and

\tag{9} q(g(n))=p(n)\qquad(n\in\mathbb N).

Proof. Lemma 3 gives increasing maps $u,v:\mathbb N\to\mathbb N$ with

q(u(n))=p(n),\qquad p(v(n))=q(n).

Apply Lemma 2 to the relation $R(x,y)\iff p(x)=q(y)$ . ◻

The permutation group

Define

\tag{11} P=\left\{g\in\mathrm{Sym}(\mathbb N): \begin{array}{l} \text{there are }r\geq1\text{ and }c:\mathbb N\to\{1,\ldots,r\}\text{ such that}\\ c(x)=c(y),\ x<y\ \Longrightarrow\ g(x)<g(y) \end{array}\right\}.

Thus the fibers of $c$ are increasing pieces for $g$ ; empty fibers may be omitted.

Lemma 5. The set $P$ is a subgroup of $\mathrm{Sym}(\mathbb N)$ containing every transposition. In particular, it is transitive on $\mathbb N$ .

Proof. The identity is increasing on all of $\mathbb N$ . Suppose $f,g\in P$ have colorings $c_f,c_g$ with $r,s$ colors, respectively. Color $x$ by

\bigl(c_f(g(x)),c_g(x)\bigr).

If $x<y$ have the same color, then $g(x)<g(y)$ and hence $f(g(x))<f(g(y))$ . This gives at most $rs$ increasing pieces for $fg$ .

If $g\in P$ has coloring $c$ , color $y$ by $c(g^{-1}(y))$ . For $y<y'$ of the same color, the inequality $g^{-1}(y')<g^{-1}(y)$ would imply $y'<y$ ; equality is also impossible. Hence $g^{-1}(y)<g^{-1}(y')$ , proving $g^{-1}\in P$ .

The transposition interchanging distinct points $a,b$ is increasing on each of $\{a\}$ , $\{b\}$ and $\mathbb N\setminus\{a,b\}$ . Such a transposition sends $a$ to $b$ . ◻

Lemma 6. The subgroup $P$ is proper.

Proof. Partition $\mathbb N$ into the finite intervals

J_n=\{n^2,n^2+1,\ldots,n^2+2n\}\qquad(n\in\mathbb N).

Define a permutation $\rho$ by reversing each interval:

\tag{14} \rho(n^2+j)=n^2+2n-j\qquad(0\leq j\leq2n).

The intervals are consecutive and exhaust $\mathbb N$ , and the formula gives $\rho^2=1$ .

Suppose $\rho$ admitted a coloring with $r$ increasing pieces. The $r+1$ points

r^2,r^2+1,\ldots,r^2+r

lie in $J_r$ , where $\rho$ is strictly decreasing. No two of these points can have the same color. This would inject an $(r+1)$ -element set into an $r$ -element set, a contradiction. ◻

Proof of Theorem 1. Let $P$ be the subgroup (11); Lemmas 5 and 6 give transitivity and properness. Given the two partitions, define $p(n)=i$ when $n\in A_i$ and $q(n)=i$ when $n\in B_i$ . Proposition 4 supplies a bijection $g$ satisfying (9) and increasing on two complementary subsets, so $g\in P$ .

For every $i$ , equation (9) gives $g(A_i)\subseteq B_i$ . Conversely, if $y\in B_i$ , write $y=g(x)$ ; then $p(x)=q(y)=i$ , so $y\in g(A_i)$ . Thus $g(A_i)=B_i$ .

For an arbitrary countably infinite set $\Omega$ , choose a bijection $e:\mathbb N\to\Omega$ and use the conjugate subgroup $ePe^{-1}$ . Conjugation preserves properness and point transitivity; pulling both partitions back along $e$ and applying the result on $\mathbb N$ gives the required matching on $\Omega$ . ◻

References

Preprint · Lean (GitHub)

Y. Cornulier, answer to An equivalence relation on group actions, MathOverflow, 27 October 2012, https://mathoverflow.net/questions/110703.

S. M. Corson and S. Shelah, A permutation group acting transitively on certain collections of models, European J. Combin. 137 (2026), 104415, doi:10.1016/j.ejc.2026.104415.

P. R. Halmos, Permutations of sequences and the Schröder–Bernstein theorem, Proc. Amer. Math. Soc. 19 (1968), 509–510, doi:10.1090/S0002-9939-1968-0226590-1.

E. I. Khukhro and V. D. Mazurov (eds.), The Kourovka Notebook: Unsolved problems in group theory, 21st ed., September 2026 update, Problem 9.41(c), arXiv:1401.0300v46.