# Can we extend the monoid $(\mathcal P(A),\cup,\emptyset)$ to a group?

Natural numbers are famously a way to build up "the rest" of the numbers: integers as pairs of natural numbers modulo the correct equivalence relation, and similarly for rational numbers, etc.

The powerset of some set $$A$$ has a similar structure to the natural numbers, in that $$(\mathbb{N}, +, 0)$$ is a monoid, and so is $$(\mathcal{P}(A), \cup, \emptyset)$$, but neither has a subtraction that is always nicely behaved. However, one could imagine extending $$\mathcal{P}(A)$$ in an analogous way to how we obtain the integers, by defining an equivalence relation

$$(X, Y) \sim (Z, W) \iff X \cup W = Z \cup Y$$

Essentially making $$(X, Y)$$ into $$X \setminus Y$$, but without losing information in the case that $$Y \subsetneq X$$, just as we can represent an integer $$a - b$$ as $$(a,b)$$ without losing information when $$b > a$$ (assuming we use saturating subtraction for natural numbers).

At any rate, my question is, does this structure have a name, and if so, does the study of it lead anywhere interesting?

Contra your claim, the relation $$\sim$$ is not an equivalence relation: consider $$\alpha=(\{1,2\},\{1,2\})$$, let $$\beta=(\{1,2\},\{1\})$$ and let $$\gamma=(\{1\},\{1,2\})$$. Then we have $$\alpha\sim \beta$$ and $$\alpha\sim\gamma$$ but $$\beta\not\sim\gamma$$.

The issue is that whenever $$Z\cup W\subseteq X=Y$$ we have $$(X,Y)\sim (Z,W)$$ for silly reasons: $$X\cup W=X$$, $$Z\cup Y=Y$$, and $$X=Y$$.

In fact, more generally we have $$(\mathbb{N},\mathbb{N})\sim(X,Y)$$ for every $$X,Y\subseteq\mathbb{N}$$. So if we try to fix things by looking at the transitive closure of $$\sim$$ instead, everything trivializes.

EDIT: We can fix this specific problem by restricting attention to the set $$Disj_2(\mathbb{N})$$ of disjoint pairs of sets of natural numbers. However, this causes two new issues.

First, there's no point in bringing an equivalence relation into the picture anymore: if $$A\cup Y=B\cup X$$ and $$A\cap B=X\cap Y=\emptyset$$ then $$A=X$$ and $$B=Y$$. For example, we have $$A\subseteq A\cup Y=B\cup X$$ so $$A\subseteq X$$ since $$A\cap B=\emptyset$$, and similarly $$X\subseteq A$$; and by symmetry, we also have $$B\subseteq Y$$ and $$Y\subseteq B$$.

More importantly, we now need to be careful about our arithmetic operations: "coordinatewise union" is no longer defined on $$Disj_2(\mathbb{N})$$ since it doesn't preserve disjointness! Instead, the best addition analogue seems to be $$(A,B)\oplus (X,Y)=((A\setminus Y)\cup (X\setminus B), (Y\setminus A)\cup(B\setminus X)).$$ This unfortunately isn't too well-behaved: while it is commutative and has identity and inverses, it is not associative. This is because it is idempotent: $$(A,B)\oplus (A,B)=(A,B)$$.

There is a natural way to think of the structure $$(Disj_2(\mathbb{N}), \oplus)$$, however. Intuitively, we start with the set $$M$$ of all multisets of natural numbers where multiplicities are allowed to be arbitrary integers; this is a group under "multiset union" $$\underline{\cup}$$, and really is just a messy way of describing the product group $$\prod_\mathbb{N}\mathbb{Z}$$. We think of $$(A,B)\in Disj_2(\mathbb{N})$$ as representing the multiset containing one of each $$a\in A$$, negative one of each $$b\in B$$, and zero of every other number. Then $$(Disj_2(\mathbb{N}), \oplus)$$ can be gotten from the group $$(M,\underline{\cup})$$ by "truncating" each multiset to allow only the multiplicities $$-1,0$$, and $$1$$, with $$\oplus$$ being the analogous "truncation" of $$\underline{\cup}$$.

More abstractly, given any group (or indeed magma) $$(G,*)$$ and any function $$\mathfrak{F}:G\rightarrow G$$, we can build a new structure $$(G_\mathfrak{F},*_\mathfrak{F})$$ defined by setting $$G_\mathfrak{F}=ran(\mathfrak{F}),\quad g*_\mathfrak{F}h=\mathfrak{F}(g*h).$$ Unfortunately, this isn't a very nice construction in general, as we've seen in the case above; indeed, I don't think it has a name at all.

• Ah. Thanks, I should've checked more than a couple cases... What if we only consider this relation on pairs of disjoint sets? I believe this makes it into an equivalence relation (I checked it with the proof assistant Isabelle this time...hopefully didn't make any mistakes there.) – Reed Oei Jul 9 at 22:07
• @ReedOei I've deleted my comments and incorporated them into a new edit. – Noah Schweber Jul 9 at 23:01
• @MishaLavrov No, I don't think so. We have $(A,B)\oplus (B,A)=(\emptyset,\emptyset)$ and $(X,Y)\oplus (\emptyset,\emptyset)=(\emptyset,\emptyset)\oplus (X,Y)=(X,Y)$ for all appropriate $A,B,X,Y$. So $(\emptyset,\emptyset)$ is the identity, "flipping" yields inverses, and we get nonassociativity since no idempotent operation with identity and inverses on a set with more than one element can be associative. Or am I having a stupid moment? – Noah Schweber Jul 10 at 6:53
• No, I'm having one! (In my defense, it was 2am.) I saw how idempotent operations could prove that we have no inverses, but I didn't notice that I used associativity to do it. – Misha Lavrov Jul 10 at 14:13