Demostrando que el conjunto dado tiene como máximo $2^{n-1}$ elementos

Question

Sea $n$ un número natural y $X$ = {$1,2,...,n$}. Para los subconjuntos $A$ y $B$ de $X$ definimos $A\Delta B$ como el conjunto de todos los elementos de $X$ que pertenecen exactamente a uno de los conjuntos $A$ y $B$. Sea $F$ una colección de subconjuntos de $X$ tal que para cualquier par de elementos distintos $A$ y $B$ en $F$ el conjunto $AB$ tiene al menos dos elementos. Demuestra que $F$ tiene a lo sumo $2^{n-1}$ elementos. Encuentra todas esas colecciones $F$ con $2^{n1}$ elementos.

No tengo ni idea de cómo ni por dónde empezar. Por favor ayuda.

Answer 1

Expandiré uno de los comentarios de bof. Si $n>0$ fijemos algún $a\in X$ y emparejemos los subconjuntos de $X$ como $y,\,y\cup\{a\}$ con $a\notin y$. Ninguno de estos dos está en $F$ porque $y\Delta(y\cup\{a\})=\{a\}$, así que $|F|$ es a lo sumo la mitad del número de subconjuntos de $X$, es decir, $2^{n-1}$ como se deseaba. (Te dejo considerar el caso $n=0$ por separado.)

Answer 2

Tomemos $X=\{1,\ldots, n\}$ y sea $P_{n-1}$ la colección de subconjuntos de $X \setminus \{n\}$. Para cada $S \in P_{n-1}$, definimos $f(S) = S \cup \{n\}$. Ahora sea $P_n$ la colección de subconjuntos de $X$. Notemos que

1. Se define $f(S)$ para cada $S \in P_{n-1}$;

2. $f(S) \not \in P_{n-1}$ para cada $S \in P_{n-1}$;

3. Si $S$ y $S'$ son conjuntos distintos en $P_{n-1}$ entonces $f(S) \not = f(S')$;

4. Por lo tanto, $P_{n-1}$ y $\{f(S); S \in P_{n-1}\}$ son disjuntos y de igual cardinalidad, y además, $P_{n-1}$ y $\{f(S); S \in P_{n-1}\}$ particionan $P_n$.

Entonces escribimos $P_n = \{S_1,S_2,\ldots, S_{2^n}\}$ donde los $S_i$ son distintos y donde $f(S_i) = S_{i+1}$ para cada $i$ impar; esto es posible gracias a 1. y 4. juntos. Luego $F$ puede contener a lo sumo un $S_i$ y $S_{i+1}$ para cada $i$ impar, ya que la unión disjunta de $S$ y $f(S)$ es precisamente $\{n\}$ que tiene solo 1 < 2 elementos.

Answer 3

En cuanto a una colección $F$ con $2^{n-1}$ elementos, sea $F$ el conjunto de subconjuntos de $X$ de cardinalidad impar. [Asegúrate de entender por qué funciona]

El conjunto de subconjuntos de $X$ de cardinalidad par también funcionaría. [Asegúrate de entender por qué funciona] Así, el conjunto de subconjuntos de cardinalidad par tiene, según las respuestas anteriores, solo $2^{n-1}$ elementos, lo que implica que el conjunto $F$ de subconjuntos de $X$ de cardinalidad impar tiene $2^{n-1}$ elementos. Y viceversa.