www.wikidata.uk-ua.nina.az

Частково впорядкована множина poset англ partially ordered set це множина P displaystyle P з заданим частковим порядком

Частково впорядкована множина

Частково впорядкована множина (poset — англ. partially ordered set) — це множина з заданим частковим порядком (антисиметричним передпорядком), тобто з бінарним відношенням, що є транзитивним, рефлексивним та антисиметричним. Позначається

Додатні числа впорядковані за подільністю
Діаграма Гассе дільників числа 60, частково впорядкована за подільністю
Діаграма Гассе усіх підмножин триелементної множини {x, y, z}, які впорядковані відношенням включення множин.

Скінченні частково впорядковані множини графічно зображаються діаграмами Гассе.

Визначення Редагувати

Частковим порядком, на множині називається бінарне відношення , визначене деякою множиною ), яке задовольняє наступні умови:

Терміни та позначення Редагувати

Відношення часткового порядку зазвичай позначають символом , за аналогією з відношенням «менше або дорівнює» на множині дійсних чисел. При цьому, якщо , то кажуть, що елемент не перевершує , або, що підпорядкований .

Якщо і , то пишуть , і кажуть, що менше , або, що строго підпорядковане .

Іноді, щоб відрізнити довільний порядок на деякій множині від відомого відношення «менше або дорівнює» на множині дійсних чисел, замість і використовують спеціальні символи і відповідно.

Строгий і нестрогий порядок Редагувати

Відношення, що задовольняє умовам рефлексивності, транзитивності і антисиметричності, також називають нестрогим, або рефлексивним порядком. Якщо умову рефлексивності замінити на умову антирефлексивності (тоді властивості антисиметричності зміняться на асиметричність):

то отримаємо визначення строгого, або антирефлексивного порядку.

Пов'язані визначення Редагувати

Незрівняні елементи Редагувати

Якщо і  — дійсні числа, то має місце тільки одне з наступних співвідношень :

У разі, якщо і  — елементи довільної частково впорядкованої множини, то існує четверта логічна можливість: не виконується жодне з вказаних трьох співвідношень. В цьому випадку елементи і називаються непорівнюваними. Наприклад, якщо  — множина дійснозначних функцій на відрізку , то елементи і будуть непорівнювані. Можливість існування непорівнюваних елементів пояснює сенс терміну «частково впорядкована множина».

Мінімальні/максимальні та найменші/найбільші елементи Редагувати

Максимальні та мінімальні елементи

Через те, що в частково впорядкованій множині можуть бути пари непорівнюваних елементів, вводяться два різні визначення: мінімальний елемент і найменший елемент.

Елемент називається мінімальним (англ. minimal element), якщо не існує елемента . Іншими словами  — мінімальний елемент, якщо для будь-якого елемента або , або , або і непорівнювані.

Елемент називається найменшим ((англ. least element, lower bound (opp. upper bound)), якщо для будь-якого елементу має місце нерівність . Очевидно, всякий найменший елемент є також мінімальним, але зворотне в загальному випадку є невірним: мінімальний елемент може і не бути найменшим, якщо існують елементи , непорівнювані з .

Очевидно, що якщо в множині існує найменший елемент, то він єдиний. А ось мінімальних елементів може бути декілька. Як приклад, розглянемо множину натуральних чисел без одиниці, впорядковану по відношенню подільності . Тут мінімальними елементами будуть прості числа, а ось найменшого елементу не існує.

Аналогічно вводяться поняття максимального (англ. maximal element) і найбільшого (англ. greatest element) елементів.

Верхні та нижні грані Редагувати

Нехай  — підмножина частково впорядкованої великої множини . Елемент називається верхньою гранню (англ. upper bound) , якщо будь-який елемент не перевершує . Аналогічно вводиться поняття нижньої грані (англ. lower bound) множини .

Будь-який елемент, більший, ніж деяка верхня грань , також буде верхньою гранню . А будь-який елемент, менший, ніж деяка нижня грань , також буде нижньою гранню . Ці міркування ведуть до введення понять найменшої верхньої грані (англ. least upper bound) і найбільшої нижньої грані (англ. greatest lower bound).

Верхня і нижня множина Редагувати

Елементи верхньої множини відмічені зеленим

Для елементу частково впорядкованої множини верхньою множиною (англ. upper set, upset) називається множина усіх елементів, яким передує ().

Двоїстим чином визначається нижня множина (англ. down set, lower set), як множина усіх елементів, передуючих заданому : .

Спеціальні типи частково впорядкованих множин Редагувати

Лінійно впорядковані множини Редагувати

Нехай  — частково впорядкована множина. Якщо в будь-які два елементи порівнянні, то множина називається лінійно впорядкованою (англ. linearly ordered set). Лінійно впорядковану множину також називають абсолютно впорядкованою (англ. totally ordered set), або просто, впорядкованою множиною. Таким чином, в лінійно впорядкованій множині для будь-яких двох елементів і має місце одне і тільки одне зі співвідношень: або , або , або .

Також всяку лінійно впорядковану підмножину частково впорядкованої множини називають ланцюгом (англ. chain), тобто ланцюг в частково впорядкованій множині  — така його підмножина, в якій будь-які два елементи порівнювані.

З наведених вище прикладів частково впорядкованих множин тільки множина дійсних чисел є лінійно впорядкованою. Множина дійснозначних функцій на відрізку (за умови ), булеан (при ), натуральні числа з відношенням подільності — не є лінійно впорядкованими.

Цілком впорядковані множини Редагувати

Лінійно впорядкована множина називається цілком впорядкованою (англ. well-ordered), якщо кожна його непорожня підмножина має найменший елемент. Такий порядок на множині називається повним порядком (англ. well-order), в контексті, де його неможливо сплутати з повним порядком в сенсі повних частково впорядкованих множин, (англ. complete order).

Класичний приклад цілком впорядкованої множини — множина натуральних чисел . Твердження про те, що будь-яка непорожня підмножина містить найменший елемент, рівносильно принципу математичної індукції. Як приклад лінійно впорядкованої, але не цілком впорядкованої множини можна навести множину невід'ємних чисел, впорядковану природним чином . Дійсно, його підмножина не має найменшого елемента.

Цілком впорядковані множини грають виключно важливу роль в загальній теорії множин.

Повна частково впорядкована множина Редагувати

Повна частково впорядкована множина (англ. complete partial ordered, ω-complete partial ordered) — частково впорядкована множина, у якої є дно — єдиний елемент, який передує будь-якому іншому елементу і у кожної спрямованої підмножини, у якої є точна верхня межа. Повні частково впорядковані множини застосовуються в λ-обчисленнях і інформатиці, зокрема, на них вводиться топологія Скотта, на основі якої будується несуперечлива модель λ-обчислення і денотаційна семантика обчислень. Спеціальним випадком повної частково впорядкованої множини є повні ґратки — якщо будь-яка підмножина, не обов'язково спрямована, має точну верхню грань, то вона виявляється повними ґратками.

Впорядкована множина тоді і тільки тоді є повною частково впорядкованою, коли будь-яка функція , монотонна відносно порядку володіє хоча б одною нерухомою точкою: .

Будь-яку множину можна перетворити на повну частково впорядковану виділенням дна і визначенням порядку як і для всіх елементів множини .

Теореми про частково впорядковані множини Редагувати

До числа фундаментальних теорем про частково впорядковані множини відносяться принцип максимуму Гаусдорфа і лема Куратовського — Цорна, які є еквівалентними аксіомі вибору.

Приклади Редагувати

  • Множина дійсних чисел із звичайним відношенням порядку є лінійно впорядкованою множиною.
  • На множині натуральних чисел визначимо відношення порядку за подільністю, тобто тоді і тільки тоді, коли є дільником Таким чином ми отримаємо частково впорядковану множину. Наведені вище аксіоми справджуються тому, що будь-яке натуральне число є своїм дільником, два числа, які є дільниками одне одного, збігаються, і, нарешті, якщо є дільником а є дільником то є дільником Ця множина не є лінійно впорядкованою, наприклад, жодне з чисел 2,3 не є дільником іншого. При цьому 1 є дільником будь-якого натурального числа, тому воно є найменшим елементом цієї частково упорядкованої множини.
  • Будь-яка множина перетворюється на частково впорядковану множину, якщо визначити на ній таке відношення порядку:

У цьому разі можна порівняти два елементи , лише коли вони збігаються. Така частково впорядкована множина називається антиланцюгом.

  • Нехай  — це довільна множина, а  — це множина всіх підмножин (булеан). Визначимо на частковий порядок за включенням, тобто означає, що де  — дві підмножини

якщо або або або інакше кажучи, якщо у послідовності перший ненульовий елемент — додатний. У такий спосіб перетворюється на лінійно впорядковану множину, яка відіграє провідну роль у комп'ютерній алгебрі (див. базис Гребнера).

Див. також Редагувати

Примітки Редагувати

  1. Колмогоров, 2004.
  2. Колмогоров, 2004, с. 38.
  3. Колмогоров, 2004, с. 40.
  4. Барендрегт, 1985, с. 23.

Джерела Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Chastkovo vporyadkovana mnozhina poset angl partially ordered set ce mnozhina P displaystyle P z zadanim chastkovim poryadkom displaystyle leqslant antisimetrichnim peredporyadkom tobto z binarnim vidnoshennyam sho ye tranzitivnim refleksivnim ta antisimetrichnim Poznachayetsya P displaystyle P leqslant Dodatni chisla vporyadkovani za podilnistyuDiagrama Gasse dilnikiv chisla 60 chastkovo vporyadkovana za podilnistyuDiagrama Gasse usih pidmnozhin trielementnoyi mnozhini x y z yaki vporyadkovani vidnoshennyam vklyuchennya mnozhin Skinchenni chastkovo vporyadkovani mnozhini grafichno zobrazhayutsya diagramami Gasse Zmist 1 Viznachennya 1 1 Termini ta poznachennya 1 2 Strogij i nestrogij poryadok 2 Pov yazani viznachennya 2 1 Nezrivnyani elementi 2 2 Minimalni maksimalni ta najmenshi najbilshi elementi 2 3 Verhni ta nizhni grani 2 4 Verhnya i nizhnya mnozhina 3 Specialni tipi chastkovo vporyadkovanih mnozhin 3 1 Linijno vporyadkovani mnozhini 3 2 Cilkom vporyadkovani mnozhini 3 3 Povna chastkovo vporyadkovana mnozhina 4 Teoremi pro chastkovo vporyadkovani mnozhini 5 Prikladi 6 Div takozh 7 Primitki 8 DzherelaViznachennya RedaguvatiChastkovim poryadkom na mnozhini S displaystyle S nbsp nazivayetsya binarne vidnoshennya displaystyle leqslant nbsp viznachene deyakoyu mnozhinoyu R S S displaystyle R leqslant subset S times S nbsp yake zadovolnyaye nastupni umovi 1 Tranzitivnist a b c a b b c a c displaystyle forall a b c quad a leqslant b wedge b leqslant c Rightarrow a leqslant c nbsp Refleksivnist a a a displaystyle forall a quad a leqslant a nbsp Antisimetrichnist a b a b b a a b displaystyle forall a b quad a leqslant b wedge b leqslant a Rightarrow a b nbsp Termini ta poznachennya Redaguvati Vidnoshennya chastkovogo poryadku zazvichaj poznachayut simvolom displaystyle leqslant nbsp za analogiyeyu z vidnoshennyam menshe abo dorivnyuye na mnozhini dijsnih chisel Pri comu yaksho a b displaystyle a leqslant b nbsp to kazhut sho element a displaystyle a nbsp ne perevershuye b displaystyle b nbsp abo sho a displaystyle a nbsp pidporyadkovanij b displaystyle b nbsp Yaksho a b displaystyle a leqslant b nbsp i a b displaystyle a neq b nbsp to pishut a lt b displaystyle a lt b nbsp i kazhut sho a displaystyle a nbsp menshe b displaystyle b nbsp abo sho a displaystyle a nbsp strogo pidporyadkovane b displaystyle b nbsp Inodi shob vidrizniti dovilnij poryadok na deyakij mnozhini vid vidomogo vidnoshennya menshe abo dorivnyuye na mnozhini dijsnih chisel zamist displaystyle leqslant nbsp i lt displaystyle lt nbsp vikoristovuyut specialni simvoli displaystyle preccurlyeq nbsp i displaystyle prec nbsp vidpovidno Strogij i nestrogij poryadok Redaguvati Vidnoshennya sho zadovolnyaye umovam refleksivnosti tranzitivnosti i antisimetrichnosti takozh nazivayut nestrogim abo refleksivnim poryadkom Yaksho umovu refleksivnosti zaminiti na umovu antirefleksivnosti todi vlastivosti antisimetrichnosti zminyatsya na asimetrichnist a a f a displaystyle forall a neg a varphi a nbsp to otrimayemo viznachennya strogogo abo antirefleksivnogo poryadku Pov yazani viznachennya RedaguvatiNezrivnyani elementi Redaguvati Yaksho a displaystyle a nbsp i b displaystyle b nbsp dijsni chisla to maye misce tilki odne z nastupnih spivvidnoshen a lt b a b b lt a displaystyle a lt b qquad a b qquad b lt a nbsp U razi yaksho a displaystyle a nbsp i b displaystyle b nbsp elementi dovilnoyi chastkovo vporyadkovanoyi mnozhini to isnuye chetverta logichna mozhlivist ne vikonuyetsya zhodne z vkazanih troh spivvidnoshen V comu vipadku elementi a displaystyle a nbsp i b displaystyle b nbsp nazivayutsya neporivnyuvanimi Napriklad yaksho M displaystyle M nbsp mnozhina dijsnoznachnih funkcij na vidrizku 0 1 displaystyle 0 1 nbsp to elementi f x x displaystyle f x x nbsp i g x 1 x displaystyle g x 1 x nbsp budut neporivnyuvani Mozhlivist isnuvannya neporivnyuvanih elementiv poyasnyuye sens terminu chastkovo vporyadkovana mnozhina Minimalni maksimalni ta najmenshi najbilshi elementi Redaguvati Maksimalni ta minimalni elementi Dokladnishe Maksimalni ta minimalni elementi Dokladnishe Najbilshij ta najmenshij elementCherez te sho v chastkovo vporyadkovanij mnozhini mozhut buti pari neporivnyuvanih elementiv vvodyatsya dva rizni viznachennya minimalnij element i najmenshij element Element a M displaystyle a in M nbsp nazivayetsya minimalnim angl minimal element yaksho ne isnuye elementa b lt a displaystyle b lt a nbsp Inshimi slovami a displaystyle a nbsp minimalnij element yaksho dlya bud yakogo elementa b M displaystyle b in M nbsp abo b gt a displaystyle b gt a nbsp abo b a displaystyle b a nbsp abo b displaystyle b nbsp i a displaystyle a nbsp neporivnyuvani Element a displaystyle a nbsp nazivayetsya najmenshim angl least element lower bound opp upper bound yaksho dlya bud yakogo elementu b M displaystyle b in M nbsp maye misce nerivnist b a displaystyle b geqslant a nbsp Ochevidno vsyakij najmenshij element ye takozh minimalnim ale zvorotne v zagalnomu vipadku ye nevirnim minimalnij element a displaystyle a nbsp mozhe i ne buti najmenshim yaksho isnuyut elementi b displaystyle b nbsp neporivnyuvani z a displaystyle a nbsp Ochevidno sho yaksho v mnozhini isnuye najmenshij element to vin yedinij A os minimalnih elementiv mozhe buti dekilka Yak priklad rozglyanemo mnozhinu N 1 2 3 displaystyle mathbb N setminus 1 2 3 ldots nbsp naturalnih chisel bez odinici vporyadkovanu po vidnoshennyu podilnosti displaystyle mid nbsp Tut minimalnimi elementami budut prosti chisla a os najmenshogo elementu ne isnuye Analogichno vvodyatsya ponyattya maksimalnogo angl maximal element i najbilshogo angl greatest element elementiv Verhni ta nizhni grani Redaguvati Dokladnishe Verhnya ta nizhnya mezhaNehaj A displaystyle A nbsp pidmnozhina chastkovo vporyadkovanoyi velikoyi mnozhini M displaystyle langle M leqslant rangle nbsp Element u M displaystyle u in M nbsp nazivayetsya verhnoyu grannyu angl upper bound A displaystyle A nbsp yaksho bud yakij element a A displaystyle a in A nbsp ne perevershuye u displaystyle u nbsp Analogichno vvoditsya ponyattya nizhnoyi grani angl lower bound mnozhini A displaystyle A nbsp Bud yakij element bilshij nizh deyaka verhnya gran A displaystyle A nbsp takozh bude verhnoyu grannyu A displaystyle A nbsp A bud yakij element menshij nizh deyaka nizhnya gran A displaystyle A nbsp takozh bude nizhnoyu grannyu A displaystyle A nbsp Ci mirkuvannya vedut do vvedennya ponyat najmenshoyi verhnoyi grani angl least upper bound i najbilshoyi nizhnoyi grani angl greatest lower bound Verhnya i nizhnya mnozhina Redaguvati Dokladnishe Verhnya mnozhina nbsp Elementi verhnoyi mnozhini 2 1 2 3 4 1 displaystyle 2 1 2 3 4 uparrow 1 nbsp vidmicheni zelenimDlya elementu m displaystyle m nbsp chastkovo vporyadkovanoyi mnozhini M displaystyle langle M leqslant rangle nbsp verhnoyu mnozhinoyu angl upper set upset nazivayetsya mnozhina M m displaystyle M uparrow m nbsp usih elementiv yakim m displaystyle m nbsp pereduye x M m x displaystyle x in M mid m leqslant x nbsp Dvoyistim chinom viznachayetsya nizhnya mnozhina angl down set lower set yak mnozhina usih elementiv pereduyuchih zadanomu M m d e f x M x m displaystyle M downarrow m stackrel mathrm def x in M mid x leqslant m nbsp Specialni tipi chastkovo vporyadkovanih mnozhin RedaguvatiLinijno vporyadkovani mnozhini Redaguvati Dokladnishe Linijno vporyadkovana mnozhinaNehaj M displaystyle langle M leqslant rangle nbsp chastkovo vporyadkovana mnozhina Yaksho v M displaystyle M nbsp bud yaki dva elementi porivnyanni to mnozhina M displaystyle M nbsp nazivayetsya linijno vporyadkovanoyu angl linearly ordered set Linijno vporyadkovanu mnozhinu takozh nazivayut absolyutno vporyadkovanoyu angl totally ordered set abo prosto vporyadkovanoyu mnozhinoyu 2 Takim chinom v linijno vporyadkovanij mnozhini dlya bud yakih dvoh elementiv a displaystyle a nbsp i b displaystyle b nbsp maye misce odne i tilki odne zi spivvidnoshen abo a lt b displaystyle a lt b nbsp abo a b displaystyle a b nbsp abo b lt a displaystyle b lt a nbsp Takozh vsyaku linijno vporyadkovanu pidmnozhinu chastkovo vporyadkovanoyi mnozhini nazivayut lancyugom angl chain tobto lancyug v chastkovo vporyadkovanij mnozhini M displaystyle langle M leqslant rangle nbsp taka jogo pidmnozhina v yakij bud yaki dva elementi porivnyuvani Z navedenih vishe prikladiv chastkovo vporyadkovanih mnozhin tilki mnozhina dijsnih chisel ye linijno vporyadkovanoyu Mnozhina dijsnoznachnih funkcij na vidrizku a b displaystyle a b nbsp za umovi a lt b displaystyle a lt b nbsp bulean P M displaystyle mathcal P M nbsp pri M 2 displaystyle M geqslant 2 nbsp naturalni chisla z vidnoshennyam podilnosti ne ye linijno vporyadkovanimi Cilkom vporyadkovani mnozhini Redaguvati Dokladnishe Cilkom vporyadkovana mnozhinaLinijno vporyadkovana mnozhina nazivayetsya cilkom vporyadkovanoyu angl well ordered yaksho kozhna jogo neporozhnya pidmnozhina maye najmenshij element 3 Takij poryadok na mnozhini nazivayetsya povnim poryadkom angl well order v konteksti de jogo nemozhlivo splutati z povnim poryadkom v sensi povnih chastkovo vporyadkovanih mnozhin angl complete order Klasichnij priklad cilkom vporyadkovanoyi mnozhini mnozhina naturalnih chisel N displaystyle mathbb N nbsp Tverdzhennya pro te sho bud yaka neporozhnya pidmnozhina N displaystyle mathbb N nbsp mistit najmenshij element rivnosilno principu matematichnoyi indukciyi Yak priklad linijno vporyadkovanoyi ale ne cilkom vporyadkovanoyi mnozhini mozhna navesti mnozhinu nevid yemnih chisel vporyadkovanu prirodnim chinom R x x 0 displaystyle mathbb R x x geqslant 0 nbsp Dijsno jogo pidmnozhina x x gt 1 displaystyle x x gt 1 nbsp ne maye najmenshogo elementa Cilkom vporyadkovani mnozhini grayut viklyuchno vazhlivu rol v zagalnij teoriyi mnozhin Povna chastkovo vporyadkovana mnozhina Redaguvati Povna chastkovo vporyadkovana mnozhina angl complete partial ordered w complete partial ordered chastkovo vporyadkovana mnozhina u yakoyi ye dno yedinij element yakij pereduye bud yakomu inshomu elementu i u kozhnoyi spryamovanoyi pidmnozhini u yakoyi ye tochna verhnya mezha 4 Povni chastkovo vporyadkovani mnozhini zastosovuyutsya v l obchislennyah i informatici zokrema na nih vvoditsya topologiya Skotta na osnovi yakoyi buduyetsya nesuperechliva model l obchislennya i denotacijna semantika obchislen Specialnim vipadkom povnoyi chastkovo vporyadkovanoyi mnozhini ye povni gratki yaksho bud yaka pidmnozhina ne obov yazkovo spryamovana maye tochnu verhnyu gran to vona viyavlyayetsya povnimi gratkami Vporyadkovana mnozhina M displaystyle M nbsp todi i tilki todi ye povnoyu chastkovo vporyadkovanoyu koli bud yaka funkciya f M M displaystyle f colon M rightarrow M nbsp monotonna vidnosno poryadku a b f a f b displaystyle a leqslant b Rightarrow f a leqslant f b nbsp volodiye hocha b odnoyu neruhomoyu tochkoyu x M f x x displaystyle exists x in M f x x nbsp Bud yaku mnozhinu M displaystyle M nbsp mozhna peretvoriti na povnu chastkovo vporyadkovanu vidilennyam dna displaystyle bot nbsp i viznachennyam poryadku displaystyle leqslant nbsp yak m displaystyle bot leqslant m nbsp i m m displaystyle m leqslant m nbsp dlya vsih elementiv m displaystyle m nbsp mnozhini M displaystyle M nbsp Teoremi pro chastkovo vporyadkovani mnozhini RedaguvatiDo chisla fundamentalnih teorem pro chastkovo vporyadkovani mnozhini vidnosyatsya princip maksimumu Gausdorfa i lema Kuratovskogo Corna yaki ye ekvivalentnimi aksiomi viboru Prikladi RedaguvatiMnozhina R displaystyle mathbb R nbsp dijsnih chisel iz zvichajnim vidnoshennyam poryadku ye linijno vporyadkovanoyu mnozhinoyu Naturalni chisla cili chisla racionalni chisla irracionalni chisla tosho vsi ye pidmnozhinami dijsnih chisel tomu utvoryuyut linijno vporyadkovani mnozhini zi zvichajnim vidnoshennyam poryadku Na mnozhini naturalnih chisel N displaystyle mathbb N nbsp viznachimo vidnoshennya poryadku za podilnistyu tobto a b displaystyle a leq b nbsp todi i tilki todi koli a displaystyle a nbsp ye dilnikom b displaystyle b nbsp Takim chinom mi otrimayemo chastkovo vporyadkovanu mnozhinu Navedeni vishe aksiomi spravdzhuyutsya tomu sho bud yake naturalne chislo ye svoyim dilnikom dva chisla yaki ye dilnikami odne odnogo zbigayutsya i nareshti yaksho a displaystyle a nbsp ye dilnikom b displaystyle b nbsp a b displaystyle b nbsp ye dilnikom c displaystyle c nbsp to a displaystyle a nbsp ye dilnikom c displaystyle c nbsp Cya mnozhina ne ye linijno vporyadkovanoyu napriklad zhodne z chisel 2 3 ne ye dilnikom inshogo Pri comu 1 ye dilnikom bud yakogo naturalnogo chisla tomu vono ye najmenshim elementom ciyeyi chastkovo uporyadkovanoyi mnozhini Lancyug z n displaystyle n nbsp elementiv ce linijno vporyadkovana mnozhina z n displaystyle n nbsp elementiv U kombinatorici lancyug yakij skladayetsya z 1 lt 2 lt lt n displaystyle 1 lt 2 lt ldots lt n nbsp poznachayetsya n displaystyle n nbsp abo n displaystyle mathbf n nbsp Bud yaka mnozhina A displaystyle A nbsp peretvoryuyetsya na chastkovo vporyadkovanu mnozhinu yaksho viznachiti na nij take vidnoshennya poryadku a b a b displaystyle a leq b iff a b nbsp U comu razi mozhna porivnyati dva elementi A displaystyle A nbsp lishe koli voni zbigayutsya Taka chastkovo vporyadkovana mnozhina nazivayetsya antilancyugom Nehaj A displaystyle A nbsp ce dovilna mnozhina a W A displaystyle Omega A nbsp ce mnozhina vsih pidmnozhin A displaystyle A nbsp bulean Viznachimo na W A displaystyle Omega A nbsp chastkovij poryadok za vklyuchennyam tobto B C displaystyle B leq C nbsp oznachaye sho B C displaystyle B subseteq C nbsp de B C W A displaystyle B C in Omega A nbsp dvi pidmnozhini A displaystyle A nbsp Todi W A displaystyle Omega A nbsp peretvoryuyetsya na chastkovo vporyadkovanu mnozhinu z najmenshim elementom displaystyle emptyset nbsp ta najbilshim elementom A displaystyle A nbsp Rozglyanemo mnozhinu N n displaystyle mathbb N n nbsp vsih n displaystyle n nbsp elementnih poslidovnostej naturalnih chisel z leksikografichnim poryadkom A same a 1 a 2 a n b 1 b 2 b n displaystyle a 1 a 2 ldots a n leq b 1 b 2 ldots b n nbsp yaksho a 1 lt b 1 displaystyle a 1 lt b 1 nbsp abo a 1 b 1 a 2 lt b 2 displaystyle a 1 b 1 a 2 lt b 2 nbsp abo displaystyle ldots nbsp abo a 1 b 1 a 2 b 2 a n b n displaystyle a 1 b 1 a 2 b 2 ldots a n b n nbsp inakshe kazhuchi yaksho u poslidovnosti b 1 a 1 b 2 a 2 b n a n displaystyle b 1 a 1 b 2 a 2 ldots b n a n nbsp pershij nenulovij element dodatnij U takij sposib N n displaystyle mathbb N n nbsp peretvoryuyetsya na linijno vporyadkovanu mnozhinu yaka vidigraye providnu rol u komp yuternij algebri div bazis Grebnera Div takozh Redaguvati nbsp Portal Matematika Peredporyadok Linijno vporyadkovana mnozhina Cilkom vporyadkovana mnozhina Najbilshij ta najmenshij element Maksimalni ta minimalni elementi Verhnya ta nizhnya mezha Poslidovno paralelnij chastkovij poryadok Shilnij poryadokPrimitki Redaguvati Kolmogorov 2004 Kolmogorov 2004 s 38 Kolmogorov 2004 s 40 Barendregt 1985 s 23 Dzherela RedaguvatiHausdorf F Teoriya mnozhestv Moskva Leningrad ONTI 1937 304 s ISBN 978 5 382 00127 2 ros Kuratovskij K Mostovskij A Teoriya mnozhestv Set Theory Teoria mnogosci M Mir 1970 416 s ros Aleksandrov P S Vvedenie v teoriyu mnozhestv i obshuyu topologiyu Moskva Nauka 1977 368 s ISBN 5354008220 ros Malcev A I Algebraicheskie sistemy Moskva Nauka 1970 392 s ros Kolmogorov A N Fomin S V Elementy teorii funkcij i funkcionalnogo analiza 4 e izd Moskva Nauka 1976 544 s ISBN 5 9221 0266 4 ros Otrimano z https uk wikipedia org w index php title Chastkovo vporyadkovana mnozhina amp oldid 37637654