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

• Variant

Prove that $$\mathcal A$$ together with the symmetric difference form a vector space above $$\mathbb Z_2$$.

• Solution

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.

• Variant

Depending on the size of $$\mathcal A$$, determine the dimension of this space. What values can $$| \mathcal A |$$ attain?

• Solution

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