{"id":970,"date":"2016-02-01T14:37:56","date_gmt":"2016-02-01T13:37:56","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=970"},"modified":"2016-02-19T14:09:11","modified_gmt":"2016-02-19T13:09:11","slug":"sets-with-atoms","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/sets-with-atoms","title":{"rendered":"9. Sets with atoms"},"content":{"rendered":"

Let us fix an infinite set \"\atoms\", which we will call the\u00a0atoms. <\/em>Consider the set of all permutations of the atoms, which is a group.\u00a0\u00a0An\u00a0action\u00a0<\/em>of\u00a0the group of permutations of atoms\u00a0on a set \"X\" is a function<\/p>\n

  <\/span>   <\/span>\"\[(\pi \mbox{ a permutation of atoms}, x \in X) \qquad \mapsto \qquad \pi(x)\]\"<\/p>\n

which is consistent with the group structure in the sense that <\/p>\n

  <\/span>   <\/span>\"\[\pi(\sigma(x)) = (\pi \circ \sigma)(x).\]\"<\/p>\n

Given such an action, we say that a set of atoms \"S\"\u00a0supports\u00a0<\/em>some \"x \in X\" if \"\pi(x)\" is uniquely determined by the values of \"\pi\" on atoms from \"S\". In other words,<\/p>\n

  <\/span>   <\/span>\"\[\big( \forall a \in S\ \pi(a) = \sigma(a) \big) \quad \mbox{implies} \quad \pi(x)=\sigma(x)\]\"<\/p>\n

Define a\u00a0set with atoms<\/em> to be a set \"X\" equipped with an action of permutations of atoms such that every element \"x \in X\" has some finite support.<\/p>\n

Equivariance.\u00a0<\/strong>If \"X\" is a set with atoms, call a subset \"Y \subseteq X\" equivariant<\/em> if the subset is invariant under renaming atoms, i.e. <\/p>\n

  <\/span>   <\/span>\"\[x \in Y \qquad \mbox{iff} \qquad \pi(x) \in Y\]\"<\/p>\n

holds for every \"x \in X\" and every permutation of the atoms \"\pi\". \u00a0A function \"f : X \to Y\" is called\u00a0equivariant\u00a0<\/em>if <\/p>\n

  <\/span>   <\/span>\"\[f(\pi(x)) = \pi(f(x))\]\"<\/p>\n

holds for every \"x \in X\" and every permutation of the atoms \"\pi\". These definitions are compatible in the sense that: a subset is equivariant if and only if its characteristic function is equivariant, and a function is equivariant if and only if its graph is an equivariant relation.<\/p>\n

Orbit-finiteness.\u00a0<\/strong>If \"X\" is a set with atoms, we say that \"x,y \in X\" are in the same orbit if some permutation of the atoms takes \"x\" to \"y\". This is an equivalence relation, and its equivalence classes are called orbits. A set with atoms is called orbit-finite\u00a0<\/i>if it has finitely many orbits. The motivation for this notion is that the state space, input alphabet and all other components in a register automaton<\/a>\u00a0 are orbit-finite sets with atoms.<\/p>\n

\n

 <\/p>\n

Lemma\u00a01.\u00a0<\/strong>Let \"f : X \to Y\" be an equivariant function. If a set of atoms supports \"x \in X\", then it also supports \"f(x) \in Y\".<\/p>\n

Proof.\u00a0<\/strong>From the definition: if \"\pi\" is a permutation of atoms which fixes \"x\", then it also fixes \"f(x)\" by equivariance. \"\Box\"<\/p>\n

 <\/p>\n

\n

 <\/p>\n

A representation theorem.<\/strong><\/p>\n

Let us write \"\atoms^{(n)}\" for the set of non-repeating \"n\"-tuples of atoms. This is a single-orbit set with atoms.\u00a0On the set \"\atoms^{(n)}\", we can define an action of permutations of\u00a0\u00a0\"\set{1,\ldots,n}\" as follows: <\/p>\n

  <\/span>   <\/span>\"\[\pi(a_1,\ldots,a_n) = (a_{\pi(1)},\ldots,a_{\pi(n)})\]\"<\/p>\n

\u00a0 Note that we have two groups acting on \"\atoms^{(n)}\", permutations of the atoms, and permutations of the coordinates. These actions commute with each other in the following sense: if \"\pi\" is a permutation of the coordinates and \"\sigma\" is a permutation of the atoms, then<\/p>\n

  <\/span>   <\/span>\"\[\pi ( \sigma (a_1,\ldots,a_n)) = \sigma ( \pi (a_1,\ldots,a_n)).\]\"<\/p>\n

If \"G\" is a subgroup of all permutations of \"\set{1,\ldots,n}\", then we define\u00a0<\/p>\n

  <\/span>   <\/span>\"\[\atoms^{(n)} /_G\]\"<\/p>\n

to be \"\atoms^{(n)}\" modulo the equivalence relation which identifies two tuples if they are in the same orbit with respect to the action of \"G\".\u00a0The following theorem shows that this is essentially the only possible\u00a0construction for sets with atoms.<\/p>\n

Theorem 1.\u00a0<\/b>Every set with atoms is isomorphic (where isomorphisms are equivariant bijections) to a disjoint union of sets of the form <\/p>\n

  <\/span>   <\/span>\"\[\atoms^{(n)} /_G\]\"<\/p>\n

where \"n\" is a natural number and \"G\" is a subgroup of the permutation group on \"\set{1,\ldots,n}\".<\/p>\n

Proof.\u00a0<\/strong>It suffices to prove the theorem for single orbit sets, because every set with atoms is isomorphic to the disjoint union of its orbits. Let then \"X\" be a single-orbit set. Choose some \"x \in X\", and let \"\set{a_1,\ldots,a_n}\" be the least support of \"x\", in some order. Consider the\u00a0relation<\/p>\n

  <\/span>   <\/span>\"\[\set{ \pi(a_1,\ldots,a_n) , \pi(x)} \subseteq \atoms^{(n)} \times X,\]\"<\/p>\n

which is equivariant by definition. Because \"a_1,\ldots,a_n\" supports \"x\", the above is actually an equivariant function, call it <\/p>\n

  <\/span>   <\/span>\"\[f : \atoms^{(n)} \to X.\]\"<\/p>\n

\u00a0Consider the inverse image \"f^{-1}(x)\", and define \"G\" to be the permutations of \"\set{1,\ldots,n}\" such that<\/p>\n

  <\/span>   <\/span>\"\[f(\pi(a_1,\ldots,a_n)) = f(a_1,\ldots,a_n)\]\"<\/p>\n

The set \"G\" is easily seen to \u00a0be a subgroup. To conclude the proof, we make the following claim, which implies that \"X\" is isomorphic to \"\atoms^{(n)} /_G\".<\/p>\n

Claim.\u00a0<\/strong>The following conditions are equivalent for every\u00a0\"\bar b, \bar c \in \atoms^{(n)}\":
\n1) \"f(\bar b) = f (\bar c)\"
\n2) there is some \"\pi \in G\" such that \"\bar c = \pi(\bar b)\".<\/p>\n

2) implies 1) Assume 2) holds for some \"\pi \in G\". By definition of \"f\", we have
\n<\/p>\n

  <\/span>   <\/span>\"\[f(\bar a) = f(\pi(\bar a))\]\"<\/p>\n

<\/span>Let \"\sigma\" be some permutation of the atoms such that \"\sigma(\bar a) = \bar b\", which exists because there is only one orbit of non-repeating tuples. Applying \"\sigma\" to both sides of the equality above, we get<\/p>\n

  <\/span>   <\/span>\"\[\sigma(f(\bar a)) = \sigma(f(\pi(\bar a)))\]\"<\/p>\n

<\/span>By equivariance of \"f\", we have<\/p>\n

  <\/span>   <\/span>\"\[f(\sigma(\bar a)) = f(\sigma(\pi(\bar a)))\]\"<\/p>\n

Because permutations with atoms commute with permutations of coordinates, we have<\/p>\n

  <\/span>   <\/span>\"\[f(\sigma(\bar a))=f(\pi(\sigma(\bar a))).\]\"<\/p>\n

By choice of \"\sigma\", the above is<\/p>\n

  <\/span>   <\/span>\"\[f(\bar b)=f(\pi(\bar b))=f(\bar c).\]\"<\/p>\n

 <\/p>\n

1) implies 2)\u00a0Suppose \"f(\bar b) = f(\bar c)\". Let \"\sigma\" be some permutation of the atoms such that \"\sigma(\bar b) = \bar a\". By equivariance of \"f\", we have<\/p>\n

  <\/span>   <\/span>\"\[f(\bar a) = f(\sigma(\bar b)) = f(\sigma(\bar c)).\]\"<\/p>\n

By Lemma 1, the tuple \"\sigma(\bar c)\" supports \"f(\bar a)\". By the least support theorem<\/a>, the set of atoms in \"\sigma(\bar c)\" must be equal to \"\set{a_1,\ldots,a_n}\",\u00a0i.e. there must be some permutation \"\pi\" of coordinates such that<\/p>\n

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

Since \"\sigma(\bar c)\" has the same image under \"f\" as \"\bar a\", it follows that \"\pi \in G\". Therefore,<\/p>\n

  <\/span>   <\/span>\"\[\bar c = \sigma^{-1}(\pi(\bar a)) = \pi(\sigma^{-1}(\bar a)) = \pi(\bar b)\]\"<\/p>\n

which completes the proof of the claim and therefore also of the theorem. \"\Box\"<\/p>\n","protected":false},"excerpt":{"rendered":"

Let us fix an infinite set , which we will call the\u00a0atoms. Consider the set of all permutations of the atoms, which is a group.\u00a0\u00a0An\u00a0action\u00a0of\u00a0the group of permutations of atoms\u00a0on a set is a function     which is consistent with the group structure in the sense that     Given such an action, we […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":535,"menu_order":9,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-970","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/970"}],"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=970"}],"version-history":[{"count":39,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/970\/revisions"}],"predecessor-version":[{"id":1039,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/970\/revisions\/1039"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/535"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}