Uniform bound on the size of support of a witness

Let $R\subset X\times Y$ be an equivariant relation. We show that under a certain assumption on $X$ , for every $x\in X$ , if there exists a witness $y\in Y$ such that $R(x,y)$ holds, then there also exists one with small support. We show an application to extending homomorphisms.

The assumption on the set $X$ is that it is locally finite, i.e., for every finite support $S$ there are only finitely many elements supported by $S$ in $X$ . 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 $X$ is locally finite and $R\subset X\times Y$ is an equivariant relation. Then there is a function $f:\Nat \to \Nat$ such that for every $x\in X$ if there exists a witness $y\in Y$ such that $R(x,y)$ , then there is one with $|\sup y|\le f(|\sup x|)$ .

Proof. For an element $x\in X$ , let $s(x)$ denote the minimal size of the support of an element $y$ such that $R(x,y)$ holds, and $0$ if no such element exists. Then $s$ is an equivariant function from $X$ to $\Nat$ .

For a number $n$ , let $X_n$ denote the set of elements of $X$ whose support has size at most $n$ . By local finiteness of $X$ , the set $X_n$ is orbit-finite, for each number $n$ . Therefore, the mapping $s$ , restricted to $X_n$ , attains a maximal value, let it be denoted by $f(n)\in\Nat$ . The function $f$ satisfies the condition of the lemma. $\square$

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 $A,B$ be two orbit-finite relational structures. Let $h$ be a finitely supported, partial homomorphism from $A$ to $B$ , which extends to some homomorphism $\hat h:A\to B$ . Then the extension $\hat h:A\to B$ can be chosen so that $|\sup {\hat h}|\le f(|\sup {h}|)$ , where $f:\Nat\to\Nat$ is some mapping depending on $A,B$ .

Proof. Apply the lemma to the relation $R$ , consisting of pairs $(f_0,f)$ where $f_0$ is a partial homomorphism from $A$ to $B$ and $f$ is an extension of $f_0$ to $f$ . $\square$

2 thoughts on “Uniform bound on the size of support of a witness”

Bartek says:

June 7, 2014 at 9:25 am

The assumption that the domain of $R$ is all of $X$ is not necessary, is it? Later you say “if a witness exists” anyway… Just say that the function $f$ is partial and everything should work.

1. szymtor says:
  
  June 7, 2014 at 11:56 am
  
  Fixed – the assumption is not necessary. But $f$ doesn’t need to be partial.

Atompress

Uniform bound on the size of support of a witness

2 thoughts on “Uniform bound on the size of support of a witness”

Leave a Reply Cancel reply

Computation with atoms