Problem on sets (own)

[nayel]

Let $S$ be a nonempty collection of finite sets such that if $A,B\in S$ then $(A\cup B)\backslash (A\cap B)\in S$ as well. Prove that if $S$ is finite, then $|S|=2^n$ for some integer $n$.

[Avik Roy]

Trying to provide a proof:

Lets define $(A,B)=(A\cup B)\backslash (A\cap B)$
Now, it is easy to see that $(A,A) = \phi$ and $(A,\phi)=A$. Hence, a 'one non empty element' $S$ is certainly consisting of $2$ members, namely $A,\phi$
For two nonempty elements $S=\{A,B,(A,B),\phi\}$, since $(A,(A,B))=B$ and $(B,(A,B))=A$
Now let us assume that we want to add another member $C$ in $S$ so that $C \ne A$ and $C \ne B$. It is easy to check that if we pair $C$ with any of the existing elements, say $X$, we are to find four interaction outcomes of them, $C$, $X$, $\phi$ and $(C,X)$ among which $X$ and $\phi$ already exist in $S$. So at most one new elements is added to $S$ due to $C$ interacting with each of the existing elements of $S$. Hence, for each new seed being added to $S$, we have $|S|$ just being doubled each time provided that for each distinct element $X$ already existing in $S$, $(X,S)$ is distinct.

Let, $(A,B)=(A,C)$. Assuming that $x \in B$ and $x \not\in A$. Hence,
$x \in (A,B)$
$\Rightarrow x \in (A,C)$
$\Rightarrow x \in (A\backslash C) or, x \in (C\backslash A)$
$\Rightarrow x \in C$
Now, assuming $x \in B$ and $x \in A$. Hence,
$x \not\in (A,B)$
$\Rightarrow x \not\in (A,C)$
$\Rightarrow x \not\in (A\backslash C) and, x \not\in (C\backslash A)$
$\Rightarrow x \in C$

This implies that for distinct elements already existing in $S$, the new seed is certainly going to produce equally many new elements, just doubling the cardinality of $S$. So for every finite $S$, $|S| = 2^n$ for some integer $n$

[nayel]

Actually this has a pretty nice solution!
Hint:

Define the symmetric difference of two sets, $A$ and $B$, by $A\Delta B=(A\cup B)\backslash (A\cap B)$. Then $S$ forms a group under the operation $\Delta$.

[tanvirab]

@Nayel : Very nice solution. I think this is the most beautiful application of Sylow's theorem I have ever seen.

[Avik Roy]

Nayel, post your full solution here please. I did it using groups also (after you mentioned it), but I didn't need to use Sylow

[nayel]

@Tanvir bhai: How did you do it using Sylow's theorem? I can prove it using Cauchy's: if $p$ is an odd prime dividing $|S|$, then there must exist an element in $S$ of order $p$. But every element in $S$ has order $2$, a contradiction.

Without using Cauchy: every element in $S$ has order $2$, hence $S$ is abelian. Consider a minimal generating set $\{g_1, g_2,\dots, g_n\}$ of $S$. Then the elements of $S$ are precisely $g_1^{a_1}g_2^{a_2}\cdots g_n^{a_n}$, where $a_i\in\{0,1\}$. Hence $|S|=2^n$.

[tanvirab]

Sylow is a generalization of Cauchy

[Avik Roy]

However, I didn't use Cauchy either (at least explicitly)
It is trivial to show that $|S| = k.2^n$ wherw $(k,2)=1$. Lets consider a subgroup of $S$, say $G$, with $|G|=2^n$. Then Lagrange assures that there are $k$ disjoint left cosets of $S$. Take two cosets, $G$ and $gG$ with $g \in S$. It can be shown that $H=G \cup gG$ is a subgroup of $S$. Hence, $G$ has a subgroup of order $2^{n+1}$ which does not divide the order of $S$. So, $k=1$

[tanvirab]

$2^n$ order এর সাবগ্রুপ যে থাকবে এইটা নিশ্চিত হইলা কেমনে?

[Avik Roy]

Ohhh.......
That's Sylow