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

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email