Problem on sets (own)
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$.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Problem on sets (own)
Trying to provide a proof:
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor
Re: Problem on sets (own)
Actually this has a pretty nice solution!
Hint:
Hint:
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Problem on sets (own)
@Nayel : Very nice solution. I think this is the most beautiful application of Sylow's theorem I have ever seen.
Re: Problem on sets (own)
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
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor
Re: Problem on sets (own)
@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$.
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$.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
Re: Problem on sets (own)
Sylow is a generalization of Cauchy
Re: Problem on sets (own)
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$
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$
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor
Re: Problem on sets (own)
$2^n$ order এর সাবগ্রুপ যে থাকবে এইটা নিশ্চিত হইলা কেমনে?
Re: Problem on sets (own)
Ohhh.......
That's Sylow
That's Sylow
"Je le vois, mais je ne le crois pas!" - Georg Ferdinand Ludwig Philipp Cantor