Циклічний порядок

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
DC8.png

У математиці, циклічний порядок являє собою спосіб організації безлічі об'єктів в колі. На відміну від більшості структур в теорії порядку, циклічний порядок не може бути змодельований як бінарне відношення "a < b". Циклічний порядок визначається як потрійне відношення [a, b, c], що означає "після a, досягається b перед c". Наприклад: [червень, жовтень, лютий]. Потрійне відношення називається циклічним порядком, якщо воно циклічне, асиметричне, транзитивне і повне. Якщо відношення неповне, то воно називається частковим циклічним порядком.

Множина з циклічним порядком називається циклічно впорядкованою множиною або просто циклом. Деякі цикли називаються дискретними. Вони мають тільки скінченний ряд елементів : є сім днів тижня, чотири сторони світу, дванадцять нот в хроматичній гамі, три можливі дії в грі камінь-ножиці-папір. У кінцевому циклі, кожен елемент має "наступний елемент" і "попередній елемент". Є також неперервно-мінливі цикли: нескінченні з багатьма елементами, як наприклад одиничне коло на площині.

Циклічні порядки тісно пов'язані з лінійними порядками, які організовують об'єкти в лінію. Будь-який лінійний порядок може бути зігнутий в коло і будь-який лінійний порядок може бути вирізаний в точці, у результаті чого утворюється лінія. Ці операції означають, що питання про циклічні порядки часто може бути перетворене в питання про лінійні порядки. Цикли мають більше симетрій, ніж лінійні порядки.

Кінцеві цикли[ред.ред. код]

цикл з 5 елементів

Циклічний порядок на множині X з n елементів, подібний до розташування X на циферблаті годинника, в n-годинному форматі. Кожен елемент х з X має "наступний елемент" і "попередній елемент", і беручи або наступні елементи, або попередні, можна обійти цикл точно один раз через всі елементи x(1), x(2), ..., x(n). Іншими словами, циклічний порядок на X схожий на перестановку, яка створює зі всіх елементів множини X єдиний цикл.

Істотне використання циклічних порядків знаходиться у визначенні спряжених класів вільних груп. Два елементи g і h вільної групи F на множині Y спряжені тоді і тільки тоді, коли вони записуються у вигляді добутку елементів y, y−1 з y в Y, а потім ці елементи включаються в циклічний порядок. Циклічний порядок еквівалентний щодо правил перезапису, які дозволяють видалити або додати сусідні y, y−1. Циклічний порядок на множині X може бути визначений лінійним порядком на X, але не єдиним чином. Вибір лінійного порядку еквівалентний вибору першого елементу, так що є рівно n лінійних порядків, які продукують даний циклічний порядок. Так як є n! можливих лінійних порядків, є (n − 1)! можливих циклічних порядків.

Означення[ред.ред. код]

Нескінченна множина може також бути впорядкована циклічно. Прикладами нескінченних циклів можуть бути одиничне коло, S1, і раціональні числа, Q. Основна ідея та сама: ми розташовуємо велику кількість елементів по колу. Проте, в нескінченному випадку ми не можемо користуватися безпосереднім подальшим відношенням елементів; замість цього ми користуємося потрійним відношенням, яке означає, що елементи a, b, c з'являються один за одним (не обов'язково безпосередньо), оскільки ми йдемо по колу. З аргументів потрійного відношення [a, b, c] можна розглядати циклічний порядок як однопараметричне сімейство бінарних відношень порядку, які називаються розрізи, або двохпараметричним сімейством підмножин K, що носить назву інтервали.

Потрійне відношення[ред.ред. код]

Загальне визначення виглядає наступним чином: циклічний порядок на множині X є відношення CX3, написане [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, [ ]), кожен елемент якої aK визначає природний лінійний порядок <a на залишку множини Ka за наступним правилом: x <a y тоді і тільки тоді, коли [a, x, y].

Крім того, <a може бути розширена додаванням в якості a найменшого елемента, отриманого лінійного порядку на K. Його називають головним розрізом з найменшим елементом a.

Інтервали[ред.ред. код]

З урахуванням двох елементів abK, відкритий інтервал від a до b, записується як (a, b), є множина всіх xK таких, що [a, x, b]. Система відкритих інтервалів повністю визначає циклічний порядок і може бути використана в якості альтернативного визначення циклічних відношень порядку.

Інтервал (a, b) має натуральний лінійний порядок <a. Можна визначити напівзакриті і закриті інтервали [a, b), (a, b] та [a, b] приєднанням a в якості найменшого елемента і/або b як найбільший елемент. Як окремий випадок відкритого інтервалу розглядається інтервал (a, a) і визначається як розріз Ka.

В цілому, власна підмножина S з K називається опуклою, якщо вона містить інтервал між кожною парою точок: для abS, або (a, b), або (b, a) і також є в S. Опуклу множину лінійно впорядковано розрізом <x для будь-якого x не в множині. Це впорядкування не залежить від вибору x.

Монотонні функції[ред.ред. код]

"Циклічний порядок = організація в колі" - ідея, яка працює, тому що будь-яка підмножина циклу сама по собі є циклом. Для того, щоб користуватися цією ідеєю, щоб ввести циклічні порядки на множинах, які не є насправді підмножинами одиничного кола в площині, необхідно розглянути функції між множинами.

Функція між двома циклічно впорядкованими множинами f : XY називається монотонною функцією або гомоморфізмом, якщо вона визначає порядок на 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 : XY є вкладенням. Загалом, ін'єктивна функція f з невизначеної множини X в циклі Y індукує унікальний циклічний порядок на X, який робить f вкладенням.

Додаткові конструкції[ред.ред. код]

Розгортання циклу[ред.ред. код]

Починаючи з циклічно впорядкованої множини K можна утворити лінійний порядок розгорнувши його вздовж нескінченної лінії. Це відображає інтуїтивне поняття відстеження скільки разів ми проходимо по колу. Формально лінійний порядок визначається на декартовому добутку Z × K, де Z це множина цілих чисел, які утворені шляхом фіксації елементів a і вимагаючи, щоб для всіх i:

Якщо [a, x, y], то ai < xi < yi < ai + 1.

Наприклад, місяці січня 2014, травня 2014, вересня 2014, і січня 2015 відбуватимуться в такому порядку.

Зворотна побудова починається з лінійно упорядкованої множини і скручує її в циклічно впорядковану множину. Маючи лінійно впорядковану множину L і бієкцію T : LL, яка зберігає порядок, з необмеженими орбітами, орбіти простору L / T циклічно відсортовані за вимогою:

Якщо a < b < c < T(a), то [[a], [b], [c]].

Зокрема, можна поновити K шляхом визначення T(xi) = xi + 1 on Z × K.

Лексикографічний добуток[ред.ред. код]

CyclicLinearProductLabels.svg

Маючи циклічно впорядковану множину (K, [ ]) і лінійно упорядковану множину (L, <), (повний) лексикографічний добуток - це циклічний порядок на добутку множин K × L, визначається як [(a, x), (b, y), (c, z)], якщо виконуються наступні твердження:

  • [a, b, c]
  • a = bc and x < y
  • b = ca and y < z
  • c = ab and z < x
  • a = b = c and [x, y, z]

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

Пов'язані структури[ред.ред. код]

Групи[ред.ред. код]

Циклічно впорядкована група - множина як з груповою структурою, так і з циклічним порядком, що лівий і правий добуток зберігає циклічний порядок. Циклічно впорядковані групи уперше глибоко вивчав Ладіслав Рігер в 1947 році. Вони є узагальненням циклічних груп: нескінченної циклічної групи Z і скінченної циклічної групи Z/n. Так як лінійний порядок індукує циклічний порядок, циклічно впорядковані групи є також узагальненням лінійно впорядкованих груп: дійсні числа R, раціональні числа Q тощо. Деякі з найбільш важливих циклічно впорядкованих груп не потрапляють до попередньої категорії: циклічна група T і її підгрупи, такі як підгрупа раціональних точок.

Посилання[ред.ред. код]

Список літератури

Додаткові матеріали[ред.ред. код]

Див. також[ред.ред. код]