Proof. We prove each case separately. Let $n=2$ and $\mathcal {A}=\{A_j:j\in J\}$ be an infinite family of pairwise disjoint finite sets (we can assume they are disjoint by replacing each $A_i$ with the set $A_i^*=A_i\times \{A_i\}$ ). Set $x=\bigcup \mathcal {A}$ and apply $\mathrm {2RC_{fin}}$ to get an infinite $y\subseteq x$ and a function $g:[y]^{>2}\to [y]^2$ such that, for all $Y\in [y]^{>2}$ , $g(Y)\subseteq Y$ . Since every element of $\mathcal {A}$ is finite, there must be an infinite subset I of J such that, for all $i\in I$ , $A_i\cap y\neq \emptyset $ . If for infinitely many $i\in I$ , $|A_i\cap y|=2$ the claim is obvious, and likewise if $i\in I$ , $|A_i\cap y|>2$ for infinitely many $i\in I$ , then we are done by defining for each and every such $i\in I$ the function $f:A_i\mapsto g(A_i\cap y)$ . If that is not the case, apply a second time $\mathrm {2RC_{fin}}$ to $\bigcup \{A_i:i\in I\}\setminus y$ , to get another infinite subset $z\subseteq x$ with $z\cap y=\emptyset $ . If, again, $\{i\in I: |A_i\cap z|\geq 2\}$ is finite, then we get that $K=\{i\in I: |A_i\cap y|=|A_i\cap z|=1\}$ is infinite, together with the obvious function $f:A_k\mapsto A_k\cap (y\cup z)$ , for all $k\in K$ .

For the other case we start similarly: let $n=3$ and $\mathcal {A}=\{A_j:j\in J\}$ be an infinite family of pairwise disjoint finite sets. Set $x=\bigcup \mathcal {A}$ and apply $\mathrm {3RC_{fin}}$ to get an infinite $y\subseteq x$ and a function $g:[y]^{>3}\to [y]^3$ such that, for all $Y\in [y]^{>3}$ , $g(Y)\subseteq Y$ . Since every element of $\mathcal {A}$ is finite, there must be an infinite subset I of J such that, for all $i\in I$ , $A_i\cap y\neq \emptyset $ . If $\{i\in I: |A_i\cap y|=1\:\mathrm {or}\:|A_i\cap y|\geq 3\}$ is infinite, with a perfectly analogous approach to the previous case we get the conclusion. Otherwise, for all but finitely many $i\in I$ , $|A_i\cap y|=2$ . At this point we use Montenegro’s result that $\mathrm {RC_4}$ implies $\mathrm {C_4^-}$ , which in turns implies $\mathrm {C_2^-}$ . Since, by Lemma [9.1], $\mathrm {3RC_{fin}}$ implies $\mathrm {RC_4}$ , by applying $\mathrm {C_2^-}$ to $\{A_i: |A_i\cap y|=2\}$ we get to a case which has already been solved, namely the one in which $\{i\in I: |A_i\cap y|=1\}$ is infinite.

Proof. Let $\mathcal {A}=\{A_j:j\in J\}$ be an infinite family of pairwise disjoint finite sets. Set $x=\bigcup \mathcal {A}$ and apply $\mathrm {4RC_{fin}}$ to get an infinite $y\subseteq x$ and a function $g\colon [y]^{>4}\to [y]^4$ such that, for all $Y\in [y]^4$ , $g(Y)\subseteq Y$ . Since every element of $\mathcal {A}$ is finite, there must be an infinite subset I of J such that, for all $i\in I$ , $A_i\cap y\neq \emptyset $ . With perfectly analogous arguments as in the previous lemma, it is easy to see that the only difficult case is when, for all $i\in I$ , $|A_i\cap y|=3$ . The following part of the proof shows that $\mathrm {4RC_{fin}}$ implies $\mathrm {C_3^-}$ .

For all $i\in I$ , set $B_i=A_i\cap y$ . We define a directed graph $G\subseteq I^2$ on I: let $(i,j)$ be an edge if and only if $B_j\nsubseteq g(B_i\cup B_j)$ . The idea behind this definition is that every time $(i,j)$ is an edge, then the function g selects one element from $B_j$ whenever considered together with $B_i$ (we choose the element in $B_i\setminus g(B_i\cup B_j)$ if $\lvert B_i\cup g(B_i\cup B_j)\rvert =2$ ). We say that an $i\in I$ has outdegree k whenever $|\{j\in I: (i,j)\in G\}|=k$ . Notice that we can assume that no $i\in I$ has infinite outdegree, otherwise we could easily select one element from infinitely many $B_i$ . Now we claim that for each $k\in \omega $ there are only finitely many $i\in I$ such that i has outdegree k. To prove this, assume towards a contradiction that there exists some $k'\in \omega $ and $\widetilde {I}\subseteq I$ such that $|\widetilde {I}|=2k'+3$ and that for all $i\in \widetilde {I}$ , i has outdegree $k'$ . By construction, if n is the number of edges contained in $\widetilde {I}^2$ , then $\binom {|\widetilde {I}|}{2}\leq n\leq |\widetilde {I}|k'$ , from which follows $k'+1\leq k'$ , a contradiction. We have obtained a well ordered partition of I into finite classes according to the outdegree of every $i\in I$ . In symbols:

$$ \begin{align*}I_k=\{i\in I: i\textrm{ has outdegree }k\}\text{ for every }k\in\omega. \end{align*} $$

Applying $\mathrm {4RC_{fin}}$ to I, we extract at most $4$ elements from each class, and for some $1\leq m\leq 4$ , we get exactly m elements from infinitely many classes, so we can assume that we get m elements from every class. Write $f(I_k)$ for the m extracted elements from $I_k$ . We finish the proof by analyzing each of these cases separately.

If $m=1$ , then, for all $k\in \omega $ , there is at least one edge between the element of $f(I_{2k})$ and the one of $f(I_{2k+1})$ , and this allows us to select one element from $B_{2k}$ or $B_{2k+1}$ .

If $m=2$ , we just consider, for all $k\in \omega $ , the edges (there must be at least one) between the two elements of $f(I_k)$ , and conclude the proof as in the previous case.

If $m=3$ , consider again, for all $k\in \omega $ , all the inner edges contained in $f(I_k)^2$ . Since each $i\in f(I_k)$ can be chosen at most $2$ times and there are at least $3$ inner edges, we are always able to choose one element from some some $B_j$ with $j\in f(I_k)$ .

If $m=4$ , consider, for all $k\in \omega $ , $g(\cup _{i\in f(I_k)}B_i)$ . If it selects less than $4$ elements from $f(I_k)$ , we are in one of the previous cases and if it selects exactly one element from each $B_i$ , with $i\in f(I_k)$ , we are also done. This concludes the proof.

Proof. Let $\mathcal {A}=\{A_j:j\in J\}$ be an infinite family of pairwise disjoint finite sets. Set $x=\bigcup \mathcal {A}$ and apply $\mathrm {6RC_{fin}}$ to get an infinite $y\subseteq x$ and a function $g\colon [y]^{>6}\to [y]^6$ . As usual, we can assume $|A_j\cap y|<6$ for all $j\in J$ . Moreover, it is possible to assume $|A_j\cap y|<4$ for all $j\in J$ , as well. To see it, take for instance the case in which $|A_i\cap y|=5$ for all the infinitely many $i\in I\subseteq J$ . As in the previous theorem, define an oriented graph $G\subseteq I^2$ and let $(i,j)$ be an edge if and only if $A_j\nsubseteq g(A_i\cup A_j)$ . This way, we obtain a well ordered partition of I into finite classes $I_k$ , for $k\in \omega $ , according to the outdegree of each $i\in I$ . Apply $\mathrm {6RC_{fin}}$ to I and extract a finite set $f(I_k)$ of at most $6$ elements from each class $I_k$ . Then extract again at most $6$ elements from each $\cup _{i\in f(I_k)}(A_i\cap y)$ . The only case which is not solved by the last extraction is when $|f(I_k)|=1$ for all $k\in \omega $ , but this is easily handled as the case $m=1$ , at the end of the previous proof. The case when $|A_i\cap y|=4$ for infinitely many $i\in I\subseteq J$ can be solved in the same way.

Now, given $\mathcal {A}=\{A_j:j\in J\}$ and $y\subseteq \bigcup \mathcal {A}$ , let $I=\{i\in J:A_i\cap y\neq \emptyset \}$ . Apply $\mathrm {6RC_{fin}}$ to $\cup _{i\in I}A_i\setminus y$ to get an infinite $z\subseteq \bigcup \mathcal {A}\setminus y$ . Similarly, if $K=\{k\in I:A_k\cap z\neq \emptyset \}$ , apply $\mathrm {6RC_{fin}}$ to $\cup _{k\in K}A_k\setminus (y\cup z)$ to get an infinite $w\subseteq \bigcup \mathcal {A}\setminus (y\cup z)$ . A straightforward analysis shows that the only non-trivial case is given, modulo symmetries, by the one in which

$$ \begin{align*}|A_j\cap y|=3,\,|A_j\cap z|=|A_j\cap w|=2\textrm{ and }|A_j|=7,\textrm{ for all }j\in J.\end{align*} $$

Our goal is to select one element either from $|A_j\cap y|$ or $|A_j\cap z|$ , for infinitely many $j\in J$ . In order to do this, we consider the family of edges and the corresponding partitions

$$ \begin{align*}F^j_a&=\{e\in(A_j\cap y)\times(A_j\cap z):e(1)=a\},\,a\in A_j\cap y,\\G^j_b&=\{e\in(A_j\cap y)\times(A_j\cap z):e(2)=b\},\,b\in A_j\cap z. \end{align*} $$

Notice that for all $j\in J$ , $|F^j_a|=2$ and $|G^j_b|=3$ . It is easy to see that whenever we select a proper subset of $E_j$ for some $j\in J$ , we are able to select one element from $A_j\cap y$ or from $A_j\cap z$ . Also for this reason, when applying $\mathrm {6RC_{fin}}$ to , we can assume that we get a selection function f on the set of all edges E. To simplify the notation, let $\widetilde {f}$ be defined as $\widetilde {f}\colon [E]^7\to E$ , $\widetilde {f}\colon S\mapsto S\setminus f(S)$ . Now, for $j\in J$ and $b\in A_j\cap z$ , define the degree

$$ \begin{align*}\mathrm{deg}(G^j_b)=|\{F^i_a\cup F^i_{a'}:i\in J\wedge a,a'\in(A_j\cap z)\wedge \widetilde{f}(G^j_b\cup F^i_a\cup F^i_{a'})\in F^i_a\cup F^i_{a'}\}|.\end{align*} $$

We can assume that every $G_b^j$ has finite degree, since we would be otherwise able to select a proper subset from infinitely many $E_j$ . In addition, assume that for some $k_0\in \omega $ there are infinitely many $G^j_b$ with degree equal to $k_0$ . Then order $k_0+1$ distinct $4$ -element sets of the form $F^i_a\cup F^i_{a'}$ for some $i\in J$ and $a,a'\in (A_j\cap z)$ . For each $G^j_b$ , there must be a first of these $k_0+1$ sets with the property that $\widetilde {f}(G^j_b\cup F^i_a\cup F^i_{a'})\in G^j_b$ , but this fact allows us to select one edge from each $G^j_b$ with degree equal to $k_0$ . Thus, assume that for each $k\in \omega $ there are only finitely many $G^j_b$ with degree k. This gives us a well ordered partition of $\{G^j_b:j\in J\wedge b\in A_j\cap z\}$ into finite subclasses. Explicitly into the subclasses

$$ \begin{align*}H_k=\{G^j_b:\mathrm{deg}(G^j_b)=k\}. \end{align*} $$

Apply one last time the function f to each $\bigcup H_k$ and notice that the only case in which we are not able to select a proper subset from infinitely many $E_j$ , is when, for all but finitely many $k\in \omega $ , $f(\bigcup H_k)=E_i$ for some $i\in J$ . We conclude the proof by solving this last case. Suppose that for infinitely many $k\in \omega $ , given $f(\bigcup H_k)=E_i$ , there is at least one $G^i_b\subseteq E_i$ such that for an $l\in J$ and a $k'\in \omega $ , with $f(\bigcup H_{k'})=E_l$ , it is possible to select an element from $G^i_b$ by considering the set

Then we can conclude by choosing, for each such $k\in \omega $ , the first $k'\in \omega $ with the mentioned property. If that is not the case, fix $k_1\in \omega $ with $f(H_{k_1})=E_i$ such that for infinitely many $j\in J$ and $k\in \omega $ with $f(H_k)=E_j$ we have that

$$ \begin{align*}|\mathrm{sel}(G_b^i,j)|=3\textrm{ for both }b\in A_i\cap z, \end{align*} $$

and conclude by fixing some $b_0\in A_i\cap z$ and $a_0\in A_i\cap y$ . This selects a proper subset from infinitely many $E_j$ , namely that unique $F^j_a\cup F^j_{a'}\subseteq E_j$ such that

$$ \begin{align*}\widetilde{f}(G^i_b\cup F^j_a\cup F^j_{a'})=(a_0,b_0).\\[-34pt]\end{align*} $$

Proof. Let $\mathcal {A}=\{A_i:i\in \omega \}$ be a well-ordered family of finite sets such that $|A_i|>p^k$ for all $i\in \omega $ . $\mathrm {p^{kWOC^-_{fin}}}$ is basically obtained by repeated applications of $\mathrm {p^kRC_{fin}}$ to $\bigcup \mathcal {A}$ , together with the following two considerations: The first is that if a finite sum $\sum a$ of divisors of $p^k$ is such that $\sum a>p^k$ , then it is possible to extract a subsum $\sum a'$ such that $\sum a'=p^k$ . The second consideration, which allows us to conclude the proof, is the following: Given a well-ordered family $\mathcal {B}=\{B_i:i\in B\}$ of finite sets of the same size $m\nmid p^k$ , with $\mathrm {p^kRC_{fin}}$ we can extract a family of subsets $\mathcal {B'}=\{B^{\prime }_i:i\in B'\subseteq B\}$ such that for every $i\in B'$ , $\emptyset \subsetneq B^{\prime }_i\subsetneq B_i$ . To see this, it is enough to apply $\mathrm {p^kRC_{fin}}$ to $\bigcup \mathcal {B}$ and, if needed, to choose $p^k$ elements from the union the first l sets, where l is the least natural number such that $lm>p^k$ , and repeat for every next block of l elements of the family $\mathcal {B}$ .

Proof. It suffices to prove the theorem for $l=1$ . The general case then follows from

$$ \begin{align*}\mathcal{V}_{p_1^{a_1},\dots,p_l^{a_l}}\models\mathrm{nRC_{fin}}\iff\bigwedge_{k=1}^l\mathcal{V}_{p_k^{a_k}}\models\mathrm{nRC_{fin}}, \end{align*} $$

and

$$ \begin{align*}\mathcal{V}_{p_1^{a_1},\dots,p_l^{a_l}}\models\mathrm{nC^-_{fin}}\iff\bigwedge_{k=1}^l\mathcal{V}_{p_k^{a_k}}\models\mathrm{nC^-_{fin}}. \end{align*} $$

In [Reference Schumacher8, Proposition 5.3, Lemma 5.4] it is shown that

$$ \begin{align*}\mathcal{V}_{p_1^{a_1}}\models\mathrm{nC^-_{fin}}\iff n\textrm{ is a multiple of }p_1^{a_1}. \end{align*} $$

It remains to show that the same holds for $\mathrm {nRC_{fin}}$ . We start with showing that $\mathrm {p_1^{a_1}RC_{fin}}$ holds. In order to do so, we use the construction from [Reference Halbeisen and Tachtsis3, Fact 4], which we now briefly recall. To help the reader, we use the same notation. Let x be an infinite not well-orderable set with support E and $z\in x$ an element with support $E_z$ which is not supported by E. Let $A_r$ be a block of atoms included in $E_z$ but not in E. Then, if we define the set f as

$$ \begin{align*}f=\{(\varphi(z),\varphi(A_r)):\varphi\in\mathrm{fix}_G(E_z\setminus A_r)\},\end{align*} $$

the following statements hold:

• • f is supported by $E_z\setminus A_r$ ;

• • f is a function with $\mathrm {dom}(f)\subseteq x$ and $\mathrm {ran}(f)=\{A_q:q\in I\}$ for some possibly unbounded interval $I\subseteq \mathbb {Q}$ ;

• • if $y=\mathrm {dom}(f)$ and $\mathcal {Y}=\{f^{-1}(A_q):q\in I\}$ , then $\mathcal {Y}$ is a linearly orderable partition of y;

• • the elements of $\mathcal {Y}$ are finite sets all having the same cardinality, which has to be a divisor of $p_1^{a_1}$ ;

• • we can write $\mathcal {Y}=\{U_\varphi :\varphi \in \mathrm {fix}_G(E_z\setminus A_r)\}$ , where for $\varphi \in \mathrm {fix}_G(E_z\setminus A_r)$ ,

  $$ \begin{align*}U_\varphi=\{\eta z:\eta\in\mathrm{fix}_G(E_z\setminus A_r),\varphi^{-1}\eta(A_r)=A_r\}. \end{align*} $$

Consider now the orbits $O_s=\{\varphi (s):s\in [y]^{>p_1^{a_1}},\varphi \in \mathrm {fix}_G(E_z\setminus A_r)\}$ and write $\mathcal {O}=\{O_s:s\in [y]^{>p_1^{a_1}}\}$ . The goal is to show that it is possible to choose for each $O_s$ a subset $\tilde {s}\subsetneq s$ such that $|\tilde {s}|=p_1^{a_1}$ and if $O_s=O_t$ with $\varphi (s)=t$ , then $\varphi (\tilde {s})=\tilde {t}.$ Notice that this is equivalent to requiring that every time $\varphi (s)=s$ for some $\varphi \in \mathrm {fix}_G(E_z\setminus A_r)$ , then $\varphi (\tilde {s})=\tilde {s}.$ Now, fix an $O_s\in \mathcal {O}$ . Notice that if s is a union $s=\bigcup \{U_\varphi :\varphi \in P_s\}$ for some subset $P_s\subseteq \mathrm {fix}_G(E_z\setminus A_r)$ the conclusion is trivial. To deal with the other cases, once more we will fully rely on the fact that if a sum of divisors of $p_1^{a_1}$ is greater than $p_1^{a_1}$ , then there is a subsum equal to $p_1^{a_1}$ . Indeed, notice that for all $a\in s$ , the cardinality of $\{\varphi (a):\varphi \in \mathrm {fix}_G(E_z\setminus A_r),\varphi (s)=s\}$ has to be a divisor of $p_1^{a_1}$ . The conclusion is given by the last claim together with the fact that if $\tilde {s}\subseteq s$ is a union of orbits in the form $\{\varphi (a):\varphi \in \mathrm {fix}_G(E_z\setminus A_r),\varphi (s)=s\}$ , then $\varphi (s)=s$ implies $\varphi (\tilde {s})=\tilde {s}$ .

To finish the proof, we have to show that $\mathrm {nRC_{fin}}$ is false in $\mathcal {V}_{p_1^{a_1}}$ whenever n is not a multiple of $p_1^{a_1}$ . But this can easily be shown on the set of all atoms.

Proof. If a set X has cardinality $|X|>kn$ , by extracting k times n elements we can extract $kn$ elements.

Proof. Consider the set of the atoms and suppose that there is an infinite subset A with a function f which selects n elements from every finite and large enough subset of A. Let S be a support of f. Let M be any model of the theory $\mathrm {T}_m$ with cardinality $|M|=mk$ for $k\in \omega $ such that $m(k-1)<n<mk$ . Then it is possible to find an $mk$ -element subset $N=\{x_1,\dots ,x_{mk}\}\subseteq \omega $ such that:

1. 1. N and M are isomorphic as models of $\mathrm {T}_m$ ;

2. 2. $\mathrm {Sel}(Z)$ can be fixed arbitrarily whenever $Z\subseteq S\cup N$ with $\lvert Z\cap S\rvert \geq 1$ and $\lvert Z\cap N\rvert \geq 1$ ;

3. 3. $\mathrm {Sel}(\{x_{im+1},\dots ,x_{mk}\})=\{x_{im+1},\dots , x_{(i+1)m}\}$ holds for all $i< k$ .

Notice that that condition 3 is only a matter of reordering. Consider the following permutation of N, written as a finite product of finite cycles:

$$ \begin{align*}\widetilde{\pi}=\prod_{i< k}(x_{im+1},x_{im+2},\dots,x_{(i+1)m}). \end{align*} $$

Our conclusion will follow by showing that there is a model M of $\mathrm {T_m}$ , a corresponding subset $N\subseteq \omega $ and a permutation $\pi \in \mathrm {fix_G}(S)$ such that $\pi $ acts on N exactly as $\widetilde {\pi }$ on M. First we want to find a $\mathrm {T_m}$ -model $M=\{x_1,\dots , x_{mk}\}$ such that M and $\widetilde {\pi }M$ are isomorphic as $\mathrm {T_m}$ -models. Naturally, we first impose condition 3, namely for all $i\leq k$

$$ \begin{align*}\mathrm{Sel}(\{x_{im+1},x_{im+2},\dots,x_{mk}\})=\{x_{im+1},x_{im+2},\dots,x_{(i+1)m}\}. \end{align*} $$

The main idea of the proof is the following: Let L be a subset of M with $|L|>m$ and $L\neq \{x_{im+1},x_{im+2},\dots ,x_{mk}\}$ for every $i\in k$ . Consider the orbit $\{\widetilde {\pi }^lL:l\in \omega \}$ . Now we choose an m-element subset $L^\prime \subseteq L$ and define $\mathrm {Sel}(L):=L^\prime $ . Extend this choice to the whole orbit by defining

$$ \begin{align*}\mathrm{Sel}(\widetilde{\pi}^lL):=\widetilde{\pi}^l(\mathrm{Sel}(L)). \end{align*} $$

The choice of $\mathrm {Sel}(L)$ has to be suitable in the sense that $\widetilde {\pi }^jL=L$ must imply $\widetilde {\pi }^j(\mathrm {Sel}(L))=\mathrm {Sel}(L)$ .

• • First of all assume that for some $I\subseteq k$ ,

  $$ \begin{align*}|L\cap(\bigcup_{i\in I}\{x_{im+1},\dots,x_{(i+1)m}\})|=m. \end{align*} $$
  Then a suitable choice for $\mathrm {Sel}(L)$ is given by $\bigcup _{i\in I}\{x_{im+1},\dots ,x_{(i+1)m}\}\cap L$ .

• • Otherwise, let $J\subseteq k$ be the set of indices j such that $\widetilde {\pi }^s$ fixes

  $$ \begin{align*}L\cap\{x_{jm+1},\dots,x_{(j+1)m},\} \end{align*} $$
  only if s is a multiple of m. If $|L\setminus \bigcup _{j\in J}\{x_{jm+1},\dots ,x_{(j+1)m}\}|\leq m$ , then a suitable choice for $\mathrm {Sel}(L)$ is given by any m-element subset of L which includes $L\setminus \bigcup _{j\in J}\{x_{jm+1},\dots ,x_{(j+1)m}\}$ .

• • Let $J\subseteq k$ be as above and suppose that $m <|L\setminus \bigcup _{j\in J}\{x_{im+1},\dots ,x_{(i+1)m}\}|$ . By replacing L by $L\setminus \bigcup _{j\in J} \{x_{im+1},\dots , x_{(i+1)m}\}$ we can assume that for each $i < k$ there exists a $1< s< m$ such that $\widetilde {\pi }^s$ fixes $L\cap \{x_{im+1},\dots ,x_{(i+1)m}\}$ . Our goal is now to get rid of the case in which, for some $i< k$ , $0\neq |L\cap \{x_{im+1},\dots ,x_{(i+1)m}\}|\nmid m$ . Fix such an $i'< k$ and let $s'\in \omega $ be the least integer greater than $1$ for which $\widetilde {\pi }^{s'}$ fixes $L\cap \{x_{i'm+1},\dots ,x_{(i'+1)m}\}$ . Then the cardinality $|L\cap \{x_{i'm+1},\dots ,x_{(i'+1)m}\}|$ must be a multiple of $\frac {m}{s'}$ . Indeed, $\frac {m}{s'}$ is the cardinality of each orbit

  $$ \begin{align*}\{(\widetilde{\pi}^{s'})^s(x):x\in L\cap\{x_{i'm+1},\dots,x_{(i'+1)m}\}\land s\in\omega\}. \end{align*} $$
  In the next step we will consider each of these orbits as different subsets of the form $L\cap \{x_{im+1},\dots , x_{(i+1)m}\}$ for some $i\in k$ . In other words, we will without loss of generality assume that for all $i\in k$ there is some $1<s<m$ such that $\widetilde {\pi }^s$ fixes $L\cap \{x_{im+1},\dots , x_{(i+1)m}\}$ and such that $\lvert L\cap \{x_{im+1},\dots , x_{(i+1)m}\}\rvert $ , when non-zero, divides m.

• • Finally, choose $K\subseteq k$ such that

  1. 1. $|L\cap (\bigcup _{j\in K}\{x_{jm+1},\dots ,x_{(j+1)m}\})|\geq m$ is minimal and

  2. 2. $|L\cap \{x_{jm+1},\dots ,x_{(j+1)m}\}|\mid m$ for all $j\in K$ .

  Replace L by $L\cap \left (\bigcup _{j\in K}\{x_{jm+1},\dots ,x_{(j+1)m}\}\right )$ . Set $a_j=|L\cap \{x_{jm+1},\dots , x_{(j+1)m}\}|$ for each $j\in K$ . By writing $\sum _{j\in K}{a_j}=m+(|L|-m)$ , we can see that $\gcd _{j\in K}(a_j)\mid (|L|-m)$ . Now, notice that in order for a power $\widetilde {\pi }^s$ to fix $L\cap \{x_{jm+1},\dots ,x_{(j+1)m}\}$ for some $j\in K$ , s has to be a multiple of $\frac {m}{a_j}$ . It follows that, in order for a power $\widetilde {\pi }^s$ to fix L, s has to be a multiple of $m'=\mathrm {lcm}_{j\in K}(\frac {m}{a_j})=\frac {m}{\gcd _{j\in K}(a_j)}$ . Summarizing:

  1. 1. $\gcd _{j\in K}(a_j)\mid (|L|-m)$ .

  2. 2. $\widetilde {\pi }^s$ fixes L if and only if s is a multiple of $m'=\frac {m}{\gcd _{j\in K}(a_j)}$ .

  3. 3. $|L|-m<a_j$ , for all $j\in K$ .

  Fix a $j\in K$ . The conclusion will follow by finding an $F\subseteq L\cap \{x_{jm+1},\dots ,x_{(j+1)m}\}$ of cardinality $|L|-m$ such that whenever some $\widetilde {\pi }^s$ fixes L, then $\widetilde {\pi }^s$ fixes F as well. We can find such a set F through the following procedure: Start with $F=\emptyset $ . Let $x\in (L\cap \{x_{jm+1},\dots ,x_{(j+1)m}\})\setminus F$ , and replace F by $F\cup \{(\widetilde {\pi }^{m'})^t(x):t\in \omega \}$ , noticing that the cardinality of the orbit is exactly $\gcd _{j\in K}(a_j)$ . If $|F|=|L|-m$ , we are done, otherwise repeat the procedure with some $y\in (L\cap \{x_{jm+1},\dots ,x_{(j+1)m}\})\setminus F$ . After a finite number of repetitions we get $\lvert F\rvert =\lvert L\rvert -m$ .

Now we can show that S is not a support of the selection function f we chose at the beginning of the proof. Let M be the $\mathrm {T_m}$ -model we constructed above that satisfies $\widetilde {\pi }M=M$ . Let $N\subseteq \omega $ be a $\mathrm {T_m}$ -model that is isomorphic to M and satisfies conditions 1,2 and 3. The proof above shows that $\pi (\mathrm {Sel}(L))=\mathrm {Sel}(\pi (L))$ for all $L\subseteq N$ . Moreover, condition 2 says that N can even be chosen such that $\pi (\mathrm {Sel}(L))=\mathrm {Sel}(\pi (L))$ for all $L\subseteq N\cup S$ . So $\pi $ can be extended to a function $\pi \in \mathrm {fix_G}(S)$ on the whole model $\mathbf {F}$ . Note that for all n-element subsets of N we have that $\pi (N)\not = N$ . So S is indeed not a support of the selection function f. This is a contradiction.

Proof. Let A be an infinite set and apply $\mathrm {4RC_{fin}}$ to get an infinite subset $B\subseteq A$ with a function $\widetilde {f}\colon [B]^{>4}_{\mathrm {fin}}\to [B]^4$ . Let S be a $7$ -element subset of B. In this proof we are going to consider all the possible ways in which the function $\widetilde {f}$ can act on the subsets of S in order to show that it is always possible to choose a particular element of S, and hence to verify $\mathrm {RC_7}$ . Though making use of symmetries in a few passages, it will substantially be a case-by-case analysis. Let $S=\{x,y,z,a,b,c,d\}$ with $\widetilde {f}(S)=\{a,b,c,d\}$ . To simplify the notation, define the two functions

• • $f\colon [S]^{>4}\to \mathscr {P}(S)$ given by $f\colon T\mapsto T\setminus \widetilde {f}(T)$ ;

• • $g\colon [S]^{<3}\to [S]^{<3}$ given by $g\colon T\mapsto f(S\setminus T)$ .

For simplicity we will write, for instance, $g(a)$ instead of $g(\{a\})$ . We can assume that for all $l\in \widetilde {f}(S)=\{a,b,c,d\}$ we have that $g(l)\cap \{x,y,z\}=\emptyset $ . Otherwise, there is a natural way to choose an element from S. Now we build, step by step, all the possibilities for $\{g(a),g(b),g(c),g(d)\}$ which do not allow us to immediately choose an element from S.

1. 1. By symmetry, we can fix $g(d)=f(x,y,z,a,b,c)=\{a,b\}$ .

2. 2. There are now only two non-equivalent cases:

   1. (a) $g(d)=\{a,b\}$ and $g(c)=\{a,b\}$ ;

   2. (b) $g(d)=\{a,b\}$ and $g(c)=\{a,d\}$ , which is equivalent to the third possible choice $g(c)=\{b,d\}$ .

3. 3. The two cases branch now in five:

   1. (a) $g(d)=\{a,b\}$ , $g(c)=\{a,b\}$ and $g(b)=\{a,c\}$ . This is symmetric to which is symmetric to $g(d)=\{a,b\}$ , $g(c)=\{a,b\}$ and $g(b)=\{a,d\}$ .

   2. (b) $g(d)=\{a,b\}$ , $g(c)=\{a,b\}$ and $g(b)=\{c,d\}$ .

   3. (c) $g(d)=\{a,b\}$ , $g(c)=\{a,d\}$ and $g(b)=\{a,c\}$ .

   4. (d) $g(d)=\{a,b\}$ , $g(c)=\{a,d\}$ and $g(b)=\{c,d\}$ .

   5. (e) $g(d)=\{a,b\}$ , $g(c)=\{a,d\}$ and $g(b)=\{a,d\}$ .

Notice how the option 3.c can be ignored, since it allows us to choose a in S independently from $g(a)$ . With similar arguments we can show that the only four non-symmetric choices for $g(a)$ in which we cannot immediately choose an element from S are

1. 1. $g(d)=\{a,b\}$ , $g(c)=\{a,b\}$ , $g(b)=\{a,c\}$ and $g(a)=\{b,d\}$ ;

2. 2. $g(d)=\{a,b\}$ , $g(c)=\{a,b\}$ , $g(b)=\{c,d\}$ and $g(a)=\{c,d\}$ ;

3. 3. $g(d)=\{a,b\}$ , $g(c)=\{a,d\}$ , $g(b)=\{c,d\}$ and $g(a)=\{b,c\}$ ;

4. 4. $g(d)=\{a,b\}$ , $g(c)=\{a,d\}$ , $g(b)=\{a,d\}$ and $g(a)=\{c,d\}$ .

For each of the above cases we can check that the only permutations on $\{a,b,c,d\}$ that preserve g are given by

1. 1. $(a,b)(c,d)$ ;

2. 2. $(a,b)$ , $(c,d)$ , $(a,b)(c,d)$ , $(a,c)(b,d)$ , $(a,d)(b,c)$ ;

3. 3. $(a,c)(b,d)$ ;

4. 4. $(a,d)(b,c)$ .

In each of these cases, it is possible to select a particular double transposition (in case 2, pick $(a,b)(c,d)$ ). Last, consider how g acts on the six distinct pairs included in $\{a,b,c,d\}$ . A double transposition selects exactly two of these pairs: for instance, $(a,b)(c,d)$ selects $\{a,b\}$ and $\{c,d\}$ . We conclude the proof by considering the uniquely determined $g(g(a,b)\cup g(c,d))$ .

Proof. We have that either $n=1+4k$ or $n=3+4k$ for a $k\in \omega $ . The first case follows directly by Lemma 9.1. In the second case let x be an infinite set and apply $\mathrm {4RC_{fin}}$ to get an infinite subset $y\subseteq x$ with a selection function $f:[y]^{>4}_{\mathrm {fin}}\to [y]^4$ . Let $z\subseteq y$ be an n-element subset. Apply f exactly k times to find a $3$ -element subset $z_0$ of z. Then $\lvert z_0\cup f(z)\rvert =7$ and we can use Theorem 9.2.

Proof. Let $n,m\in \omega \setminus \{0\}$ and let p be a prime divisor of m such that ${n\not \equiv 1 (\mathrm {mod}\ {p})}$ . Consider the set of the atoms and suppose that there is an infinite subset A with a function f which selects an element from every n-element subset of A. Let S be a support of f. Let M be any $\mathrm {T_m}$ -model with cardinality $|M|=n$ and write $n=pk+r$ for unique $k,r\in \omega $ , with $1< r< p$ . Then it is possible to find an n-element subset $N=\{x_1,\dots ,x_n\}$ of C such that:

1. 1. N and M are isomorphic as models of T;

2. 2. $\mathrm {Sel}(Z)$ can be arbitrarily fixed whenever $Z\subseteq S\cup N$ with $\lvert Z\cap S\rvert \geq 1$ and $\lvert Z\cap N\rvert \geq 1$ ;

3. 3. $\mathrm {Sel}(\{x_{im+1},\dots ,x_n\})=\{x_{im+1},\dots , x_{(i+1)m}\}$ holds for all $i< k$ .

Consider the following permutation of N:

$$ \begin{align*}\widetilde{\pi}=(x_{pk+1},x_{pk+2},\dots,x_n)\prod_{i=0}^{k-1}(x_{pi+1},x_{pi+2},\dots,x_{p(i+1)}).\end{align*} $$

Our conclusion will follow by showing that there is a model M of $\mathrm {T}_m$ , a corresponding subset $N\subseteq C$ and a permutation $\pi \in \mathrm {fix_G}(S)$ such that $\pi $ acts on N exactly as $\widetilde {\pi }$ acts on M. First, we want to find a $\mathrm {T_m}$ -model $M=\{x_1,\dots , x_n\}$ such that M and $\widetilde {\pi }M$ are isomorphic as $\mathrm {T_m}$ -models. We first impose condition 3, namely that for all $i<k$

$$ \begin{align*}\mathrm{Sel}(\{x_{im+1},x_{im+2},\dots,x_n\})=\{x_{im+1},x_{im+2},\dots,x_{(i+1)m}\}. \end{align*} $$

Let L be a subset of M with $|L|>m$ , $L\neq \{x_{im+1},x_{im+2},\dots ,x_n\}$ for every $i< k$ . Consider the orbit $\{\widetilde {\pi }^lL:l\in \omega \}$ . Now we will choose an m-element subset $L^\prime \subseteq L$ and define $\mathrm {Sel}(L):=L^\prime $ . Extend this choice to the whole orbit by defining

$$ \begin{align*}\mathrm{Sel}(\widetilde{\pi}^lL)=\widetilde{\pi}^l(\mathrm{Sel}(L)). \end{align*} $$

As in Theorem 8.2, we need $\widetilde {\pi }^jL=L$ to imply $\widetilde {\pi }^j(\mathrm {Sel}(L))=\mathrm {Sel}(L)$ .

• • First of all assume that for some $I\subseteq k$ ,

  $$ \begin{align*}|L\cap(\bigcup_{i\in I}\{x_{pi+1},\dots,x_{p(i+1)}\})|\in\{m,m-|L\cap\{x_{pk+1},\dots,x_n\}|\}. \end{align*} $$
  Then a suitable choice for $\mathrm {Sel}(L)$ is given by either $L\cap (\bigcup _{i\in I}\{x_{pi+1},\dots ,x_{p(i+1)}\})$ or by $L\cap (\bigcup _{i\in I}\{x_{pi+1},\dots ,x_{p(i+1)}\}\cup \{x_{pk+1},\dots ,x_n\})$ .

• • Otherwise, let $J\subseteq k$ be the set of indices j such that $0<|L\cap \{x_{jp+1},\dots , x_{(j+1)p}\}|\neq p$ . Moreover, replace J by $J\cup \{k\}$ if $|L\cap \{x_{kp+1},\dots ,x_{n}\}|$ either is $1$ or does not divide r. For the sake of notation, let us write $\{x_{kp+1},\dots ,x_{(k+1)p}\}$ instead of $\{x_{kp+1},\dots ,x_n\}$ . If $|L\setminus \bigcup _{j\in J}\{x_{jp+1},\dots ,x_{(j+1)p}\}|\leq m$ , then we claim that a suitable choice for $\mathrm {Sel}(L)$ is given by any m-subset of L which includes $L\setminus \bigcup _{j\in J}\{x_{jp+1},\dots ,x_{(j+1)p}\}$ . The claim follows by the fact that, given a set $\{y_1,\dots ,y_{p'}\}$ for some prime $p'\in \omega $ , if $\tau $ is the permutation $(y_1,\dots ,y_{p'})$ and some power $\tau ^a$ fixes a proper subset $H\subsetneq \{y_1,\dots ,y_{p'}\}$ , then $\tau ^a$ is the identity on $\{y_1,\dots ,y_{p'}\}$ .

Note that we covered every possible case. Indeed, if we are not in the last case, then for some $k',r'\in \omega $ with $r'\leq r$ it is true that $m< k'p+r'$ . Then, since $r< p$ and $p\mid m$ , we are actually in the first case.

Now we can show that S is not a support of the selection function f we chose at the beginning of the proof. Let M be the $\mathrm {T_m}$ -model we constructed above that satisfies $\widetilde {\pi }M=M$ . Let $N\subseteq \omega $ be a $\mathrm {T_m}$ -model that is isomorphic to M and satisfies conditions 1,2 and 3. With the proof above and condition 2 we can choose N such that $\pi (\mathrm {Sel}(L))=\mathrm {Sel}(\pi (L))$ for all $L\subseteq N\cup S$ . So $\pi $ can be extended to a function $\pi \in \mathrm {fix_G}(S)$ on the whole model $\mathbf {F}$ . Note that for all n-element subsets of N we have that $\pi (N)\not = N$ . So S is indeed not a support of the selection function f. This is a contradiction.

Proof. Exactly as in the previous theorem: just consider the permutation

$$ \begin{align*}\widetilde{\pi}=(x_1,\dots,x_n), \end{align*} $$

and impose that $\mathrm {Sel}(L)\supset L\cap N$ whenever $L\cap N\neq \emptyset $ , with $L\subseteq S\cup N$ .