Si dos sistemas de elementos, todos tienen incluso intersección, entonces el producto de su cardinalidad es $\le 2^n$

Question

Estoy tratando de resolver el siguiente problema:

Deje $\mathcal{A}, \mathcal{B} \subset \mathcal{P}(n)$ ser dos sistemas que $|A \cap B|$ es, incluso, para cada $A \in \mathcal{A}, B \in \mathcal{B}$. Demostrar que $|\mathcal{A}||\mathcal{B}| \le 2^n$.

Mi idea para la solución es la construcción de una inyección de $f: \mathcal{A} \times \mathcal{B} \to \mathcal{P}(n)$, y creo que la función dada por $A \times B \mapsto A \cup B$ debería funcionar. Sin embargo, estoy seguro de cómo probar esto.

He estado mirando la diferencia simétrica de dos conjuntos en $\mathcal{A}$ a intentar ayudar con esto (porque me había dado una pista para el uso de este), pero no puedo hacer este trabajo.

¿Alguien tiene alguna pista?

Answer 1

Esto puede ser probado utilizando álgebra lineal en el campo de dos elementos, $GF(2).$ Conjuntos forman un espacio vectorial sobre $GF(2)$ donde la diferencia simétrica es la adición de vectores. Supongamos que hay $k$ linealmente independiente pone en $\mathcal A.$ Deje $\mathcal A'$ ser un complemento de espacio vectorial, por lo que tiene dimensión $n-k.$ Cada conjunto $B\in\mathcal B$ define lineal mapa de $\mathcal A'\to GF(2)$ $S\mapsto |S\cap B|$ mod $2.$ Si $B,B'\in\mathcal B$ satisfacer $|S\cap B|=|S\cap B'|$ mod $2$ todos los $S\in\mathcal A',$, a continuación, por la linealidad y el hecho de que el %de$|S\cap B|=|S\cap B'|$mod $2$ todos los $S\in\mathcal A$ sabemos que $|S\cap B|=|S\cap B'|$ mod $2$ todos los $S.$, En particular, $|\{i\}\cap B|=|\{i\}\cap B'|$ mod $2$ para todos los elementos de la $i,$, lo que implica $B=B'.$, por Lo que los pone en $\mathcal B$ mapa injectively para el espacio vectorial lineal de los mapas de $\mathcal A'\to GF(2),$ que tiene dimensión $n-k.$ $|\mathcal A|\cdot|\mathcal B|\leq 2^k2^{n-k}=2^n.$