Циклічний порядок У математиці циклічний порядок являє собою спосіб організації множини об єктів у колі На відміну від б

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

Функція називається вкладеною, якщо воно є монотонною і ін'єктивною. Еквівалентно, вкладена функція, яка призводить до порядку на $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$ :

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

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

Зокрема, можна поновити $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. 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. Discussiones Mathematicae - General Algebra and Applications 21 (1): 31–46. Процитовано 22 травня 2011. ^{[недоступне посилання з травня 2019]}
Courcelle, Bruno (21 серпня 2003). . У Berwanger, Dietmar; Grädel, Erich. Problems in Finite Model Theory. с. 12. Архів оригіналу за 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. 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. 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. ISBN 0-262-51098-7. Процитовано 23 травня 2011.
Kuhlmann, Salma; Marshall, Murray; Osiak, Katarzyna (1 червня 2011). . Journal of Algebra 335 (1): 36–48. doi:10.1016/j.jalgebra.2011.02.026. Архів оригіналу за 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. MR 2150368. doi:10.1002/malq.200410040.
Macpherson, H. Dugald (2011). A survey of homogeneous structures. 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. 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. ISBN 0-8218-0449-9. arXiv:math/9409209.
Świerczkowski, S. (1959a). On cyclically ordered groups. 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. 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). . Teaching Mathematics and Computer Science 4 (1): 111–130. Архів оригіналу за 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. 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. 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. 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.