Theorem. Let be a set with atoms, and let
. If
is supported by two finite sets of atoms
, then
is also supported by
.
We say that a permutation of the atoms fixes a set of atoms
if
holds for all
. By definition, a set
supports
if every permutation
fixing
satisfies
. To prove the theorem, it suffices to show the following claim.
Claim. For every permutation of the atoms which fixes
, there exist permutations of the atoms
such that
and each fixes either
or
.
Proof of the claim. Take as in the assumption of the claim. The proof is by induction on the number of elements in
that are not fixed by
, with the induction base being the case when either
or
is fixed. Define a cycle of
to be a set of the form
for some . 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 . Each element on the cycle is either from
, or from
or from outside
. Necessarily, there must be two consecutive elements on the cycle such that one of the cases
or
is avoided, let us assume without loss of generality that
and
. Define
to be the transposition which swaps
with
, this transposition fixes
. It is not difficult to see that applying first the transposition
and then
is a permutation
of the atoms satisfying
This means that fixes all that
fixed, and it fixes
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 . This means that there is some
such that
and
. Choose some atom
, let
be the transposition of
and
. Then
The new permutation has a cycle of length 3 which contains both
and it is no worse with respect to the induction assumption, therefore we can apply the reasoning above.
Leave a Reply