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

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

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

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

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

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

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

Зворотна побудова починається з лінійно упорядкованої множини і скручує її в циклічно впорядковану множину. Маючи лінійно впорядковану множину 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, http://www.warwick.ac.uk/~masgak/abstracts/pla.html, процитовано 31 May 2011 
• Brown, Kenneth S. (February 1987), «Finiteness properties of groups», Journal of Pure and Applied Algebra 44 (1–3): 45–75, doi:10.1016/0022-4049(87)90015-6, http://www.math.cornell.edu/~kbrown/scan/1987.0044.0045.pdf, процитовано 21 May 2011 
• Calegari, Danny; Dunfield, Nathan M. (April 2003), «Laminations and groups of homeomorphisms of the circle», Inventiones Mathematicae 152 (1): 149–204, doi:10.1007/s00222-002-0271-6 
• Černák, Štefan (2001), «Cantor extension of a half linearly cyclically ordered group», Discussiones Mathematicae - General Algebra and Applications 21 (1): 31–46, http://lord.uz.zgora.pl:7777/bib/bibwww.pdf?nIdA=4493, процитовано 22 May 2011 
• Courcelle, Bruno (21 August 2003), «2.3 Circular order», у Berwanger, Dietmar; Grädel, Erich, Problems in Finite Model Theory, p. 12, http://www-mgi.informatik.rwth-aachen.de/FMT/problems.pdf, процитовано 15 May 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, pp. 1–72, ISBN 0-521-58955-X, http://www.amsta.leeds.ac.uk/Pure/preprints/hdm/hdm5.ps, процитовано 5 May 2011 
• Freudenthal, Hans; Bauer, A. (1974), «Geometry—A Phenomenological Discussion», у Behnke, Heinrich; Gould, S. H., Fundamentals of mathematics, 2, MIT Press, pp. 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 February 1924), «Sets of Completely Independent Postulates for Cyclic Order», Proceedings of the National Academy of Sciences of the United States of America 10 (2): 74–78, http://www.pnas.org/content/10/2/74.full.pdf, процитовано 8 May 2011 
• Huntington, Edward V. (July 1935), «Inter-Relations Among the Four Principal Types of Order», Transactions of the American Mathematical Society 38 (1): 1–9, doi:10.1090/S0002-9947-1935-1501800-1, http://www.ams.org/journals/tran/1935-038-01/S0002-9947-1935-1501800-1/S0002-9947-1935-1501800-1.pdf, процитовано 8 May 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, ISBN 0-262-51098-7, https://www.aaai.org/Papers/AAAI/1998/AAAI98-091.pdf, процитовано 23 May 2011 
• Kuhlmann, Salma; Marshall, Murray; Osiak, Katarzyna (1 June 2011), «Cyclic 2-structures and spaces of orderings of power series fields in two variables», Journal of Algebra 335 (1): 36–48, doi:10.1016/j.jalgebra.2011.02.026, http://math.usask.ca/~marshall/r%5B%5Bx,y%5D%5D_20,11.pdf, процитовано 11 May 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, http://mi.mathnet.ru/eng/smj1965, процитовано 24 May 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 
• Macpherson, H. Dugald (2011), «A survey of homogeneous structures», Discrete Mathematics, doi:10.1016/j.disc.2011.01.024, http://www.amsta.leeds.ac.uk/pure/staff/macpherson/homog_final2.pdf, процитовано 28 April 2011 
• McMullen, Curtis T. (2009), «Ribbon R-trees and holomorphic dynamics on the unit disk», Journal of Topology 2 (1): 23–76, doi:10.1112/jtopol/jtn032, http://www.math.harvard.edu/~ctm/papers/home/text/papers/rtrees/rtrees.pdf, процитовано 15 May 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), 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, pp. 101–174, ISBN 0-8218-0449-9 
• Świerczkowski, S. (1959a), «On cyclically ordered groups», Fundamenta Mathematicae 47: 161–166, http://matwbn.icm.edu.pl/ksiazki/fm/fm47/fm4718.pdf, процитовано 2 May 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), «О группах автоморфизмов циклически упорядоченных множеств» (Russian), Sibirskii Matematicheskii Zhurnal 42 (1): 212–230, http://mi.mathnet.ru/eng/smj1484, процитовано 30 April 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, http://mi.mathnet.ru/eng/mz333, процитовано 22 May 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, pp. 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 
• 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, Cambridge University Press, http://www.labri.fr/perso/courcell/Book/TheBook.pdf, процитовано 17 May 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», Teaching Mathematics and Computer Science 4 (1): 111–130, http://tmcs.math.klte.hu/Contents/2006-Vol-IV-Issue-I/konya-abstract.pdf, процитовано 17 May 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, Rzeszów University Press, pp. 102–108, ISBN 978-83-7338-420-0, http://www.cme.rzeszow.pl/pdf/part_2_3.pdf, процитовано 17 May 2011 
• Leloup, Gérard (February 2011), «Existentially equivalent cyclic ultrametric spaces and cyclically valued groups», Logic Journal of the IGPL 19 (1): 144–173, doi:10.1093/jigpal/jzq024, http://math.usask.ca/fvk/leloup3.pdf, процитовано 30 April 2011 
• Marongiu, Gabriele (1985), «Some remarks on the ℵ₀-categoricity of circular orderings» (Italian), Unione Matematica Italiana. Bollettino. B. Serie VI 4 (3): 883–900 
• McCleary, Stephen; Rubin, Matatyahu (6 October 2005), Locally Moving Groups and the Reconstruction Problem for Chains and Circles 
• Müller, G. (1974), «Lineare und zyklische Ordnung», Praxis der Mathematik 16: 261–269 
• Rubin, M. (1996), «Locally moving groups and reconstruction problems», у Holland, W. Charles, Ordered groups and infinite permutation groups, Mathematics and Its Applications, 354, Kluwer, pp. 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», Fundamenta Mathematicae 47: 167–172, http://matwbn.icm.edu.pl/ksiazki/fm/fm47/fm4719.pdf, процитовано 2 May 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 

Див. також

• Цикл
• Лінійний_порядок