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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема  —  Пусть X — n -мерная топологическая сфера в ( n +1)-мерном евклидовом пространстве R ^{n +1} ( n > 0), т. е. образ инъективного непрерывного отображения n- мерной сферы S ⁿ в R ^{n +1} . Тогда дополнение Y сферы X в R ^{n +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 -мерным компактным связным подмногообразием R ^{n +1} (или S ^{n +1} ) без границы, его дополнение имеет 2 связные компоненты.

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

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

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

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

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

В обратной математике и компьютерно-формализованной математике теорема о кривой Жордана обычно доказывается путем ее первоначального преобразования в эквивалентную дискретную версию, похожую на сильную теорему Гекса, а затем доказательства дискретной версии. ^[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 соседей», где каждая вершина связана с тогда и только тогда , когда , и . ${\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).

Первое доказательство этой теоремы было дано Камиллом Жорданом в его лекциях по вещественному анализу и опубликовано в его книге Cours d'analyse de l'École Polytechnique . ^[1] Существуют некоторые разногласия относительно того, было ли доказательство Жордана полным: большинство комментаторов утверждали, что первое полное доказательство было дано позже Освальдом Вебленом , который сказал следующее о доказательстве Жордана:

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

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

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

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

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

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

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

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

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

Корень трудности объясняется в Tverberg (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}}$

Приложение

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

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

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

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

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

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

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

Примечания

1. Джордан (1887).
2. Клайн, Дж. Р. (1942). «Что такое теорема о кривой Жордана?». American Mathematical Monthly . 49 (5): 281–286. doi :10.2307/2303093. JSTOR  2303093. MR  0006516.
3. Хейлз, Томас С. (2007). "Доказательство Джордана теоремы о кривой Жордана" (PDF) . От понимания к доказательству: юбилейный сборник в честь Анджея Трибулеца. Исследования по логике, грамматике и риторике . 10 (23). Университет Белостока.
4. Маэхара (1984), стр. 641.
5. Гейл, Дэвид (декабрь 1979 г.). «Игра в гексагон и теорема Брауэра о неподвижной точке». The American Mathematical Monthly . 86 (10): 818–827. doi :10.2307/2320146. ISSN  0002-9890. JSTOR  2320146.
6. Нгуен, Фуонг; Кук, Стивен А. (2007). «Сложность доказательства теоремы о дискретной жордановой кривой». 22-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS 2007) . IEEE. стр. 245–256. arXiv : 1002.2954 . doi : 10.1109/lics.2007.48. ISBN 978-0-7695-2908-0.
7. Хейлз, Томас С. (декабрь 2007 г.). «Теорема о кривой Жордана, формально и неформально». The American Mathematical Monthly . 114 (10): 882–894. doi :10.1080/00029890.2007.11920481. ISSN  0002-9890. S2CID  887392.
8. Наяр, Шри (1 марта 2021 г.). «Первые принципы компьютерного зрения: сегментация двоичных изображений | Двоичные изображения». YouTube .
9. Šlapal, J (апрель 2004 г.). «Цифровой аналог теоремы о кривой Жордана». Discrete Applied Mathematics . 139 (1–3): 231–251. doi : 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. doi :10.1007/BF00499625. MR  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. "V. Топология". 1. Теорема Жордана о кривой (PDF) . Эдинбург: Эдинбургский университет. 1978. С. 267.
18. "PNPOLY - Включение точек в полигональный тест - WR Franklin (WRF)". wrf.ecse.rpi.edu . Получено 18 июля 2021 г.
19. Адлер, Авив; Даскалакис, Константинос; Демейн, Эрик Д. (2016). Хатзигианнакис, Иоаннис; Митценмахер, Михаэль; Рабани, Юваль; Санджорджи, Давиде (ред.). «Сложность гексагональной кривой и теорема о кривой Жордана». 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). "V. Топология". Написано в Оксфорде. Что такое математика?: элементарный подход к идеям и методам . Герберт Роббинс ([4-е изд.] изд.). Соединенное Королевство: Oxford University Press. стр. 267. ISBN 978-0-19-502517-0. OCLC  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), «Теорема о кривой Жордана нетривиальна», Журнал математики и искусств , 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), «Теория плоских кривых в неметрическом анализе Situs», Труды Американского математического общества , 6 (1): 83–98, doi : 10.2307/1986378 , JSTOR  1986378, MR  1500697

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

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