Least Support

Mikołaj Bojańczyk

zajęcia / courses

Theorem. Let $X$ be a set with atoms, and let $x \in X$ . If $x$ is supported by two finite sets of atoms $S,T \subseteq \atoms$ , then $x$ is also supported by $S \cap T$ .

We say that a permutation of the atoms $\pi$ fixes a set of atoms $S$ if $\pi(a)=a$ holds for all $a \in S$ . By definition, a set $S$ supports $x \in X$ if every permutation $\pi$ fixing $S$ satisfies $\pi(x)=x$ . To prove the theorem, it suffices to show the following claim.

Claim. For every permutation of the atoms $\pi$ which fixes $S \cap T$ , there exist permutations of the atoms $\pi_1,\ldots,\pi_n$ such that

$\pi = \pi_1 \circ \cdots \circ \pi_n$

and each $\pi_i$ fixes either $S$ or $T$ .

Proof of the claim. Take $\pi$ as in the assumption of the claim. The proof is by induction on the number of elements in $S \cup T$ that are not fixed by $\pi$ , with the induction base being the case when either $S$ or $T$ is fixed. Define a cycle of $\pi$ to be a set of the form

$X = \set{\pi^i(a) : i \in \mathbb Z}$

for some $a \in \atoms$ . Such a “cycle” might be infinite.

Suppose that there is some cycle as above which has size at least 3, and which contains some atom $a \in S \cup T$ . Each element on the cycle is either from $S-T$ , or from $T-S$ or from outside $S \cup T$ . Necessarily, there must be two consecutive elements on the cycle such that one of the cases $S-T$ or $T-S$ is avoided, let us assume without loss of generality that $\pi(a) \in S-T$ and $a \not \in T$ . Define $\sigma$ to be the transposition which swaps $a$ with $\pi(a)$ , this transposition fixes $T$ . It is not difficult to see that applying first the transposition $\sigma$ and then $\pi$ is a permutation $\pi \circ \sigma$ of the atoms satisfying

$a \mapsto \pi^2(a) \qquad \pi(a) \mapsto \pi(a)$

This means that $\pi \circ \sigma$ fixes all that $\pi$ fixed, and it fixes $\pi(a)$ as well, and therefore we can apply the induction assumption.

We are left with the case when there is no cycle which has cycle at least 3 and contains an atom from $S \cup T$ . This means that there is some $a \in T - S$ such that $\pi(a) = b \in S - T$ and $\pi^2(a)=a$ . Choose some atom $c \not \in S \cup T$ , let $\sigma$ be the transposition of $c$ and $a$ . Then

$\pi(\sigma(a)) = \pi(c) \qquad \pi(\sigma(b)) = a \qquad \pi(\sigma(c)) = b$

The new permutation $\pi \circ \sigma$ has a cycle of length 3 which contains both $a,b$ and it is no worse with respect to the induction assumption, therefore we can apply the reasoning above. $\Box$

zajęcia / courses

Least Support

Least Support

Leave a Reply