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

В математике циклический порядок - это способ упорядочить набор объектов в кружке . В отличие от большинства структур в теории порядка, циклический порядок не моделируется как бинарное отношение, например «< b". One does not say that east is "more clockwise" than west. Instead, a cyclic order is defined as a троичное отношение [a, b, c], означающее «после a достигается b до c». Например, [июнь, октябрь, февраль]. Тернарное отношение называется циклическим порядком, если оно циклическое, асимметричное, транзитивное и полное. «общее» требование приводит к частичному циклическому порядку.

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

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

• 1 Конечные циклы
• 2 Определения
  • 2.1 Тернарное отношение
  • 2.2 Катание и разрезы
  • 2.3 Интервалы
  • 2.4 Автоморфизмы
• 3 Монотонные функции
  • 3.1 Функции на конечных множествах
  • 3.2 Завершение
• 4 Дальнейшие построения
  • 4.1 Развертывание и покрытие
  • 4.2 Продукты и ретракты
• 5 Топология
• 6 Связанные структуры
  • 6.1 Группы
  • 6.2 Модифицированные аксиомы
• 7 Симметрии и теория моделей
• 8 Познание
• 9 Примечания по использованию
• 10 Ссылки
• 11 Дополнительная литература
• 12 Внешние ссылки

Цикл из 5 элементов

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

Есть несколько эквивалентных способов сформулировать это определение. Циклический порядок на X аналогичен перестановке , которая превращает все X в один цикл . Цикл с n элементами также является Zn-торсором : набором со свободным транзитивным действием на конечную циклическую группу. Другая формулировка состоит в том, чтобы превратить 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 ⊂ X, записанное [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]

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

Скручивающийся и разрезающий

Учитывая линейный порядок < on a set X, the cyclic order on X induced by < is defined as follows:

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

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

Вырезание единственной точки из циклического порядка оставляет линейный порядок позади. Точнее, для данного циклически упорядоченного множества (K, []) каждый элемент a ∈ K определяет естественный линейный порядок

x

Более того,

интервалов

Для двух элементов a ≠ b ∈ K открытый интервал от a до b, записанный (a, b), - это множество всех x ∈ K таких, что [a, x, b]. Система открытых интервалов полностью определяет циклический порядок и может использоваться как альтернативное определение отношения циклического порядка.

Интервал (a, b) имеет естественный линейный порядок, задаваемый наименьший элемент и / или b как наибольший элемент. Как частный случай, открытый интервал (a, a) определяется как разрез K ∖ a.

В более общем смысле, собственное подмножество S в K называется выпуклым, если он содержит интервал между каждой парой точек: для a ≠ b ∈ S либо (a, b), либо (b, a) также должны быть в S. Выпуклое множество линейно упорядочено разрезом

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

Поскольку круг имеет порядок по часовой стрелке и порядок против часовой стрелки, любой набор с циклическим порядком имеет два смысла . биекция множества, сохраняющая порядок, называется упорядоченным соответствием . Если смысл сохраняется, как и прежде, он является прямым соответствием, иначе оно называется противоположным соответствием . Кокстер использует отношение разделения к des cribe циклический порядок, и эта связь достаточно сильна, чтобы различать два смысла циклического порядка. автоморфизмы циклически упорядоченного множества могут быть отождествлены с C 2, двухэлементной группой прямого и противоположного соответствий.

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

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

Завершение

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

[<1, <2, <3] и [x, y, z]

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

x <1y <1z,

x <1y <2z <2x и

x <1y <1z <3x <3y.

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

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

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

Если [a, x, y], то a i< xi< yi< ai + 1.

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

Этот порядок Z × K называется универсальным покрытием K. Его тип заказа не зависит от выбора a, но обозначение нет, так как целочисленная координата "перекатывается" в a. Например, хотя циклический порядок классов высоты тона совместим с алфавитным порядком от A до G, C выбирается как первая нота в каждой октаве, поэтому в note-octave, за B 3 следует C 4.

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

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

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

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

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

Для циклически упорядоченного множества (K, []) и линейно упорядоченного множества (L, <), ( total) лексикографическое произведение - это циклический порядок на множестве продуктов 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 1 и L 2, можно образовать круг, соединив их вместе на положительной и отрицательной бесконечности. Круговой порядок на непересекающемся объединении L 1 ∪ L 2 ∪ {–∞, ∞} определяется как ∞ < L1< –∞ < L2< ∞, where the induced ordering on L1, это противоположно его исходному порядку. Например, набор всех долгот упорядочен по кругу путем объединения всех точек на запад и всех точек на восток вместе с нулевым меридианом и 180-м меридианом. Kuhlmann, Marshall Osiak (2011) используют эту конструкцию при характеристике пространств порядков и двойных формальных рядов Лорана над реальным замкнутым полем.

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

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

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

Группы

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

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

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

A частичный циклический порядок - это тернарное отношение, которое обобщает (всего) циклический порядок таким же образом, как частичный порядок обобщает общий порядок. Он циклический, асимметричный и транзитивный, но не обязательно тотальный. An - это частичный циклический порядок, удовлетворяющий дополнительной аксиоме расширения. Замена аксиомы асимметрии дополнительной версией приводит к определению коциклического порядка. Соответственно, общие коциклические порядки связаны с циклическими порядками так же, как ≤ связано с <.

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

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

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

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

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

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

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

^cycleНабор с циклическим порядком можно назвать циклом (Новак 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 как циклически упорядоченную тройку. В литературе по таким группам, как wierczkowski (1959a, p. 162) и Černák Jakubík (1987, p. 157), как правило, используются квадратные скобки: [a, b, c]. Giraudet Holland (2002, стр. 1) используют круглые скобки: (a, b, c), оставляя квадратные скобки для отношения промежуточности. Campero-Arena Truss (2009, стр. 1) используют обозначение функционального стиля: R (a, b, c). Rieger (1947), цитируется по Pecinová 2008, p. 82) использует в качестве разделителя символ «меньше»: < x, y, z <. Some authors use infix notation: a < b < c, with the understanding that this does not carry the usual meaning of a < b and b < c for some binary relation < (Černy 1978, p. 262). Вайнштейн (1996, стр. 81) подчеркивает цикличность, повторяя элемент: p ↪ r ↪ q ↪ p.

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

^rollВ этом случае Giraudet Holland (2002, стр. 2) пишут, что K - это L "свернутая".

^ orbit space Bowditch (2004, стр. 33) назвал карту T архимедовой, Campero-Arena Truss (2009, стр. 582), и перевод МакМаллена (2009, стр. 10).

^ универсальная обложка МакМаллен (2009, стр. 10) называет Z × K «универсальной обложкой» К. Giraudet Holland (2002, п. 3) напишите, что K равно Z × K "свернуто". Freudenthal Bauer (1974, стр. 10) называют Z × K «∞-кратным покрытием» K. Часто эта конструкция записывается как антилексикографический порядок на K × Z.

Цитаты

Библиография

• циклический порядок в nLab
• Средства массовой информации, связанные с циклическим порядком (математика) в Wikimedia Commons