PROOF:Suppose that T and are both quasi-parity structures for a finite set S. Then for any even subset b of S, the number of odd subsets of b that lie in T is even, as is the number that lie in . Thus the same holds for their symmetric difference. And since the image under of the symmetric difference of T and is the sum of their images under , it suffices to check the result for some collection of parity structures whose images under form an -basis for RS. Hence by the previous theorem, it is enough to show that parity structures of the form , with t an even-degree monomial (in distinct indeterminants) are quasi-parity structures.
Such a monomial t equals
for some even subset c of S.
>From the definition of ,
consists of c together
with all subsets of S obtained by adding one new element to c.
Now take any even subset b of S. If c is not a subset of b,
then the number of odd subsets of b that lie in T is zero, so we
may assume that c is a subset of b. Then the odd subsets of b
that lie in T are exactly those subsets of b obtained by adding a
new element to c. But there are |b| - |c| such subsets, and since
both |b| and |c| are even, the number of such subsets is even.
Thus T is a quasi-parity structure.
This completes the proof of the theorem.
It is worth noting that the converse of Theorem 2 is false. Since the definition of a quasi-parity structure refers only to those elements of T that are odd subsets of S, any collection of even subsets of S will be a quasi-parity structure. On the other hand, the collection consisting of just the empty set will not be a parity structure, unless S is empty. More generally, since quasi-parity structures are closed under taking symmetric differences, the symmetric difference of any parity structure and any collection of even subsets of S will be a quasi-parity structure, and it can be shown that all quasi-parity structures are of this form. Moreover, for , there are exactly quasi-parity structures for S.