Циклический порядок — способ упорядочивания объектов таким образом, чтобы последовательное движение по порядку после полного обхода совокупности возвращалось на начальный объект движения; полный порядок, «соединённый концами» в цикл. В отличие от структур, изучаемых в теории порядков, такой порядок не моделируется бинарным отношением, таким как «», например, нельзя сказать, что восток «больше по часовой стрелке», чем запад; вместо этого циклический порядок определяется как тернарное отношение , означающее, что «после достигается раньше, чем ». Например, [Июнь, Октябрь, Февраль]. Тернарное отношение называется циклическим порядком, если оно является циклическим (), асимметричным, транзитивным и полным. Порядок, не обладающий всеми этими свойствами, кроме полноты, называется .
Множество с циклическим порядком называется циклически упорядоченным множеством, или просто циклом. Некоторые циклы дискретны, имея лишь конечное число элементов — имеется семь дней недели, четыре стороны света, двенадцать нот в хроматической гамме и три игрока в игре «камень, ножницы, бумага». В конечном цикле каждый элемент имеет «следующий элемент» и «предыдущий элемент». Существуют также непрерывные циклы с бесконечным числом элементов, такие как ориентированная единичная окружность на плоскости.
Циклические порядки тесно связаны с более известными линейными порядками, которые упорядочивают объекты вдоль прямой. Любой линейный порядок может быть свёрнут в цикл и любой циклический порядок может быть разрезан в точке, получая линейный порядок. Эти операции, вместе со связанными построениями интервалов и накрывающими отображениями, означают, что вопросы о циклических порядках могут часто быть трансформированы в вопросы о линейных порядках. Циклы имеют больше симметрий, чем линейные порядки, и они часто естественным образом возникают как вычеты линейных структур, как в конечных циклических группах или .
Конечные циклы
Циклический порядок на множестве с элементами подобен расположению элементов множества на циферблате с часами. Каждый элемент из имеет «следующий элемент» и «предыдущий элемент» и выбирая либо последующие, либо предыдущие элементы цикла, можно пройти в точности один раз через все элементы .
Существует несколько эквивалентных способов дать это определение. Циклический порядок на множестве будет тем же при перестановке элементов по циклу. Цикл с элементами является - — это множество со свободным транзитивным действием конечной циклической группы. Другая формулировка заключается в превращении в стандартный ориентированный граф-цикл с вершинами путём сопоставления элементов множества вершинам.
Можно использовать инстинктивно циклические порядки для симметрических функций, например, как в случае
,
где запись последнего одночлена в виде отвлекло бы внимание от структуры.
По существу, использование циклических порядков проявляется в определении классов сопряжённости свободных групп. Два элемента и группы на множестве смежны тогда и только тогда, когда они записываются как произведения на элементы и с из , а тогда эти произведения располагаются в циклическом порядке. Циклические порядки эквивалентны при переписывании правил, которые позволяют удалять или добавлять смежные и .
Циклический порядок на множестве может быть определён линейным порядком на , но не единственным образом. Выбор линейного порядка эквивалентен выбору первого элемента, так что имеется в точности линейных порядков, порождённых данным циклическим порядком. Поскольку имеется возможных линейных порядков, существует возможных циклических порядков.
Определение Бесконечное множество может также быть упорядочено циклически. Важными примерами бесконечных циклов являются единичная окружность, , и рациональные числа, . Основная идея одна и та же — мы упорядочиваем элементы в множестве по окружности. Однако в бесконечном случае мы не можем полагаться на отношение непосредственного следования, поскольку точки могут не иметь предшественника. Например, если дана точка на окружности, нет никакой «следующей точки». Нельзя также полагаться на бинарное отношение, какая из двух точек «первая». Проходя по часовой стрелке по окружности, ни с одной, ни с другой стороны точки не идут раньше, но следуют одна за другой.
Вместо этого мы используем тернарное отношение, указывая, что элементы , , идут один за другим (не обязательно немедленно) вдоль окружности. Например, в порядке часовой стрелки, [восток, юг, запад]. При использовании каррирования аргументов тернарного отношения можно считать циклический порядок однопараметрическим семейством бинарных отношений порядка, которые называются сечениями, или двупараметрическим семейством подмножеств множества , которые называются интервалами.
Тернарное отношение Общее определение следующее: циклический порядок на множестве — это отношение (пишется ), которое удовлетворяет следующим аксиомам: Цикличность: Из следует Асимметрия: Из следует неверность Транзитивность: Если и , то Полнота: Если , и различны, то либо , либо
Аксиомы названы по аналогии с аксиомами асимметрии, транзитивности и для бинарного отношения, которые вместе определяют строго линейный порядок. Эдвард Хантингтон предложил другой возможный список аксиом, включая аксиомы, подчёркивающие аналогию циклического порядка с . Тернарное отношение, удовлетворяющее первым трём аксиомам, но не обязательно аксиоме полноты, называется .
Развёртки и разрезы Если дан линейный порядок на множестве , циклический порядок на , порождённый порядком , определяется следующим образом: тогда и только тогда, когда , или , или
Два линейных порядка порождают тот же циклический порядок, если они могут быть преобразованы друг в друга циклической перестановкой, как это происходит при . Можно определить отношение циклического порядка как тернарное отношение, порождённое строго линейным порядком (как показано выше).
Удаление одной точки из циклического порядка оставляет линейный порядок. Более точно, если дано циклически упорядоченное множество (), каждый элемент определяет естественный линейный порядок на оставшемся множестве, со следующим правилом: тогда и только тогда, когда . Более того, можно расширить путём добавления в качестве наименьшего элемента. Получающийся линейный порядок на называется главным сечением с наименьшим элементом . Подобным же образом добавление в качестве наибольшего элемента приводит к сечению .
Интервалы Если даны два элемента , открытый интервал от до , записывается , — это множество всех , таких что . Система открытых интервалов полностью определяет циклический порядок и может быть использована как альтернативное определение циклического отношения.
Интервал имеет естественный линейный порядок, задаваемый отношением . Можно определить полузамкнутые и замкнутые интервалы , и путём присоединения в качестве и/или в качестве элементов. Как специальный случай открытый интервал определяется как разрез .
Более обще, собственное подмножество S множества K называется выпуклым, если оно содержит все интервалы между любой парой точек — для либо , либо должно также лежать в S. Выпуклое множество является линейно упорядоченным при сечении для любого , не входящего в множество. Это упорядочение не зависит от выбора .
Автоморфизмы Так как окружность имеет упорядочение по часовой стрелке и противоположное упорядочение, любое множество с циклическим порядком имеет два смысла. Биекция множества, сохраняющая порядок, называется упорядоченным соответствием. Если смысл (направление) то же самое, биекция называется прямым соответствием, в противном случае — обратным соответствием. Коксетер использовал для описания циклического порядка и это отношение достаточно сильно для отличия двух смыслов циклического порядка. Автоморфизмы циклически упорядоченного множества могут быть отождествлены с C2, двухэлементной группой прямых и обратных соответствий.
Монотонные функции Идея «циклический порядок = расположение на окружности» работает, поскольку любое подмножество цикла также является циклом. Чтобы использовать эту идею для введения циклического порядка на множествах, которые на самом деле не являются единичными окружностями на плоскости, нужно рассматривать функции между множествами.
Функция между двумя циклически упорядоченными множествами, , называется монотонной функцией или гомоморфизмом, если она сохраняет порядок на — если , имеем . Эквивалентно, монотонна, если в случае и элементы и различны, то . Типичный пример монотонной функции — следующая функция на цикле из 6 элементов:
Функция называется вложением, если она монотонна и инъективна. Эквивалентно, вложение — это функция, которая переносит порядок с множества : из следует . В качестве важного примера, если является подмножеством циклически упорядоченного множества и в задан естественный порядок, то является вложением.
В общем случае инъективная функция из неупорядоченного множества в цикл порождает циклический порядок на , который делает функцию вложением.
Функции на конечных множествах Циклический порядок на конечном множестве может быть определён по вложению в единичную окружность, . Существует много возможных функций, порождающих тот же циклический порядок — фактически, бесконечно много. Чтобы дать количественную оценку, необходимо использовать более сложный объект, чем число. Исследование конфигурационного пространства всех таких отображений приводит к определению многогранника, известного под названием . Циклоэдры первоначально использовались для изучения инвариантов узлов. Они позднее были применены для экспериментального выявления периодических генов при изучении биологических часов.
Категория гомеоморфизмов стандартных конечных циклов называется . Она может быть использована для построения циклической гомотопии Аллена Конна.
Можно определить степень функции между циклами аналогично степени непрерывного отображения. Например, естественное отображение квинтового круга в является отображением степени 7. Можно определить также число вращения.
Замыкание Сечение с наименьшим и наибольшим элементом называется прыжком. Например, любое разбиение конечного цикла является прыжком. Цикл без прыжков называется плотным. Сечение, в котором нет ни наименьшего, ни наибольшего элемента, называется щелью. Например, рациональные числа имеют щель в любом иррациональном числе. Для этих чисел имеется также щель на бесконечности, то есть обычный порядок. Цикл без щелей называется . Сечение с одной конечной точкой называется главным сечением. Например, любое сечение окружности является главным. Цикл, в котором любое сечение является главным, будучи плотным и полным, называется непрерывным.
Множество всех сечений является циклическим порядком со следующим отношением: тогда и только тогда, когда существуют такие что: , и .
Некоторые подмножества сечений этого цикла являются исходного цикла.
Дополнительные построения
Разворачивания и покрытия Начав с циклически упорядоченного множества , можно образовать линейный порядок путём разворачивания его на бесконечную прямую. Это отражает интуитивное понимание прохождения по окружности. Формально, линейный порядок определяется на прямом произведении , где — множество целых чисел, путём фиксации элемента и требования, чтобы для всех : Если , то . Например, месяцы , , и находятся в таком порядке.
Это упорядочение называется универсальным накрытием . Его порядковый тип не зависит от выбора , что нельзя сказать об обозначениях, поскольку целочисленная координата «перекатывается» через . Например, хотя циклический порядок высотных классов совместим с алфавитным порядком от A до G, буква C выбрана в качестве первой ноты октавы, так что в американской системе нотации за B3 следует C4.
Обратное построение начинает с линейно упорядоченного множества и сворачивает его в циклически упорядоченное множество. Если дано линейно упорядоченное множество и сохраняющая порядок биекция с незамкнутыми орбитами, пространство траекторий является циклически упорядоченным по необходимому условию: Если , то .