$P(X)$ with symmetric difference as addition as a vector space over $\mathbb{Z}_2$

Question

Let $X$ be an arbitrary set. Denote $P(X)$ the set of all subsets of $X$. Represent $P(X)$ as an abelian group with symmetric difference as addition. a) Prove that P(X) has the structure of a vector space over $\mathbb{Z}_2$

b) In the case when $X$ is finite, find a basis for the vector space.

I think I got most of part a. To show that its a vector space I need to show that $(P(X), +)$ is an abelian group, which is given and that $\forall x,y \in \mathbb{Z}_2 = {0,1}$ and $A,B \in P(X)$:

• $x(A+B) = xA + xB$
• $(x+y)A = xA + yA$
• $(xy)A = x(yA)$
• $1_{\mathbb{Z}_2}A = A$

I did the second and third one with simple tables that involve all cases for $x$ and $y$ since there were only four. I'm a little confused on the first one though I might have gotten it: If $A = \phi$ its super easy. If $A,B \neq \phi$, then $x (A+B) = x(A \Delta B) = x((A \cup B)$ \ $( A \cap B)) = (x(A \cup B))$ \ $(x(A \cap B)) = (xA \cup xB)$ \ $(xA \cap xB) = xA \Delta xB = xA + xB$ Is that right?

I'm not quite sure how to check $1_{\mathbb{Z}_2}A = A$ or how to find the basis for the vector space.

EDIT: Now that I've added a bounty I'm looking for a full answer, especially for part b. Thank you

Answer 1

1. The field $\mathbb{Z}_2$ has two elements, 0 and 1, and its addition operator behaves like "exclusive or" so that 1+1=0 and 1+0 = 1 and so on. Conceptually, this is a perfect fit for symmetric difference in which $A\triangle A = \varnothing$, $A\triangle \varnothing = A$ and so on.

2. To push this intuition further: if we list the elements of $X$ in some order: $x_1, \ldots x_n$, we can imagine every subset $A\subseteq X$ as a list of bits—position $i$ contains a 1 if $x_i$ is in the set, and 0 if $x_i$ is absent from the set. Performing the symmetric difference operator $\triangle$ on two sets $A$ and $B$ is the same as computing the exclusive-or of the two corresponding lists of bits. That's the intuition behind why $\langle P(X), \triangle\rangle$ has the structure of a vector space over $\mathbb{Z}_2$. It has one dimension for every element, and the value in that dimension can either be $1_{\mathbb{Z}_2}$ ("present") or $0_{\mathbb{Z}_2}$ ("absent"), which lets you describe all the possible subsets of $X$.

3. It's straightforward to prove that $P(X)$ is an additive abelian group over $\triangle$ because symmetric difference commutes, associates, and has a zero element $(\varnothing)$. Each set is its own additive inverse because $A\triangle A = \varnothing$.

4. To prove that $\langle P(X), \triangle\rangle$ is a vector space, we first need to define scalar multiplication. Fortunately, there's only one choice: $1_{\mathbb{Z}_2}$ must be the multiplicative unit, so $1_{\mathbb{Z}_2}\cdot A \equiv A$ by definition. And $0_{\mathbb{Z}_2}\cdot A$ must yield the zero vector, the zero element $\varnothing$.

5. Once we've defined scalar multiplication, it's pretty easy to prove properties:

   • $1_{\mathbb{Z}_2}\cdot A = A$ because we defined scalar multiplication that way.
   • $x(A\triangle B) = xA \triangle xB$. If $x=0$, we get $\varnothing \stackrel{?}{=} \varnothing\triangle \varnothing = \varnothing$, which checks out. Otherwise, $x=1$ and we get $1(A\triangle B) = A\triangle B \stackrel{?}{=} 1A \triangle 1B = A\triangle B$.
   • $(xy)A=x(yA)$. If $x=0$ or $y=0$, our definition of scalar multiplication collapses this into $\varnothing = \varnothing$, which is true. Otherwise, $x=y=1$ and the equality is trivial to show.
   • $(x+y)A=xA+yA$. Provable by cases as above.

6. Based on the intuition above, we can think of elements of $P(X)$ as lists of bits $[x_1, \ldots, x_n]$. Correspondingly, you can use the singleton sets as a basis. (If the set $X$ is finite, there will be finitely many basis elements. Represented as a list of bits, each basis element has a 1 in some position and zeroes in every other position—exactly like the standard basis in $\mathbb{R}^n$.)

   To see this, note that you can make any set by adding up $(\triangle)$ its elements: $$A = \sum_{a\in A} \{a\}$$
   And this basis of singleton sets is minimal— if you leave out any singleton, you won't be able to build certain sets.

   To formally prove that $\mathcal{B} = \{\{x\} \,:\, x\in X\}$ is a basis, we must show that it spans the space and that it's linearly independent. It spans the space because you can form any element as a linear combination of singletons: $A = \sum_{a\in A} \{a\}$. It's linearly independent because if $c_1\{x_1\} + \ldots + c_n \{x_n\} = \varnothing$ is empty, we know that all the coefficients must be zero. (Note that $\sum_i c_i \{a_i\} = \{ a_i : c_i = 1\}$, so if the sum is empty, then all of the coefficients are zero.)

Answer 2

Idea:

This answer tries to rewrite the abelian group law in this "complicated" case, $$(\ \mathcal P(X)\ , \ \Delta\ ), $$ in terms of the additive group, part of the ring structure $(R(X),+,\cdot)$ of all functions from the set $X$ to the field $\mathbb F_2$ with two elements. (The notation $\mathbb Z_2$ may be in some countries and centuries the same, but now it stays usually for the two-adic integers. I will switch to $\mathbb F_2$.)

Then everthing follows by "transport of structure".

1. The bijection $\mathcal P(X)\to R(X)$ is given by the rule: $$A\to 1_A\ ,$$ where the "abused" indicator function $1_A$ takes now values in the field with two elements. So $1_A(x)=1$ iff $x\in A$.

2. The inverse is the bijection $\mathcal P(X)\leftarrow R(X)$ given by the rule: $$f^{-1}(1)\leftarrow f\ ,$$ a function $f$ corresponds backwards to the subset of $X$ where it takes the value $1\in\mathbb F_2$.

3. On $R(X)$ we have a "componentwise", or pointwise addition, resp. multiplication, by using the operations of the field $\mathbb F_2$. Explicitly, for $f,g\in R(X)$ we define \begin{align} (f+g)(x) = f(x)+g(x)\ ,\\\\ (f\cdot g)(x) = f(x)\cdot g(x)\ . \end{align}

4. The operation $\Delta$ on $X$ corresponds to $+$ on $R(X)$: $$1_{A\Delta B}=1_A+1_B\ ,$$ since evaluated on an $x\in X$ we have:

$1_{A\Delta B}(x)=0$ iff $x\not\in A\Delta B$ iff ($x\in A$ iff $x\in B$) iff $1_A(x) = 1_B(x)$ iff $1_A(x)+1_B(x)=0$ iff $(1_A+1_B)(x)=0$.

5. Example. Let $X$ be the set with elements $0,1,2,3$ . Then a function $f:X\to \mathbb F_2$ is simply written as a $4$-tuple $(f(0), f(1), f(2), f(3))$. To minimize "white noise", we will sometimes write the "word" for the tuple, e.g. instead of $(0,1,0,0)$ we write $0100$.

6. Then the following data correspond as a map $R(X)\to \mathcal P(X)$, there is no neew to know sage (www.sagemath.org) to be able to read the code and the results:

   sage: X = [0,1,2,3]
   sage: F2 = GF(2)
   sage: F2
   Finite Field of size 2
   sage: for a in cartesian_product( [F2,F2,F2,F2] ):
   ....:     print a, ' -> ', { x for x in X if a[x]     }
       ....:     
   ....:     
   (0, 0, 0, 0)  ->  set([])
   (0, 0, 0, 1)  ->  set([3])
   (0, 0, 1, 0)  ->  set([2])
   (0, 0, 1, 1)  ->  set([2, 3])
   (0, 1, 0, 0)  ->  set([1])
   (0, 1, 0, 1)  ->  set([1, 3])
   (0, 1, 1, 0)  ->  set([1, 2])
   (0, 1, 1, 1)  ->  set([1, 2, 3])
   (1, 0, 0, 0)  ->  set([0])
   (1, 0, 0, 1)  ->  set([0, 3])
   (1, 0, 1, 0)  ->  set([0, 2])
   (1, 0, 1, 1)  ->  set([0, 2, 3])
   (1, 1, 0, 0)  ->  set([0, 1])
   (1, 1, 0, 1)  ->  set([0, 1, 3])
   (1, 1, 1, 0)  ->  set([0, 1, 2])
   (1, 1, 1, 1)  ->  set([0, 1, 2, 3])
   

7. Now it should be clear that there is a structure of "the set of tuples" as a vector space, that is usually written as $${\mathbb F_2}^{\times 4}\ .$$ Its "canonical basis" is (corresponding to) the set of indicator functions of singletons / atoms of $X$:

   (0, 0, 0, 1)  ->  set([3])
   (0, 0, 1, 0)  ->  set([2])
   (0, 1, 0, 0)  ->  set([1])
   (1, 0, 0, 0)  ->  set([0])
   

in the above list. As functions: $$ 1_{\{0\}}\ ,\ 1_{\{1\}}\ ,\ 1_{\{2\}}\ ,\ 1_{\{3\}}\ . $$ As sets after passing to $\mathcal P(X)$, of course $$ \{0\}\ ,\ \{1\}\ ,\ \{2\}\ ,\ \{3\}\ . $$

8. Please fill in details....

Answer 3

a) We know that the symmetric difference is both associative and commutative. Notice that $\emptyset$ acts as the identity and that each set is its own inverse. Define multiplication of and an element $x\in\Bbb{Z}_2$ on a subset $A\subset X$ to be $A$ if $a$ is $1$ and $\emptyset$ if $a$ is $0$. Lets check the properties you listed. Suppose $x,y \in \Bbb{Z}$ and $A,B \in P(X)$. The fourth one follows by definition. The first one is true since if $x = 1$, x(A+B)=A+B=xA+xB and if $x=0$, $x(A+B) = \emptyset = \emptyset+\emptyset = xA+xB$. The third property follows since if $x=y=0$ both sides are the empty set, if exactly one of $x$ and $y$ is $1$, then both sides are $A$, and if $x=y=1$, $(x+y)A=0A=\emptyset=A+A=xA+yA$. Fourth property follows since if $x=0$ or $y=0$, both sides are $\emptyset$ and otherwise both sides are $A$.

b) Your basis will be the singleton sets. If you take a linear combination of them, since they are disjoint, it will amount to taking the union of some of them. That is, if $X = \{x_1,\cdots,x_n\}$, then the basis is $\{\{x_1\},\cdots,\{x_n\}\}$. A linear combination $a_1\{x_1\}+\cdots+a_n\{x_n\}$ will be $\{x_i|a_i = 1\}$. So if a linear combination is the empty set, then all of the $a_i$ must be $0$ and we can get all subsets of $X$ in this way. So it is a basis.