Let be an equivariant relation. We show that under a certain assumption on , for every , if there exists a witness such that holds, then there also exists one with small support. We show an application to extending homomorphisms.

The assumption on the set is that it is locally finite, i.e., for every finite support there are only finitely many elements supported by in . Examples of such sets include all orbit-finite sets, but also the set of all finitely supported functions between two orbit-finite sets. See this post for more on locally finite sets.

Lemma. Suppose that is locally finite and is an equivariant relation. Then there is a function such that for every if there exists a witness  such that , then there is one with.

Proof. For an element , let  denote the minimal size of the support of an element such that holds, and if no such element exists. Then  is an equivariant function from to .

For a number , let denote the set of elements of whose support has size at most . By local finiteness of , the set is orbit-finite, for each number . Therefore, the mapping , restricted to , attains a maximal value, let it be denoted by . The function satisfies the condition of the lemma.

An application. In the application below, it does not really matter what an orbit-finite relational structure is. What matters is that their domains are orbit-finite, so the set of (partial) homomorphisms between two such structures is locally finite.

Proposition. Let be two orbit-finite relational structures. Let  be a finitely supported, partial homomorphism from to , which extends to some homomorphism . Then the extension can be chosen so that  , where  is some mapping depending on .

Proof. Apply the lemma to the relation , consisting of pairs where  is a partial homomorphism from to and is an extension of to .