{"id":1008,"date":"2016-02-01T15:56:16","date_gmt":"2016-02-01T14:56:16","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1008"},"modified":"2016-02-01T15:56:16","modified_gmt":"2016-02-01T14:56:16","slug":"least-support","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/sets-with-atoms\/least-support","title":{"rendered":"Least Support"},"content":{"rendered":"

Theorem.\u00a0<\/strong>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\".<\/p>\n

We say that a permutation of the atoms \"\pi\" fixes<\/em> 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.<\/p>\n

Claim.\u00a0<\/strong>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 <\/p>\n

  <\/span>   <\/span>\"\[\pi = \pi_1 \circ \cdots \circ \pi_n\]\"<\/p>\n

and each \"\pi_i\" fixes either \"S\" or \"T\".<\/p>\n

Proof of the claim.\u00a0<\/strong>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<\/p>\n

  <\/span>   <\/span>\"\[X = \set{\pi^i(a) : i \in \mathbb Z}\]\"<\/p>\n

for some \"a \in \atoms\". Such a “cycle” might be infinite.<\/p>\n

Suppose that there is some cycle as above \u00a0which has size at least 3, and which contains some atom \"a \in S \cup T\". \u00a0Each 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 <\/p>\n

  <\/span>   <\/span>\"\[a \mapsto \pi^2(a) \qquad \pi(a) \mapsto \pi(a)\]\"<\/p>\n

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.<\/p>\n

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<\/p>\n

  <\/span>   <\/span>\"\[\pi(\sigma(a)) = \pi(c) \qquad \pi(\sigma(b)) = a \qquad \pi(\sigma(c)) = b\]\"<\/p>\n

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\"<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Theorem.\u00a0Let 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":970,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1008","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1008"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=1008"}],"version-history":[{"count":17,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1008\/revisions"}],"predecessor-version":[{"id":1026,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1008\/revisions\/1026"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/970"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1008"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}