Symmetric set difference and odd number of sets containing x

alternative-proofcombinatoricsinduction

Let $A_1,A_2,\ldots,A_n$ be non-empty sets, $n\in\Bbb N$.
$$x\in A_1\triangle A_2\triangle\ldots\triangle A_n\;\iff x\text{ is in an odd number of sets}$$

In the script, this was proven by mathematical induction, but I have another question. Link to a related question

(1) base $$n=1, \;x\in A_1 \iff \; x\text{ is in an odd number of sets}$$

(3) the assumption: the statement $$x\in A_1\triangle A_2\triangle\ldots\triangle A_n\;\iff x\text{ is in an odd number of sets}$$ is true for some number $n\in \mathbb N.$

(3) step of the induction:

$\begin{aligned}x\in A_1\triangle A_2\triangle\ldots\triangle A_n\triangle A_{n+1}&\\\iff\left(x\in A_1\triangle A_2\triangle\ldots\triangle A_n\;\land x\notin A_{n+1}\right)&\\\lor\left(x\notin A_1\triangle A_2\triangle\ldots\triangle A_n\;\land x\in A_{n+1}\right)
\\\left(x\text{ is in an odd number of sets }A_1,A_2,\ldots,A_n\;\land x\notin A_{n+1}\right)&\\\lor\left(x\text{ is in an even number of sets }A_1,A_2,\ldots,A_n\land x\in A_{n+1}\right)\end{aligned}$

Now, when I have this in mind, how can I prove it without induction? Is there any other way?

Best Answer

Here's a proof that I feel is more intuitive. First of all, define the XOR ("exclusive or") operator $\oplus$ as follows: $$ p \oplus q\overset{\text{ def}}{\iff} (\lnot p \land q) \lor (p \land \lnot q). $$ Thus, $\triangle$ is defined by $$ x \in A_1 \triangle A_2 \iff (x\in A_1) \oplus (x\in A_2). $$ With that, the key is to see that $\oplus$ is really addition modulo $2$. In particular, here is a table for addition modulo 2 and a truth table for $\oplus$: $$ \begin{array}{c|cc} + & 0 & 1\\ \hline 0 & 0 & 1\\ 1 & 1 & 0 \end{array} \qquad \begin{array}{c|cc} \oplus & F & T\\ \hline F & F & T\\ T & T & F \end{array} $$ In other words, the identification $F \mapsto 0$, $T \mapsto 1$ is an isomorphism of abeliean groups. Thus, evaluating the statement $$ x \in A_1 \triangle A_2 \triangle \cdots \triangle A_n $$ amounts to evaluating $$ [[(x \in A_1) \oplus (x_1 \in A_2)] \oplus \cdots \oplus (x \in A_n)], $$ which is equivalent to evaluating the sum $$ [[x_1 + x_2] + \cdots + x_n] $$ modulo $2$ where $x_i$ is $0$ if $x \notin A_i$ and $1$ if $x \in A_i$. In other words, the result is true iff $x_1 + \cdots + x_n$ is equal to $1$ modulo $2$, which is to say that $x_1 + \cdots + x_n$ is odd.

Related Solutions

Prove through induction that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd

You can start from $0$, because one can define the multiple symmetric difference by $$ \mathop{\large\triangle}_{i=0}^0 A_i=\emptyset, \qquad \mathop{\large\triangle}_{i=0}^{n+1} A_i= \biggl(\mathop{\large\triangle}_{i=0}^{n} A_i\biggr)\mathbin{\triangle}A_{n+1} $$ Here, associativity of symmetric difference is important.

Now the base step of the induction is clear: for $n=0$, we have $|\{i\mid a\in A_i\}|=0$ and $a\notin\emptyset$.

Now suppose that the statement holds for $n$ sets and set, for simplicity, $$ B=\mathop{\large\triangle}_{i=0}^{n} A_i $$ We have that $a\in B\mathbin{\triangle}A$ if and only if $a\in B$ or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$. This is equivalent, by the induction hypothesis, to

$|\{i\mid a\in A_i\}|$ is odd or $a\in A_{n+1}$, but $a\notin B\cap A_{n+1}$.

Check the cases and you're done.

The lower bound on the symmetry difference of a number of sets

A nice formula for symmetric difference of $n$ sets, is "the set of all elements which appear an odd number of times in total". Since we assume that intersection of any 3 distinct sets is empty, that is equivalent to "the set of all elements which appear in only one of the sets". Note that our condition is that no element appears in more than 2 sets. By $f(n)$ denote minimum cardinality of $F_1 \triangle F_2 \triangle \ldots \triangle F_n$, where $F_k$ meet our conditions.

Problem 1.

We want to make as many elements as possible to appear in exactly 2 sets. We can directly check some initial minima:

| n    | 3 | 4 | 5 | 6 | 7 | 8 |
| f(n) | 9 | 8 | 5 | 0 | 1 | 0 |

I got those numbers by sketching graphs; sets are vertices, and they are connected by edge iff they share an element. Since they can share at most 1 element, this defines a simple graph. Any vertex can be of degree at most 5. Cardinality of symmetric difference is number of unpaired elements, that is for set $F_k$ (being vertex) it is $5 - \deg F_k$. Summing all unpaired elements gave results above.

Fix $n$ and set $k := n \mod 6$. If $k \in \{1, 2\}$ divide sets into $\lfloor n / 6\rfloor$ groups, where first group have $k + 6$ elements, and the rest $6$ elements. We can fill them with elements such that all sets in any group of 6 have empty symmetric difference, and the symmetric difference of the first group have at most $1$ element. So we can make cardinality as not greater than $1$.

If $k \in \{0, 3, 4, 5\}$ divide sets into $\lceil n / 6\rceil$ groups, where first group have $k$ elements (or $6$, when $k = 0$), and the rest $6$ elements. As before, we get that we can get as low as $9$.

So all in all we can always go $9$ or lower. Since for $n=3$ we have that $9$ is actual lower bound, it is the final result.

I think you could prove that $f(n) = n \mod 2$ for $n \geq 6$, but it is unnecessary for this problem.

Problem 2. (not completed)

There exists $N$ such that $f(N) = 0$. So using previous construction, exists a number $M$ such that $f(n) \leq M$, where $M = \max \{f(k)|k \leq 2N\}$. We have that $N \leq m + 1$, since we could restrict ourselves to the case where $|F_i \cap F _j| \leq 1$, and use graph approach as before ($K_{m + 1}$ would do the job).

Best Answer

Related Solutions

Prove through induction that $a \in A_1 \triangle A_2 \triangle \ldots \triangle A_n $ $\iff$ $|{\{i|a \in A_i}\}| $ is odd

The lower bound on the symmetry difference of a number of sets

Related Question