2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ To define how $\mathbb{Z}_2$ acts on the space there is no choice: anything hit with $0$ must be the zero vector, and anything hit with $1$ must be itself. This automatically guarantees that dot points 1,3,4 work (provided you have also shown the axioms for the zero vector). There is something to check on point 2 when $x=y=1$: you need to check that $A + A = 0$ . $\endgroup$ Commented Apr 2, 2018 at 22:42
  • $\begingroup$ @Joppy Thank you. Any idea how to find the basis? $\endgroup$ Commented Apr 4, 2018 at 1:11
  • $\begingroup$ You know the dimension of the vector space: if your set has $n$ elements, the size of the power set is $2^n$, and this is the number of elements in the vector space. Since you are over a field with two elements, it follows that the dimension is $n$. Try writing out all the vectors in $\mathbb{Z}_2^3$, and see if there is an obvious way to associate to each a subset of $\{1,2,3\}$. $\endgroup$ Commented Apr 4, 2018 at 1:17
  • $\begingroup$ @Joppy I'm pretty confused. Could you explain a little more? I don't get why the dimension is n and I'm not fully sure how to associate a vector to a subset of {1,2,3} $\endgroup$ Commented Apr 4, 2018 at 1:46
  • $\begingroup$ In the case $n=2$, the vectors in $\mathbb{Z}_2^2$ are $(0, 0)$, $(1, 0)$, $(0, 1)$, and $(1, 1)$. Can you see any way of associating these to subsets of $\{1, 2\}$? $\endgroup$ Commented Apr 4, 2018 at 3:17

3 Answers 3

Reset to default
7
+50
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

  2. 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])

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

  1. Please fill in details....
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.