Теорема Хеллі — це базовий результат в дискретній геометрії щодо перетину опуклих множин. Вона була відкрита у 1913, але не опублікована до 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.
- (1921), Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Mathematische Annalen, 83 (1–2): 113—115, doi:10.1007/BF01464231.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teorema Helli ce bazovij rezultat v diskretnij geometriyi shodo peretinu opuklih mnozhin Vona bula vidkrita u 1913 ale ne opublikovana do 1923 na toj moment vzhe z yavilis alternativni dovedennya Radon 1921 i Konig 1922 Teorema Helli daye pochatok Teorema Helli dlya Evklidovoyi ploshini yaksho sim ya opuklih mnozhin maye neporozhnij peretin dlya kozhnoyi trijki mnozhin todi vsya sim ya maye neporozhnij peretin TverdzhennyaNehaj X1 Xn bude skinchennoyu kolekciyeyu opuklih pidmnozhin Rd z n gt d Yaksho peretin kozhnih d 1 z cih mnozhin neporozhnij todi vsya kolekciya maye neporozhnij peretin tobto j 1 n X j displaystyle bigcap j 1 n X j neq varnothing Dlya neskinchennoyi kolekciyi treba pripustiti kompaktnist Nehaj Xa bude kolekciyeyu kompaktnih opuklih pidmnozhin Rd takih sho kozhna pidkolekciya potuzhnosti ne bilshe d 1 maye neporozhnij peretin Todi vsya kolekciya maye neporozhnij peretin DovedennyaMi dovedemo skinchennu versiyu vikoristovuyuchi teoremu Radona yak v dovedenni Radon 1921 Neskinchenna versiya sliduye z kriteriyu vlastivosti skinchennogo peretinu kompaktnosti kolekciya zamknutih pidmnozhin kompaktnogo prostoru maye neporozhnij peretin todi i tilki todi yaksho kozhna skinchenna pidkolekciya maye neporozhnij peretin shojno mi zafiksuvali odnu mnozhinu peretin usih inshih z neyu ce pevnij kompaktnij prostir Dovedennya za indukciyeyu Baza Nehaj n d 2 Zgidno z nashimi pripushennyami dlya kozhnogo j 1 n isnuye tochka xj yaka ye peretinom vsih Xi mozhlivo bez Xj Tut mi zastosovuyemo teoremu Radona do mnozhini A x1 xn yaka daye nam neperetinni pidmnozhini A1 A2 mnozhini A taki sho opukla obolonka dlya A1 peretinaye opuklu obolonku dlya A2 Pripustimo sho p ce tochka v peretini cih opuklih obolonok Mi stverdzhuyemo sho p j 1 n X j displaystyle p in bigcap j 1 n X j Naspravdi rozglyanemo bud yake j 1 n mi dovedemo sho p Xj Zauvazhimo sho yedinij element z A sho mozhe buti ne v Xj ce xj Yaksho xj A1 todi xj A2 i otzhe Xj A2 Z togo sho Xj opukla vona takozh mistit opuklu obolonku A2 i tomu p Xj Tak samo yaksho xj A1 todi Xj A1 i zavdyaki takim samim mirkuvannyam p Xj Tomu sho p lezhit v kozhnomu Xj vona takozh maye buti v yih peretini Vishe mi pripustili sho vsi tochki x1 xn rizni Yaksho ce ne tak skazhimo xi xk dlya deyakogo i k todi xi nalezhit kozhnij z mnozhin Xj i znov mi zaklyuchayemo sho peretin ne porozhnij Ce zavershuye dovedennya dlya n d 2 Krok Pripustimo sho n gt d 2 i sho tverdzhennya dotrimuyetsya dlya n 1 Dovid navedenij vishe pokazuye sho bud yaka pidkolekciya z d 2 mnozhin maye neporozhnij peretin Todi mi mozhemo rozglyanuti kolekciyu de dvi mnozhini Xn 1 i Xn zamineni na odnu mnozhinu Xn 1 Xn U cij novij kolekciyi kozhna pidkolekciya z d 1 mnozhin maye neporozhnij peretin Tomu mi mozhemo zastosuvati induktivnu gipotezu i pokazati sho nova kolekciya maye neporozhnij peretin Z cogo viplivaye sho pochatkova kolekciya maye neporozhnij peretin sho zavershuye dovedennya Div takozhNerv pokrittyaPrimitkiDanzer Grunbaum ta Klee 1963 Danzer L Grunbaum B Klee V 1963 Helly s theorem and its relatives Convexity Proc Symp Pure Math t 7 American Mathematical Society s 101 180 Konig D 1922 Uber konvexe Korper Mathematische Zeitschrift 14 1 208 220 doi 10 1007 BF01215899 1921 Mengen konvexer Korper die einen gemeinsamen Punkt enthalten Mathematische Annalen 83 1 2 113 115 doi 10 1007 BF01464231