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.

| cite | improve this answer | |
  • $\begingroup$ 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.) $\endgroup$ – Reed Oei Jul 9 at 22:07
  • 1
    $\begingroup$ @ReedOei I've deleted my comments and incorporated them into a new edit. $\endgroup$ – Noah Schweber Jul 9 at 23:01
  • $\begingroup$ @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? $\endgroup$ – Noah Schweber Jul 10 at 6:53
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Jul 10 at 14:13

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.