This question is inspired by this one. Please read my answer there to get better context.

Settings. Let $S$ be a (not necessarily finite) set, and $P$ the power set of $S$ (i.e., $P$ is the set of all subsets of $S$). A binary operator $*:P\times P\to P$ is said to be elementary if it can be given in terms of the standard set operations: the union operator $\cup$, the intersection operator $\cap$, the set difference operator $\setminus$, the symmetric difference operator $\triangle$, and the complement operator $(\_)^\complement$.

Some Examples. This operator $\star$ is considered an elementary binary operator: $$A \star B:= \big((M\setminus A)\cup (B\cap N)\big)^{\complement}\triangle \Big(A\cup B^\complement\Big)\text{ for all }A,B\subseteq S\,,$$ where $M$ and $N$ are fixed subsets of $S$. On the other hand, if $|S|=2$, then this operator $\bullet$ is not an elementary binary operator: $$A\bullet B:=\left\{ \begin{array}{ll} S&\text{if }A\subseteq B\,,\\ \emptyset&\text{otherwise}\,, \end{array}\right.$$ where $A,B\subseteq S$ (a proof can be done by imitating this answer).

Question. For which groups $G$ of order $2^{|S|}$ does there exist an elementary binary operator $*:P\times P\to P$ such that $(P,*)$ is a group isomorphic to $G$? If the case where $S$ is an infinite set is too troublesome, then an answer in the case where $S$ is a finite set is very welcome.

Let $n:=|S|$. Write $Z_k$ for the cyclic group of order $k$.

Trivial Answer. When $G\cong Z_2^n$, then the binary operator $\triangle$ does the work. My conjecture is that there are no other groups.

Known Result. When $|S|=2$ and $G\cong Z_4$, then there does not exist such an elementary binary operator.


1 Answer 1


Let us identify $P$ with $\{0,1\}^S$ in the obvious way. Then an elementary operation is just one which is given by applying some binary operation $\{0,1\}\times\{0,1\}\to\{0,1\}$ coordinatewise. Indeed, it is clear that every elementary operation must have this form (since all the basic Boolean operations have this form), and conversely it is a simple exercise in Boolean algebra to build every binary operation on $\{0,1\}$ out of the basic Boolean operations.

So, $P$ must just be a product of copies of some binary operation on $\{0,1\}$. As long as $S$ is nonempty, this means $P$ will be a group iff the corresponding operation on $\{0,1\}$ makes it a group (and the case where $S$ is empty is trivial). But there is only one group operation on $\{0,1\}$ up to isomorphism, so $P$ can only be isomorphic to $\mathbb{Z}_2^S$. (In fact, there are only two possible group operations at all: the usual symmetric difference operation and symmetric difference conjugated by swapping $0$ and $1$, which in terms of sets is just the complement of the symmetric difference.)

  • 2
    $\begingroup$ Great and very simple argument! I don't have any upvotes left for the day, so you have my gratitude for now. :D $\endgroup$ Commented Jul 12, 2020 at 22:26

You must log in to answer this question.

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