15

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.

Michał Masny
  • 1,425
  • Dear Michal, you might want to add a definition of power semigroups: not everyone knows what they are (e.g. I don't know). – André Henriques Nov 12 '13 at 21:53
  • Dear @André, I've added a definition. – Michał Masny Nov 12 '13 at 21:56
  • Re: your "added later". I don't read any of the answers as claimimg to prove your theorem, only giving evidence in its favor. – Theo Johnson-Freyd Nov 13 '13 at 01:27
  • @Theo Now that I read Tomek's answer again, I think I might have misread it. Thank you. I think I'll add a bit more about what I did in the question. – Michał Masny Nov 13 '13 at 01:43
  • I suspect your proof is the right one. I can't see any better way to do it than to prove that any automorphism of the monoid of subsets containing 0 is trivial. – Benjamin Steinberg Nov 13 '13 at 03:38
  • @Benjamin Thank you very much for your comment. But perhaps that can be done in a conceptual way? Or at least a relatively simple one? Mine is far from being either. And my proof seems difficult to generalize to anything. I was kind of hoping there might be a way of doing it with some generality... – Michał Masny Nov 13 '13 at 07:05
  • I didn't think too hard but I guess one would show idempotents are fixed and irreducible elements. – Benjamin Steinberg Nov 13 '13 at 14:54
  • @Benjamin What do you mean by "irreducible" here? I would like to see a proof going this way because this was my first idea: to do something about the idempotents. But I ended up only using $\Bbb N\setminus{1}.$ – Michał Masny Nov 13 '13 at 16:28
  • By irreducible I mean that if A=B+C then B or C is 0. For example, the two element sets containing 0 are irreducible. – Benjamin Steinberg Nov 13 '13 at 16:47
  • @Benjamin Ah, then I don't think idempotents are irreducible. Idempotents are exactly the submonoids of $\Bbb N$, and every nontrivial submonoid has the form $B+C$ where $B,C\neq{0}.$ For example, $\Bbb N\setminus{1}=(\Bbb N\setminus{1,3})+{0,3}.$ – Michał Masny Nov 13 '13 at 18:06
  • 1
    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. – Benjamin Steinberg Nov 13 '13 at 19:32
  • @Benjamin I understand now. I think it might be hard to show that irreducible elements are fixed. I thought about them quite a bit, but I couldn't get anywhere other than showing that there are $\mathfrak c$ of them. It seems to be hard to distinguish an irreducible element from a reducible one in particular. This is only my impression though. – Michał Masny Nov 13 '13 at 19:51
  • 2
    Michal, perhaps your way is the best way of doing. I don't see any conceptual reason at the moment. – Benjamin Steinberg Nov 13 '13 at 20:11
  • @Benjamin OK, thank you very much for your comments; they have been helpful. – Michał Masny Nov 13 '13 at 20:17
  • Michal, would you mind writing out the proof? In particular how do you show that sets containing zero are fixed? – Ibrahim Tencer Mar 18 '15 at 08:46
  • 1
    @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. – Michał Masny Mar 18 '15 at 21:43
  • 1
    @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 – Michał Masny Mar 18 '15 at 22:03
  • 1
    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... – Michał Masny Mar 18 '15 at 22:15
  • 1
    Ah, cofinite sets are exactly the ones that generate finite ideals in $T$ so being cofinite is invariant. I'll keep thinking, maybe it's not hopeless. – Michał Masny Mar 18 '15 at 22:30
  • @Ibrahim OK, I think I've got it all. We can also find that the max of the complement of a confinite set is invariant: for a cofinite X, it is the greatest n such that X+{0,n}=X. Now, for any set X in $T$ and n>0, we have that it doesn't contain n iff the ideal generated by X in T has a cofinite set Y in it, such that the max of the complement of Y is n. This ends the proof: if, for any n, not containing n is invariant, then containing n is invariant as well and so all sets are fixed. – Michał Masny Mar 20 '15 at 20:50

1 Answers1

2

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!

Victor
  • 1,427
  • 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... – Michał Masny Nov 14 '13 at 11:15
  • 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. – Michał Masny Nov 14 '13 at 11:17
  • 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. – Victor Nov 14 '13 at 12:46