¿Por qué no se puede construir un diagrama de Venn para $4+$ conjuntos usando círculos?

Question

Esta página da algunos ejemplos de diagramas de Venn para $4$ conjuntos. Algunos ejemplos:

Pensando un poco en ello, es imposible dividir el plano en los $16$ segmentos requeridos para un diagrama de Venn completo de $4$ conjuntos usando solo círculos como podríamos hacer para $<4$ conjuntos. Sin embargo, es factible con elipses o rectángulos, por lo que no requerimos formas no convexas como utiliza Edwards.

Entonces, ¿qué propiedades de una forma determinan su idoneidad para diagramas de Venn de $n$ conjuntos? Específicamente, ¿por qué los círculos no son suficientes para el caso $n=4$?

Answer 1

La respuesta breve, de un artículo de Frank Ruskey, Carla D. Savage y Stan Wagon es la siguiente:

... es imposible dibujar un diagrama de Venn con círculos que representen todas las posibles intersecciones de cuatro (o más) conjuntos. Esta es una simple consecuencia del hecho de que los círculos pueden intersectarse finitamente en como máximo dos puntos y la relación de Euler de F E + V = 2 para el número de caras, aristas y vértices en un grafo plano.

El mismo artículo continúa en bastante detalle sobre el proceso de creación de diagramas de Venn para valores más altos de n, especialmente para diagramas simples con simetría rotacional.

Para un resumen simple, la mejor respuesta que encontré fue en WikiAnswers:

Dos círculos se intersectan en como máximo dos puntos, y cada intersección crea una nueva región. (Al recorrer en sentido horario el círculo, la curva desde cada intersección hasta la siguiente divide una región existente en dos.)

Dado que el cuarto círculo se intersecta con los tres primeros en como máximo 6 lugares, crea como máximo 6 nuevas regiones; eso son 14 en total, pero necesitas 2^4 = 16 regiones para representar todas las posibles relaciones entre cuatro conjuntos.

Pero puedes crear un diagrama de Venn para cuatro conjuntos con cuatro elipses, porque dos elipses pueden intersectarse en más de dos puntos.

Ambas fuentes indican que la propiedad crítica de una forma que la haría adecuada o inadecuada para diagramas de Venn de orden superior es el número de intersecciones posibles (y por lo tanto, subregiones) que se pueden hacer usando dos de la misma forma.

Para ilustrar más, considera algunas de las formas complejas utilizadas para n\=5, n\=7 y n\=11 (de Wolfram Mathworld):

La estructura de estas formas se elige de tal manera que puedan intersectarse entre sí de tantas maneras diferentes como sea necesario para producir el número de regiones únicas requeridas para un determinado n.

Ver también: ¿Los Diagramas de Venn están Limitados a Tres o Menos Conjuntos?

Answer 2

Para nuestra sorpresa, descubrimos que la prueba estándar de que un diagrama de Venn rotacionalmente simétrico de $n$ conjuntos es imposible cuando $n$ no es primo es incorrecta. Por lo tanto, Peter Webb y yo encontramos y publicamos una prueba correcta que aborda el error. Todos los detalles se discuten en el documento.

Stan Wagon y Peter Webb, Venn symmetry and prime numbers: A seductive proof revisited, American Mathematical Monthly, agosto de 2008, pp 645-648.

Descubrimos todo esto después del largo documento con Savage y otros citado en otra respuesta.

Answer 3

Teorema:

No se puede crear un diagrama de Venn n con círculos para $n \geq 4$.

Prueba: Supongamos que es posible. Entonces podemos crear un grafo planar $G$ a partir del diagrama de Venn colocando vértices en cada intersección, así:

$\small\text{(un ejemplo para un diagrama de Venn de 3 conjuntos)}$

Mostraremos que un grafo creado de esta manera a partir de un diagrama de Venn de 4 conjuntos no puede ser planar, lo cual es una contradicción.

Afirmación: Cada par de círculos se intersecta en dos puntos distintos.

Supongamos que no. Entonces hay un par de círculos cuyos interiores no se intersectan. Esto no puede ser, ya que requerimos que un grafo de diagrama de Venn tenga una cara para cada intersección de conjuntos.

Afirmación: Cada vértice tiene grado cuatro.

Supongamos que no. Entonces hay tres círculos $C_1, C_2, C_3$ que comparten una intersección. Se puede verificar fácilmente mediante análisis de casos que no todas las intersecciones $\{C_1\cap C_2, C_1\cap C_3, C_2 \cap C_3, C_1\cap C_2 \cap C_3, \}$ están presentes como caras en este subgrafo.

Estas dos afirmaciones implican que hay exactamente dos vértices únicos para cada par de círculos, por lo tanto $v = 2{n \choose 2}$. Además, por la fórmula de suma de aristas tenemos $e=\frac{d_1+\cdots+d_v}{2}=2v=4{n\choose 2}$ aristas. Dado que $D$ representa todas las intersecciones posibles de $n$ conjuntos, tenemos una cara para cada conjunto individual, cada par de conjuntos, cada triplete de conjuntos, y así sucesivamente. Contando la cara exterior del grafo como ${n\choose 0}$, una aplicación del teorema binomial produce $$f= {n\choose 0} + {n\choose 1} + {n\choose 2} + \cdots + {n\choose n} = 2^n \text{ caras.}$$

Ahora sustituimos cada uno de estos resultados en la fórmula de Euler: $$v-e+f = 2{n\choose2}-4{n\choose 2} + 2^n= 2^n- 2{n\choose 2}\leq2,$$ lo cual resulta en una clara contradicción para $n = 4$. Para llegar a uno para $n>4$, notemos que si existiera dicho diagrama de Venn para algún $n > 4$ podríamos eliminar círculos del diagrama para obtener uno para $n=4$.

---

Lo siguiente es un buen recurso para explorar la combinatoria de los diagramas de Venn más profundamente: http://www.combinatorics.org/files/Surveys/ds5/VennEJC.html

Answer 4

Llego bastante tarde a la fiesta, pero me gustaría agregar una respuesta muy simple pero mucho menos rigurosa para variar.

Cada región de un diagrama de Venn debe representar alguna combinación de verdadero o falso para cada categoría. Por ejemplo, el diagrama de Venn de dos círculos tiene 4 regiones: la intersección, el exterior, y las dos últimas partes de los círculos. La intersección contiene todo lo verdadero para ambas categorías, el exterior ninguna categoría, y las dos últimas solo una de las dos categorías. (Se podrían listar como VV, VF, FV, FF)

Para cubrir completamente todos los casos de combinaciones verdadero/falso, necesitamos $2^n$ secciones. Cada nueva categoría que añadimos duplica el número de regiones, ya que debe dividir cada región existente en 2 regiones más pequeñas. (Una para el caso verdadero de la nueva categoría, la otra para falso, así que la región VV ahora se divide en VVV y VVF)

Podemos ver cómo el tercer círculo intersecta todas las 4 regiones, pero no hay forma de dibujar un cuarto círculo que intersecte las 8 nuevas regiones, lo que hace imposible dibujar un diagrama de Venn de 4 círculos.