Теорема Жордана о кривой

Замкнутая кривая делит плоскость на две области.

Иллюстрация теоремы о жордановой кривой. Кривая Жордана (нарисованная черным цветом) делит плоскость на «внутреннюю» область (голубой) и «внешнюю» область (розовый).

В топологии теорема жордановой кривой утверждает, что каждая жорданова кривая (плоская простая замкнутая кривая) делит плоскость на « внутреннюю » область , ограниченную кривой, и « внешнюю » область, содержащую все близлежащие и удаленные внешние точки. Каждый непрерывный путь , соединяющий точку одного региона с точкой другого, где-то пересекается с кривой. Хотя теорема кажется интуитивно очевидной, требуется некоторая изобретательность, чтобы доказать ее элементарными средствами. «Хотя JCT — одна из самых известных топологических теорем, многие, даже среди профессиональных математиков, никогда не читали ее доказательства». (Тверберг (1980, Введение)). Более прозрачные доказательства опираются на математический аппарат алгебраической топологии и приводят к обобщениям на многомерные пространства.

Теорема Жордана о кривой названа в честь математика Камиллы Джордана (1838–1922), который опубликовал свое первое заявленное доказательство в 1887 году. ^{[1] [2]} На протяжении десятилетий математики обычно считали, что это доказательство ошибочно и что первое строгое доказательство было ошибочным. осуществил Освальд Веблен . Однако это мнение было опровергнуто Томасом К. Хейлзом и другими. ^[3]

Определения и формулировка теоремы Жордана

Кривая Жордана или простая замкнутая кривая в плоскости R2 — это образ C инъективного непрерывного отображения окружности в плоскость ^, φ : S1 ^→ R2 ^. Жордановая дуга на плоскости — это образ инъективного непрерывного отображения замкнутого и ограниченного интервала [ a , b ] на плоскость. Это плоская кривая , которая не обязательно является гладкой или алгебраической .

Альтернативно, жордановая кривая — это образ непрерывного отображения φ : [0,1] → R2 такого, что ^φ ( 0) = φ (1) и ограничение φ на [0,1) инъективно. Первые два условия говорят, что C является непрерывной петлей, тогда как последнее условие предполагает, что C не имеет точек самопересечения.

С помощью этих определений теорему Жордана о кривой можно сформулировать следующим образом:

Теорема  .  Пусть C — жорданова кривая в плоскости R ² . Тогда его дополнение R2  \  C состоит ровно из двух ^{компонент} связности . Один из этих компонентов ограничен ( внутренний ), а другой неограничен ( внешний ), а кривая C является границей каждого компонента.

Напротив, дополнение к жордановой дуге на плоскости связно.

Доказательство и обобщения

Теорема Жордана о кривой была независимо обобщена на более высокие измерения Х. Лебегом и Л. Э. Дж. Брауэром в 1911 году, что привело к теореме разделения Джордана-Брауэра .

Теорема  .  Пусть X — n -мерная топологическая сфера в ( n +1)-мерном ^{евклидовом} пространстве Rn ⁺¹ ( n > 0), т.е. образ инъективного непрерывного отображения n ^- сферы Sn в Rn ^{. +1} . Тогда дополнение Y к X в Rn ^{+ 1} состоит ровно из двух компонент связности. Одна из этих компонент ограничена (внутренняя), а другая неограничена (внешняя). Множество X является их общей границей.

В доказательстве используется теория гомологии . Впервые установлено, что, в более общем плане, если X гомеоморфно k -сфере, то приведенные целочисленные группы гомологии Y = R ^{n +1} \ X имеют следующий вид:

$${\displaystyle {\tilde {H}}_{q}(Y)={\begin{cases}\mathbb {Z} ,&q=n-k{\text{ or }}q=n,\\\{0\},&{\text{otherwise}}.\end{cases}}}$$

Это доказывается индукцией по k с помощью последовательности Майера–Виеториса . Когда n = k , нулевая приведенная гомология Y имеет ранг 1, что означает, что Y имеет 2 связных компонента (которые, кроме того, связаны путями ), и с небольшой дополнительной работой можно показать, что их общая граница — это X. Дальнейшее обобщение было найдено Дж. У. Александером , который установил двойственность Александера между приведенными гомологиями компактного подмножества X в R ^{n +1} и приведенными когомологиями его дополнения. Если X — n -мерное компактное связное подмногообразие Rn ^{+ 1} (или Sn ^{+ 1} ) без края, его дополнение имеет 2 компонента связности.

Существует усиление теоремы о жордановой кривой, называемое теоремой Жордана-Шенфлиса , которая утверждает, что внутренняя и внешняя плоские области, определяемые жордановой кривой в R ² , гомеоморфны внутренней и внешней части единичного круга . В частности, для любой точки P во внутренней области и точки A на жордановой кривой существует жордановая дуга, соединяющая P с A и, за исключением конца A , полностью лежащая во внутренней области. Альтернативная и эквивалентная формулировка теоремы Жордана–Шенфлиса утверждает, что любая жорданова кривая ^{φ :} S1 → R2 , где S1 рассматривается как единичная окружность на плоскости, может быть продолжена до ^{гомеоморфизма} ψ : R2 ^→ R2 ^. самолета. В отличие от обобщения Лебега и Брауэра теоремы о жордановой кривой, это утверждение становится ложным в более высоких измерениях: в то время как внешняя часть единичного шара в R ³ просто связна , поскольку она втягивается в единичную сферу, рогатая сфера Александера является подмножеством R ³ гомеоморфна сфере , но настолько скручена в пространстве, что неограниченная компонента ее дополнения в R ³ не односвязна и, следовательно, не гомеоморфна внешности единичного шара.

Дискретная версия

Теорема Жордана о кривой может быть доказана на основе теоремы Брауэра о неподвижной точке (в двух измерениях) ^[4] , а теорема Брауэра о неподвижной точке может быть доказана на основе теоремы Hex: «в каждой игре Hex есть хотя бы один победитель», из которой мы получаем логическое следствие: из теоремы Hex следует теорема Брауэра о неподвижной точке, из которой следует теорема Жордана о кривой. ^[5]

Ясно, что теорема о кривой Жордана подразумевает «сильную теорему Hex»: «каждая игра в Hex заканчивается ровно одним победителем, без возможности проигрыша обеих сторон или победы обеих сторон», таким образом, теорема о кривой Жордана эквивалентна сильному Hex. теорема, которая является чисто дискретной теоремой.

Теорема Брауэра о неподвижной точке, будучи зажатой между двумя эквивалентными теоремами, также эквивалентна обеим. ^[6]

В обратной математике и компьютерно-формализованной математике теорема о кривой Жордана обычно доказывается путем сначала преобразования ее в эквивалентную дискретную версию, аналогичную сильной теореме Hex, а затем доказательства дискретной версии. ^[7]

Приложение для обработки изображений

При обработке изображений двоичное изображение представляет собой дискретную квадратную сетку из 0 и 1 или, что то же самое, компактное подмножество . Топологические инварианты на , такие как количество компонентов, могут быть не вполне определены, если у него нет надлежащим образом определенной структуры графа . ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle \mathbb {Z} ^{2}}$ ${\displaystyle \mathbb {Z} ^{2}}$

На : есть две очевидные графовые структуры : ${\displaystyle \mathbb {Z} ^{2}}$

Квадратные сетки с 8 соседями и 4 соседями.

• «квадратная сетка с 4 соседями», где каждая вершина соединена с . ${\displaystyle (x,y)}$ ${\displaystyle (x+1,y),(x-1,y),(x,y+1),(x,y-1)}$
• «квадратная сетка с 8 соседями», где каждая вершина соединена с iff и . ${\displaystyle (x,y)}$ ${\displaystyle (x',y')}$ ${\displaystyle |x-x'|\leq 1,|y-y'|\leq 1}$ ${\displaystyle (x,y)\neq (x',y')}$

Обе структуры графов не удовлетворяют сильной теореме Hex. Квадратная сетка с 4 соседями допускает ситуацию без победителя, а квадратная сетка с 8 соседями допускает ситуацию с двумя победителями. Следовательно, свойства связности в , такие как теорема Жордана о кривой, не распространяются ни на одну из структур графа. ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle \mathbb {Z} ^{2}}$

Если структура «квадратной сетки с 6 соседями» наложена на , то это гексагональная сетка и, таким образом, удовлетворяет сильной теореме Hex, позволяя обобщить теорему о кривой Жордана. По этой причине при вычислении связанных компонентов в двоичном изображении обычно используется квадратная сетка с 6 соседями. ^[8] ${\displaystyle \mathbb {Z} ^{2}}$

Теорема Штайнхауза о шахматной доске

Теорема Штайнхауза о шахматной доске в некотором смысле показывает, что сетка с 4 соседями и сетка с 8 соседями «вместе» подразумевают теорему Жордана о кривой, а сетка с 6 соседями представляет собой точную интерполяцию между ними. ^{[9] [10]}

Теорема гласит: предположим, что вы разместили бомбы на некоторых клетках шахматной доски так, что король не может перейти с нижней стороны на верхнюю, не наступив на бомбу, тогда ладья может переместиться с левой стороны на правую, наступив на нее. только на бомбах. ${\displaystyle n\times n}$

История и дальнейшие доказательства

Утверждение теоремы о жордановой кривой на первый взгляд может показаться очевидным, но доказать ее довольно сложно. Бернар Больцано был первым, кто сформулировал точную гипотезу, отметив, что это не самоочевидное утверждение, а требующее доказательства. ^[11] Этот результат легко установить для многоугольников , но проблема заключалась в том, чтобы обобщить его на все виды кривых с плохим поведением, в том числе нигде не дифференцируемые кривые, такие как снежинка Коха и другие фрактальные кривые , или даже кривая Жордана положительная зона , построенная Осгудом (1903 г.).

Первое доказательство этой теоремы было дано Камиллом Жорданом в его лекциях по реальному анализу и опубликовано в его книге « Кур анализа политехнической школы» . ^[1] Существуют некоторые разногласия по поводу того, было ли доказательство Джордана полным: большинство комментаторов утверждали, что первое полное доказательство было дано позже Освальдом Вебленом , который сказал следующее о доказательстве Джордана:

Однако его доказательство неудовлетворительно для многих математиков. Он предполагает теорему без доказательства в важном частном случае простого многоугольника, и в рассуждениях с этого момента следует признать, что, по крайней мере, не даны все детали. ^[12]

Однако Томас К. Хейлз писал:

Почти все современные цитаты, которые я нашел, подтверждают, что первое правильное доказательство принадлежит Веблену... Ввиду резкой критики доказательства Джордана я был удивлен, когда сел читать его доказательство и не нашел в нем ничего предосудительного. С тех пор я связался с рядом авторов, критиковавших Джордана, и в каждом случае автор признавал, что не знает об ошибке в доказательстве Джордана. ^[13]

Хейлз также отметил, что частный случай простых многоугольников не только является простым упражнением, но и вообще не использовался Джорданом, и процитировал слова Майкла Рикена:

Доказательство Джордана по существу верно... Доказательство Джордана не дает удовлетворительного представления деталей. Но идея верна, и при некоторой доработке доказательство будет безупречным. ^[14]

Ранее доказательство Джордана и еще одно раннее доказательство Шарля Жана де ла Валле Пуссена уже были критически проанализированы и завершены Шенфлисом (1924). ^[15]

Из-за важности теоремы о жордановой кривой в маломерной топологии и комплексном анализе она привлекла большое внимание выдающихся математиков первой половины 20 века. Различные доказательства теоремы и ее обобщения были построены Дж. В. Александром , Луи Антуаном , Людвигом Бибербахом , Луиценом Брауэром , Арно Данжуа , Фридрихом Хартогсом , Белой Керекьярто , Альфредом Прингсхаймом и Артуром Морицем Шенфлисом .

Продолжаются новые элементарные доказательства теоремы о жордановой кривой, а также упрощения предыдущих доказательств.

• Элементарные доказательства были представлены Филипповым (1950) и Твербергом (1980).
• Доказательство с использованием нестандартного анализа Наренса (1971).
• Доказательство с использованием конструктивной математики Гордона О. Берга, В. Джулиана и Р. Майнса и др. (1975).
• Доказательство с использованием теоремы Брауэра о неподвижной точке Маэхары (1984).
• Доказательство, использующее непланарность полного двудольного графа K _3,3, было дано Томассеном (1992).

Корень этой трудности объясняется Твербергом (1980) следующим образом. Сравнительно несложно доказать, что теорема о жордановой кривой справедлива для любого жорданового многоугольника (лемма 1) и что каждая жорданова кривая может быть сколь угодно хорошо аппроксимирована жордановым многоугольником (лемма 2). Жордановый многоугольник — это цепь многоугольников , граница ограниченного связного открытого множества , назовем его открытым многоугольником, а его замыкание — замкнутым многоугольником. Рассмотрим диаметр наибольшего диска, содержащегося в замкнутом многоугольнике. Судя по всему, положительно. Используя последовательность жордановых многоугольников (которые сходятся к заданной жордановой кривой), мы имеем последовательность, предположительно сходящую к положительному числу - диаметру наибольшего диска, содержащегося в замкнутой области, ограниченной жордановой кривой. Однако нам нужно доказать , что последовательность не сходится к нулю, используя только данную жорданову кривую, а не область, предположительно ограниченную этой кривой. В этом суть леммы 3 Тверберга. Грубо говоря, замкнутые многоугольники не должны везде уменьшаться до нуля. Более того, они не должны где-то утончаться до нуля, в чем и состоит смысл леммы 4 Тверберга. ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \delta _{1},\delta _{2},\dots }$ ${\displaystyle \delta }$ ${\displaystyle \delta _{1},\delta _{2},\dots }$

Первое формальное доказательство теоремы о кривой Жордана было создано Хейлсом (2007a) в системе HOL Light в январе 2005 года и содержало около 60 000 строк. Еще одно строгое формальное доказательство, состоящее из 6500 строк, было создано в 2005 году международной командой математиков с использованием системы Mizar . И доказательство Mizar, и доказательство HOL Light основаны на библиотеках ранее доказанных теорем, поэтому эти два размера несопоставимы. Нобуюки Сакамото и Кейта Ёкояма (2007) показали, что в обратной математике теорема Жордана о кривой эквивалентна слабой лемме Кенига над системой . ${\displaystyle {\mathsf {RCA}}_{0}}$

Приложение

Если начальная точка ( pa ₎ луча ( красного цвета) лежит вне простого многоугольника (области A ), количество пересечений луча и многоугольника четное . Если начальная точка ( p _b ) луча лежит внутри многоугольника (области B ), количество пересечений нечетное.

В вычислительной геометрии теорема Жордана о кривой может использоваться для проверки того, находится ли точка внутри или снаружи простого многоугольника . ^{[16] [17] [18]}

Из заданной точки проследить луч , не проходящий ни через одну вершину многоугольника (удобны все лучи, кроме конечного числа). Затем вычислите количество n пересечений луча с ребром многоугольника. Доказательство теоремы о жордановой кривой подразумевает , что точка находится внутри многоугольника тогда и только тогда, когда n нечетно .

Вычислительные аспекты

Адлер, Даскалакис и Демейн ^[19] доказывают, что вычислительная версия теоремы Джордана является PPAD-полной . Как следствие, они показывают, что из теоремы Джордана следует теорема Брауэра о неподвижной точке . Это дополняет более ранний результат Маехары о том, что из теоремы Брауэра о неподвижной точке следует теорема Джордана. ^[20]

Смотрите также

• Теорема Данжуа–Рисса , описание определенных наборов точек на плоскости, которые могут быть подмножествами жордановых кривых.
• Озера Вада
• Квазифуксова группа — математическая группа, сохраняющая жордановую кривую.

Примечания

1. Джордан (1887).
2. Клайн, младший (1942). «Что такое теорема Жордана о кривой?». Американский математический ежемесячник . 49 : 281–286. дои : 10.2307/2303093. МР  0006516.
3. Хейлз, Томас С. (2007). «Доказательство Джордана теоремы о кривой Жордана» (PDF) . От понимания к доказательству: Фестиваль в честь Анджея Трибулца. Исследования по логике, грамматике и риторике . 10 (23). Белостокский университет.
4. Маэхара (1984), с. 641.
5. Гейл, Дэвид (декабрь 1979 г.). «Игра в шестнадцатеричные числа и теорема Брауэра о фиксированной точке». Американский математический ежемесячник . 86 (10): 818–827. дои : 10.2307/2320146. ISSN  0002-9890. JSTOR  2320146.
6. Нгуен, Фуонг; Кук, Стивен А. (2007). «Сложность доказательства теоремы о дискретной жордановой кривой». 22-й ежегодный симпозиум IEEE по логике в информатике (LICS 2007) . IEEE. стр. 245–256. arXiv : 1002.2954 . дои : 10.1109/lics.2007.48. ISBN 978-0-7695-2908-0.
7. Хейлз, Томас К. (декабрь 2007 г.). «Теорема Жордана о кривой, формально и неформально». Американский математический ежемесячник . 114 (10): 882–894. дои : 10.1080/00029890.2007.11920481. ISSN  0002-9890. S2CID  887392.
8. Наяр, Шри (1 марта 2021 г.). «Основные принципы компьютерного зрения: сегментация двоичных изображений | Двоичные изображения». YouTube .
9. Шлапал, Дж (апрель 2004 г.). «Цифровой аналог теоремы Жордана о кривой». Дискретная прикладная математика . 139 (1–3): 231–251. дои : 10.1016/j.dam.2002.11.003 . ISSN  0166-218X.
10. Суровка, Войцех (1993). «Дискретная форма теоремы Жордана о кривой». Annales Mathematicae Silesianae (7): 57–61. МР  1271184.
11. Джонсон, Дейл М. (1977). «Прелюдия к теории размерностей: геометрические исследования Бернара Больцано». Архив истории точных наук . 17 (3): 262–295. дои : 10.1007/BF00499625. МР  0446838.См. стр. 285.
12. Освальд Веблен  (1905)
13. Хейлз (2007b)
14. Хейлз (2007b)
15. А. Шенфлис (1924). "Bemerkungen zu den Beweisen von C. Jordan und ChJ de la Vallée Poussin". Яресбер. немецкий. Math.-Verein . 33 : 157–160.
16. Ричард Курант (1978)
17. "В. Топология". 1. Теорема Жордана о кривой (PDF) . Эдинбург: Эдинбургский университет. 1978. с. 267.
18. «PNPOLY - Включение точек в тест полигонов - WR Франклин (WRF)» . wrf.ecse.rpi.edu . Проверено 18 июля 2021 г.
19. Адлер, Авив; Даскалакис, Константинос; Демейн, Эрик Д. (2016). Хацигианнакис, Иоаннис; Митценмахер, Майкл; Рабани, Юваль; Санджорджи, Давиде (ред.). «Сложность Hex и теорема о жордановой кривой». 43-й международный коллоквиум по автоматам, языкам и программированию (ICALP 2016) . Международные труды Лейбница по информатике (LIPIcs). 55 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 24:1–24:14. doi : 10.4230/LIPIcs.ICALP.2016.24. ISBN 978-3-95977-013-2.
20. Маэхара (1984).

Рекомендации

• Берг, Гордон О.; Джулиан, В.; Минс, Р.; Ричман, Фред (1975), «Теорема о конструктивной жордановой кривой», Rocky Mountain Journal of Mathematics , 5 (2): 225–236, doi : 10.1216/RMJ-1975-5-2-225 , ISSN  0035-7596, MR  0410701
• Курант, Ричард (1978). «В. Топология». Написано в Оксфорде. Что такое математика? : элементарный подход к идеям и методам . Герберт Роббинс ([4-е изд.] изд.). Соединенное Королевство: Издательство Оксфордского университета. п. 267. ИСБН 978-0-19-502517-0. ОСЛК  6450129.
• Филиппов А. Ф. (1950), "Элементарное доказательство теоремы Жордана" (PDF) , Успехи матем. Наук , 5 (5): 173–176.
• Хейлз, Томас К. (2007a), «Теорема о кривой Джордана, формально и неформально», The American Mathematical Monthly , 114 (10): 882–894, doi : 10.1080/00029890.2007.11920481, ISSN  0002-9890, MR  2363054, S2CID  887392
• Хейлз, Томас (2007b), «Доказательство Джордана теоремы о жордановой кривой» (PDF) , Исследования по логике, грамматике и риторике , 10 (23)
• Джордан, Камилла (1887), Курс анализа (PDF) , стр. 587–594.
• Маэхара, Рюдзи (1984), «Теорема о жордановой кривой на основе теоремы Брауэра о фиксированной точке», The American Mathematical Monthly , 91 (10): 641–643, doi : 10.2307/2323369, ISSN  0002-9890, JSTOR  2323369, MR  0769530
• Наренс, Луи (1971), «Нестандартное доказательство теоремы о кривой Жордана», Pacific Journal of Mathematics , 36 : 219–229, doi : 10.2140/pjm.1971.36.219 , ISSN  0030-8730, MR  0276940
• Осгуд, Уильям Ф. (1903), «Жордановая кривая положительной площади», Труды Американского математического общества , 4 (1): 107–112, doi : 10.2307/1986455 , ISSN  0002-9947, JFM  34.0533.02, JSTOR  1986455
• Росс, Фиона; Росс, Уильям Т. (2011), «Теорема о кривой Жордана нетривиальна», Journal of Mathematics and the Arts , 5 (4): 213–219, doi : 10.1080/17513472.2011.634320, S2CID  3257011. авторский сайт
• Сакамото, Нобуюки; Ёкояма, Кейта (2007), «Теорема Жордана о кривой и теорема Шёнфлиса в слабой арифметике второго порядка», Архив математической логики , 46 (5): 465–480, doi : 10.1007/s00153-007-0050-6, ISSN  0933-5846, MR  2321588, S2CID  33627222
• Томассен, Карстен (1992), «Теорема Джордана-Шенфлиса и классификация поверхностей», American Mathematical Monthly , 99 (2): 116–130, doi : 10.2307/2324180, JSTOR  2324180
• Тверберг, Хельге (1980), «Доказательство теоремы о жордановой кривой» (PDF) , Бюллетень Лондонского математического общества , 12 (1): 34–38, CiteSeerX  10.1.1.374.2903 , doi : 10.1112/blms/12.1 .34
• Веблен, Освальд (1905), «Теория плоских кривых в неметрическом анализе ситуации», Труды Американского математического общества , 6 (1): 83–98, doi : 10.2307/1986378 , JSTOR  1986378, MR  1500697

Внешние ссылки

• М.И. Войцеховский (2001) [1994], «Теорема Жордана», Математическая энциклопедия , EMS Press
• Полное формальное доказательство теоремы Джордана о кривой в 6500 строк в Mizar .
• Сборник доказательств теоремы Жордана о кривой на домашней странице Эндрю Раницки.
• Простое доказательство теоремы Жордана о кривой (PDF) Дэвида Б. Голда
• Браун, Р.; Антолино-Камарена, О. (2014). «Исправление к «Группоидам, свойству Фрагмена-Брауэра и теореме о жордановой кривой», J. Homotopy and родственные структуры 1 (2006) 175-183». arXiv : 1404.0556 [math.AT].