Space with symmetric difference
Task number: 4200
Let \( X \) be a finite set and \( \mathcal A \subseteq 2^X \) be a set of some of its subsets closed to the symmetric difference. Thus, if \( Y \) and \( Z \) belong to \( \mathcal A \), then \( Y \Delta Z \) also belongs to \( \mathcal A \).
Prove that \( \mathcal A \) together with the symmetric difference form a vector space above \( \mathbb Z_2 \).
A more tedious but straightforward way is to verify all eight axioms of vector space.
You can save some work by realizing that \( (\mathcal A, \Delta) \) forms a group. The neutral element is the empty set \( \emptyset \), and each set is opposite to itself, i.e. \( -Y = Y \).
Then we can use the fact that any group can be perceived as a vector space above \( \mathbb Z_2 \), because the multiplication by 1 does not change the element, while the multiplication by 0 always gives the neutral element of the group.
Depending on the size of \( \mathcal A \), determine the dimension of this space. What values can \( | \mathcal A | \) attain?
The size of a finite vector space is the size of the corresponding field powered to the dimension, in our case a power of two. Hence \( \dim (\mathcal A) = \log_2 (| \mathcal A |) \).