Usporiadanosť množiny prirodzených čísel. nerovnosti na množine prirodzených čísel v disciplíne „Abstraktná algebra“
Objednané súpravy
Definícia 1. Kopa M volal objednal, ak je medzi jej prvkami vytvorený nejaký vzťah a b(" a predchádzalo b"), ktorý má nasledujúce vlastnosti: 1) medzi ľubovoľnými dvoma prvkami a A b existuje len jeden z troch vzťahov: a = b, a b, b a; 2) pre ľubovoľné tri prvky a, b A c od a b, b c nasleduje a c.
Prázdna sada sa považuje za objednanú.
Komentujte. Znak = vždy chápeme v zmysle identity, zhody prvkov. Záznam a = b jednoducho to znamená v písmenách a A b označuje rovnaký prvok množiny M. Z vlastnosti 1) teda vyplýva, že medzi dvoma rôznymi prvkami platí jeden a len jeden z oboch vzťahov a b alebo b a.
Ak a predchádzalo b, potom to hovoria b nasleduje a a napíš: b > a.
Postoj a > b Má, ako možno ľahko overiť, vlastnosti podobné 1) a 2). Môže sa považovať za hlavný a potom prostredníctvom neho definovať vzťah a b.
Ak v objednanom sete M zmeniť roly vzťahu, t.j a b písať a > b, a naopak, dostaneme novú objednanú sadu M", ktorého poradie je údajne inverzné k poradiu M. Napríklad pre vyššie uvedené poradie v množine prirodzených čísel bude poradie obrátené:
Dve usporiadané sady zložené z rovnakých prvkov, ale usporiadané v rôznom poradí, sa považujú za odlišné. Preto pri definovaní objednaného súboru prostredníctvom jeho prvkov je potrebné uviesť ich poradie. Budeme predpokladať, že zápis zľava doprava zodpovedá poradiu prvkov a zachováme predchádzajúci zápis so zloženými zátvorkami. Rovnakú sadu je možné objednať rôznymi spôsobmi (ak obsahuje aspoň dva prvky). Množinu prirodzených čísel možno teda usporiadať obvyklým spôsobom alebo v opačnom poradí pred párne čísla alebo naopak, usporiadať ich vzostupne alebo zostupne. Dostávame objednané sady
Povieme, že prirodzené číslo a viac než prirodzené číslo b(a určiť a > b), ak existuje prirodzené číslo k také, že a = b + k.
Veta 1. Jedna nie je väčšia ako akékoľvek prirodzené číslo.
Podmienka 1 > a totiž znamená 1 = a + k, čo je nemožné: pre k = 1 dostaneme 1 = a /, čo je v rozpore s prvou axiómou prirodzených čísel; pre k ¹ 1 nachádzame jeho predchodcu a opäť prichádzame k rovnakému rozporu.
Tento vzťah „viac“ je antireflexný(nie je pravda, že a > a) a tranzitívny(a > b /\ b > c => a > c), teda je vzťah prísneho poriadku. Navyše, tento vzťah je vzťahom lineárneho poriadku, to znamená, že pre množinu prirodzených čísel platí trichotomická veta:
Trichotomická veta: Pre akékoľvek dve prirodzené čísla platí iba jedno z nasledujúcich troch tvrdení:
Dôkaz: Najprv ukážeme, že žiadne dve z troch podmienok nie sú splnené súčasne. Predpokladajme, že podmienky 1 a 2 sú splnené
a = b + k, b = a + n => a = a + (n + k) => a > a,
čo je v rozpore s antireflexívnosťou postoja „viac“. Podobne sa zistí nezlučiteľnosť podmienok 2 a 3 a podmienok 1 a 3.
Teraz dokážeme, že jedna z troch podmienok nevyhnutne platí pre ľubovoľné čísla a a b. Používame matematickú indukciu na b. Pre b = 1, v závislosti od a: buď a = 1 = b, alebo pre a existuje predchodca
a = c / = c + 1 = 1 + c = b + c => a > b.
Pre b = 1 je teda veta pravdivá. Urobme indukčný predpoklad, že veta platí pre nejaké x, totiž že x je porovnateľné s číslom a, čiže sú možné tri možnosti: buď a > x, alebo x > a, alebo x = a. Potom dokážeme, že x/ je tiež porovnateľné s a. V prvom prípade a > x, teda a = x + k. Podľa toho, či sa dané k rovná 1 alebo nie, dostaneme
a) a = x + 1 = x / (teorém je pravdivý)
b) a = x + c / = x + c + 1 = x + 1 + c = x / + c => a > x / .
V druhom prípade x > a, ale potom
x / = (a + m) +1 = a + (m + 1),
teda x / > a. Podobne pre x = a platí x / = x + 1 = a + 1, teda opäť x / > a. Veta je úplne dokázaná.
Teraz môžete predstaviť koncepty<, £, ³.
a< b ó b >a;
a £ b ó a< b \/ a = b
a ³ b ó a > b \/ a = b.
Vlastnosti monotónnosti:
Pre operáciu pridávania:
1) a > b => a + c > b + c;
2) a + c > b + c => a > b;
3) a > b /\ c > d=> a + c > b + d.
<, £, ³.
Pre operáciu násobenia:
4) a > b => a×c > b×c;
5) Zákon kontrakcie: ac = bc => a = b
6) ac > bc = > a > b;
7) a > b /\ c > d=> ac > bd.
Rovnaké vlastnosti sa vyskytujú aj pri iných znakoch<, £, ³.
Uveďme ako príklad dôkaz vlastností 4 a 5. Keďže a > b, podľa definície a = b + k, potom a×c = (b + k)×c = b×c + k×c, čo znamená že a ×c > b×c a vlastnosť 4 je dokázaná. Vlastnosť 5 dokážeme protirečením. Nech ac = bc, ale predpokladajme, že a ≠ b, ale potom podľa trichotomickej vety buď a > b, alebo b > a, ale to podľa vlastnosti 4 znamená, že buď ac > bc, alebo bc > ac, čo odporuje podmienke (ac = bc).
Veta o diskrétnosti. Nemôžete vložiť prirodzené číslo medzi dve susediace prirodzené čísla:
(" a, x О N) nie je pravda, že a< x < a /
Dôkaz(protirečivou metódou). Nechajte a< x < a / . Тогда х = а + k,
a/ = x + n = a + k + n => a + 1 = a + k + n => 1 = k + n.
Posledná rovnosť je nemožná, pretože je v rozpore s vetou, že jedna nie je väčšia ako akékoľvek prirodzené číslo.
Archimedova veža. Pre ľubovoľné prirodzené čísla a a b existuje prirodzené číslo n také, že a< bn.
Dôkaz vykonáme indukciou na b. Pre b = 1, n = a / . Urobme indukčný predpoklad, že pre b = k existuje požadované n, teda a< kn. Но тогда тем более a < k / n = kn + k. Теорема доказана.
Najmenší prvok súpravy M prvok s О М budeme nazývať taký, že pre ľubovoľné prvky m О M platí nerovnosť: с ≤ m.
Veta o najmenšom prvku. Akákoľvek neprázdna podmnožina množiny prirodzených čísel má najmenší prvok.
Dôkaz: Ak M je podmnožina N obsahujúca 1, potom 1 bude požadovaný najmenší prvok. Ak 1 nie je zahrnutá v množine M, potom uvažujme pomocnú množinu A, pozostávajúcu zo všetkých prirodzených čísel menších ako všetky prirodzené čísla z množiny M:
A = (a О N| ("m О M) a< m}.
Z tejto konštrukcie predovšetkým vyplýva, že množiny A a M nemajú spoločné prvky. Navyše, A nie je prázdne, keďže 1 Î A. V A je tiež prvok b, taký, že b / Ï A. Ak by totiž taký prvok neexistoval, potom by axiómou indukcie bolo možné dokázať že A = N, ale potom by M bolo prázdne, čo nezodpovedá podmienkam vety. Prvok b / = c bude presne najmenší prvok v množine M. Skutočne, c £ m pre ľubovoľné m ОМ (ak by to tak nebolo, potom by nerovnosť c > m platila aspoň pre jedno prirodzené m, ale b О A , teda b< m < c = b / , что противоречит теореме о дискретности). Кроме того, с не может быть строго меньше всех элементов множества М, иначе с Î А, что противоречит его выбору. Таким образом, с равен хотя бы одному элементу из М, а значит с Î М, то есть действительно с – наименьший элемент множества М. Теорема доказана.
Všimnite si, že nie každá podmnožina množiny prirodzených čísel má najväčší prvok, ale ak je táto podmnožina konečná, potom má aj najväčší prvok. Platí to aj naopak. Ak má podmnožina prirodzených čísel najväčší prvok, potom je táto podmnožina konečná. Dá sa dokázať ešte všeobecnejšie tvrdenie: neprázdna podmnožina množiny prirodzených čísel je zhora ohraničená práve vtedy, ak je konečná (má najväčší prvok).
Úlohy na samostatné riešenie
č. 1.8. Dokážte, že vzťah „viac ako“ je antireflexívny a tranzitívny na množine prirodzených čísel.
č. 1.9. Dokážte vlastnosti monotónnosti 1, 2, 3, 6, 7 z tejto sekcie.
č. 1.10. Dokážte nerovnosti pre všetky prirodzené čísla n
a) 5 n > 7 n – 3;
b) 2n +2 > 2n + 5;
Platné (reálny) čísla sú dobre známe zo školských kurzov matematiky. V krátkosti sa zastavíme pri ich vlastnostiach, ktoré celkom ľahko vníma každý z nás. Reálne čísla tvoria množinu prvkov, ktoré majú nasledujúce vlastnosti.
Objednať nehnuteľnosť
Pre ľubovoľné dve čísla %%a%% a %%b%% je definovaný vzťah poradia, t.j. Akékoľvek dve reálne čísla %%a%% a %%b%% spĺňajú jeden z nasledujúcich vzťahov: %%a< b, a = b%% или %%a >b%%; Navyše, ak %%a< b%% и %%b < c%%, то %%a < c%%.
Vlastnosti operácie sčítania
čiastka a označené %%a + b%%, že sú splnené nasledujúce vlastnosti.
- Komutatívnosť: %%a + b = b + a %%.
- Asociativita: %%a + (b + c) = (a + b) + c%% pre ľubovoľné čísla %%a, b%% a %%c%%.
- nula a označené ako %%0%% , čo znamená %%a + 0 = a%% pre akékoľvek číslo %%a%%.
- Pre akékoľvek číslo %%a%% existuje volané číslo opak%%a%% a označené %%-a%%, čo je %%a + (-a) = 0%%.
- Ak< b%%, то %%a + c < b + c%% для любого числа %%c%%. Нуль единственен, и для каждого числа единственно противоположное ему число. Для любой пары чисел %%a%% и %%b%% число %%a + (-b) %% называют rozdielčísla %%a%% a %%b%% a označujú %%a - b%%.
Vlastnosti operácie násobenia
Pre každý pár čísel %%a%% a %%b%% existuje jedinečné číslo nazývané ich práca a označené %%ab%% (alebo %%a \cdot b%%), že sú splnené nasledujúce vlastnosti.
- Komutatívnosť: %%ab = ba%%.
- Asociativita: %%a(bc) = (ab)c%% pre ľubovoľné čísla %%a, b%% a %%c%%.
- Je tam volané číslo jednotka a označené %%1%%, že %%a \cdot 1 = a%% pre akékoľvek číslo %%a%%.
- Pre akékoľvek číslo %%a%%, ktoré sa nerovná nule, existuje volané číslo obrátene k tomuto a označené ako %%1 / a%%, čo je %%a \cdot (1 / a) = 1%%.
- Ak buď %%a%% alebo %%b%%, alebo obe %%a%% a %%b%% sú nula, potom %%ab = 0%%.
- Ak< b%% и %%c >0%%, potom %%ac< bc%%. Единица единственна, и для каждого ненулевого числа существует единственное обратное к нему. Для любой пары чисел %%a%% и %%b (b \neq 0)%% число %%a \cdot (1/b)%% называют súkromné z delenia %%a%% %%b%% a označeného %%a/b%%.
Vlastnosť distribúcie
Pre akúkoľvek trojicu čísel %%a, b%% a %%c%% platí rovnosť %%(a + b)c = ac + bc%%.
Archimedovský majetok
Bez ohľadu na číslo %%a%% existuje celé číslo %%n \in \mathbb(N)%% také, že %%n > a%%.
Ryža. 1. Číselný rad
Pred formulovaním ďalšej vlastnosti reálnych čísel si pripomeňme, že priamka je daná referenčného rámca, ak sú na tejto priamke fixované dva rôzne body (body %%O%% a %%e%% na obr. 1). Ľavý (bod %%O%%) sa nazýva počiatok a dĺžka segmentu %%Oe%% určuje jednotku mierky. Priamka s daným referenčným systémom sa nazýva súradnicová os. Zvyčajne sa označuje ako %%Ox%%. Bod %%O%% rozdeľuje súradnicovú os na dve časti: kladnú poloos, kde leží bod %%e%%, a zápornú poloos.
Koordinovať body %%M%% na osi %%Ox%% sú dĺžkou segmentu %%OM%%, brané so znamienkom %%+%%, ak bod %%M%% leží na kladnej polomere a so znamienkom %%-%%, ak bod %%M%% leží na zápornej poloosi.
Je zrejmé, že každý bod %%M%% na osi %%Ox%% zodpovedá skutočnému číslu %%x%%, konkrétne jeho súradnici. A naopak, každé reálne číslo na osi %%Ox%% zodpovedá bodu, pre ktorý je toto reálne číslo jeho súradnicou. Kedykoľvek je to potrebné, budeme predpokladať, že tento druh korešpondencie bol vytvorený medzi skutočnými číslami a bodmi nejakej čiary, pričom %%e = 1%%, %%O = 0%%.
Množinu všetkých reálnych čísel teda možno považovať za číselný rad. Niekedy sa namiesto číselnej osi používa aj výraz „skutočná línia“. Identifikácia reálnych čísel pomocou bodov na číselnej osi bude v budúcnosti mimoriadne užitočná, pretože slúži ako pomôcka na pochopenie a motivuje k zavádzaniu nových pojmov.
Volá sa podmnožina %%X%% množiny reálnych čísel medzi, ak spolu s akýmikoľvek dvoma číslami %%x_1, x_2%% táto podmnožina obsahuje akékoľvek %%x%% uzavreté medzi nimi. Používajú sa tieto typy medzier:
- %%(a, b) = \(x: a< x < b\}%% - interval, alebo otvorené rozpätie;
- %% = \(x: a \leq x \leq b\)%% - úsečka, alebo uzavretá medzera(niekedy sa používa výraz „segment“);
- %%(a, b] = \(x: a< x \leq b\}%% и %% \supseteq %%, то отрезок %%%% называют vnorené do segmentu %%%%.
Vlastnosť kontinuity
Pre každý systém vnorených segmentov $$ \supseteq \supseteq \supseteq \ldots \supseteq \supseteq \ldots $$ existuje aspoň jeden bod patriaci všetkým segmentom tohto systému. Táto vlastnosť sa nazýva aj princíp vnorených segmentov (Cantorov princíp).
Z uvedených vlastností reálnych čísel možno získať, že 1 > 0, ako aj pravidlá pre operácie s racionálnymi zlomkami; pravidlá znakov na násobenie a delenie reálnych čísel; pravidlá pre transformáciu rovnosti a nerovností; vlastnosti absolútnej hodnoty reálneho čísla.
Absolútna hodnota
Absolútna hodnota(alebo modul) %%|a|%% z akéhokoľvek reálneho čísla %%a%% je reálne číslo, ktoré spĺňa podmienky: $$ |a| = \begin(cases) a, \text( if ) a \geq 0 \\ -a, \text( if ) a< 0 \end{cases} ~~~~~~~~~~(1) $$
Z toho vyplýva, že absolútna hodnota akéhokoľvek reálneho čísla je nezáporná %%(|a| \geq 0)%%, rovnako ako $$ \begin(pole)(l) |a| = |-a|, \\ |a| \geq a, \\ |a| \geq -a, \\ -|a| \leq a \leq |a|. \end(pole)~~~~~~~~~~(2) $$
Geometricky %%|a|%% zodpovedá vzdialenosti medzi bodmi na číselnej osi reprezentujúcej čísla %%0%% a %%a%%.
Nech je nerovnosť %%|a|< \varepsilon%%, где %%\varepsilon%% - некоторое положительное число (%%\varepsilon >0 %%). Potom je táto nerovnosť ekvivalentná dvojitej nerovnosti $$ -\varepsilon< a < \varepsilon. $$ Равносильность рассмотренных неравенств будет сохранена, если строгие неравенства (%%<%%) заменить на нестрогие (%%\leq%%): %%|a| \leq \varepsilon%% равносильно %%-\varepsilon \leq a \leq \varepsilon%%.
Pre akékoľvek reálne čísla %%a%% a %%b%% platí rovnosť $$ |ab| = |a||b| ~~~~~~~~~~(3) $$ a platia nasledujúce nerovnosti: $$ \begin(pole)(lr) |a + b| \leq |a| + |b| &~~~~~~~~~~(4),\\ |a - b| \geq \big||a| - |b|\big|&~~~~~~~~~~~(5). \end(pole) $$
Pomocou (1) a (2) dokážeme nerovnosť (4): ak %%a + b \geq 0%%, potom $$ |a + b| = a + b \leq |a| + |b| $$ a ak %%a + b< 0%%, то $$ |a + b| = -(a + b) = (-a) + (-b) < |a| + |b| $$
Vyššie uvedené vlastnosti úplne opisujú množinu všetkých reálnych čísel.
Množina všetkých reálnych čísel, ako aj množina bodov na číselnej osi sa zvyčajne označuje ako %%\mathbb R%%.
Kompletná sada reálnych čísel
Doplnené(alebo rozšírené) množina reálnych čísel je množina vytvorená zo všetkých reálnych čísel %%x \in \mathbb R%% s pridaním dvoch prvkov, označených %%+\infty%% (“plus nekonečno”) a %%-\ infty%% ( "mínus nekonečno") Predpokladá sa, že %%-\infty< +\infty%% и для всех чисел %%x \in \mathbb R%% справедливо %%-\infty < x < +\infty%%. Пополненное множество обозначают %%\overline{\mathbb R}%%. Ему соответствует predĺžený(alebo doplnené) číselný rad. Prvky %%-\infty%% a %%+\infty%% sa nazývajú nekonečné body takejto priamky.
Podmnožiny množiny %%\mathbb R%% reálnych čísel
- Množina celých čísel$$ \mathbb Z = \(\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \) $$ je správna podmnožina množiny %%\mathbb R%% (%%\mathbb Z\subset\mathbb R%%).
- Množina prirodzených čísel$$ \mathbb N = \(1, 2, 3, \ldots \) $$ je správna podmnožina množiny %%\mathbb Z %% a množiny %%\mathbb R%% %%( \mathbb N \ podmnožina \mathbb Z \podmnožina \mathbb R)%%.
Množina všetkých reálnych čísel, ktoré možno znázorniť ako podiel celého čísla %%m \in \mathbb Z%% vydeleného prirodzeným číslom %%n \in \mathbb N%%, sa nazýva množina. racionálne čísla a označujú %%\mathbb Q%%, t.j. $$ \mathbb Q = \left\(\frac(m)(n): m \in \mathbb Z, n \in \mathbb N\right\) $$
Pomery %%\frac(m)(n)%% a %%\frac(m"))(n")%% sa považujú za rovnaké (predstavujúce rovnaké racionálne číslo %%r \in \mathbb Q%%) , ak %%mn" = nm"%%. Každé racionálne číslo %%r = \frac(m)(n)%% teda môže mať nekonečne veľa obrázkov %%r = \frac(p m)(p n), p \in \mathbb N%%.
Je zrejmé, že %%\mathbb N \subset \mathbb Z \subset \mathbb Q \subset \mathbb R%%.
Nekonečné intervaly
Na vyplnenej číselnej osi sú nekonečné intervaly $$ (b, +\infty) = \(x: x > b\), (-\infty, a) = \(x: x< a\} $$ и бесконечные полуинтервалы $$ = \{x: x \leq a\} $$ По аналогии с бесконечными интервалами множество всех точек на числовой прямой R обозначают часто %%(-\infty, +\infty)%% или просто %%(-\infty, \infty)%%.
Ryža. 2. Okolie bodu
Volá sa ľubovoľný interval %%(a, b)%% obsahujúci nejaký bod %%x_0%%. okolí tento bod a označujú %%\text(U)(x_0)%%, t.j. %%\text(U)(x_0) = (a, b)%% ak %%x_0 \v (a, b)%%. Bod %%x_0%%, ktorý sa nachádza v strede jeho okolia %%(a, b)%%, sa v tomto prípade nazýva centrum susedstva, a vzdialenosť %%\varepsilon = \frac((b - a))(2)%% je polomer okolia. Potom nastavte %%\(x: |x - x_0|< \varepsilon\}%% называют %%\varepsilon%%-окрестностъю точки %%x_0%% и обозначают %%\text{U}(x_0, \varepsilon)%% или %%\text{U}_\varepsilon(x_0)%% (рис. 2).
Na rozšírenej číselnej osi je predstavený pojem susedstva pre nekonečné body %%+\infty%% a %%-\infty%%, čím sa tieto body pri zvažovaní mnohých problémov rovnajú konečným bodom. Nech %%M%% je nejaké kladné číslo. Potom %%\text(U)(+\infty) = \(x \in \mathbb(R): x > M\)%% a %%\text(U)(-\infty) = \(x \ in\mathbb(R): x< -M\}%%, а для объединения бесконечных точек %%\text{U}(\infty) = \{x \in \mathbb{R}: |x| >M\)%%. Je jasné, že pre ktorýkoľvek z nekonečných bodov okolie s menšou hodnotou %%M%% zahŕňa okolie s väčšou hodnotou %%M%%.
Ministerstvo školstva a vedy Ruskej federácie
Federálna agentúra pre vzdelávanie
OBECNÝ ÚSTAV NIŽNEKAMSK
Katedra informatiky, matematiky a prírodných vied -
vedných odborov
Skupina 561
ABSTRAKT
v disciplíne "Abstraktná algebra"
Úroveň vzdelania špecialista
Téma: Objednané súpravy
Hlava ____________________ R.M. Munipov
Študent ____________________ A.V. Glazunov
Nižnekamsk 2007
ÚVOD………………………………………………………………………………………..3
1. Čiastočne objednané súpravy…………………………………5
2. Dobre usporiadané súpravy………………………………………..20
3. Parciálne grupoidy a ich vlastnosti………………………………..23
ZÁVER………………………………………………………………..35
LITERATÚRA………………………………………………………………..36
Úvod
V súčasnosti sa algebra chápe najmä ako všeobecná teória algebraických operácií a vzťahov. Vyznačuje sa veľkou vnútornou prirodzenosťou počiatočných myšlienok a úloh, jednotou metód a ďalekosiahlou šírkou základných pojmov. Jeho oblasť je jasne a jasne vymedzená. A predsa existujúce hranice teórie nemožno považovať za pevne a definitívne stanovené. Čoraz častejšie sa začína objavovať túžba prekročiť svoje hranice. Je potrebné zvážiť operácie nielen úplné, ale aj čiastočné.
Teória čiastkových činov musí prirodzene pokračovať v teórii úplných činov. Tá je v súčasnosti mimoriadne rozsiahla, bohatá a je v rozkvete. Prirodzene, vzniká myšlienka preniesť koncepty a výsledky, ktoré sa tam vyvinuli, do novej oblasti. To je, samozrejme, potrebné a v mnohých prípadoch aj prospešné. Už od prvých krokov vo vývoji teórie čiastkových akcií sa však prejavuje výrazná špecifickosť tohto smeru. Priamy prenos výsledkov teórie úplných akcií sa často ukazuje ako zložitý alebo dokonca nemožný. Zvyčajný algebraický materiál musí byť podrobený značnému spracovaniu alebo prehodnoteniu, navyše vznikajú úplne nové koncepty a problémy, ktoré sú špecifické pre nový smer; Vyžadujú si vlastnú metodiku výskumu.
Teória parciálnych algebraických akcií ešte nebola dostatočne úplná a súvislá. V počiatočných pojmoch a dokonca aj v zápisoch a terminológii je nejednotnosť. Medzi jednotlivými dielami nie je dostatok väzieb. Pociťuje sa neadekvátnosť rozvoja jednotlivých otázok potrebných na konštrukciu všeobecnej teórie.
1 . Hasticky usporiadané sady
Binárny vzťah na množine A volal antisymetrický Ak:
(a,c A) A? V V? A
A volal reflexné Ak:
( a A) a a
Binárny vzťah na množine A volal tranzitívny Ak:
(a,V,c A) a V V c>a S
Príklad 1
Vzťah deliteľnosti (úplne) na množine prirodzených čísel N antisymetrický. V skutočnosti, ak A V, V A, potom sú prirodzené q1 ,q N, také že a=bq1 , v=aq kde a=aq1 q , teda q1 q = 1. Ale,
q1 ,q N,teda q1 = q = 1, z ktorého vyplýva, že a = b.
Reflexná antisymetrická tranzitívna binárna relácia na množine A volal objednávkový vzťah (čiastočná objednávka) na scéne A.
Kopa A s čiastočným objednávkovým vzťahom uvedeným na ňom? volajú čiastočne objednaná súprava a označujú< A; ? >.
V nasledujúcom texte budeme pre zjednodušenie používať skratku PLAGUE , označujúci čiastočne usporiadanú súpravu.
Príklad 2
< N, ? > ? obyčajná neprísna nerovnosť čísel (v školskom zmysle). Je potrebné dokázať tranzitivitu, reflexivitu a antisymetriu tohto vzťahu?
a)a? a,(2 ? 2) - reflexivita,
b) ak A? V , V? s, To a ? c, (3 ? 4, 4 ? 5 > 3 ? 5) - tranzitivita,
c) ak a ? V , V?a, To a=in,(3 x 3, 3 x 3 > 3=3) - antisymetria.
Z toho vyplýva < N, ? > - CHUM.
Príklad 3
< N, > .
a) Vzťah deliteľnosti na množine prirodzených čísel N reflexívne, pretože každé číslo je násobkom samého seba, t.j. pretože pre kohokoľvek A N Vždy a = a 1 (1 N), toto v zmysle vzťahu máme A A. Preto je reflexná.
b) Ak je prvé číslo deliteľné druhým (t. j. násobkom druhého) a druhé je násobkom tretieho, potom prvé je násobkom tretieho, čo znamená, že vzťah je tranzitívny, t.j. Ak A V, V S, a,V,c N. Takže existujú také q ,q N, Čo
a= vq ,
v =c q ,
a = c (q q ).
Označme: q = q q N. Máme
Kde q N, t.j. A S- a-priorita . Preto je vzťah tranzitívny.
c) Antisymetria vzťahu vyplýva z toho, že dve prirodzené čísla, ktoré sú navzájom násobkami, sa rovnajú, t.j. Ak A V, V A, potom sú také q1 ,q N, Čo
a=bq1 ,
v=aq ,
a=aq1 q ,
to jest q1 q = 1. Ale, q1 ,q N,teda q1 = q = 1, z ktorého vyplýva, že a = b. Preto antisymetrické.
Preto existuje čiastočná objednávka, a preto < N, > - CHUM (čiastočne objednaná súprava).
Prvky a,V Mor A sa volajú neporovnateľné sú zapísané
A|| V, Ak a? V A V? A.
Prvky a,V Mor A sa volajú porovnateľné Ak a? V alebo V? A.
Čiastočná objednávka? na A volal lineárne, ale samý mor lineárne - usporiadané alebo reťaz, ak nejaké dva prvky z A porovnateľné, t.j. pre akékoľvek a,V A, alebo a ? V, alebo V? a.
Príklad 4 .
< N, ? >, < R, ? > - sú reťaz. Avšak<В(M); > ,kde B( M) - množina všetkých podmnožín množiny M alebo v ( M) sa nazýva Boolean na súprave M, nie je reťaz, pretože nie pre žiadne dve podmnožiny množiny M jeden je podmnožinou druhého.
Nechaj < A, ? > - svojvoľný mor.
Element m A volal minimálne, ak pre nejaké X A z čoho X ? m by mal X = m.
Význam tohto pojmu je taký A neobsahuje prvky striktne menšie ako tento prvok m. To hovoria X striktne menej m a zapíšte si X< m, Ak X ? m, ale v rovnakom čase X ? m. Maximálny prvok tohto moru sa určuje podobným spôsobom. Je jasné, že ak m , m - rôzne minimálne (maximálne) prvky moru, potom m || m .
V teórii čiastočne usporiadaných stanoví podmienku a ? V niekedy čítaj takto: elementA obsiahnuté v prvkuV alebo elementV obsahuje prvokA .
Lemma.
Každý prvok konečného moru obsahuje minimálny prvok a je obsiahnutý v maximálnom prvku tohto moru.
dôkaz:
Nechaj A- svojvoľný prvok konečného moru S. Ak A - minimálny prvok, potom je vďaka reflexivite lemma dokázaná. Ak A nie je minimálny, potom je tu prvok A také že
A < A(1)
Ak A je minimálna, vtedy je všetko dokázané. Ak prvok A nie je
minimálne, potom pre niektorých A dostaneme
A < а (2)
Ak A je minimálna, potom z (1), (2) vďaka tranzitivite usudzujeme, že A obsahuje minimálny prvok A . Ak A nie je teda minimálny
A < A (3)
pre niektoré A S. A tak ďalej. Tento proces nemôže byť nekonečný kvôli konečnosti samotnej množiny S.
Teda na nejaký čas n- v kroku uvažovania proces končí, čo je ekvivalentné skutočnosti, že prvok A minimálne. V čom
A < а < < а < а < а
Vzhľadom na priechodnosť vyplýva, že prvok A obsahuje minimálny prvok A . Rovnako aj prvok A obsiahnuté v maximálnom prvku. Lema je dokázaná.
Dôsledok.
Finálny mor obsahuje aspoň jeden minimálny prvok.
Teraz predstavíme koncept, ktorý je dôležitý pre ďalšiu prezentáciu diagramy konečný mor S.
Najprv vezmeme všetky minimálne prvky m , m , m V S. Podľa vyšetrovania takí ľudia budú. Potom v čiastočne objednanej súprave
S = S \ {m , m , m },
ktoré, ako S, je konečný, berieme minimálne prvky,
, a zvážte súpravu
= S \ {, , }
Prvky „prvého radu“ m , m , m znázornené bodkami. O niečo vyššie označíme prvky „druhého radu“ bodkami, , a spojte body so segmentmi v tom a len tom prípade, ak m <
Ďalej nájdeme minimálne prvky moru, zobrazíme ich bodmi „tretieho radu“ a spojíme ich s bodmi „druhého radu“ spôsobom uvedeným vyššie. Pokračujeme v procese, až kým sa nevyčerpajú všetky prvky tohto Moru S. Proces je konečný vzhľadom na konečnosť množiny S. Výsledná množina bodov a segmentov sa nazýva diagram PLAGUE S. Zároveň a < в vtedy a len vtedy, ak z „bodu“ A môžete prejsť na „body“ V pozdĺž nejakej „vzostupnej“ prerušovanej čiary. Vzhľadom na túto okolnosť môže byť každý konečný mor identifikovaný pomocou jeho diagramu.
Príklad 5 .
Tu je dané CHUM diagramom S = {m , m , , ), kde m < , m < , m < m < , m < m < , m < .
Element m volal najmenší prvok MOR, ak pre niekoho X A Vždy m ? X.
Je jasné, že najmenší prvok je minimálny, ale opak nie je pravdou: nie každý minimálny prvok je najmenší. Existuje iba jeden najmenší prvok (ak existuje). Najväčší prvok je určený podobne.
Príklad 6.
· · · ·
Ide o mor, ktorého prvky sú v pároch neporovnateľné. Tieto sú čiastočne
objednané sady sa nazývajú antireťazce.
Príklad 7 .
Toto je reťaz s najmenším a najväčším prvkom. Kde 0 je najmenší prvok a 1 je najväčší prvok.
Nechaj M- podmnožina čiastočnej usporiadanej množiny A. Element A A volal spodný okraj súpravy M, Ak A? X pre hocikoho X M.
Najväčší zo všetkých infimov súboru M, ak existuje, je tzv presný spodný okraj súpravy M a označujú inf M.
Nechaj < A, ? > - svojvoľný mor. Element S A volal presný spodný okraj prvkov a,V A, Ak S= inf( a,V}.
Poznámka 1.
Nie v každej pliage existuje presné infimum pre akékoľvek dva prvky.
Ukážme si to na príklade.
Príklad 8 .
Pre ( a;c},{d;e) nemá spodný okraj,
inf( a;V}=d, inf( V;c}=e.
Príklad 9 .
Uveďme príklad moru, ktorý má presné infimum pre akékoľvek prvky.
inf( a;V}=d, inf( a;d}=d, inf( a;0 }=0 , inf( a;c}=0 , inf( a;e}=0 ,
inf( V;c}=e, inf( V;e}=e, inf( V;d}=d,
inf( c;e}=c, inf( c;0 }=0 , inf( c;d}=0 ,
inf( d;e}=0 , inf( d;0 }=0 ,
inf( e;0 }=0 .
Definícia: Volá sa čiastočne usporiadaná množina, v ktorej pre ľubovoľné dva prvky existuje infimum polomriežkový.
Príklad 10 .
Uveďme príklad moru, ktorý nie je polomreža.
Nechaj < N, ? > - lineárne usporiadaná množina prirodzených čísel a e ,e N. Na scéne N = N { e ,e ) definovať binárny vzťah? , za predpokladu, že X ? r, Ak X, r N, Kde X ? r, alebo ak X N, r { e ,e ). Podľa definície tiež uvažujeme: e ? e ,e ? e .
Schéma tohto moru je nasledovná:
Akékoľvek prirodzené číslo n ? e a n? e , ale v N neexistuje teda žiadny najväčší prvok, N - CHUM, ale nie polovičná mriežka.
Polomriežka je teda podľa svojej definície model (ako množina s reláciou?). Ako teraz uvidíme, je možný aj iný prístup k pojmu semimriežka, a to, že semimriežku možno definovať ako určitú algebru.
Aby sme to dosiahli, zavedieme niekoľko ďalších algebraických konceptov. Ako je známe, poloskupina je neprázdna množina, na ktorej je definovaná asociatívna binárna algebraická operácia.
Zvyčajne sa označuje ľubovoľná pologrupa S(polskupina).
Definícia. Element eS volal idempotentný, Ak
e = e, to jest e · e = e.
Príklad 11 .
Poloskupina< N; · > ? má len jeden idempotent 1.
Poloskupina< Z; + > ? má jediný idempotent 0.
Poloskupina< N; + > ? nemá idempotent, pretože 0 N.
Pre akúkoľvek neprázdnu množinu X, ako obvykle, označuje množinu všetkých podmnožín množiny X - boolovskú hodnotu množiny X.
Poloskupina<В;>- je taká, že každý jej prvok je idempotentný.
A IN, A = A A.
Pologrupa sa nazýva idempotentná poloskupina alebo partia, ak je každý jeho prvok idempotentný. Príkladom spojky je teda ľubovoľný booleovský vzťah k spojeniu.
Príklad 12 .
Nechaj X- ľubovoľná množina.
B- množina všetkých podmnožín množiny X.
B- sa na scéne nazýva Boolean X.
Ak X= (1,2,3), potom
B = (0,(1),(2),(3),(1,2),(2,3),(1,3),(1,2,3)).
Od priesečníka dvoch podmnožín množiny X je opäť podmnožinou X, potom máme grupoid< В;>, navyše je to pologrupa a dokonca aj spojka, keďže A V a A = A A=A.
Presne rovnakým spôsobom máme spojenie<; В > .
Komutatívna spojka je tzv polomriežkový.
Príklad 13 .
Nechaj X= (1,2,3), zostavme diagram< В ; >.
Uveďme príklady rán, ale nie polomriežky.
Príklad 14 .
CHUM s dvoma spodnými plochami e A d , ktoré nie sú navzájom porovnateľné: e|| d. Preto inf( a;S) neexistuje.
Príklad 15.
CHUM s dvoma spodnými plochami S A d, ktoré sú navzájom neporovnateľné: S|| d. Preto inf( a;V) neexistuje.
Uveďme príklady polomriežok.
Príklad 16 .
Diagram:
A
inf( a;V}=V, inf( a;S}=S, inf( a;d}=d,
inf( V;c}=d, inf( V;d}=d,
inf( c;d}=d.
Príklad 17 .
Je to polomriežka, pretože pre ľubovoľné dva prvky existuje infimum, t.j.
inf( a;V}=V, inf( a;S}=S, inf( V;c}=S.
Veta 1.
Nechaj<S ; ? > - polomriežka. Potom<S ; > komutatívne spojovacie, kde
a V=inf( a,V} (*).
dôkaz:
Je potrebné dokázať, že v<S ; > majú nasledujúce identity:
(1) X y = y X
(2) (X r) z = x (r z)
(3) X X = X
1) Podľa rovnosti (*)
X y = inf( X,r) = inf ( r,X) = r X
2) Označme A = (X r) z, v =X ( r z)
Dokážme to A = V.
Aby to bolo možné, stačí to dokázať
A ? V (4)
V ? A(5) (kvôli antisymetrii)
Označme
S = X r , d = r z
V zmysle, A presná spodná hranica medzi S A z
A? S , A ? z , c ? X, teda v dôsledku prechodnosti a ? X.
podobne, A? r, t.j. A- spoločná dolná hranica pre r A z. A d- ich presná dolná hranica.
teda a ? d, Ale V=inf( X, d}.
Z nerovnosti a ? X , a ? d z toho vyplýva A X A d, A V je teda ich presné infimum,
A? V(4) preukázané.
(5) sa preukazuje obdobným spôsobom.
Z (4) a (5) vzhľadom na antisymetriu usudzujeme, že
a = b.
Tým sme dokázali asociatívnosť operácie ().
3) Máme X X=inf( X,X} = X.
Rovnosť sa dosahuje reflexiou: X? X.
To. konštruovaná algebra<S ; > bude komutatívna idempotentná poloskupina, t.j. komutatívny odkaz.
Veta 2.
Nechaj<S ; · > je komutatívna idempotentná pologrupa, potom binárna relácia? na S, definovaná rovnosťou
? = a·в = а,
je čiastočná objednávka. Zároveň MOR<S ; ? > je polomriežka.
dôkaz:
1) reflexivita?
Podľa podmienok<S ; · > spĺňa tri identity:
(1) X = X
(2) x y = y x
(3) (x y)· z = x(r· z)
Potom x x = x = x - na základe (1). Preto X? X.
2) antisymetria? .
Nechaj X? pri A y? X, potom podľa definície,
(4) x y = x
teda vďaka komutativite máme x = y.
3) prechodnosť?.
Nechaj X? pri A y?z potom podľa definície
(6) x y = x
(7) r z= y
Máme X· z = (X· r)· z X· (r· z) xy X
takže, X· z = X, teda X?z.
Takže máme CHUM<S ; ? >. Zostáva ukázať, že pre akékoľvek ( A,V)S existuje inf( a,c}.
Berieme svojvoľne A,V S a dokázať, že prvok c = a b je inf( a,c), t.j. S= inf( a,c}.
Naozaj,
c a =(a·c)·A A·(a·c) (a·a)· V a·b = c,
To. s? A.
podobne, s·v =(a·c)·V A·(v · v) a·b = c,
tie. s? V.
takže, S- spoločná spodná hranica ( a,c}.
Poďme dokázať jeho presnosť.
Nechaj d- nejaká spoločná spodná hranica pre A A V:
(8) d? a
(9)d? V
(10) d a = d
(11)d v =d
d· c = d· (a·c) (d·A)· V d·V d,
d· c = d, teda, d ? c.
Záver: c = inf( a,V}.
Dokázané vety 1 a 2 nám umožňujú pozerať sa na pologrupy z dvoch uhlov pohľadu: ako na CUM a ako v algebre (idempotentné komutatívne pologrupy).
2. Dobre usporiadané súpravy
Teóriu usporiadaných množín vytvoril G. Cantor . Šatunovskij . Hausdorff (1914).
Dobre usporiadané súpravy - Usporiadaná množina sa nazýva dobre usporiadaná, ak každá z jej podmnožín má prvý prvok (t. j. prvok, za ktorým nasledujú všetky ostatné). Všetky konečné usporiadané množiny sú kompletne usporiadané. Prirodzené série, usporiadané vzostupne (ako aj niektorými inými spôsobmi), tvoria úplne usporiadanú množinu. Dôležitosť úplne usporiadaných množín je daná najmä tým, že pre ne platí princíp transfinitnej indukcie.
Usporiadané množiny, ktoré majú rovnaký ordinálny typ, majú aj rovnakú kardinalitu, takže môžeme hovoriť o kardinalite daného ordinálneho typu. Na druhej strane, konečné usporiadané množiny rovnakej kardinality majú rovnaký ordinálny typ, takže každá konečná kardinalita zodpovedá určitému konečnému ordinálnemu typu. Situácia sa mení pri prechode do nekonečných množín. Dve nekonečné usporiadané množiny môžu mať rovnakú mohutnosť, ale rôzne typy poradia.
3. Parciálne grupoidy a ich vlastnosti
Ako je známe, binárna algebraická operácia na množine S je mapovanie z karteziánskeho štvorca S?S. V tomto prípade sa hovorí, že akcia je nastavená na S. V tomto odseku to nazveme plný účinok.
Akékoľvek mapovanie z podmnožiny S?S V S volal čiastočný efekt na S. Inými slovami, čiastočné pôsobenie na S je nejaká funkcia z S?S > S.
Dá sa povedať, že na Sčiastočná akcia (čiastočné násobenie) je špecifikovaná, ak pre nejaké prvky a,c S práca a·c buď nedefinované alebo jednoznačne definované. Jednoducho povedané, nie sú tu znásobené všetky prvky.
Kopa S s čiastočným násobením v ňom uvedeným sa nazýva parciálny grupoid a je označený ( S ; · ) na rozdiel od úplného grupoidu< S ; · >.
Ak pre úplný grupoid môžeme hovoriť o Cayleyho tabuľke, potom pre čiastočný grupoid môžeme hovoriť o nejakom analógu Cayleyho tabuľky, konkrétne o tabuľke, kde sú niektoré bunky prázdne - to je prípad, keď je súčin prvkov neurčitý.
Príklad 1
a
A· v = v, Ale V· A nedefinované, t.j. V· A= O. symbol " O" nepatrí S, t.j. nie je prvkom S.
Príklad 2
Zvážte mor ( S ; ? ).
S = {a,V,c, d), Kde A? A, V? V, s? S, d ? d, s? A, s? V, d? A, d? V.
V svojvoľnom moru ( S ; ? ) súhlasíme s označením:
A V= inf( a,V}.
Potom je mor naznačený v príklade s ohľadom na túto čiastočnú akciu čiastočným grupoidom ( S;), ktorého Cayleyho tabuľka je nasledujúca
d
a
d
c
-
V tejto časti sa pozrieme na tri typy asociatívnosti: silná asociativita, stredná asociativita, slabá asociativita.
Definícia 1.
Čiastočný grupoid ( S ; · ) sa nazýva slabo asociatívne , Ak
(X,y,z S) (X· r)· z O X·( r· z) > (X· r)· z= X·( r· z) (*)
Definícia 2.
Čiastočný grupoid ( S ; · ) sa nazýva stredne asociatívne , Ak
(X,y,z S) (X· r)· z O r· z > (X· r)· z= X·( r· z)
Definícia 3.
Čiastočný grupoid ( S ; · ) sa nazýva silne asociatívny , Ak
(X,y,z S) [(X· r)· z O X·( r· z) O> (X· r)· z= X·( r· z)] (*)
Silne asociatívny parciálny grupoid spĺňa vlastnosti strednej a slabej asociatívnosti. Opak však v žiadnom prípade nie je potrebný.
Príklad 3
Dané A = {a, v, s). Nastavíme to na Ačiastočná operácia násobenia „čiastočnou Cayleyho tabuľkou“.
Získame nejaký parciálny grupoid. Skontrolujeme, či je grupoid silne asociatívny.
Nechajte ( X· r)· z O pretože X A, potom buď x = c x = b
1) nech x = c, Potom y = in y = c
a) nech y = in, Potom z = a
(S· V)· A O S·( V· A) definované
(S· V)· a = c·( V· A) je splnená rovnosť
b) nech y = c, Potom z= v z= c
A keď z= v, Potom
(S· S)· V O S·( S· V) definované
(S· S)· v = c·( S· V) je splnená rovnosť
b), ak z= c, Potom
(S· S)· S O S·( S· S) definované
(S· S)· c = c·( S· S) je splnená rovnosť
2) nech x = b, Potom y = a, A z= v z = c
A keď y = a A z= v
(V· A)· V O= v·( A· V) nedefinované
(V· A)· V V·( A· V) nie je splnená rovnosť
b) nech y = a A z= c
(V· A)· S O= v·( A· S) nedefinované
(V· A)· S V·( A· S) nie je splnená rovnosť
Čiastočný grupoid teda podľa definície nie je silne asociatívny. To však neznamená, že ( S ; · ) nie je slabo asociatívna.
Poďme zistiť.
Nechaj (X· r)· z O X·( r· z) O .
o X A, pri A, totiž kedy
x = b x = c
y = in y = c
tento parciálny grupoid je slabo asociatívny.
Príklad 4.
Nechaj A ={a, v, s), možno nastaviť na A nasledujúca Cayleyho tabuľka. Získame nejaký parciálny grupoid. Pozrime sa, či je tento grupoid stredne asociatívny.
Nechajte ( X· r)· z O pretože X V, Potom x = a x = c
1) nech x = a, Potom y = a y = in
a) nech y = a, Potom z = a, z= v
A keď z= a, Potom
(A· A)· A O A· a definované
(A· A)· A A·( A· a) nie je splnená rovnosť
b), ak z= v, Potom
(A· A)· V O A· V definované
(A· A)· V A·( A· V) nie je splnená rovnosť
Vidíme teda, že grupoid nie je priemerne asociatívny. Zistite, či je slabo asociatívna.
Nechajte ( X· r)· z O X·( r· z) O, pretože X V, Potom x = a x = c
1) nech x = a, Potom y = a y = in
a) nech y = a, Potom z = a, z= v
A keď z= a, Potom
(A· A)· A O= a·( A· a) nedefinované
(A· A)· A A·( A· a)
b), ak z= v, Potom
(A· A)· V O A·( A· V) definované
(A· A)· v = a·( A· V) je splnená rovnosť
b) nech y = in, Potom z = a, z= v
A keď z= a, Potom
(A· V)· A O= a·( V· a) nedefinované
(A· V)· A A·( V· a)
b), ak z= v, Potom
(A· V)· V O A·( V· V) nedefinované
(A· V)· V A·( V· V) nie je splnená rovnosť
2) nech x = c, Potom y = a,y = in
a) nech y = a, Potom z = a, z= v
A keď z= a, Potom
(S· A)· A O= c·( A· a) nedefinované
(S· A)· A S·( A· a) nie je splnená rovnosť
b), ak z= v, Potom
(S· A)· V O S·( A· V) definované
(S· A)· v = c·( A· V) je splnená rovnosť
Vidíme teda, že čiastočný grupoid je slabo asociatívny pre x = a A z= v alebo kedy x = c Ak y = a A z= v.
Definícia 4.
Čiastočný grupoid ( S ; · ) sa nazýva komutatívny , Ak
(X,r S) X· r = r· X
Definícia 5.
Čiastočný grupoid ( S ; · ) sa nazýva trolejového vedenia , Ak
(X,y,z S) (X· r O r· z) > [(X· r)· z O X·( r· z)]
Definícia 6.
Čiastočný grupoid ( S ; · ) sa nazýva idempotentný , Ak
(X S) X = X
Uveďme príklad nekatenárneho parciálneho grupoidu.
Príklad 5.
d
a
d
c
-
Máme S a = c O, A d = d O. Avšak, ( S A) d = c d O. Dané CG teda nie je trolejové vedenie.
Je jasné, čo rozumieme pod pojmom „spoločná horná hranica“ prvkov A A V nejaký mor.
Definícia 7.
Volá sa to mor kategorický , ak ktorékoľvek dva jeho prvky, ktoré majú hornú hranicu, majú presnú dolnú hranicu.
Príklad 6.
Príklad 7.
Čiastočne usporiadaná množina definovaná Cayleyho tabuľkou:
Príklad 8.
Čiastočne objednaná sada
s nasledujúcou Cayleyho tabuľkou:
-
-
-
Je jasné, že každá polomreža je kategorický mor (ale nie naopak), pretože akékoľvek dva prvky majú presné infimum. Inými slovami, trieda všetkých kategorických rán obsahuje triedu všetkých polomriežok, ale nezhoduje sa s ňou. To. každé tvrdenie dokázané pre kategorické pliagy má za následok ako zrejmý dôsledok určitú vetu týkajúcu sa polomriežok.
Uveďme príklady polomriežok.
Príklad 9.
Diagram:
volal diamant
d
a
d
c
Príklad 10.
Diagram:
volal Pentagon a je definovaný polomriežkou s nasledujúcou Cayleyho tabuľkou:
Príklad 11.
Polomriežka definovaná Cayleyho tabuľkou:
má schému:
Veta 1.
Nechajte ( S ; ? ) - kategorický mor, potom ( S;) - reťazový idempotentný komutatívny slabo asociatívny parciálny grupoid.
dôkaz:
Pre hocikoho A S Vždy
A A= inf( a, a} = a teda čiastočný grupoid S idempotentný.
Máme A V= inf( a,V) = inf( V,a} = V A, a preto S komutatívny
Skontrolujme slabú asociativitu.
Nechajte ( A V) S O A (V S), označujú
A V = d, V S = e, (A V) S= d S = f, A (V S) = A e= g
Dokážme to f = g.
Podľa definície máme f ? d ? a f ? a,
f ? d? V f? V (1)
f ? c (2)
Pretože e= inf( v, s), potom z (1), (2) vyplýva, že f ? e. To. f - nejaká spoločná dolná hranica pre A A e, A g je ich presné infimum, tak
f ? g (3)
podobne,
g ? f (4)
Nerovnosť (3), (4) a antisymetria vzťahu? poskytnúť f = g. Dokázala sa slabá asociativita.
Skontrolujeme trolejové vedenie S.
Nechaj A V O V S, označovať A b = x, V S = r, odtiaľ X? V, y? V, t.j.
V- spoločná horná hranica X A pri. Pretože PLAGUE S kategoricky, potom existuje inf( x, y), t.j. existuje v S X pri. Označme X y = z, to si ukážeme
A (V S) = X S= z. Máme z ? X, z ? r (pretože z = inf( x, y}), r ? z z ? X, z ? c,
z - spodný okraj pre X A S.
Zabezpečíme presnosť.
Nechaj t ? X , t ? c (t- akákoľvek dolná hranica), pretože t ? X , To t ? a, t? V, podľa podmienky t? S, t.j. t- spoločná dolná hranica pre V A S. Z toho vyplýva z definície pri, t ? r.
takže, t ? X, t? pri teda t ? z (a-priorita z).
Vedenie trolejového vedenia sa osvedčilo.
Veta 2.
Ak ( S ; · ) je reťazový idempotentný komutatívny slabo asociatívny parciálny grupoid, potom vzťah
? = (a,c) S?S (2)
Je to vzťah objednávky. Zároveň MOR<S ; ? > - je trolejové vedenie.
dôkaz:
Dokážme reflexívnosť vzťahu? . Pretože parciálny grupoid S idempo-tenten teda a· a = a teda podľa definície (2) A? A.
Skontrolujeme antisymetriu.
Ak A? v, v? A, To а·в = а, в·а = в,ľavé strany sú rovnaké kvôli komutativite, čo znamená, že pravé strany sú rovnaké a = b.
Zostáva dokázať prechodnosť.
Nechaj A? V, V? S, Potom a·b = a, v s = in, a·с =(a·c)· S. Z dôvodu trolejového vedenia máme ( A· V)· S O , A·( V· S) O, teda kvôli slabej asociativite
(a·c)·c = a·(v s), a preto, a·c = a·(v s) = a·b = a.
takže, a·c = a, t.j. A? S.
To. máme mor<S ; ? > .
Nechaj z- spoločná horná hranica pre X A pri. teda X?z, r ? z, odtiaľ X·z = X, r· z = r, Potom z· r = r. Z dôvodu trolejového vedenia ( X· r)· z O X· r O.
Označme x y =s, dokážme to s presný spodný okraj.
Máme s· X = (X· r)· X = X· (X· r) = (X· X)· r = X· r = s (v dôsledku trolejového vedenia a slabej asociatívnosti), preto s ? X, t.j. s- spoločná spodná hranica.
Z týchto teorémov vyplývajú dva dôsledky dobre známe v teórii polomriežok.
Dôsledok 1.
Ak<S ; · > je idempotentná komutatívna pologrupa, potom vzťah? , definovaný rovnosťou (2), je čiastkový poriadok. Navyše pre akékoľvek dva prvky v S existuje presná spodná hranica.
Dôsledok 2.
Ak<S ; · > je čiastočne usporiadaná množina, v ktorej je infimum ľubovoľných dvoch prvkov, teda vzhľadom na operáciu
A V= inf( a,V} (3)
kopa S je idempotentná komutatívna pologrupa.
ZÁVER
Na záver možno poznamenať, že teóriu usporiadaných množín vytvoril G. Cantor . V roku 1883 zaviedol pojem úplne usporiadaná množina a poradové číslo av roku 1895 pojem usporiadaná množina a radový typ. V rokoch 1906-07 S.O. Šatunovskij sformuloval definície riadenej množiny (v Shatunovskom - lokalizovaný komplex) a limitu nad riadenou množinou (americkými matematikmi E. . G. Moore a G. L. Smith uvažovali o tých istých konceptoch nezávisle od Shatunovského, ale oveľa neskôr - v roku 1922). Všeobecný koncept čiastočne usporiadaného súboru patrí F. Hausdorff (1914).
Teória čiastočných algebraických akcií, ktorá je pokračovaním teórie úplných akcií, využíva jej úspechy, s ňou spojené nápady a skúsenosti s aplikáciami mimo algebry, by sa teda mala stále formovať ako nezávislý smer v obrovskej oblasti moderná algebra.
K dnešnému dňu boli publikované stovky prác špeciálne venovaných štúdiu čiastkových akcií. Pokiaľ ide o práce, v ktorých sa v priebehu štúdie vyskytujú určité čiastkové akcie, ich počet nemožno odhadnúť. O čiastkových akciách sa hovorí aj v niektorých všeobecných algebraických prácach, ale vždy veľmi stručne.
Bibliografia
A.K. Clifford, G. Preston. Algebraická teória pologrúp. 1972.
Greitzer. Všeobecná teória mriežok Moskva.-284 s.
Kozhevnikov O.B. Čiastočne usporiadané množiny parciálnych grupoidov Moskva, 1998. - 680-te roky.
E.S. Lyapin. Pologrupy. Moskva: Fizmat, 1960.- 354 s.
Lyapin E.S. Algebra a teória čísel. Moskva, 1980.-589 s.
Pri zavádzaní operácií s nadmnožinami sme nebrali do úvahy, že samotné množiny môžu mať svoju vnútornú štruktúru, to znamená, že sme predpokladali, že všetky prvky množiny sú rovnocenné. V matematike sú však takéto „čisté“ množiny málo zaujímavé a oveľa častejšie sa študujú množiny, medzi ktorých prvkami existujú určité vzťah . Jedným z najdôležitejších vzťahov medzi prvkami množiny je objednávkový vzťah .
Objednávkový vzťah nie je nič iné ako spravidla stanovenie poradia „postupnosti“ prvkov súboru.
Nechaj A- nejaký súbor, súprava A volal objednaná sada , ak pre ktorékoľvek dva jeho prvky a, b je nainštalované jedno z nasledujúcich poriadkové vzťahy :
alebo a ≤ b (A nepresahuje b),
alebo b ≤ a (b nepresahuje A),
majúce nasledujúce vlastnosti:
1) reflexivita:
žiadny prvok nie je nadradený sám sebe;
2) antisymetria:
Ak A nepresahuje b, A b nepresahuje A, potom prvky A A b vyrovnať sa;
3) prechodnosť:
Ak A nepresahuje b, a b nepresahuje S, To A nepresahuje S.
Bolo dohodnuté, že prázdna súprava bude považovaná za objednanú. Vo vyššie uvedenej definícii usporiadanej množiny, ktorej prvkami môžu byť predmety akejkoľvek povahy, znak ≤ znie „nepresahuje“. Tento znak (ako znak „menej ako alebo rovný“) nadobúda svoje obvyklé čítanie a význam v prípade, keď prvky množiny A- čísla.
Dve množiny zložené z rovnakých prvkov, ale s rôznymi vzťahmi usporiadania, sa považujú za rôzne usporiadané množiny.
Rovnakú súpravu je možné objednať rôznymi spôsobmi, čím získate rôzne objednané súpravy.
Príklad
Uvažujme množinu, ktorej prvkami sú rôzne konvexné mnohouholníky: trojuholník, štvoruholník, päťuholník, šesťuholník atď. Jedným zo spôsobov, ako vytvoriť usporiadanú množinu z danej neusporiadanej množiny, môže byť napríklad vziať trojuholník ako prvý prvok usporiadanej množiny , druhý je štvoruholník, tretí je päťuholník atď., t.j. množinu usporiadame v rastúcom poradí podľa počtu vnútorných uhlov mnohouholníkov. Množinu polygónov je možné zoradiť aj iným spôsobom, napríklad tak, že sa polygóny zoradia vo vzostupnom poradí podľa plochy, keď sa ako prvý vyberie polygón s najmenšou plochou, polygón s plochou nepresahujúcou plochu všetkých ostatné okrem už vybratého sa vyberie ako druhý atď.
Usporiadané (konečné alebo spočítateľné) množiny sa často píšu tak, že ich prvky sú usporiadané v danom poradí v zátvorkách.
Príklad
Zápisy (1; 2; 3) a (2; 1; 3) predstavujú rôzne konečné usporiadané množiny, ktoré možno získať z tej istej množiny (1; 2; 3) jej usporiadaním dvoma rôznymi spôsobmi.
Ak chcete napísať počítateľnú usporiadanú množinu, musíte uviesť prvý prvok objednanej množiny a uviesť poradie (pravidlo) usporiadania nasledujúcich prvkov.