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

У математиці, циклічний порядок являє собою спосіб організації множини об'єктів у колі. На відміну від більшості структур в теорії порядку, циклічний порядок не може бути змодельований як бінарне відношення «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⁻¹ з 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]

Аксіоми названо по аналогії з аксіомами асиметрії, транзитивності та повноти для бінарного відношення, які разом визначають строгий лінійний порядок.

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

Враховуючи лінійний порядок < на множині 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 ≠ b ∈ K, відкритий інтервал від a до b, записується як (a, b), є множина всіх x ∈ K таких, що [a, x, b]. Система відкритих інтервалів повністю визначає циклічний порядок і може бути використана як альтернативне визначення циклічних відношень порядку.

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

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

Монотонні функції

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

Функція між двома циклічно впорядкованими множинами 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 вкладенням.

Додаткові конструкції

Розгортання циклу

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

Якщо [a, x, y], то a_i < x_i < y_i < a_{i + 1}.

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

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

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

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

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

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

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

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

Пов'язані структури

Групи

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

Див. також

• Цикл
• Лінійний_порядок
• Проєктивно розширена числова пряма

Посилання

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

• Bowditch, Brian H. (November 2004), Planar groups and the Seifert conjecture, Journal für die reine und angewandte Mathematik, 576: 11—62, doi:10.1515/crll.2004.084, процитовано 31 травня 2011
• Brown, Kenneth S. (February 1987), Finiteness properties of groups (PDF), Journal of Pure and Applied Algebra, 44 (1–3): 45—75, doi:10.1016/0022-4049(87)90015-6, процитовано 21 травня 2011
• Calegari, Danny; Dunfield, Nathan M. (April 2003), Laminations and groups of homeomorphisms of the circle, Inventiones Mathematicae, 152 (1): 149—204, arXiv:math/0203192, doi:10.1007/s00222-002-0271-6
• Černák, Štefan (2001), Cantor extension of a half linearly cyclically ordered group (PDF), Discussiones Mathematicae - General Algebra and Applications, 21 (1): 31—46, процитовано 22 травня 2011^{[недоступне посилання з травня 2019]}
• Courcelle, Bruno (21 серпня 2003), 2.3 Circular order, у Berwanger, Dietmar; Grädel, Erich (ред.), Problems in Finite Model Theory (PDF), с. 12, архів оригіналу (PDF) за 27 травня 2011, процитовано 15 травня 2011
• Evans, David M.; Macpherson, Dugald; Ivanov, Alexandre A. (1997), Finite Covers, у Evans, David M. (ред.), Model theory of groups and automorphism groups: Blaubeuren, August 1995, London Mathematical Society Lecture Note Series, т. 244, Cambridge University Press, с. 1—72, ISBN 0-521-58955-X, процитовано 5 травня 2011
• Freudenthal, Hans; Bauer, A. (1974), Geometry—A Phenomenological Discussion, у Behnke, Heinrich; Gould, S. H. (ред.), Fundamentals of mathematics, т. 2, MIT Press, с. 3–28, ISBN 0-262-02069-6
• Freudenthal, Hans (1983), Didactical phenomenology of mathematical structures, D. Reidel, ISBN 90-277-1535-1
• Huntington, Edward V. (15 лютого 1924), Sets of Completely Independent Postulates for Cyclic Order (PDF), Proceedings of the National Academy of Sciences of the United States of America, 10 (2): 74—78, процитовано 8 травня 2011
• Huntington, Edward V. (July 1935), Inter-Relations Among the Four Principal Types of Order (PDF), Transactions of the American Mathematical Society, 38 (1): 1—9, doi:10.1090/S0002-9947-1935-1501800-1, процитовано 8 травня 2011
• Isli, Amar; Cohn, Anthony G. (1998), An algebra for cyclic ordering of 2D orientations, AAAI '98/IAAI '98 Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence (PDF), ISBN 0-262-51098-7, процитовано 23 травня 2011
• Kuhlmann, Salma; Marshall, Murray; Osiak, Katarzyna (1 червня 2011), Cyclic 2-structures and spaces of orderings of power series fields in two variables (PDF), Journal of Algebra, 335 (1): 36—48, doi:10.1016/j.jalgebra.2011.02.026, архів оригіналу (PDF) за 21 липня 2011, процитовано 11 травня 2011
• Kulpeshov, Beibut Sh. (December 2006), On ℵ₀-categorical weakly circularly minimal structures, Mathematical Logic Quarterly, 52 (6): 555—574, doi:10.1002/malq.200610014
• Kulpeshov, Beibut Sh. (March 2009), Definable functions in the ℵ₀-categorical weakly circularly minimal structures, Siberian Mathematical Journal, 50 (2): 282—301, doi:10.1007/s11202-009-0034-3 Translation of Kulpeshov (2009), Определимые функции в ℵ₀-категоричных слабо циклически минимальных структурах, Sibirskiĭ Matematicheskiĭ Zhurnal, 50 (2): 356—379, процитовано 24 травня 2011
• Kulpeshov, Beibut Sh.; Macpherson, H. Dugald (July 2005), Minimality conditions on circularly ordered structures, Mathematical Logic Quarterly, 51 (4): 377—399, doi:10.1002/malq.200410040, MR 2150368
• Macpherson, H. Dugald (2011), A survey of homogeneous structures (PDF), Discrete Mathematics, doi:10.1016/j.disc.2011.01.024, процитовано 28 квітня 2011
• McMullen, Curtis T. (2009), Ribbon R-trees and holomorphic dynamics on the unit disk (PDF), Journal of Topology, 2 (1): 23—76, doi:10.1112/jtopol/jtn032, процитовано 15 травня 2011
• Morton, James; Pachter, Lior; Shiu, Anne; Sturmfels, Bernd (January 2007), The Cyclohedron Test for Finding Periodic Genes in Time Course Expression Studies, Statistical Applications in Genetics and Molecular Biology, 6 (1), arXiv:q-bio/0702049, doi:10.2202/1544-6115.1286
• Mosher, Lee (1996), A user's guide to the mapping class group: once-punctured surfaces, у Baumslag, Gilbert (ред.), Geometric and computational perspectives on infinite groups, DIMACS, т. 25, AMS Bookstore, с. 101—174, arXiv:math/9409209, ISBN 0-8218-0449-9
• Świerczkowski, S. (1959a), On cyclically ordered groups (PDF), Fundamenta Mathematicae, 47: 161—166, процитовано 2 травня 2011
• Tararin, Valeri Mikhailovich (2001), On Automorphism Groups of Cyclically Ordered Sets, Siberian Mathematical Journal, 42 (1): 190—204, doi:10.1023/A:1004866131580. Translation of Tamarin (2001), О группах автоморфизмов циклически упорядоченных множеств, Sibirskii Matematicheskii Zhurnal (Russian) , 42 (1): 212—230, процитовано 30 квітня 2011
• Tararin, Valeri Mikhailovich (2002), On c-3-Transitive Automorphism Groups of Cyclically Ordered Sets, Mathematical Notes, 71 (1): 110—117, doi:10.1023/A:1013934509265. Translation of Tamarin (2002), О c-3-транзитивных группах автоморфизмов циклически упорядоченных множеств, Matematicheskie Zametki, 71 (1): 122—129, процитовано 22 травня 2011
• Weinstein, Tilla (July 1996), An introduction to Lorentz surfaces, De Gruyter Expositions in Mathematics, т. 22, Walter de Gruyter, ISBN 978-3-11-014333-1

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

• Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1998), Notes on Infinite Permutation Groups, Lecture Notes in Mathematics, т. 1698, Springer, с. 108—109, doi:10.1007/BFb0092550
• Bodirsky, Manuel; Pinsker, Michael (to appear), Reducts of Ramsey Structures, Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics, AMS, arXiv:1105.6073
• Cameron, Peter J. (June 1976), Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, 148 (2): 127—139, doi:10.1007/BF01214702
• Cameron, Peter J. (June 1977), Cohomological aspects of two-graphs, Mathematische Zeitschrift, 157 (2): 101—119, doi:10.1007/BF01215145
• Courcelle, Joost; Engelfriet (April 2011), Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach (PDF), Cambridge University Press, процитовано 17 травня 2011
• Droste, M.; Giraudet, M.; Macpherson, D. (March 1995), Periodic Ordered Permutation Groups and Cyclic Orderings, Journal of Combinatorial Theory, Series B, 63 (2): 310—321, doi:10.1006/jctb.1995.1022
• Ivanov, A. A. (January 1999), Finite Covers, Cohomology and Homogeneous Structures, Proceedings of the London Mathematical Society, 78 (1): 1—28, doi:10.1112/S002461159900163X
• Kennedy, Christine Cowan (August 1955), On a cyclic ternary relation ... (M.A. Thesis), Tulane University, OCLC 16508645
• Kónya, Eszter Herendine (2006), A mathematical and didactical analysis of the concept of orientation (PDF), Teaching Mathematics and Computer Science, 4 (1): 111—130, архів оригіналу (PDF) за 26 липня 2011, процитовано 17 травня 2011
• Kónya, Eszter Herendine (2008), Geometrical transformations and the concept of cyclic ordering, у Maj, Bożena; Pytlak, Marta; Swoboda, Ewa (ред.), Supporting Independent Thinking Through Mathematical Education (PDF), Rzeszów University Press, с. 102—108, ISBN 978-83-7338-420-0, процитовано 17 травня 2011
• Leloup, Gérard (February 2011), Existentially equivalent cyclic ultrametric spaces and cyclically valued groups (PDF), Logic Journal of the IGPL, 19 (1): 144—173, doi:10.1093/jigpal/jzq024, процитовано 30 квітня 2011
• Marongiu, Gabriele (1985), Some remarks on the ℵ₀-categoricity of circular orderings, Unione Matematica Italiana. Bollettino. B. Serie VI (Italian) , 4 (3): 883—900, MR 0831297
• McCleary, Stephen; Rubin, Matatyahu (6 жовтня 2005), Locally Moving Groups and the Reconstruction Problem for Chains and Circles, arXiv:math/0510122
• Müller, G. (1974), Lineare und zyklische Ordnung, Praxis der Mathematik, 16: 261—269, MR 0429660
• Rubin, M. (1996), Locally moving groups and reconstruction problems, у Holland, W. Charles (ред.), Ordered groups and infinite permutation groups, Mathematics and Its Applications, т. 354, Kluwer, с. 121—157, ISBN 978-0-7923-3853-6
• Świerczkowski, S. (1956), On cyclic ordering relations, Bulletin de l'Académie Polonaise des Sciences, Classe III, 4: 585—586
• Świerczkowski, S. (1959b), On cyclically ordered intervals of integers (PDF), Fundamenta Mathematicae, 47: 167—172, процитовано 2 травня 2011
• Truss, J.K. (July 1992), Generic Automorphisms of Homogeneous Structures, Proceedings of the London Mathematical Society, s3-65 (1): 121—141, doi:10.1112/plms/s3-65.1.121