Supporting materials:

Note: this article uses supporting theorems, such as “Common commutative law” and “About amount of subsets in the given set”. Since I’m yet unable to find their analogues on English-language resources, I’ll cite their statements in this section.

Theorem “The common commutative law”: suppose given non-empty set \(G\), \(+\) – associative and commutative binary algebraic operation, defined in G. Then for any elements \(a_i \in G\), \(i = \overline{1, n}\), \(n \in \mathbb{N}\) row \(\alpha_1+\alpha_2+\ldots+\alpha_n\) does not change its value because of transposition of summands.

Theorem “About amount of subsets in the given set”: suppose a given finite set \(G\). Then if \(\left| G \right| = n \in \mathbb{N}\) – cardinality of G, then there are \(2^n\) of subsets in set G.

Note: XOR, \(\oplus\) (eXclusive OR) – operation addition modulo 2.

Supporting definition: XOR-sum over the non-empty, finite sequence \(\{ \alpha_i \}_{i = 1}^{n}\), where \(\alpha_i \in \{ 0, 1 \}\) – bits, \(i = \overline{1, n}\), \(n \in \mathbb{N}\), is an operation:
\(\oplus { \left( \{ \alpha_i \}_{i = 1}^{n} \right) } = \) \(\alpha_1\) \(\oplus\) \(\alpha_2\) \(\oplus\) \(\ldots\) \(\oplus\) \(\alpha_n\).

Theorem “About amount of XOR-sums over the given sequence of bits”

Statement: Suppose a given sequence of bits \(\{ \alpha_i \}_{i = 1}^{n}\) (with length \(n\)), \(\alpha_i \in \{ 0, 1 \}\) \(i = \overline{1, n}\), \(n \in \mathbb{N}\). Then there exists \(2^{n}-1\) non-empty various sequences, composed of elements of the sequence \(\{ \alpha_i \}_{i = 1}^{n}\), for which are defined corresponding XOR-sums.

The proof is based on simple review of properties of the XOR operation. Due to operation XOR \(\oplus\) is associative and commutative, it satisfies the conditions of theorem “The common commutative law”. Additionally presents a property of operation \(\oplus\), named self-reversiblity: \(a \oplus a = 0\) \(\forall a \in \{0, 1\}\). Therefore, during the choice of sequence the value of XOR-sum is not affected by order of selected elements and elements, which were selected even number of times (due to self-reversiblity of operation). But then for the given sequence \(\{ \alpha_i \}_{i = 1}^{n}\) composed of its elements sequences-operands have representation \(\{ \alpha_i \}_{i \in A \ne \emptyset}^{A \subseteq \{1, 2, \ldots n\}}\). In other words, composition of sequence-operand from the elements of given sequence of bits is equivalent to selection of the subset from the given set (because composed sequences-operands, in fact, are sequences of elements, every one of which is unique (because of self-reversiblity of the XOR operation), and herewith transposition of the given elements of the sequence does not affect the result, due to validity of theorem “Common commutative law” for the XOR operation, and that means, that these sequences-operands are equivalent to sets relatively to the XOR operation). Theorem “About amount of subsets in the given set” says, that amount of such selections equals \(2^{n}\), but because of the fact, that this theorem includes empty set as a possible option, (and condition of the given theorem excludes such situation), subtract one (empty sequence) from the total amount of sequences. In this way, there exists exactly \(2^{n}-1\) non-empty various sequences, composed of elements of the sequence \(\{ \alpha_i \}_{i = 1}^{n}\), for which are defined corresponding XOR-sums. Theorem is proven.

Consequence: due to the proven theorem, XOR-sum over the subsequence can be redefined as XOR-sum over the set of indexes of corresponding bits of sequence.