Теорема Хеллі
Теорема Хеллі — це базовий результат в дискретній геометрії щодо перетину опуклих множин. Вона була відкрита Едвардом Хеллі у 1913,[1] але не опублікована до 1923, на той момент вже з'явились альтернативні доведення Radon, (1921) і König, (1922). Теорема Хеллі дає початок сім'ї Хеллі.
Твердження
Нехай X1, ..., Xn буде скінченною колекцією опуклих підмножин Rd, з n > d. Якщо перетин кожних d + 1 з цих множин непорожній, тоді вся колекція має непорожній перетин; тобто
Для нескінченної колекції треба припустити компактність:
Нехай {Xα} буде колекцією компактних опуклих підмножин Rd, таких що кожна підколекція потужності не більше d + 1 має непорожній перетин. Тоді вся колекція має непорожній перетин.
Доведення
Ми доведемо скінченну версію використовуючи теорему Радона як в доведенні Radon, (1921). Нескінченна версія слідує з критерію властивості скінченного перетину компактності: колекція замкнутих підмножин компактного простору має непорожній перетин тоді і тільки тоді якщо кожна скінченна підколекція має непорожній перетин (щойно ми зафіксували одну множину, перетин усіх інших з нею це певний компактний простір).
Доведення за індукцією:
База: Нехай n = d + 2. Згідно з нашими припущеннями, для кожного j = 1, ..., n існує точка xj, яка є перетином всіх Xi можливо без Xj. Тут ми застосовуємо теорему Радона до множини A = {x1, ..., xn}, яка дає нам неперетинні підмножини A1, A2 множини A, такі що опукла оболонка для A1 перетинає опуклу оболонку для A2. Припустимо, що p — це точка в перетині цих опуклих оболонок. Ми стверджуємо, що
Насправді, розглянемо будь-яке j ∈ {1, ..., n}. ми доведемо, що p ∈ Xj. Зауважимо, що єдиний елемент з A, що може бути не в Xj — це xj. Якщо xj ∈ A1, тоді xj ∉ A2, і отже Xj ⊃ A2. З того, що Xj опукла, вона також містить опуклу оболонку A2 і тому p ∈ Xj. Так само, якщо xj ∉ A1, тоді Xj ⊃ A1, і завдяки таким самим міркуванням p ∈ Xj. Тому, що p лежить в кожному Xj, вона також має бути в їх перетині.
Вище, ми припустили, що всі точки x1, ..., xn різні. Якщо це не так, скажімо xi = xk для деякого i ≠ k, тоді xi належить кожній з множин Xj, і знов, ми заключаємо, що перетин не порожній. Це завершує доведення для n = d + 2.
Крок: Припустимо, що n > d + 2 і, що твердження дотримується для n−1. Довід наведений вище показує, що будь-яка підколекція з d + 2 множин має непорожній перетин. Тоді ми можемо розглянути колекцію де дві множини Xn−1 і Xn замінені на одну множину Xn−1 ∩ Xn. У цій новій колекції, кожна підколекція з d + 1 множин має непорожній перетин. Тому ми можемо застосувати індуктивну гіпотезу і показати, що нова колекція має непорожній перетин. З цього випливає, що початкова колекція має непорожній перетин, що завершує доведення.
Див. також
Примітки
- Danzer, L.; Grünbaum, B.; Klee, V. (1963), Helly's theorem and its relatives, Convexity, Proc. Symp. Pure Math., т. 7, American Mathematical Society, с. 101—180.
- König, D. (1922), Über konvexe Körper, Mathematische Zeitschrift, 14 (1): 208—220, doi:10.1007/BF01215899.
- Radon, J. (1921), Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Mathematische Annalen, 83 (1–2): 113—115, doi:10.1007/BF01464231.