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

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

Означення ред.

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

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

Загальне визначення виглядає наступним чином: циклічний порядок на множині $X$ є відношення $C \subset X 3$ , написане $[a, b, c]$ , яке задовольняє наступним аксіомам:

Циклічність: Якщо $[a, b, c]$ , то $[b, c, a]$
Асиметрія: Якщо $[a, b, c]$ , то не $[c, b, a]$
Транзитивність: якщо $[a, b, c]$ і $[a, c, d]$ , то $[a, b, d]$
Повнота: Якщо $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 \in K$ визначає природний лінійний порядок $< a$ на залишку множини $K ∖ a$ за наступним правилом: $x < a y$ тоді і тільки тоді, коли $[a, x, y]$ .

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

Інтервали ред.

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

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

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

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

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

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

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

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

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

Якщо

[a, x, y]

, то

a i < x i < y i < a i + 1

.

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

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

Якщо

a < b < c < T (a)

, то [[

a

], [

b

], [

c

]].

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

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

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

$[a, b, c]$
$a = b \neq c$ and $x < y$
$b = c \neq a$ and $y < z$
$c = a \neq b$ and $z < x$
$a = b = c$ and $[x, y, z]$

Лексикографічний добуток $K \times 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