I believe I've proved that the power semigroup of non-negative integers with addition has a trivial automorphism group. The proof is a bit long, completely elementary and rather unremarkable (as the fact itself probably) so I won't post it here. However, I spent a long time thinking it up. Probably way too long. So I would like to know whether the fact

  • is actually a fact;

  • is completely trivial;

  • follows immediately from a theorem that's maybe not that trivial;

  • has any significance.

Added: For a semigroup $(S,\star)$, the power semigroup of $S$, denoted by $P(S)$ is the semigroup of all non-empty subsets of $S$ with the operation $A\star B=\{a\star b\,|\,a\in A,b\in B\}.$

Added later: I'm confused by the answers given so far. The answerers seem to be showing that any automorphism of $P(\Bbb N)$ has to fix every singleton. Showing this was the first step in my proof, but I couldn't see how it showed immediately that such an automorphism has to fix everything. That's why my proof was getting longer and longer. I kept showing that an automorphism had to fix more and more things, until it had to fix all things. If that was unnecessary, I would like to understand it. Even if it is completely obvious, please do spell it out for me if possible. My mathematical spirits haven't been above sea level for a very long time, and being unable to understand something that people seem to consider obvious always brings me down.

Edit: I only really started feeling like I might get anywhere with this when I realized it was enough to work on sets containing zero. This is because the idempotent elements in $P(\Bbb N)$ are exactly the submonoids of $\Bbb N$ and $\Bbb N$ is the only idempotent $E$ such that for any other idempotent $F$ we have $E+F=E$. (In fact more is true: $E\supseteq F\iff E+F=E,$ which is to say that inclusion is the reversed standard partial order on idempotents of a semigroup: $e\leq f\iff ef=fe=e.$) This means $\Bbb N$ is fixed by any automorphism, and a set $X$ contains $0$ iff $X+\Bbb N=\Bbb N.$ So sets containing zero must go to sets containing zero. And additionally any set can be written uniquely as the sum of a singleton and a set containing zero, so it's enough to show any automorphism has to fix any such set. And these are a lot nicer because there are all kinds of relationships between adding such sets and inclusion.

Further on my proof is just ugly grinding so it doesn't make any sense to post it here I think.

  • 1
    $\begingroup$ Idempotents are definitely not irreducible. What I mean was show idempotents are fixed and irreducible elements are fixed. Note every finite subset containing 0 is a sum of irreducible elements by a simple induction argument on size, so if irreducible elements are fixed, then so are finite subsets. $\endgroup$ – Benjamin Steinberg Nov 13 '13 at 19:32
  • 2
    $\begingroup$ Michal, perhaps your way is the best way of doing. I don't see any conceptual reason at the moment. $\endgroup$ – Benjamin Steinberg Nov 13 '13 at 20:11
  • 1
    $\begingroup$ @Ibrahim I seem to have lost the proof for good. I've only found the first page which is useless. I remember that an important step was to show that the sets $\{0,n\}$ were fixed and there was something about cofinite sets. Sorry... I'll try to remember. $\endgroup$ – Michał Masny Mar 18 '15 at 21:43
  • 1
    $\begingroup$ @Ibrahim, OK I've got some of it. First note that $\Bbb N\setminus\{1\}$ is the second smallest idempotent of $P(\Bbb N)$ and so it's fixed. Let $T$ be the semigroup of sets containing $0$. Then $\Bbb N$ is the absorbing element of $T,$ so, for $R\subseteq T,$ let's call $\text{ann}(R):=\{X\in T\,|\,(\forall Y\in R) X+Y=\Bbb N\}$ the annihilator of $R.$ If $R=\{Y\},$ we'll write also $\mathrm{ann}(Y):=\mathrm{ann}(R)$ abusing the notation slightly. It's clear that $\mathrm{ann}(\Bbb N\setminus\{1\})$ is the family of sets that contain both $0$ and $1.$ Therefore this family is invariant. TBC $\endgroup$ – Michał Masny Mar 18 '15 at 22:03
  • 1
    $\begingroup$ cont'd. Now $\{0,1\}$ can be shown to have strictly the least annihilator among the sets of this family. Therefore $\{0,1\}$ is fixed. Consequently, any set $[n]:=\{0,1,\ldots,n\}$ is fixed as a finite sum of $\{0,1\}$s. From this, we can see that the $\max$ of a finite set is automorphism invariant: for example the sets with max=5 are exactly the ones satisfying the equation $Y+[100]=[105].$ Now we can show that $\{0,n\}$ has strictly the smallest annihilator among the sets with max=n.$ I'll try to remember the rest, but I'm not sure I can... $\endgroup$ – Michał Masny Mar 18 '15 at 22:15

Cannot make a remark so write here: every automorphism of $P(\mathbb{N})$ may be extended to an endomorphism of $P(\mathbb{Z})$, which in fact may be even turns out to be an automorphism of $P(\mathbb{Z})$, and may be then you can reason in a much simpler way, since by thesis of Peter Gallagher you know what are the indecomposables in the group power-semigroups.

The only little warning i would like to make: you see, power-semigroups is a tricky topic to work on, since it leads eventually to lots of frustration (as the whole semigroup theory in fact). I used to study at bachelor with a really genius guy so much naturally fitting to Maths and he did his phd on power-semigroups, it just happenned so, but since the topic is quite weird, he would feel not to finish his phd and went into industry and Maths lost a very brilliant person. So be careful!

  • $\begingroup$ Dear Victor, could you please expand on the facts you've mentioned in the first paragraph? I would be very happy to learn about the indecomposables in group power semigroups. As for your warning, my situation is a bit specific. I'm not very talented, and I'm even having trouble getting my Master's. I've thought about power semigroups enough to have seen that some basic questions turn out to be very hard, and I simply try not to touch these. Hoever, since not that many people have thought about these semigroups, there are still not that difficult questions that haven't been asked. tbc... $\endgroup$ – Michał Masny Nov 14 '13 at 11:15
  • $\begingroup$ This situation suits me. I'm most likely never going to prove anything hard or even more than mildly interesting. But if I can contribute by just picking the low-hanging fruit, I'm OK with that. $\endgroup$ – Michał Masny Nov 14 '13 at 11:17
  • $\begingroup$ Michal, i think i should better write you on e-mail about work of Peter Gallagher. Please send me a message to gmail -- so that i don't forget to reply today in the evening, now i have to run away. $\endgroup$ – Victor Nov 14 '13 at 12:46

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.