$X$ is a set and $X!$ is the set of bijections from $X$ to $X$. Let $A(m)$ be the set defined as $A(m)=\{f^x(m)\mid x\in\mathbb Z\}$ for some $f$ in $X!$ and some $m$ in $X$. Now, how do I prove that for $m, n\in X$, $A(m)\cap A(n)=\emptyset$ or $A(m) = A(n)$?

I have tried the following strategy. Assume $A(m) \cap A(n) \ne \emptyset$. Then, there exists $x \in A(m) \cap A(n)$, which implies $x \in A(m)$ and $x \in A(n)$. Then, I think we have to use the set membership criteria. What I am not sure is how does that help us use the double containment argument to prove that $A(m) = A(n)$? To me, it seems very trivially right. I am not sure how to proceed in these kinds of questions.

  • $\begingroup$ You perhaps need that $X$ is finite? $\endgroup$ – enedil Feb 10 at 20:54
  • $\begingroup$ I do not think so. $\endgroup$ – Ufomammut Feb 10 at 20:55
  • $\begingroup$ Ah, $x$ in the definition of $A$ can be negative, right? $\endgroup$ – enedil Feb 10 at 20:56
  • 1
    $\begingroup$ No, that is false. Consider $X=\mathbb Z$ and $f(x)=x+1$. This is a bijection, but doesn't have this property. $\endgroup$ – enedil Feb 10 at 20:58
  • 1
    $\begingroup$ Just a word on notation. Using $X$ for a set, and then $x$ for an element of $\Bbb Z$ is awful. Even worse, $m$ is a common letter for denoting an element of $\Bbb Z$, and you use it to denote an element of $X$ (I suppose?) $\endgroup$ – Asaf Karagila Feb 10 at 21:10

I don't think I'm understanding the definition as written. It appears that you've written $A(m)=\{f^x(m): x\in\Bbb{Z}, f\in X!\}$. Do you perhaps mean to instead say: Fix $f\in X!$, then for each $m\in X$, we define $A(m)=\{f^x(m):x\in\Bbb{Z}\}$? It must be the latter I think.

In that case, this is a special case of the fact that orbits under a group action are either equal or disjoint, which in this case is proved in the following manner.

Suppose $A(m)\cap A(n)\ne \varnothing$. Let $f^x(m)=f^y(n)$. Then $m=f^{y-x}(n)$, so $f^k(m)=f^{y-x+k}(n)\in A(n)$. Thus $A(m)\subseteq A(n)$, and by symmetry, we also have $A(n)\subseteq A(m)$. Thus $A(m)=A(n)$.

  • $\begingroup$ Yes, the $f$ is fixed. What I do not understand is in your solution, why did you say "Let $f^x(m) = f^y(n)$." I mean I got the same, but in following way: If $A(m)$ $\cap$ $A(n)$ $\neq$ $\emptyset$, then there exists an $a$ $\in$ $X$ such that a $\in$ $A(m)$ $\cap$ $A(n)$, and then I concluded that $f^x(m) = f^y(n)$. Is that your way as well? $\endgroup$ – Ufomammut Feb 10 at 21:08
  • 1
    $\begingroup$ @Ufomamut, yes, that's the same. Since we know that $A(m)\cap A(n)$ is nonempty, then there is an element in $A(m)$ that equals an element of $A(n)$, and those elements have the form $f^x(m)$ and $f^y(n)$ for some $x$ and $y$ in $\Bbb{Z}$. $\endgroup$ – jgon Feb 10 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.