$P(X)$ with symmetric difference as addition as a vector space over $\mathbb{Z}_2$ 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
 A: *

*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.

*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$.

*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$. 

*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$. 

*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.


*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.)
A: 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".


*

*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$.

*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$.

*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}

*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$.


*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$.

*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])


*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\}\ .
$$


*Please fill in details....

A: 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.
