3
$\begingroup$

[Reposted from math.stackexchange]

Consider a monoid $M$ acting on a set $X$, where $M$ is the full transformation monoid on some set $A$ (i.e., the set of all functions from $A$ to itself, with function composition as the monoid operation).

Say that $B\subseteq A$ fixes $x\in X$ iff, for all $m\in M$, if $m(b) = b$ for all $b\in B$, then $mx=x$.

Say that $B\subseteq A$ pins down $x\in X$ iff, for all $m,n\in M$, if $m(b)=n(b)$ for all $b\in B$, then $mx=nx$.

[Apologies if there's more standard terminology for these notions]

Question 1: If $B$ fixes $x$, does it follow that $B$ pins down $x$?

Question 2: If $B$ and $B'$ both pin down $x$, does it follow that $B\cap B'$ pins down $x$?

$\endgroup$
4
  • $\begingroup$ Is A arbitrary or finite? If A is finite I have an idea for (2). $\endgroup$ Jan 3, 2018 at 10:38
  • $\begingroup$ For the applications I'm interested in it's important that $A$ can be infinite. Possibly relevant: the sets of subsets of $A$ that pin down $x$ needn't be closed under arbitrary intersections. Let $A$ be infinite, let $X := \mathcal{P}(M)$, and let $mx := \{n\circ m: n\in x\}$. Consider some $a\in A$, and let $y$ be the set of all $m\in M$ that map all but finitely many members of $A$ to $a$. Then $y$ is pinned down by all co-finite subsets of $A$, but is not pinned down by the empty set. $\endgroup$
    – Jeremy
    Jan 3, 2018 at 18:15
  • $\begingroup$ I expected problems like that in the infinite case. $\endgroup$ Jan 3, 2018 at 20:05
  • $\begingroup$ Just for people like me who generally use "transformation" for somewhat bijective stuff, "full transformation monoid on $A$" means the set of all self-maps of $A$, monoid under composition. $\endgroup$
    – YCor
    Jan 10, 2018 at 0:43

2 Answers 2

2
$\begingroup$

The answer to (1) is yes. Let $B$ fix $x$. If $B$ is empty, then $M$ fixes $x$ so nothing to prove. Else choose any idempotent $e\in M$ with image $B$ (so fix $B$ and send all other elements to arbitrary elements of $B$). Then $e(x)=x$. If $f,g\in M$ agree on $B$, then $fe=ge$ and so $f(x)=fe(x)=ge(x)=g(x)$. So $B$ pins down $x$.

I will think about (2).

$\endgroup$
3
  • $\begingroup$ I fixed my answer. You just need to apply my old answer in the power set of $A$. $\endgroup$ Jan 2, 2018 at 21:27
  • $\begingroup$ I'm also interested in cases where $X = \mathcal{P}(M)$, $mx = \{n\circ m: n\in x\}$, and $M$ a submonoid of the full transformation monoid on $A$. For example, if $A$ is infinite and $M$ is the monoid of surjective functions on $A$, then the answer to question (1) is "no": let $B$ contain all but $n$ members of $A$, for finite $n > 1$, and let $x$ be the set of functions that are surjective on $B$. But what about, e.g., the monoid of functions that map all but finitely many members of $A$ to themselves, or the monoid of functions that are non-injective for only finitely many members of $A$? $\endgroup$
    – Jeremy
    Jan 5, 2018 at 16:51
  • $\begingroup$ The answer is still "yes" in those cases, for basically the reason you give -- in the case of the monoid of functions with finite support, for any $f, g$ that agree on $B$, there is an $e$ that fixes $B$ and maps every element not in $B$ that is moved either by $f$ or by $g$ to some arbitrary $x\in B$ (provided $B$ is non-empty); we then argue as before. Similarly for the monoid of only finitely non-injective functions. $\endgroup$
    – Jeremy
    Jan 9, 2018 at 23:41
2
$\begingroup$

The answer to Question 2 is also "yes". Trivially so if $B\subseteq B'$ or $B'\subseteq B$, so assume otherwise. Given the affirmative answer to Question 1, it suffices to show that $mx=x$ when $mb=b$ for all $b\in B\cap B'$ (on the assumption that $B$ and $B'$ both fix $x$). Case 1: Assume that for some $a\in A$, $a\in B$ if and only if $a\in B'$. For any $c\in A, C\subseteq A$, let $g(C,c)\in M$ be the function that maps every member of $C$ to $c$ and every other member of $A$ to itself. Let $n=g(B'\backslash B,a)$, $n' =g(B\backslash B',a)$, $n''= g(A\backslash(B\cup B'),a)$, and $n'''(\{a\},m(a))$. $n$ maps every member of $B$ to itself, $n'$ maps every member of $B'$ to itself, and $n''$ and $n'''$ do both. So $nx = n'x=n''x=n'''x = x$. Since $m\circ n''\circ n'\circ n = n'''\circ n''\circ n'\circ n$, it follows that $mx = x$. Case 2: Suppose $B = A\backslash B'$ and $|A|> 2$. Consider some $b\in B,b'\in B'$. Since $B$ fixes $x$, so does $B\cup\{b'\}$; by Case 1, so does $(B\cup\{b'\})\cap B' = \{b'\}$; similarly, so does $\{b\}$; since $|A|>2$, there is an $a\in A$ such that $a\not\in \{b\}$ and $a\not\in \{b'\}$; so, by Case 1, $\{b\}\cap\{b'\}=\emptyset = B\cap B'$ fixes $x$. Case 3: Suppose $B = A\backslash B'$ and $|A|= 2$. So $B= \{b\}$ and $B'=\{b'\}$. So $m$ is either the identity function on $A$, the constant function $k$ with image $B$, the constant function $k'$ with image $B'$, or the transposition $(bb')$. Any of the first three functions either maps every member of $B$ to itself or every member of $B'$ to itself, so $mx=x$ if $m$ is one of them; likewise if $m=(bb')$, since $(bb')x = (bb')kx = ((bb')\circ k)x = k'x=x$.

$\endgroup$
1

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.