Циклический порядок

В математике циклический порядок — это способ расположить набор объектов по кругу . ^[nb] В отличие от большинства структур в теории порядка , циклический порядок не моделируется как бинарное отношение , например, « a < b ». Нельзя сказать, что восток «больше по часовой стрелке», чем запад. Вместо этого циклический порядок определяется как тернарное отношение [ a , b , c ] , означающее «после a , b достигается раньше c ». Например, [июнь, октябрь, февраль], но не [июнь, февраль, октябрь], см. рисунок. Тернарное отношение называется циклическим порядком, если оно циклическое, асимметричное, транзитивное и связное. Отказ от требования «связности» приводит к частичному циклическому порядку .

Множество с циклическим порядком называется циклически упорядоченным множеством или просто циклом . ^[nb] Некоторые знакомые циклы являются дискретными, имеющими только конечное число элементов : есть семь дней недели , четыре стороны света , двенадцать нот в хроматической гамме и три игры в камень -ножницы-бумага . В конечном цикле каждый элемент имеет «следующий элемент» и «предыдущий элемент». Существуют также циклические порядки с бесконечным числом элементов, такие как ориентированная единичная окружность на плоскости.

Циклические порядки тесно связаны с более знакомыми линейными порядками , которые располагают объекты в линию . Любой линейный порядок можно согнуть в окружность, а любой циклический порядок можно разрезать в точке, получив в результате линию. Эти операции, наряду с соответствующими конструкциями интервалов и покрывающих отображений, означают, что вопросы о циклических порядках часто можно преобразовать в вопросы о линейных порядках. Циклы имеют больше симметрий, чем линейные порядки, и они часто естественным образом возникают как остатки линейных структур, как в конечных циклических группах или действительной проективной прямой .

Циклический порядок на множестве X с n элементами подобен расположению X на циферблате для n -часовых часов. Каждый элемент x в X имеет «следующий элемент» и «предыдущий элемент», и взятие либо последующих, либо предшествующих элементов циклически проходит ровно один раз по элементам как x (1), x (2), ..., x ( n ) .

Есть несколько эквивалентных способов сформулировать это определение. Циклический порядок на X - это то же самое, что перестановка , которая превращает все X в один цикл , что является особым типом перестановки - круговой перестановкой . С другой стороны, цикл с n элементами также является Z _n - торсором : множеством со свободным транзитивным действием конечной циклической группы . ^[1] Другая формулировка - превратить X в стандартный направленный циклический граф на n вершинах, путем некоторого сопоставления элементов с вершинами.

Может оказаться инстинктивным использовать циклические порядки для симметричных функций , например, как в

ху + yz + zx

где написание конечного одночлена как xz отвлекало бы от рисунка.

Существенное применение циклических порядков заключается в определении классов сопряженности свободных групп . Два элемента g и h свободной группы F на множестве Y сопряжены тогда и только тогда, когда они записаны как произведения элементов y и y ⁻¹ с y в Y , а затем эти произведения помещены в циклический порядок, циклические порядки эквивалентны по правилам переписывания , которые позволяют удалять или добавлять смежные y и y ⁻¹ .

Циклический порядок на множестве X может быть определен линейным порядком на X , но не единственным способом. Выбор линейного порядка эквивалентен выбору первого элемента, поэтому существует ровно n линейных порядков, которые индуцируют заданный циклический порядок. Поскольку существует n ! возможных линейных порядков (как в перестановках ), существует ( n − 1)! возможных циклических порядков (как в круговых перестановках ).

Бесконечное множество также может быть упорядочено циклически. Важные примеры бесконечных циклов включают единичную окружность , S ¹ , и рациональные числа , Q . Основная идея та же: мы располагаем элементы множества по окружности. Однако в бесконечном случае мы не можем полагаться на отношение непосредственного следования, поскольку у точек может не быть последователей. Например, если задана точка на единичной окружности, то нет «следующей точки». Мы также не можем полагаться на бинарное отношение, чтобы определить, какая из двух точек идет «первой». Двигаясь по часовой стрелке по окружности, ни восток, ни запад не приходят первыми, но каждый следует за другим.

Вместо этого мы используем тернарное отношение, обозначающее, что элементы a , b , c следуют друг за другом (не обязательно сразу) по мере обхода круга. Например, по часовой стрелке, [восток, юг, запад]. Каррируя аргументы тернарного отношения [ a , b , c ] , можно представить себе циклический порядок как однопараметрическое семейство бинарных отношений порядка, называемых разрезами , или как двухпараметрическое семейство подмножеств K , называемых интервалами .

Общее определение таково: циклический порядок на множестве X — это отношение C ⊂ X ³ , записанное как [ a , b , c ] , которое удовлетворяет следующим аксиомам: ^[nb]

1. Цикличность: Если [ a , b , c ] , то [ b , c , a ]
2. Асимметрия: Если [ a , b , c ] , то не [ c , b , a ].
3. Транзитивность: Если [ a , b , c ] и [ a , c , d ] , то [ a , b , d ]
4. Связность: Если a , b и c различны, то либо [ a , b , c ], либо [ c , b , a ].

Аксиомы названы по аналогии с аксиомами асимметрии , транзитивности и связности для бинарного отношения, которые вместе определяют строгий линейный порядок . Эдвард Хантингтон  (1916, 1924) рассмотрел другие возможные списки аксиом, включая один список, который должен был подчеркнуть сходство между циклическим порядком и отношением промежуточности . Тройное отношение, которое удовлетворяет первым трём аксиомам, но не обязательно аксиоме тотальности, является частичным циклическим порядком .

При наличии линейного порядка < на множестве X циклический порядок на X, индуцированный <, определяется следующим образом: ^[2]

[ a , b , c ] тогда и только тогда, когда a < b < c или b < c < a или c < a < b

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

Вырезание одной точки из циклического порядка оставляет линейный порядок позади. Точнее, учитывая циклически упорядоченный набор , каждый элемент определяет естественный линейный порядок на оставшейся части набора, , по следующему правилу: ^[5]${\displaystyle (К,[\cdot ,\cdot ,\cdot ])}$${\displaystyle a\in K}$${\displaystyle <_{a}}$${\displaystyle K\setminus \{a\}}$

${\displaystyle x<_{a}y}$тогда и только тогда, когда .${\displaystyle [а,х,у]}$

Более того, может быть расширен путем присоединения в качестве наименьшего элемента; полученный линейный порядок на называется главным разрезом с наименьшим элементом . Аналогично, присоединение в качестве наибольшего элемента приводит к разрезу . ^[6]${\displaystyle <_{a}}$${\displaystyle а}$${\displaystyle К}$${\displaystyle а}$${\displaystyle а}$${\displaystyle <^{a}}$

При наличии двух элементов открытый интервал от до , записанный как , представляет собой множество всех таких, что . Система открытых интервалов полностью определяет циклический порядок и может использоваться как альтернативное определение отношения циклического порядка. ^[7]${\displaystyle a\neq b\in K}$${\displaystyle а}$${\displaystyle б}$${\displaystyle (а,б)}$${\displaystyle x\in K}$${\displaystyle [а,х,б]}$

Интервал имеет естественный линейный порядок, заданный как . Можно определить полузамкнутые и замкнутые интервалы , , и , примыкая как наименьший элемент и/или как наибольший элемент . ^[8] В качестве особого случая открытый интервал определяется как разрез .${\displaystyle (а,б)}$${\displaystyle <_{a}}$${\displaystyle [а,б)}$${\displaystyle (а,б]}$${\displaystyle [а,б]}$${\displaystyle а}$${\displaystyle б}$${\displaystyle (а,а)}$${\displaystyle K\setminus a}$

В более общем случае собственное подмножество называется выпуклым , если оно содержит интервал между каждой парой точек: для , либо или также должно быть в . ^[9] Выпуклое множество линейно упорядочено разрезом для любого , не входящего в множество; этот порядок не зависит от выбора .${\displaystyle S}$${\displaystyle К}$${\displaystyle a\neq b\in S}$${\displaystyle (а,б)}$${\displaystyle (б,а)}$${\displaystyle S}$${\displaystyle <_{x}}$${\displaystyle x}$${\displaystyle x}$

Так как окружность имеет порядок по часовой стрелке и порядок против часовой стрелки, любое множество с циклическим порядком имеет два смысла . Биекция множества, которая сохраняет порядок, называется упорядоченным соответствием . Если смысл сохраняется, как и прежде, это прямое соответствие , в противном случае оно называется противоположным соответствием . ^[10] Коксетер использует отношение разделения для описания циклического порядка, и это отношение достаточно сильное, чтобы различать два смысла циклического порядка. Автоморфизмы циклически упорядоченного множества можно отождествить с C2 _, двухэлементной группой прямых и противоположных соответствий.

Идея «циклического порядка = расположения по кругу» работает, потому что любое подмножество цикла само по себе является циклом. Чтобы использовать эту идею для наложения циклических порядков на множества, которые на самом деле не являются подмножествами единичной окружности на плоскости, необходимо рассмотреть функции между множествами.

Функция между двумя циклически упорядоченными множествами, f  : X → Y , называется монотонной функцией или гомоморфизмом , если она восстанавливает порядок на Y : всякий раз, когда [ f ( a ), f ( b ), f ( c )] , имеем [ a , b , c ] . Эквивалентно, f является монотонной, если всякий раз, когда [ a , b , c ] и f ( a ), f ( b ) , и f ( c ) все различны, то [ f ( a ), f ( b ), f ( c )] . Типичным примером монотонной функции является следующая функция на цикле с 6 элементами:

ф (0) = ф (1) = 4,

ф (2) = ф (3) = 0,

ф (4) = ф (5) = 1.

Функция называется вложением, если она является одновременно монотонной и инъективной . ^[nb] Эквивалентно, вложение — это функция, которая продвигает вперед порядок на X : всякий раз, когда [ a , b , c ] , имеем [ f ( a ), f ( b ), f ( c )] . В качестве важного примера, если X является подмножеством циклически упорядоченного множества Y , и X задан его естественный порядок, то отображение включения i  : X → Y является вложением.

В общем случае инъективная функция f из неупорядоченного множества X в цикл Y индуцирует уникальный циклический порядок на X , который делает f вложением.

Циклический порядок на конечном множестве X может быть определен инъекцией в единичный круг, X → S ¹ . Существует много возможных функций, которые индуцируют тот же самый циклический порядок — на самом деле, бесконечно много. Чтобы количественно оценить эту избыточность, требуется более сложный комбинаторный объект, чем простое число. Изучение конфигурационного пространства всех таких отображений приводит к определению ( n − 1) -мерного многогранника, известного как циклоэдр . Циклоэдры были впервые применены для изучения инвариантов узлов ; ^[11] они совсем недавно были применены для экспериментального обнаружения периодически экспрессируемых генов при изучении биологических часов . ^[12]

Категория гомоморфизмов стандартных конечных циклов называется циклической категорией ; ее можно использовать для построения циклических гомологий Алена Конна .

Можно определить степень функции между циклами, аналогично степени непрерывного отображения . Например, естественное отображение из круга квинт в хроматический круг является отображением степени 7. Можно также определить число вращения .

• Разрез с наименьшим и наибольшим элементом называется прыжком . Например, каждый разрез конечного цикла Z _n является прыжком. Цикл без прыжков называется плотным . ^{[13] [14]}
• Разрез без наименьшего и наибольшего элемента называется разрывом . Например, рациональные числа Q имеют разрыв на каждом иррациональном числе. Они также имеют разрыв на бесконечности, т.е. обычный порядок. Цикл без разрывов называется полным . ^{[15] [14]}
• Разрез с ровно одной конечной точкой называется главным или дедекиндовым разрезом. Например, каждый разрез окружности S ¹ является главным разрезом. Цикл, где каждый разрез является главным, будучи одновременно плотным и полным, называется непрерывным . ^{[16] [14]}

Множество всех разрезов циклически упорядочено следующим отношением: [< ₁ , < ₂ , < ₃ ] тогда и только тогда, когда существуют x , y , z такие, что: ^[17]

х < ₁ у < ₁ z ,

х < ₁ у < ₂ z < ₂ х , и

х < ₁ у < ₁ z < ₃ х < ₃ у .

Определенное подмножество этого цикла разрезов представляет собой дедекиндово завершение исходного цикла.

Начиная с циклически упорядоченного множества K , можно сформировать линейный порядок, развернув его вдоль бесконечной линии. Это отражает интуитивное представление о том, как отслеживать, сколько раз человек проходит по кругу. Формально линейный порядок определяется на декартовом произведении Z × K , где Z — множество целых чисел , фиксируя элемент a и требуя, чтобы для всех i : ^[18]

Если [ a , x , y ] , то a _i < x _i < y _i < a _{i +1} .

Например, месяцы январь 2024 г., май 2024 г., сентябрь 2024 г. и январь 2025 г. следуют именно в таком порядке.

Этот порядок Z × K называется универсальным покрытием K . [ ^nb] Его тип порядка не зависит от выбора a , но нотация не зависит, поскольку целочисленная координата «переворачивается» в a . Например, хотя циклический порядок классов высоты тона совместим с алфавитным порядком от A до G, нота C выбирается первой нотой в каждой октаве, поэтому в нотно-октавной нотации за нотой B ₃ следует нота C ₄ .

Обратная конструкция начинается с линейно упорядоченного множества и сворачивает его в циклически упорядоченное множество. Если задано линейно упорядоченное множество L и сохраняющая порядок биекция T  : L → L с неограниченными орбитами, то пространство орбит L / T циклически упорядочено требованием: ^{[7] [nb]}

Если a < b < c < T ( a ) , то [[ a ], [ b ], [ c ]] .

В частности, можно восстановить K , определив T ( x _i ) = x _{i +1} на Z × K .

Существуют также n -кратные покрытия для конечного n ; в этом случае одно циклически упорядоченное множество покрывает другое циклически упорядоченное множество. Например, 24-часовые часы являются двойным покрытием 12-часовых часов . В геометрии пучок лучей, исходящих из точки в ориентированной плоскости, является двойным покрытием пучка неориентированных прямых, проходящих через ту же точку. ^[19] Эти покрывающие отображения можно охарактеризовать, подняв их до универсального покрытия. ^[7]

Для заданного циклически упорядоченного множества ( K , [ ]) и линейно упорядоченного множества ( L , <) (полное) лексикографическое произведение является циклическим порядком на множестве произведений K × L , определяемым как [( a , x ), ( b , y ), ( c , z )], если выполняется одно из следующих условий: ^[20]

• [ а , б , в ]
• а = b ≠ с и х < у
• b = c ≠ a и y < z
• с = а ≠ b и z < x
• а = b = с и [ х , у , z ]

Лексикографическое произведение K × L глобально выглядит как K , а локально — как L ; его можно рассматривать как K копий L. Эта конструкция иногда используется для характеристики циклически упорядоченных групп. ^[21]

Можно также склеить различные линейно упорядоченные множества, чтобы сформировать круговое упорядоченное множество. Например, если заданы два линейно упорядоченных множества L ₁ и L ₂ , можно образовать круг, соединив их вместе в положительной и отрицательной бесконечности. Круговой порядок на несвязном объединении L ₁ ∪ L ₂ ∪ {–∞, ∞ } определяется как ∞ < L ₁ < –∞ < L ₂ < ∞ , где индуцированный порядок на L ₁ противоположен его исходному порядку. Например, множество всех долгот кругово упорядочено путем соединения всех точек на западе и всех точек на востоке, вместе с нулевым меридианом и 180-м меридианом . Кульман, Маршалл и Осиак (2011) используют эту конструкцию при характеристике пространств упорядочений и действительных мест двойных формальных рядов Лорана над действительным замкнутым полем . ^[22]

Открытые интервалы образуют базу для естественной топологии , топологии циклического порядка . Открытые множества в этой топологии — это в точности те множества, которые открыты в каждом совместимом линейном порядке. ^[23] Чтобы проиллюстрировать разницу, в множестве [0, 1) подмножество [0, 1/2) является окрестностью 0 в линейном порядке, но не в циклическом порядке.

Интересные примеры циклически упорядоченных пространств включают конформную границу односвязной поверхности Лоренца ^[24] и пространство листов поднятого существенного ламинирования некоторых 3-многообразий. ^[25] Дискретные динамические системы на циклически упорядоченных пространствах также были изучены. ^[26]

Топология интервала забывает исходную ориентацию циклического порядка. Эту ориентацию можно восстановить, обогатив интервалы их индуцированными линейными порядками; тогда получается множество, покрытое атласом линейных порядков, которые совместимы там, где они пересекаются. Другими словами, циклически упорядоченное множество можно рассматривать как локально линейно упорядоченное пространство: объект, подобный многообразию , но с отношениями порядка вместо координатных карт. Эта точка зрения позволяет легче быть точным в отношении таких понятий, как покрывающие карты. Обобщение на локально частично упорядоченное пространство изучается в Roll (1993); см. также Направленная топология .

Циклически упорядоченная группа — это множество с групповой структурой и циклическим порядком, такое, что левое и правое умножение сохраняют циклический порядок. Циклически упорядоченные группы были впервые подробно изучены Ладиславом Ригером в 1947 году. ^[27] Они являются обобщением циклических групп : бесконечной циклической группы Z и конечных циклических групп Z / n . Поскольку линейный порядок индуцирует циклический порядок, циклически упорядоченные группы также являются обобщением линейно упорядоченных групп : рациональных чисел Q , действительных чисел R и так далее. Некоторые из наиболее важных циклически упорядоченных групп не попадают ни в одну из предыдущих категорий: группа окружности T и ее подгруппы, такие как подгруппа рациональных точек .

Каждая циклически упорядоченная группа может быть выражена как фактор L / Z , где L — линейно упорядоченная группа, а Z — циклическая конфинальная подгруппа L . Каждая циклически упорядоченная группа может быть также выражена как подгруппа произведения T × L , где L — линейно упорядоченная группа. Если циклически упорядоченная группа является архимедовой или компактной, она может быть вложена в саму T ^{. [28]}

Частичный циклический порядок — это тернарное отношение, которое обобщает (полный) циклический порядок таким же образом, как частичный порядок обобщает полный порядок . Он циклический, асимметричный и транзитивный, но не обязательно полный. Многообразие порядка — это частичный циклический порядок, который удовлетворяет дополнительной аксиоме распространения . ^[29] Замена аксиомы асимметрии на дополнительную версию приводит к определению коциклического порядка . Соответственно, полные коциклические порядки связаны с циклическими порядками таким же образом, как ≤ связано с < .

Циклический порядок подчиняется относительно сильной аксиоме транзитивности 4 точек. Одной из структур, которая ослабляет эту аксиому, является система CC : тернарное отношение, которое является циклическим, асимметричным и полным, но в целом не транзитивным. Вместо этого система CC должна подчиняться аксиоме транзитивности 5 точек и новой аксиоме внутреннего , которая ограничивает конфигурации 4 точек, которые нарушают циклическую транзитивность. ^[30]

Циклический порядок должен быть симметричным относительно циклической перестановки, [ a , b , c ] ⇒ [ b , c , a ] , и асимметричным относительно обращения: [ a , b , c ] ⇒ ¬[ c , b , a ] . Тройное отношение, которое асимметрично относительно циклической перестановки и симметрично относительно обращения, вместе с соответствующими версиями аксиом транзитивности и тотальности, называется отношением промежуточности . Отношение разделения является четверичным отношением , которое можно рассматривать как циклический порядок без ориентации. Отношение между циклическим порядком и отношением разделения аналогично отношению между линейным порядком и отношением промежуточности. ^[31]

Эванс, Макферсон и Иванов (1997) дают теоретико-модельное описание накрывающих отображений циклов.

Tararin (2001, 2002) изучает группы автоморфизмов циклов с различными свойствами транзитивности . Giraudet & Holland (2002) характеризуют циклы, полные группы автоморфизмов которых действуют свободно и транзитивно . Campero-Arena & Truss (2009) характеризуют счетные цветные циклы, группы автоморфизмов которых действуют транзитивно. Truss (2009) изучает группу автоморфизмов единственного (с точностью до изоморфизма) счетного плотного цикла.

Кулпешов и Макферсон (2005) изучают условия минимальности на циклически упорядоченных структурах , т.е. модели языков первого порядка, которые включают циклическое отношение порядка. Эти условия являются аналогами o-минимальности и слабой o-минимальности для случая линейно упорядоченных структур. Кулпешов (2006, 2009) продолжает с некоторыми характеристиками ω-категоричных структур. ^[32]

Ганс Фройденталь подчеркивал роль циклических порядков в когнитивном развитии, в отличие от Жана Пиаже , который рассматривал только линейные порядки. Были проведены некоторые эксперименты для исследования ментальных репрезентаций циклически упорядоченных множеств, таких как месяцы года.

^циклический порядок Отношение может быть названо циклическим порядком (Huntington 1916, стр. 630), круговым порядком (Huntington 1916, стр. 630), циклическим упорядочением (Kok 1973, стр. 6) или круговым упорядочением (Mosher 1996, стр. 109). Некоторые авторы называют такое упорядочение полным циклическим порядком (Isli & Cohn 1998, стр. 643), полным циклическим порядком (Novák 1982, стр. 462), линейным циклическим порядком (Novák 1984, стр. 323) или l-циклическим порядком или ℓ- циклическим порядком (Černák 2001, стр. 32), чтобы отличать от более широкого класса частичных циклических порядков , которые они называют просто циклическими порядками . Наконец, некоторые авторы могут понимать циклический порядок как неориентированное четверичное разделительное отношение (Bowditch 1998, стр. 155).

^цикл Множество с циклическим порядком можно назвать циклом (Novák 1982, стр. 462) или окружностью (Giraudet & Holland 2002, стр. 1). Вышеуказанные вариации также появляются в форме прилагательных: циклически упорядоченное множество ( cyklicky uspořádané množiny , Čech 1936, стр. 23), циклически упорядоченное множество , полное циклически упорядоченное множество , полное циклически упорядоченное множество , линейно циклически упорядоченное множество , l-циклически упорядоченное множество , ℓ- циклически упорядоченное множество . Все авторы согласны, что цикл полностью упорядочен.

^тернарное отношение Для циклического отношения используется несколько различных символов. Хантингтон (1916, стр. 630) использует конкатенацию: ABC . Чех (1936, стр. 23) и (Новак 1982, стр. 462) используют упорядоченные тройки и символ принадлежности множеству: ( a , b , c ) ∈ C . Мегиддо (1976, стр. 274) использует конкатенацию и принадлежность множеству: abc ∈ C , понимая abc как циклически упорядоченную тройку. В литературе по группам, такой как Сверчковский (1959a, стр. 162) и Чернак и Якубик (1987, стр. 157), как правило, используются квадратные скобки: [ a , b , c ] . Giraudet & Holland (2002, стр. 1) используют круглые скобки: ( a , b , c ) , оставляя квадратные скобки для отношения промежуточности. Campero-Arena & Truss (2009, стр. 1) используют нотацию в стиле функции: R ( a , b , c ) . Rieger (1947), цитируемый по Pecinová 2008, стр. 82), использует символ «меньше чем» в качестве разделителя: < x , y , z < . Некоторые авторы используют инфиксную нотацию: a < b < c , понимая, что это не несет обычного значения a < b и b < c для некоторого бинарного отношения < (Černy 1978, стр. 262). Вайнштейн (1996, стр. 81) подчеркивает цикличность, повторяя элемент: p ↪ r ↪ q ↪ p .

^вложение Новак (1984, стр. 332) называет вложение «изоморфным вложением».

^roll В этом случае Жироде и Холланд (2002, стр. 2) пишут, что K — это L , «свернутое».

^пространство орбит Отображение T названо архимедовым Боудичем (2004, стр. 33), котерминальным Камперо-Арена и Трасс (2009, стр. 582) и переводом МакМаллена (2009, стр. 10).

^универсальное покрытие МакМаллен (2009, стр. 10) называет Z × K «универсальным покрытием» K . Жироде и Холланд (2002, стр. 3) пишут, что K — это Z × K «спирализованный». Фрейденталь и Бауэр (1974, стр. 10) называют Z × K «∞-кратным покрытием» K . Часто эту конструкцию записывают как антилексикографический порядок на K × Z .

• циклический порядок в n Lab