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

Циклический порядок — способ упорядочивания объектов таким образом, чтобы последовательное движение по порядку после полного обхода совокупности возвращалось на начальный объект движения; полный порядок, «соединённый концами» в цикл. В отличие от структур, изучаемых в теории порядков, такой порядок не моделируется бинарным отношением, таким как «a < b», например, нельзя сказать, что восток «больше по часовой стрелке», чем запад; вместо этого циклический порядок определяется как тернарное отношение [a, b, c], означающее, что «после a достигается b раньше, чем c». Например, [Июнь, Октябрь, Февраль]. Тернарное отношение $[a,b,c]$ называется циклическим порядком, если оно является циклическим ($[a,b,c]\Rightarrow [b,c,a]$), асимметричным, транзитивным и полным. Порядок, не обладающий всеми этими свойствами, кроме полноты, называется частичным циклическим порядком.

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

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

Конечные циклы

5-элементный цикл

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

Существует несколько эквивалентных способов дать это определение. Циклический порядок на множестве X будет тем же при перестановке элементов по циклу. Цикл с n элементами является Z_n-торсором — это множество со свободным транзитивным действием конечной циклической группы. Другая формулировка заключается в превращении X в стандартный ориентированный граф-цикл с n вершинами путём сопоставления элементов множества вершинам.

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

xy + 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\subset X^{3}$ (пишется [a, b, c]), которое удовлетворяет следующим аксиомам:

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]

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

Развёртки и разрезы

Если дан линейный порядок < на множестве X, циклический порядок на X, порождённый порядком <, определяется следующим образом:

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

Два линейных порядка порождают тот же циклический порядок, если они могут быть преобразованы друг в друга циклической перестановкой, как это происходит при снятии карт. Можно определить отношение циклического порядка как тернарное отношение, порождённое строго линейным порядком (как показано выше).

Удаление одной точки из циклического порядка оставляет линейный порядок. Более точно, если дано циклически упорядоченное множество (K, [ ] ), каждый элемент a ∈ K определяет естественный линейный порядок <_a на оставшемся множестве, K ∖ a со следующим правилом:

x <_a y тогда и только тогда, когда [a, x, y].

Более того, <_a можно расширить путём добавления a в качестве наименьшего элемента. Получающийся линейный порядок на K называется главным сечением с наименьшим элементом a. Подобным же образом добавление a в качестве наибольшего элемента приводит к сечению <^a.

Интервалы

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

Интервал (a, b) имеет естественный линейный порядок, задаваемый отношением <_a. Можно определить полузамкнутые и замкнутые интервалы [a, b), (a, b] и [a, b] путём присоединения a в качестве наименьшего и/или b в качестве наибольшего элементов. Как специальный случай открытый интервал (a, a) определяется как разрез K ∖ a.

Более обще, собственное подмножество S множества K называется выпуклым, если оно содержит все интервалы между любой парой точек — для $a\neq b\in S$ либо (a, b), либо (b, a) должно также лежать в S. Выпуклое множество является линейно упорядоченным при сечении <_x для любого x, не входящего в множество. Это упорядочение не зависит от выбора x.

Автоморфизмы

Так как окружность имеет упорядочение по часовой стрелке и противоположное упорядочение, любое множество с циклическим порядком имеет два смысла. Биекция множества, сохраняющая порядок, называется упорядоченным соответствием. Если смысл (направление) то же самое, биекция называется прямым соответствием, в противном случае — обратным соответствием. Коксетер использовал отношение разделения для описания циклического порядка и это отношение достаточно сильно для отличия двух смыслов циклического порядка. Автоморфизмы циклически упорядоченного множества могут быть отождествлены с C₂, двухэлементной группой прямых и обратных соответствий.

Монотонные функции

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

Функция между двумя циклически упорядоченными множествами, 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 элементов:

f(0) = f(1) = 4,

f(2) = f(3) = 0,

f(4) = f(5) = 1.

Функция называется вложением, если она монотонна и инъективна. Эквивалентно, вложение — это функция, которая переносит порядок с множества 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)-мерного многогранника, известного под названием циклоэдр. Циклоэдры первоначально использовались для изучения инвариантов узлов. Они позднее были применены для экспериментального выявления периодических генов при изучении биологических часов.

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

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

Замыкание

• Сечение с наименьшим и наибольшим элементом называется прыжком. Например, любое разбиение конечного цикла Z_n является прыжком. Цикл без прыжков называется плотным.
• Сечение, в котором нет ни наименьшего, ни наибольшего элемента, называется щелью. Например, рациональные числа Q имеют щель в любом иррациональном числе. Для этих чисел имеется также щель на бесконечности, то есть обычный порядок. Цикл без щелей называется полным.
• Сечение с одной конечной точкой называется главным сечением. Например, любое сечение окружности S¹ является главным. Цикл, в котором любое сечение является главным, будучи плотным и полным, называется непрерывным.

[<₁, <₂, <₃] и [x, y, z]

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

x <₁ y <₁ z,

x <₁ y <₂ z <₂ x и

x <₁ y <₁ z <₃ x <₃ y.

Некоторые подмножества сечений этого цикла являются пополнением Дедекинда исходного цикла.

Дополнительные построения

Разворачивания и покрытия

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

Если [a, x, y], то a_i < x_i < y_i < a_{i + 1}.

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

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

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

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

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

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

Произведения и стягивания

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

• [a, b, c]
• a = b ≠ c и x < y
• b = c ≠ a и y < z
• c = a ≠ b и z < x
• a = b = c и [x, y, z]

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

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

Топология

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

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

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

Связанные структуры

Группы

Основная статья: Циклическая упорядоченная группа

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

Любая циклически упорядоченная группа может быть выражена как фактор-группа L / Z, где L является линейно упорядоченной группой, а Z — циклическая конфинальная подгруппа группы L. Любую циклическую упорядоченную группу можно выразить как произведение T × L, где L — линейно упорядоченная группа. Если циклически упорядоченная группа является архимедовой или компактной, её можно вложить в саму группу T.

Модифицированные аксиомы

Частичный циклический порядок — это тернарное отношение, обобщающее (полный) циклический порядок тем же образом, как частично упорядоченное множество обобщает линейно упорядоченное множество. В этом случае порядок является циклическим, асимметричным и транзитивным, но не обязательно полным. Упорядоченное многообразие — это частичный циклический порядок, удовлетворяющий дополнительной распределительной аксиоме. Замена аксиомы асимметрии на комплементарную версию приводит к определению коциклического порядка. Полные коциклические порядки связаны с циклическими порядками таким же образом, как ≤ связан с <.

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

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

Симметрии и теория моделей

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

Тарарин изучал группы автоморфизмов циклов с различными свойствами транзитивности. Жироде и Холланд описали циклы, полные группы автоморфизмов которых действуют свободно и транзитивно. Камперо-Арена и Трасс описали счётные цветные циклы, группы автоморфизмов которых действуют транзитивно. Трасс изучал группу автоморфизмов уникального (с точностью до изоморфизмов) счётного плотного цикла.

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

Восприятие

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

Примечания

↑ В литературе на английском языке этот порядок может называться cyclic order, circular order (круговой порядок) , cyclic ordering (циклическое упорядочение) или circular ordering (круговое упорядочение). Можно встретить также названия total cyclic order (вполне циклический порядок), complete cyclic order (полностью циклический порядок), linear cyclic order (линейный циклический порядок) , l-cyclic order или ℓ-cyclic order (l-/ℓ-циклический порядок), чтобы подчеркнуть отличие от более широкого класса частичных циклических порядков, которые они называют просто циклическими порядками. Наконец, некоторые авторы используют термин циклический порядок для обозначения неориентированного кватернарного отношения разделения.

↑ Множество с циклическим порядком можно назвать циклом или окружностью. В литературе на английском языке появляются также названия cyclically ordered set (циклически упорядоченное множество), circularly ordered set (упорядоченное по кругу множество), total cyclically ordered set (вполне циклически упорядоченное множество), complete cyclically ordered set (полностью циклически упорядоченное множество ), linearly cyclically ordered set (линейно циклически упорядоченное множество), l-cyclically ordered set (l-циклически упорядоченное множество), ℓ-cyclically ordered set (ℓ-циклически упорядоченное множество ). Все авторы соглашаются, что цикл полностью упорядочен.

↑  Существует несколько различных символов для циклического отношения. Хантингтон использовал соединение в цепочку: ABC. Чех и Новак использовали упорядоченные тройки и символ включения: (a, b, c) ∈ C. Мегиддо использовал соединение в цепочку и символ включения: abc ∈ C, понимая под abc циклически упорядоченную тройку. В литературе по теории групп, как у Швирцковского, Чернака и Якубика, чаще употребляются квадратные скобки: [a, b, c]. Жироде и Холланд используют круглые скобки: (a, b, c), оставляя квадратные скобки для отношения «между». Камперо-Арена и Трасс используют запись в стиле функций: R(a, b, c). Ригер, которого цитирует Пекинова), использует символ «меньше» как разделитель: < x, y, z <. Некоторые авторы используют инфиксное обозначение: a < b < c, понимая, что такое обозначение не соответствует обычной интерпретации a < b и b < c для того же бинарного отношения <. Вайнштайн подчёркивает циклическую природу отношения путём повторения элемента: p ↪ r ↪ q ↪ p.

↑  Новак называет вложение «изоморфным вложением».

↑  Отображение T Бодвич называет архимедовым, Камперо-Арена и Трасс называют котерминальным, а Макмаллен называет трансляцией.

↑  Макмаллен называет Z × K «универсальным накрытием» K. Жироде и Холланд написали, что K является «свёрткой» Z × K. Фройдентал и Бауэр называют Z × K «∞-кратным накрытием» K. Часто это построение записывается в антилексикографическом порядке на K × Z.

Ссылки

• cyclic order на сайте nLab