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$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Is A arbitrary or finite? If A is finite I have an idea for (2). $\endgroup$
    – Benjamin Steinberg
    Commented 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
    Commented Jan 3, 2018 at 18:15
  • $\begingroup$ I expected problems like that in the infinite case. $\endgroup$
    – Benjamin Steinberg
    Commented 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
    Commented Jan 10, 2018 at 0:43

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I fixed my answer. You just need to apply my old answer in the power set of $A$. $\endgroup$
    – Benjamin Steinberg
    Commented 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
    Commented 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
    Commented 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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Looks OK to me. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 10, 2018 at 1:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .