Теорема Хеллі
Теорема Хеллі — це базовий результат в дискретній геометрії щодо перетину опуклих множин. Вона була відкрита Едвардом Хеллі у 1913,[1] але не опублікована до 1923, на той момент вже з'явились альтернативні доведення Шаблон:Harvtxt і Шаблон:Harvtxt. Теорема Хеллі дає початок сім'ї Хеллі.
Твердження
Нехай Шаблон:Math буде скінченною колекцією опуклих підмножин Шаблон:Math, з Шаблон:Math. Якщо перетин кожних Шаблон:Math з цих множин непорожній, тоді вся колекція має непорожній перетин; тобто
Для нескінченної колекції треба припустити компактність:
Нехай Шаблон:Math буде колекцією компактних опуклих підмножин Шаблон:Math, таких що кожна підколекція потужності не більше Шаблон:Math має непорожній перетин. Тоді вся колекція має непорожній перетин.
Доведення
Ми доведемо скінченну версію використовуючи теорему Радона як в доведенні Шаблон:Harvtxt. Нескінченна версія слідує з критерію властивості скінченного перетину компактності: колекція замкнутих підмножин компактного простору має непорожній перетин тоді і тільки тоді якщо кожна скінченна підколекція має непорожній перетин (щойно ми зафіксували одну множину, перетин усіх інших з нею це певний компактний простір).
Доведення за індукцією:
База: Нехай Шаблон:Math. Згідно з нашими припущеннями, для кожного Шаблон:Math існує точка Шаблон:Math, яка є перетином всіх Шаблон:Math можливо без Шаблон:Math. Тут ми застосовуємо теорему Радона до множини Шаблон:Math яка дає нам неперетинні підмножини Шаблон:Math множини Шаблон:Mvar, такі що опукла оболонка для Шаблон:Math перетинає опуклу оболонку для Шаблон:Math. Припустимо, що Шаблон:Mvar — це точка в перетині цих опуклих оболонок. Ми стверджуємо, що
Насправді, розглянемо будь-яке Шаблон:Math ми доведемо, що Шаблон:Math Зауважимо, що єдиний елемент з Шаблон:Mvar, що може бути не в Шаблон:Math — це Шаблон:Math. Якщо Шаблон:Math, тоді Шаблон:Math, і отже Шаблон:Math. З того, що Шаблон:Math опукла, вона також містить опуклу оболонку Шаблон:Math і тому Шаблон:Math. Так само, якщо Шаблон:Math, тоді Шаблон:Math, і завдяки таким самим міркуванням Шаблон:Math. Тому, що Шаблон:Mvar лежить в кожному Шаблон:Math, вона також має бути в їх перетині.
Вище, ми припустили, що всі точки Шаблон:Math різні. Якщо це не так, скажімо Шаблон:Math для деякого Шаблон:Math, тоді Шаблон:Math належить кожній з множин Шаблон:Math, і знов, ми заключаємо, що перетин не порожній. Це завершує доведення для Шаблон:Math.
Крок: Припустимо, що Шаблон:Math і, що твердження дотримується для Шаблон:Math. Довід наведений вище показує, що будь-яка підколекція з Шаблон:Math множин має непорожній перетин. Тоді ми можемо розглянути колекцію де дві множини Шаблон:Math і Шаблон:Math замінені на одну множину Шаблон:Math. У цій новій колекції, кожна підколекція з Шаблон:Math множин має непорожній перетин. Тому ми можемо застосувати індуктивну гіпотезу і показати, що нова колекція має непорожній перетин. З цього випливає, що початкова колекція має непорожній перетин, що завершує доведення.