En matemáticas , un girasol o-system [1] es una colección de conjuntos cuya intersección por pares es constante. Esta intersección constante se llama núcleo del girasol.
La principal pregunta de investigación relacionada con los girasoles es: ¿en qué condiciones existe un girasol grande (un girasol con muchos conjuntos)? La-lema , lema de girasol y conjetura de girasol dan varias condiciones que implican la existencia de un gran girasol en una determinada colección de conjuntos.
Definicion formal
Suponer es un sistema de conjuntos , es decir, una colección de subconjuntos de un conjunto. La colecciónes un girasol (o-sistema ) si hay un subconjunto de tal que para cada distinto y en , tenemos . En otras palabras, es un girasol si la intersección por pares de cada conjunto en es constante. Tenga en cuenta que esta intersección,, puede estar vacío ; una colección de subconjuntos disjuntos también es un girasol.
Lema y conjetura del girasol
Erdős & Rado (1960 , p. 86) probaron el lema del girasol , afirmando que si y son enteros positivos, luego una colección de conjuntos de cardinalidad como máximo contiene un girasol con más de conjuntos.
La conjetura del girasol es una de varias variaciones de la conjetura de Erdős y Rado (1960 , p. 86) de que el factor de puede ser reemplazado por por alguna constante . Un artículo de 2020 de Alweiss, Lovett, Wu y Zhang da el mejor progreso hacia la conjetura, demostrando el resultado para( Alweiss et al. 2020 ). [2]
Analógico para colecciones infinitas de conjuntos
La -lema establece que toda colección incontable de conjuntos finitos contiene un incontable-sistema.
La -lema es una herramienta combinatoria de teoría de conjuntos que se utiliza en las demostraciones para imponer un límite superior al tamaño de una colección de elementos incompatibles por pares en un poset forzado . Por ejemplo, puede usarse como uno de los ingredientes en una prueba que demuestre que es consistente con la teoría de conjuntos de Zermelo-Fraenkel que la hipótesis del continuo no se sostiene. Fue introducido por Shanin ( 1946 ).
Si es un colección de tamaño de subconjuntos contables de, y si la hipótesis del continuo se mantiene, entonces hay una -tamaño -subsistema. Dejar enumerar . Para, dejar . Por el lema de Fodor , arregle estacionario en tal que es constantemente igual a en . Construirde cardinalidad tal que siempre que estan en luego . Usando la hipótesis del continuo, solo hay-muchos subconjuntos contables de , por lo que mediante un adelgazamiento adicional podemos estabilizar el núcleo.
Ver también
Referencias
- Alweiss, Ryan; Lovett, Shachar; Wu, Kewen; Zhang, Jiapeng (junio de 2020), "Límites mejorados para el lema del girasol", Actas del 52º Simposio Anual de ACM SIGACT sobre Teoría de la Computación , Association for Computing Machinery, págs. 624–630, arXiv : 1908.08483 , doi : 10.1145 / 3357713.3384234 , ISBN 978-1-4503-6979-4
- Deza, M .; Frankl, P. (1981), "Cada gran conjunto de vectores equidistantes (0, + 1, –1) forma un girasol", Combinatorica , 1 (3): 225-231, doi : 10.1007 / BF02579328 , ISSN 0209- 9683 , MR 0637827
- Erdős, Paul ; Rado, R. (1960), "Teoremas de intersección para sistemas de conjuntos", Journal of the London Mathematical Society , Segunda serie, 35 (1): 85–90, doi : 10.1112 / jlms / s1-35.1.85 , ISSN 0024 -6107 , MR 0111692
- Jech, Thomas (2003), Teoría de conjuntos , Springer
- Kunen, Kenneth (1980), Teoría de conjuntos: una introducción a las pruebas de independencia , Holanda del Norte, ISBN 978-0-444-85401-8
- Shanin, NA (1946), "Un teorema de la teoría general de conjuntos", CR (Doklady) Acad. Sci. URSS , nueva serie, 53 : 399–400
- Tao, Terence (2020), El lema del girasol a través de la entropía de Shannon , Novedades (blog personal)
Notas
- ^ El término original para este concepto era "-sistema ". Más recientemente, el término" girasol ", posiblemente introducido por Deza y Frankl (1981) , lo ha ido reemplazando gradualmente.
- ^ "Revista Quanta - Ciencia que ilumina" . Revista Quanta . Consultado el 10 de noviembre de 2019 .