Přednáška 3.
s. 3. Vztahy na množinách. Vlastnosti binárních vztahů.
3.1. Binární vztah.
Když hovoří o příbuznosti dvou lidí, například Sergeje a Anny, znamená to, že existuje určitá rodina, k jejímž členům patří. Objednaný pár (Sergey, Anna) se liší od ostatních objednaných párů lidí tím, že mezi Sergejem a Annou existuje jakýsi vztah (bratranec, otec atd.).
V matematice patří mezi všechny seřazené dvojice přímých součin dvou sad A a B (A´ B) „Zvláštní“ páry se také odlišují vzhledem k tomu, že mezi jejich složkami existují určité „příbuzenské“ vztahy, které ostatní nemají. Jako příklad zvažte sadu S univerzitní studenti a mnoho K. číst zde kurzy. V přímé práci S´ K. velká podmnožina seřazených párů ( s, k) s majetkem: student s poslouchá kurz k... Vytvořená podmnožina odráží postoj „... naslouchá ...“, který přirozeně vzniká mezi sadami studentů a kurzů.
Pro podrobný matematický popis jakýchkoli spojení mezi prvky dvou množin zavedeme koncept binární relace.
Definice 3.1. Binární (nebo dvojnásobek ) přístup rmezi sadami A a Bse nazývá libovolná podmnožina A´ B, tj.
Zejména pokud A \u003dB(tj. rÍ A2), pak se říká, že r je vztah na množině A.
Elementy a a b se nazývají komponenty (nebo souřadnice ) vztahy r.
Komentář. Souhlasme s tím, že řecká abeceda by měla být použita k označení vztahů mezi prvky množin: r, t, j, s, w atd.
Definice 3.2. Rozsah Dr \u003d ( a| $ b, co ar b) (levá strana). Rozsah hodnot binárního vztahu r se nazývá množina Rr \u003d ( b| $ a, co ar b) (pravá část).
Příklad 3. 1. Nechť jsou uvedeny dvě sady A\u003d (1; 3; 5; 7) a B\u003d (2; 4; 6). Vztah definujeme následovně t \u003d (( x; y)Î A´ B | x +y\u003d 9). Tento poměr bude sestávat z následujících párů (3; 6), (5; 4) a (7; 2), které lze zapsat jako t \u003d ((3; 6), (5; 4), (7; 2 )). V tomto příkladu Dt \u003d (3; 5; 7) a Rt \u003d B={2; 4; 6}.
Příklad 3. 2. Vztah rovnosti na množině reálných čísel je množina r \u003d (( x; y) | x a y - reálná čísla a x stejně y). Pro tento vztah existuje speciální zápis „\u003d“. Rozsah definice se shoduje s rozsahem hodnot a je množinou reálných čísel, Dr \u003d Rr.
Příklad 3. 3. Nech být A - mnoho produktů v obchodě a B - sada reálných čísel. Pak j \u003d (( x; y)Î A´ B | y - cena x) Je vztah množin A a B.
Pokud věnujeme pozornost příkladu 3.1., Pak vidíme, že tento vztah byl poprvé specifikován ve tvaru t \u003d (( x; y)Î A´ B | x +y\u003d 9), a poté zapsán jako t \u003d (((3; 6), (5; 4), (7; 2)). To naznačuje, že vztahy na množinách (nebo jedné sadě) lze specifikovat různými způsoby. Zvažme způsoby nastavení binárních vztahů.
Způsoby, jak definovat vztahy:
1) použití vhodného predikátu;
2) sada uspořádaných párů;
3) v grafické podobě: let A a B Jsou dvě konečné množiny ar je binární vztah mezi nimi. Prvky těchto sad jsou reprezentovány body v rovině. Pro každou seřazenou dvojici vztahů r je nakreslena šipka spojující body představující komponenty dvojice. Takový objekt se nazývá řízený grafnebo digraf, obvykle se nazývají body představující prvky množin vrcholy grafu.
4) ve formě matice: let A={a1, a2, …, an) a B={b1, b2, …, bm), r je poměr na A´ B. Maticová reprezentace r se nazývá matice M=[mij] velikost n´ mdefinované vztahy
.
Mimochodem, maticová reprezentace je reprezentace vztahu v počítači.
Příklad 3. 4. Nechť jsou uvedeny dvě sady A\u003d (1; 3; 5; 7) a B\u003d (2; 4; 6). Poměr je definován takto t \u003d (( x; y) | x +y\u003d 9). Určete tento vztah jako sadu uspořádaných párů pomocí digrafu ve formě matice.
Rozhodnutí.1) t \u003d (((3; 6), (5; 4), (7; 2)) - existuje specifikace vztahu jako množina uspořádaných párů;
2) odpovídající orientovaný graf je zobrazen na obrázku.
https://pandia.ru/text/78/250/images/image004_92.gif "width \u003d" 125 "height \u003d" 117 "\u003e.,
Příklad 3. 5 . Dalším příkladem je navrhovaný J. von Neumann (1903 - 1957) blokové schéma sekvenčního počítače, který se skládá z mnoha zařízení M:
,
kde a - vstupní zařízení, b - aritmetická jednotka (procesor), c - ovládací zařízení, d - paměťové zařízení, e - výstupní zařízení.
Zvažte výměnu informací mezi zařízeními mi a mjkteré jsou ve vztahu r if from device mi informace vstupují do zařízení mj.
Tento binární vztah lze specifikovat uvedením všech jeho 14 uspořádaných párů prvků:
Odpovídající digraf definující tento binární vztah je zobrazen na obrázku:
Maticová reprezentace tohoto binárního vztahu je:
. ,
Pro binární vztahy jsou množinově-teoretické operace definovány obvyklým způsobem: sjednocení, průnik atd.
Představme si obecný koncept vztahu.
Definice 3.3. n-postel (n-arno ) relace r je podmnožinou přímého produktu n množiny, tj. množina uspořádaných množin ( n-tice )
rÍ Ajeden An={(a1, …, an)| a1Î A1Ù… Ù anÎ An}
Je vhodné definovat multiplace vztahy pomocí relační tabulky ... Takový úkol odpovídá výčtu množiny n-k vztah r. Relační tabulky jsou v počítačové praxi široce používány v relačních databázích. Pamatujte, že relační tabulky se používají v každodenní praxi. Všechny druhy produkčních, finančních, vědeckých a jiných zpráv jsou často ve formě relačních tabulek.
Slovo " relační„Vychází z latinského slova vztah, což v překladu do ruštiny znamená „postoj“. Proto se v literatuře písmeno používá k označení vztahu R (Latinsky) nebo r (řecky).
Definice 3.4. Ať rÍ A´ Bexistuje vztah k A´ B.Poté se nazývá poměr r-1 inverzní postoj k danému vztahu r o A´ Bkterý je definován takto:
r-1 \u003d (( b, a) | (a, b) Îr).
Definice 3.5. Nechť r Í A´ Bexistuje vztah k A´ B,a s Í B´ C -postoj k B´ C. Složenívztahys a r je poměr t Í A´ Ckterý je definován takto:
t \u003d s◦r \u003d (( a, c)| $ bÎ B to (a, b) Îr a (b, c) Je).
Příklad 3. 6 . Nechť, a C\u003d (,!, d, a). A nechte poměr zapnutý A´ B a poměr s k B´ C uveden jako:
r \u003d ((1, x), (1, y), (3, x)};
s \u003d (( x,), (x, !), (y, d), ( y, à)}.
Najděte r-1 a s◦r, r◦s.
Rozhodnutí. 1) Podle definice r-1 \u003d (( x, 1), (y, 1), (x, 3)};
2) Pomocí definice složení dvou vztahů získáme
s◦r \u003d (((1,), (1 ,!), (1, d), (1, a), (3,), (3 ,!)),
protože od (1, x) Îr a ( x,) Îs implikuje (1,) Îs◦r;
od (1, x) Îr a ( x,!) Îs následuje (1 ,!) Îs◦r;
od (1, y) Îr a ( y, d) Îs implikuje (1, d) Îs◦r;
od (3, x) Îr a ( x,!) Îs sleduje (3 ,!) Îs◦r.
Věta 3.1. Pro jakýkoli binární vztah platí následující vlastnosti:
2) 
;
3) 
- asociativita složení.
Důkaz. Vlastnost 1 je zřejmá.
Ukážeme vlastnost 2. Abychom dokázali druhou vlastnost, ukážeme, že množiny zapsané na levé a pravé straně rovnosti se skládají ze stejných prvků. Nech být ( a; b) Î (s◦r) -1 Û ( b; a) Î s◦r Û $ c takový, že ( b; c) Î r a ( c; a) Î s Û $ c takový, že ( c; b) Î r-1 a ( a; c) Î s-1 Û ( a; b) Î r -1◦s -1.
Prokázat vlastnost 3 samostatně.
3.2. Vlastnosti binárních vztahů.
Zvažte speciální vlastnosti binárních vztahů na množině A.
Vlastnosti binárních vztahů.
1. Poměr r k A´ A volala reflexní , Pokud ( a,a) patří r pro všechny a z A.
2. Poměr r se nazývá antireflexní pokud z ( a,b) Îr naznačuje a¹ b.
3. Poměr r symetricky pokud pro a a bpatřící A, z ( a,b) Itr z toho vyplývá, že ( b,a) Îr.
4. Poměr r se nazývá antisymetrický pokud pro a a b z A, z příslušnosti ( a,b) a ( b,a) z vztahu r vyplývá, že a=b.
5. Poměr r přechodně pokud pro a, b a c z A ze skutečnosti, že ( a,b) Îr a ( b,c) Îr, z toho vyplývá, že ( a,c) Îr.
Příklad 3. 7. Nech být A\u003d (1; 2; 3; 4; 5; 6). Na této množině vztah rÍ A2, který má tvar: r \u003d ((1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2 ), (1; 4), (2; 1), (2; 4), (3; 5), (5; 3), (4; 1), (4; 2)). Jaké vlastnosti má tento vztah?
Rozhodnutí. 1) Tento přístup je reflexivní, protože pro každého aÎ A, (a; a) Îr.
2) Postoj není antireflexní, protože podmínka této vlastnosti není splněna. Například (2, 2) Îr, ale to neznamená, že 2¹2.
3) Zvažte všechny možné případy, které ukazují, že poměr r je symetrický:
(a, b) Îr | (b, a) | (b, a) Nebo? |
|
4) Tento vztah není antisymetrický, protože (1, 2) Îr a (2,1) Îr, ale to neznamená, že 1 \u003d 2.
5) Je možné ukázat, že vztah r je tranzitivní pomocí metody hrubou silou.
(a, b) Îr | (b, c) Îr | (a, c) | (a, c) Nebo? |
|
Podle matice zobrazení
definovat vlastnosti binárního vztahu
1. Reflexivita: všechny jsou na hlavní úhlopříčce, nuly nebo jednotky jsou hvězdičky.
.
2. Antireflexní úprava: všechny nuly na hlavní úhlopříčce.
3. Symetrie: Pokud .
4. Antisymetrie: všechny prvky mimo hlavní úhlopříčku jsou nulové; na hlavní úhlopříčce mohou být také nuly.
.
Operace „*“ se provádí podle následujícího pravidla: 
, kde ,.
5. Transitivita: Pokud . Operace "◦" se provádí podle obvyklého pravidla násobení, přičemž se bere v úvahu :.
3.3 Vztah ekvivalence. Vztah částečné objednávky.
Vztah ekvivalence je formalizace takové situace, když se hovoří o podobnosti (identitě) dvou prvků množiny.
Definice 3.6. Poměr r k Atady je vztah ekvivalence, pokud si to reflexivní, symetrické a tranzitivní. Vztah ekvivalence ar b často označeno: a~ b.
Příklad 3. 8 . Vztah rovnosti na množině celých čísel je vztahem rovnocennosti.
Příklad 3. 9 . Poměr „jedné výšky“ je relací ekvivalence na množině lidí X.
Příklad 3. 1 0 . Nechť ¢ je množina celých čísel. Zavolejme dvě čísla x a y od ¢ srovnatelné v modulum(mÎ ¥) a po vydělení čísly napište, zda jsou zbývající čísla stejná m, tj. rozdíl ( x-y) děleno m.
Poměr „srovnatelný v absolutní hodnotě m celá čísla “je vztah ekvivalence na množině celých čísel ¢. Vskutku:
tento postoj je reflexivní, protože pro „ xÎ ¢ máme x-x\u003d 0, a proto je dělitelné m;
tento vztah je symetrický, protože pokud ( x-y) děleno m, pak ( y-x) je také dělitelný m;
tento vztah je tranzitivní, protože pokud ( x-y) děleno m, pak na celé číslo t1 máme https://pandia.ru/text/78/250/images/image025_23.gif "width \u003d" 73 "height \u003d" 24 src \u003d "\u003e, proto 
, tj. ( x-z) děleno m.
Definice 3.7. Poměr r k Atady je vztah částečné objednávky, pokud si to reflexivní, antisymetrické a tranzitivní a je označeno °.
Částečné pořadí je důležité v situacích, kdy chceme nějakým způsobem charakterizovat senioritu. Jinými slovy, rozhodněte, za jakých podmínek považujete jeden prvek množiny za lepší než jiný.
Příklad 3. 11 . přístup x£ y na množině reálných čísel existuje relace dílčího řádu. ,
Příklad 3. 1 2 . V sadě podmnožin nějaké univerzální sady U přístup AÍ B existuje vztah částečného řádu.
Příklad 3. 1 3 . Organizační schéma podřízenosti v instituci je vztah částečného řádu na sadě pozic.
Prototypem relace dílčího řádu je intuitivní koncept preferenčního vztahu (priority). Preference relace definuje třídu problémů, které lze kombinovat jako problém volby nejlepší objekt .
Prohlášení o problému: ať existuje sbírka předmětů A a je nutné je porovnat podle jejich preferencí, tj. nastavit preferenční vztah na množině A a identifikovat nejlepší objekty.
Preference vztah P, které lze definovat jako „ aPb, a, bÎ A Û objekt a ne méně výhodné než objekt b"Je reflexivní a antisymetrický ve smyslu (každý objekt není o nic horší než on sám, a pokud je objektem." a ne horší b a b ne horší a, pak jsou přednostně stejné). Je přirozené předpokládat, že postoj P přechodně (i když například v případě preferencí diskutuje skupina lidí s opačnými zájmy, může být tato vlastnost porušena), tj. P - vztah částečné objednávky.
Jedním z možných způsobů, jak vyřešit problém srovnávání objektů podle preferencí, je v rozsahu , tj. Řazení objektů v souladu s klesající preferencí nebo ekvivalencí. Výsledkem hodnocení je výběr „nejlepších“ nebo „nejhorších“ objektů z hlediska preferenčního vztahu.
Oblasti použití problémy s výběrem nejlepšího objektu: teorie rozhodování, aplikovaná matematika, technologie, ekonomie, sociologie, psychologie.
Definice
- 1. Jakákoli podmnožina kartézského součinu RAB, RAA se nazývá binární vztah mezi prvky množin A a B.
- 2. Pokud A \u003d B, pak R je binární relace na A.
- 3. Označení: (x, y) R xRy.
- 4. Doménou definice binárního vztahu R je množina R \u003d (x: existuje y takové, že (x, y) R).
- 5. Rozsah hodnot binárního vztahu R je množina R \u003d (y: existuje x takové, že (x, y) R).
- 6. Doplněk binárního vztahu R mezi prvky A a B je množina R \u003d (AB) R.
- 7. Inverzní relací pro binární relaci R je množina R1 \u003d ((y, x): (x, y) R).
- 8. Produktem vztahů R1AB a R2BC je vztah R1 R2 \u003d ((x, y): existuje zB takové, že (x, z) R1 a (z, y) R2).
- 9. Poměr f se nazývá funkce od A do B, pokud jsou splněny dvě podmínky:
- a) f \u003d A, f B
- b) pro všechna x, y1, y2 skutečnost, že (x, y1) f a (x, y2) f znamená y1 \u003d y2.
- 10. Poměr f se nazývá funkce od A do B, pokud v prvním odstavci f \u003d A, f \u003d B.
- 11. Označení: (x, y) f y \u003d f (x).
- 12. Funkce identity iA: AA je definována následovně: iA (x) \u003d x.
- 13. Funkce f se nazývá funkce 1-1, pokud pro libovolné x1, x2, y skutečnost, že y \u003d f (x1) a y \u003d f (x2) implikuje x1 \u003d x2.
- 14. Funkce f: AB provádí vzájemnou korespondenci mezi A a B, pokud f \u003d A, f \u003d B af je funkce 1-1.
- 15. Vlastnosti binárního vztahu R na množině A:
- - reflexivita: (x, x) R pro všechna xA.
- - Irreflexivita: (x, x) R pro všechna xA.
- - symetrie: (x, y) R (y, x) R.
- - antisymetrie: (x, y) R a (y, x) R x \u003d y.
- - tranzitivita: (x, y) R a (y, z) R (x, z) R.
- - dichotomie: buď (x, y) R, nebo (y, x) R pro všechna xA a yA.
- 16. Sady A1, A2, ..., Ar z P (A) tvoří oddíl sady A if
- - Аi, i \u003d 1, ..., r,
- - A \u003d A1A2 ... Ar,
- - AiAj \u003d, i j.
Podmnožiny Аi, i \u003d 1, ..., r se nazývají bloky oddílů.
- 17. Ekvivalence na množině A je reflexivní, přechodný a symetrický vztah na A.
- 18. Třída ekvivalence prvku x ekvivalencí R je množina [x] R \u003d (y: (x, y) R).
- 19. Faktorová množina A vzhledem k R je množina tříd ekvivalence prvků množiny A. Notace: A / R.
- 20. Třídy ekvivalence (prvky množiny kvocientů A / R) tvoří oddíl množiny A. Naopak. Libovolný oddíl množiny A odpovídá relaci ekvivalence R, jejíž třídy ekvivalence se shodují s bloky zadaného oddílu. Jinak. Každý prvek množiny A spadá do nějaké třídy ekvivalence od A / R. Třídy ekvivalence se buď neprotínají, ani se neshodují.
- 21. Předobjednávka na množině A je reflexivní a přechodný vztah na A.
- 22. Částečné uspořádání na množině A je reflexivní, přechodný a antisymetrický vztah na A.
- 23. Lineární řád na množině A je reflexivní, přechodný a antisymetrický vztah na A, který splňuje vlastnost dichotomie.
Nechť A \u003d (1, 2, 3), B \u003d (a, b). Napíšeme kartézský součin: AB \u003d ((1, a), (1, b), (2, a), (2, b), (3, a), (3, b)). Vezměte libovolnou podmnožinu tohoto kartézského součinu: R \u003d ((1, a), (1, b), (2, b)). Pak R je binární relace na množinách A a B.
Bude tento vztah fungovat? Zkontrolujeme splnění dvou podmínek 9a) a 9b). Doménou definice vztahu R je množina R \u003d (1, 2) (1, 2, 3), to znamená, že první podmínka není splněna, takže do R musí být přidána jedna z dvojic: (3, a) nebo (3, b). Pokud přidáte oba páry, druhá podmínka nebude splněna, protože ab. Ze stejného důvodu musí být jeden z párů (1, a) nebo (1, b) vyřazen z R. Vztah R \u003d (((1, a), (2, b), (3, b)) je tedy funkce. Všimněte si, že R není funkce 1-1.
Na daných množinách A a B budou funkcemi také následující vztahy: ((1, a), (2, a), (3, a)), ((1, a), (2, a), (3, b)), ((1, b), (2, b), (3, b)) atd.
Nechť A \u003d (1, 2, 3). Příkladem relace na množině A je R \u003d ((1, 1), (2, 1), (2, 3)). Příkladem funkce na množině A je f \u003d ((1, 1), (2, 1), (3, 3)).
Příklady řešení problémů
1. Najděte R, R, R1, RR, RR1, R1R pro R \u003d ((x, y) | x, y D a x + y0).
Pokud (x, y) R, pak xay procházejí všemi reálnými čísly. Proto R \u003d R \u003d D.
Pokud (x, y) R, pak x + y0, pak y + x0 a (y, x) R. Proto R1 \u003d R.
Pro libovolné xD, yD vezměte z \u003d - | max (x, y) | -1, pak x + z0 a z + y0, tj. (x, z) R a (z, y) R. Proto RR \u003d RR1 \u003d R1R \u003d D2.
2. Pro které binární vztahy platí R \u003d R?
Nechte RAB. Jsou možné dva případy:
- (1) AB. Vezměte xAB. Poté (x, x) R (x, x) R1 (x, x) R (x, x) (AB) R (x, x) R. Rozpor.
- (2) AB \u003d. Protože R1BA a RAB, pak R1 \u003d R \u003d. Z R1 \u003d vyplývá, že R \u003d. Z R \u003d vyplývá, že R \u003d AB. Rozpor.
Pokud tedy A a B, pak neexistuje žádný takový vztah R.
3. Na množině D reálných čísel definujeme vztah R následovně: (x, y) R (x-y) je racionální číslo. Dokažte, že R je rovnocennost.
Reflexivita:
Pro jakékoli xD x-x \u003d 0 je racionální číslo. Proto (x, x) R.
Symetrie:
Pokud (x, y) R, pak x-y \u003d. Pak y-x \u003d - (x-y) \u003d - je racionální číslo. Proto (y, x) R.
Transitivita:
Pokud (x, y) R, (y, z) R, pak x-y \u003d a y-z \u003d. Přidáním těchto dvou rovnic zjistíme, že x-z \u003d + je racionální číslo. Proto (x, z) R.
Proto je R ekvivalentní.
4. Rozdělení roviny D2 se skládá z bloků znázorněných na obrázku a). Napište vztah ekvivalence R odpovídající tomuto oddílu a třídám ekvivalence.
Podobný úkol pro b) ac).
a) dva body jsou ekvivalentní, pokud leží na přímce ve tvaru y \u003d 2x + b, kde b je libovolné reálné číslo.
b) dva body (x1, y1) a (x2, y2) jsou ekvivalentní, pokud (celočíselná část x1 se rovná celočíselné části x2) a (celočíselná část y1 se rovná celočíselné části y2).
c) rozhodněte se sami.
Úkoly pro nezávislé řešení
- 1. Dokažte, že pokud f je funkce od A do B a g je funkce od B do C, pak fg je funkce od A do C.
- 2. Nechť A a B jsou konečné množiny skládající se z prvků ma respektive n.
Kolik binárních vztahů existuje mezi prvky množin A a B?
Kolik funkcí existuje od A do B?
Kolik 1-1 funkcí existuje od A do B?
Pro které m a n existuje individuální korespondence mezi A a B?
3. Dokažte, že f splňuje podmínku f (AB) \u003d f (A) f (B) pro libovolné A a B právě tehdy, když f je funkce 1-1.
Relace definovaná v sadě může mít řadu vlastností, jmenovitě:
2. Reflexivita
Definice.přístup Rmnoho X se nazývá reflexivní, pokud každý prvek xzástupy X je ve vztahu Rse mnou.
Pomocí symbolů lze tento vztah zapsat následovně:
Rreflexivně na X Û(" xÎ X) x R x
Příklad.Vztah rovnosti na množině segmentů je reflexivní, protože každý segment se rovná sobě samému.
Graf reflexivní relace má smyčky na všech vrcholech.
2. Antireflexnost
Definice.přístup Rmnoho X se nazývá antireflexní, pokud žádný prvek neexistuje xzástupy X ne ve vztahu Rse mnou.
Rantireflexní na X Û(" xÎ X)
Příklad. Vztah „přímý x kolmo na přímku v»Na množině přímek v rovině je antireflexní, protože žádná přímka roviny není na sebe kolmá.
Antireflexní relační graf neobsahuje žádné smyčky.
Všimněte si, že existují vztahy, které nejsou reflexivní ani antireflexní. Zvažte například vztah „bod x symetrický k bodu v»Na množině bodů v rovině.
Tečka x symetrický k bodu x - skutečný; tečka vsymetrický k bodu v - false, proto nemůžeme tvrdit, že všechny body roviny jsou k sobě symetrické, ani nemůžeme tvrdit, že žádný bod v rovině není symetrický sám k sobě.
3. Symetrie
Definice... přístup Rmnoho X se nazývá symetrický, pokud ze skutečnosti, že prvek x je ve vztahu R s prvkem v, z toho vyplývá, že prvek v je ve vztahu R s prvkem x.
Rsymetrický X Û(" x, vÎ X) x R y Þ y R x
Příklad.Vztah „přímý x protíná přímku v na množině přímek v rovině "symetricky, protože pokud rovný x protíná přímku vpak přímka v určitě překročí přímku x.
Symetrický vztahový graf spolu s každou šipkou z bodu x přesně v by měla obsahovat šipku spojující stejné body, ale v opačném směru.
4. Asymetrie
Definice... přístup Rmnoho X se nazývá asymetrický, pokud pro žádné prvky x, v zástupu Xnemůže se stát, že prvek x je ve vztahu R s prvkem v a prvek v je ve vztahu R s prvkem x.
Rasymetrické X Û(" x, vÎ X) x R y Þ
Příklad.Přístup " x < v»Asymetricky, protože pro žádný pár prvků x, v nelze to říci současně x < va v< X.
Asymetrický relační graf nemá žádné smyčky a pokud jsou dva vrcholy grafu spojeny šipkou, pak existuje pouze jedna šipka.
5. Antisymetrie
Definice... přístup Rmnoho X se nazývá antisymetrický, pokud ze skutečnosti, že x je ve vztahu s v, a v je ve vztahu s x z toho vyplývá x = v.
Rantisymetrický X Û(" x, vÎ X) x R y Ù y R xÞ x \u003d y
Příklad.Přístup " x£ v»Antisymetrický, protože podmínky x£ va v£ xjsou současně prováděny pouze tehdy, když x = v.
Antisymetrický relační graf má smyčky a pokud jsou dva vrcholy grafu spojeny šipkou, pak existuje pouze jedna šipka.
6. Přechodnost
Definice... přístup Rmnoho X se pro všechny prvky nazývá tranzitivní x, v, z zástupu X z čeho x je ve vztahu s v, a v je ve vztahu s zz toho vyplývá xje ve vztahu s z.
Rpřechodně X Û(" x, v, zÎ X) x R y Ù y R zÞ x R z
Příklad. Přístup " x násobky v»Přechodně od roku je-li první číslo násobkem druhého a druhé je násobkem třetího, bude první číslo násobkem třetího.
Transitivní relační graf s každou dvojicí šipek z x na v a od vna z obsahuje šipku z x na z.
7. Konektivita
Definice... přístup Rmnoho X se nazývá spojený if pro nějaké prvky x, vzástupu X x je ve vztahu s v nebo v je ve vztahu s x nebo x \u003d y.
Rpřipojeno X Û(" x, v, zÎ X) x R y Ú y R zÚ X= v
Jinými slovy: postoj Rmnoho X se nazývá spojený, pokud pro různé prvky x, vzástupu X x je ve vztahu s v nebo v je ve vztahu s x nebo x \u003d y.
Příklad.Přístup " x< v»Je připojen, protože ať už vezmeme jakákoli reálná čísla, jedno z nich bude určitě větší než druhé, nebo budou stejné.
Na grafu spojeného vztahu jsou všechny vrcholy navzájem propojeny šipkami.
Příklad.Zkontrolujte, jaké vlastnosti
přístup " x -dělič v»Definováno na televizoru
X= {2; 3; 4; 6; 8}.
1) tento postoj je reflexivní, protože každé číslo z dané množiny je jejím dělitelem;
2) tento postoj nemá vlastnost antireflexivity;
3) vlastnost symetrie není splněna, protože například 2 je dělitelem 4, ale 4 není dělitelem 2;
4) tento poměr je antisymetrický: dvě čísla mohou být současně děliteli navzájem, pouze pokud jsou tato čísla stejná;
5) vztah je tranzitivní, protože pokud je jedno číslo dělitelem druhého a druhé je dělitelem třetího, pak první číslo bude nutně dělitelem třetího;
6) relace nemá vlastnost konektivity, protože například čísla 2 a 3 v grafu nejsou od té doby spojena šipkou dvě různá čísla 2 a 3 nejsou navzájem děliteli.
Tento vztah má tedy vlastnosti reflexivity, asymetrie a tranzitivity.
§ 3. Vztah ekvivalence.
Vztah vztahu ekvivalence s rozdělením množiny do tříd
Definice.přístup Rna scéně Xse nazývá vztah ekvivalence, pokud je reflexivní, symetrický a tranzitivní.
Příklad.Zvažte vztah „ x spolužák v„Na spoustu pedagogických studentů. Má vlastnosti:
1) reflexivita, protože každý student je svým spolužákem;
2) symetrie, protože pokud student x vpak student v je spolužák x;
3) tranzitivita, protože pokud student x - spolužák va student v - spolužák zpak student xbude spolužák z.
Tento vztah tedy má vlastnosti reflexivity, symetrie a přechodnosti, což znamená, že jde o vztah ekvivalence. Soubor pedagogických studentů lze dále rozdělit na podmnožiny složené ze studentů zapsaných do stejného kurzu. Dostáváme 5 podmnožin.
Rovnocennými vztahy jsou také například vztah rovnoběžnosti přímek, vztah rovnosti čísel. Každý takový vztah je spojen s rozdělením množiny do tříd.
Teorém.Pokud na scéně X je dán vztah ekvivalence, poté se tato sada rozdělí na párové disjunktní podmnožiny (třídy ekvivalence).
Platí také konverzace: pokud je v sadě definován jakýkoli vztah X, generuje oddíl této sady do tříd, pak se jedná o vztah ekvivalence.
Příklad.Na scéně X \u003d (1; 2; 3; 4; 5; 6; 7; 8) je uveden vztah „mají stejný zbytek po dělení 3“. Je to vztah ekvivalence?
Vytvořme graf tohoto vztahu:
Tento vztah má vlastnosti reflexivity, symetrie a tranzitivity; proto se jedná o vztah ekvivalence a rozděluje množinu Xdo tříd ekvivalence. Každá třída ekvivalence bude obsahovat čísla, která po dělení třemi dávají stejný zbytek: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.
Předpokládá se, že třídu ekvivalence určuje kterýkoli z jejích zástupců, tj. libovolný prvek této třídy. Třídu stejných zlomků lze tedy určit zadáním libovolného zlomku patřícího do této třídy.
V základním kurzu matematiky existují také ekvivalenční vztahy, například „výrazy x a v mít stejné číselné hodnoty "", obrázek x rovná se číslu v».
Jazyk T-SQL na serveru SQL Server je založen na standardním jazyce SQL, který je založen na relačním modelu, který je zase založen na matematických základech, jako je teorie množin a predikátová logika. Tento článek pojednává o základním tématu z teorie množin: vlastnosti vztahů na množinách. Čtenáři mohou pomocí navrhovaných kódů T-SQL zkontrolovat existenci určitých vlastností určitých vztahů. Před použitím řešení popsaných v tomto článku však můžete zkusit napsat své vlastní verze skriptů (abyste zjistili, zda má vztah konkrétní vlastnost).
Sady a vztahy
Georg Cantor, tvůrce teorie množin, definuje množinu jako „sjednocení do určitého celku M množiny určitých dobře rozlišitelných objektů m naší kontemplace nebo myšlení (které se budou nazývat prvky množiny M)“ . Prvky množiny mohou být objekty libovolné povahy: lidé, čísla a dokonce i samotné množiny. Symboly ∈ a ∉ označují operátory odrážející příslušnost (výskyt, členství) a nečlenství prvku v sadě. Označení x ∈ V tedy znamená, že x je prvkem množiny V a zápis x ∉ V znamená, že x není prvkem V.
Binární relace na množině je množina uspořádaných párů prvků původní množiny. Takže pro množinu prvků V \u003d (a, b, c) je binární relace R na dané množině V libovolná podmnožina množiny všech uspořádaných párů kartézského součinu V × V \u003d (((a, a ), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)) . Relace R \u003d ((a, b), (b, c), (a, c)) je platná binární relace na V. Můžeme říci, že a souvisí s b od R. Předpokládejme, že R \u003d ((a , b), (b, c), (c, d)). Takový R není platným vztahem na V, protože dvojice (c, d) nepatří do kartézského součinu V × V. Všimněte si, že pořadí, ve kterém jsou prvky uvedené v sadě označeny, není důležité. Množinu V lze zadat jako (a, b, c) nebo jako (b, a, c) atd. Pořadí v uspořádaných párech, například v binárním vztahu (a, b), je však důležité; tedy (a, b) ≠ (b, a).
Jako realističtější příklad binárního vztahu zvažte množinu F členů rodiny: (Itzik, Mickey, Inna, Mila, Gabi). Mickey je Itsikovo dvojče, Inna je jeho starší sestra, Mila je jeho matka a Gaby je jeho otec. Příkladem relace R na množině F by bylo: „je bratr“. Prvky tohoto vztahu jsou ((Itzik, Mickey), (Mickey, Itzik), (Itzik, Inna), (Mickey, Inna)). Všimněte si, že uspořádaný pár (Itzik, Inna) se objeví v R, ale pár (Inna, Itzik) ne. Ačkoli Itzik je Innin bratr, není to jeho bratr.
Vlastnosti vztahů na množinách
Nyní, když jsme obnovili naše chápání množin a vztahů, pojďme k tématu článku - vlastnosti vztahů na množinách. Například údaje najdete v kódech v seznamu 1 a vytvořte tabulky V a R. V bude představovat množinu a R na ní bude představovat binární vztah. Pomocí kódu v seznamu 2 vytvořte proceduru nazvanou ClearTables, která dokáže vymazat obě tyto tabulky před jejich naplněním novými ukázkovými daty. Nakonec použijte kódy v seznamech 3, 4 a 5 k naplnění tabulek V a R různými sadami testovacích dat (budeme jim říkat ukázková data 1, 2 a 3).
/IMAGE/1285154887_073-lis2.gif)
Reflexivita. Relace R na množině V je reflexivní, pokud pro jakýkoli prvek v množiny V, v ∈ V vyplývá, že (v, v) ∈ R, tj. Pár (v, v) vždy patří R. relace R na V není reflexivní, pokud existuje prvek v ∈ V takový, že dvojice (v, v) ∉ R. Zvažte znovu příklad množiny F - členů mé rodiny.
Vztah „mít stejný věk od“ do F je zjevně reflexivní. Prvky vztahu budou následující páry: ((Itzik, Itzik), (Itzik, Mickey), (Mickey, Mickey), (Mickey, Itzik), (Inna, Inna), (Mila, Mila), (Gabi , Gabi)).
Začněme psát dotaz T-SQL pro tabulky V a R (představující množinu a relaci v této sadě), který kontroluje, zda má R vlastnost reflexivity:
VYBRAT
PŘÍPAD
KDY EXISTUJE
(SELECT v, v FROM dbo.V
AŽ NA
SELECT r1, r2 FROM dbo.R)
Tak to pak ne"
JINÉ „Ano“,
KONEC AS reflexní
První poddotaz v operaci EXCEPT vrací sadu všech seřazených párů (v, v) pro všechny řádky v tabulce V. Druhý poddotaz vrací sadu seřazených párů (r1, r2) pro všechny řádky v tabulce R. Operace EXCEPT tak vrátí všechny seřazené páry, které se vyskytnou v první sadě a chybí ve druhé sadě. Predikát EXISTUJE se používá k testování existence alespoň jednoho záznamu v sadě výsledků. Pokud existuje alespoň jeden takový záznam, pak výraz CASE nám vrátí „Ne“ (žádná reflexivita), ale také „Ano“ - jinak (existuje reflexivita).
Podívejte se na tři ukázkové datové sady v seznamech 3, 4 a 5 a pokuste se určit, bez spuštění dotazu, které z nich budou mít reflexivní vztah. Odpovědi jsou uvedeny dále v textu článku.
/IMAGE/1285155165_073-lis2.gif)
/IMAGE/1285155228_073-lis4.gif)
/IMAGE/1285155272_073-lis5.gif)
Nereagující. Relace R na množině V se nazývá irreflexivní (nezaměňovat s nereflexivitou), pokud pro každý prvek v ∈ V vyplývá, že (v, v) ∉ R. Vztah není ireflexivní, pokud existuje prvek v ∈ V pro což (v, v) ∈ R. Příkladem ireflexivního vztahu na množině F členů mé rodiny je vztah „být rodičem“, protože nikdo nemůže být rodičem sám sobě. Členy tohoto vztahu na F jsou následující dvojice: ((Mila, Itzik), (Mila, Mickey), (Mila, Inna), (Gabi, Itzik), (Gabi, Mickey), (Gabi, Inna)).
Následující dotaz je test, zda je vztah R k V ireflexivní:
VYBRAT
PŘÍPAD
KDY EXISTUJE
(VYBRAT * Z Dbo.R
KDE r1 \u003d r2)
Tak to pak ne"
JINÉ „Ano“
END AS irreflexive
Cizí klíče v definici tabulky R byly zavedeny, aby bylo zajištěno, že atributy prvku r1 a r2 záznamu R mohou tvořit pouze prvky V. Zbývá tedy jen zkontrolovat, zda R nemá záznamy s stejné atributy r1 a r2. Je-li takový záznam nalezen, relace R není ireflexivní, pokud neexistuje žádný záznam, je ireflexivní.
Symetrie. Relace R na množině V se nazývá symetrická, pokud spolu s (r1, r2) ∈ R a (r2, r1) ∈ R. Relace není symetrická, pokud existuje pár (r1, r2) ∈ R, pro který (r2, r1) ∉ R. Na množině F členů rodiny Ben-Gan, vztah „je sourozenec“ by byl příkladem symetrického vztahu. Dvojice tohoto vztahu budou následující sady: ((Itzik, Mickey), (Itzik, Inna), (Mickey, Itzik), (Mickey, Inna), (Inna, Itzik), (Inna, Mickey)).
Následující dotaz je test, zda je poměr R k V symetrický:
VYBRAT
PŘÍPAD
KDY EXISTUJE
(VYBRAT r1, r2 Z dbo.R
AŽ NA
SELECT r2, r1 FROM dbo.R)
Tak to pak ne"
JINÉ „Ano“
KONEC AS symetrický
Kód požadavku používá operaci EXCEPT. První poddotaz operace EXCEPT vrací sadu uspořádaných párů (r1, r2) - záznamy tabulky R a druhý - sadu uspořádaných párů (r2, r1) pro každý záznam R. Pokud je relace R na sada V není symetrická, operace EXCEPT vrátí neprázdnou sadu výsledků a predikát EXISTUJE hodnotu PRAVDA a nakonec výraz CASE vrátí hodnotu „Ne“.
Pokud je vztah symetrický, pak výraz CASE dá „Ano“.
Asymetrie. Relace R na množině V je asymetrická (tato vlastnost by neměla být zaměňována s asymetrií), pokud pro každou kolekci (r1, r2) ∈ R, ve které r1 ≠ r2, platí (r2, r1) ∉ R. Příklad asymetrického vztahu na množině Členové rodiny F autora budou mít rodičovský vztah, který byl popsán výše. Jako cvičení zkuste vymyslet příklad vztahu na neprázdné množině, která je symetrická i asymetrická. Řešení najdete v ukázkových datech v tomto článku.
VYBRAT
PŘÍPAD
KDY EXISTUJE
(VYBERTE r1, r2 Z dbo.R KDE r1 r2
PROSÍT
VYBERTE r2, r1 Z dbo.R KDE r1 r2)
Tak to pak ne"
JINÉ „Ano“
END AS asymetric
Tento kód používá operaci INTERSECT. První poddotaz v této operaci vrátí uspořádaný pár (r1, r2) pro každý záznam v tabulce R, ve které r1 r2.
Druhý poddotaz operace INTERSECT vrací uspořádaný pár (r2, r1) pro každý záznam v tabulce R, ve které r1 je r2. Pokud sada výsledků (výsledek průniku těchto sad) obsahuje alespoň jeden záznam, bude to znamenat, že R není asymetrický; jinak R je asymetrický.
Přechodnost. Vztah R na množině V je tranzitivní, pokud inkluze (a, b) ∈ R a (b, c) ∈ R vždy znamenají, že (a, c) ∈ R. Příklad tranzitivního vztahu na množině členů rodiny F je vztah „Je bratr nebo sestra“, který byl diskutován výše.
Níže uvedený kód testuje tranzitivitu vztahu R:
VYBRAT
PŘÍPAD
KDY EXISTUJE
(VYBRAT *
Z dbo.R AS RA
VNITŘNÍ PŘIPOJENÍ dbo.R JAKO RB
ON RA.r2 \u003d RB.r1
VLEVO VNĚJŠÍ PŘIPOJTE se k dbo.R jako RC
ON RA.r1 \u003d RC.r1 A RB.r2 \u003d RC.r2
KDE JE RC.r1 NULL)
Tak to pak ne"
JINÉ „Ano“
END AS tranzitivní
Nejprve kód používá vnitřní spojení mezi dvěma instancemi R, aby vybral pouze ty řádky, kde r2 v první instanci odpovídá r1 ve druhé instanci. Za druhé, kód používá levé vnější spojení s třetí instancí R, takže r1 první instance R odpovídá r1 třetí instance a r2 druhé instance odpovídá r2 třetí. Pokud je ve vnitřním poddotazu alespoň jeden výsledný řádek (podmínka výběru pro třetí instanci: r1 je Null), znamená to, že relace není tranzitivní; jinak je vztah R tranzitivní.
Vztah ekvivalence. Vztah ekvivalence je vztah, který současně má vlastnosti reflexivity, symetrie a tranzitivity. Výše navržené dotazy můžete použít k samostatné kontrole přítomnosti každé vlastnosti: pokud má relace všechny tři, mělo by dojít k závěru, že existuje relace ekvivalence. Kromě toho můžete pomocí kódů v seznamu 6 otestovat všechny vlastnosti R na V, které byly dříve popsány v tomto článku, včetně kontroly, zda je vlastnost rovnocenná. Pokud spustíte výpis 6 pro ukázková data 1, 2 a 3 (odvozená z výpisů 3, 4 a 5), \u200b\u200bzískáte výsledky uvedené v tabulkách 1, 2 a 3.
/IMAGE/1285156246_074-lis6.gif)
Zpět na základy T-SQL
Proto jsme probrali základní téma z matematické teorie množin: vlastnosti vztahů na množinách. Navrhl jsem kontrolní kódy T-SQL pro kontrolu vlastností nějakého vztahu představovaného tabulkou R (seřazené páry prvků) na množině prvků představovaných tabulkou V.
Použití základních konstrukcí T-SQL nám pomohlo správně nakonfigurovat a použít nástroje tohoto jazyka, abychom lépe porozuměli vlastnostem relací na množinách.
Itzik Ben-Gan ( [chráněno e-mailem]) - Trainer and Consultant, author of books on T-SQL, has the title of SQL Server MVP
Pojem relace spolu s pojmem množiny „prostupuje“ celou matematikou. Intuitivně je vztah chápán jako spojení mezi objekty. Naším úkolem je pomocí výše formulovaných konstrukcí teorie množin definovat v matematickém jazyce to, co se v matematice rozumí pojmu „vztah“.
Binární vztahy na množině
Vzhledem k sadě A. Spojovací prvky hena zástupy Amodelováno párem (du\u003e). Pokud prvek x související s y, proto máme pár (l :, y) jako prvek nějaké množiny; pokud d; není spojen s v, proto dvojice (n: ^) není předmětem množiny. Máme tedy následující definici.
Binárním vztahem na množině A se nazývá libovolná sada párů prvků z A.
Jinými slovy, binární relace na množině A - z podmnožiny přímého produktu AxA \u003d A 2. Zejména samotná sada A 2 všech párů je binární relace.
Analogicky s binárním (nebo dvoumístným) vztahem lze uvažovat p-místní vztah na množině jako podmnožina přímého produktu A". Budeme uvažovat hlavně o binárních vztazích, ale pro stručnost lze jednoduše říci: „vztah na množině A".
Označme libovolný binární vztah řeckým písmenem p.
Já létám ) e p, pak řeknou, že l „je ve vztahu k p s y, a piš
Pokud (dy)? P\u003e máme negaci odpovídajícího tvrzení. V tomto případě spolu se zápisem ~ | (xru) (nebo xru) napište Dr. a přeškrtněte znak vztahu.
Příklad 8.1.1. Zvažte sadu A \u003d (1,2,3,4,5). Spousta párů
definuje na A poměr „méně“, označený znaménkem<.>
11 na stejné sadě, můžeme uvažovat o další sadě párů
definuje vztah rovnosti.
Příklad 8.1.2. Zvažte množinu (N, Z, Q, I, R) základních číselných množin a množinu párů
Máme vztah, který jsme definovali v části 2.2 jako vztah přísného zahrnutí množin. Všimněte si, že například dvojice (Q. I) ns leží v označené množině, protože Qczl se navíc tyto sady neprotínají.
Příklad 8.1.3. Mnoho slov L \u003d (aktuální, kočka, šok, kůl, lak) je uvedeno. Zvažte tento vztah:
p \u003d ((proud, šok), (šok, proud), (šok, počet), (počet, šok),
(kůl, lak), (lak, kůl), (kočka, kůl), (kůl, kočka)).
Tento vztah lze vyjádřit následovně: slova množiny Ajsou ve vztahu k p právě tehdy, pokud mají přesně dvě stejná písmena.
Všimněte si, že jakákoli sada párů je vztah, bez ohledu na to, zda pro tento vztah existuje dobrý slovní popis.
Vzhledem k tomu, že relace je množina, lze ji určit charakteristickou vlastností, síť pak predikátem P (xy):p \u003d ((. *, \u003e\u003e) eL 2 P (xy)). Používá se také notace:
Přečtěte si: „g je ve vztahu k v jen a jen pokud je to pravda P (xy) ".
Příklad 8.1.4.Definujeme na množině /! \u003d (1,2,3,4,5) poměr:
Tady P (xy) \u003d (l + 2 \u003d y). Pojďme definovat tento vztah výčtem párů:
Příklad 8.1.5.Pojďme definovat na množině Z(nebo na televizoru N)relace pomocí věty: „Existuje celé číslo /? takové, že x \u003d n y ". Můžete psát symbolicky:
Máme již dříve definovaný vztah dělitelnosti, označený znaménkem:. Tento vztah zahrnuje takové páry jako (6,2), (6,3), (4,4), (111, -37) a další. Na rozdíl od předchozích příkladů je tato sada párů nekonečná a nebude možné vypsat všechny páry.
Zvažte nejdůležitější vlastnosti, které mohou mít binární vztahy na množině.
Poměr p na množině A volala reflexnípokud nějaký prvek x z A je ve vztahu k p sám o sobě, tedy pro všechna q; z Aprovedl jsem:
Příklad 8.1.6.Zvažte vztah dělitelnosti na množině Z.Vezměte libovolné celé číslo x. Protože x \u003d x 9 pak x ‘: x. To znamená, že každé celé číslo je dělitelné samo o sobě: V.veZ (l: l).Proto je vztah dělitelnosti reflexivní.
Jelikož je libovolná množina sama o sobě podmnožinou, relace zahrnutí množiny je reflexivní (na jakékoli množině množin).
Poměr p na množině A volala aireireflexivnípokud žádný prvek sady A není ve vztahu k p sám se sebou:
Příklad 8.1.7. Rantireflexní, protože žádný počet není menší než on sám.
Vytvořme negaci věty „Vztah p je reflexivní“:
Relace p tedy není reflexivní právě tehdy, když existuje prvek heA, který není ve vztahu k p sám se sebou. Postoj, který není reflexivní, nemusí být aitireflexivní.
Příklad 8.1.8.Zvažte vztah na scéně R,dané větou "Číslo x naproti číslu y ". Číslo x zavolal opak čísla y, pokud částka x + y se rovná 0.
Tento postoj nereflektuje. Protipříklad: x \u003d 1. Protože 1 + 1 * 0, pak číslo 1 není opakem 1.
Tento přístup není antireflexní. Protipříklad :, v \u003d 0. Protože 0 + 0 \u003d 0, pak je číslo 0 opakem 0.
Poměr p na množině A volala symetrickýpokud z čeho x je ve vztahu k p s y, z toho vyplývá v je ve vztahu k p s
Příklad 8.1.9.Z identity x + y \u003d y + .x prohlášení následuje: pro všechna reálná čísla x a v Pokud x naproti v, tedy vopak x. To znamená, že tento vztah je symetrický. Často říkají jednoduše: „Čísla x a v jsou naproti. “
Poměr "Počet x menší počet y " na scéně Rnení symetrický: 3 je menší než 4, ale 4 není menší než 3.
Poměr p na množině A volala antisymetrickýpokud pro žádné jiné prvky xay z A, takhle hru, neprovedeno
urx:
Příklad 8.1.10.Poměr „méně“ na sadě Rantisymetrický.
Definici antisymetrického vztahu lze formulovat i jinak. Pojďme si představit notaci:
Pomocí tabulky pravdivosti lze dokázat, že vzorec 1 R l M -ekvivalentní vzorci M l K -\u003e P, což je podle pravidla kontrapozice ekvivalentní 1 R -\u003e ~ | (L / L NA). Na základě toho můžeme říci, že poměr p je antisymetrický právě tehdy, když je splněna jedna z ekvivalentních podmínek:
A) Ze skutečnosti, že hru a hurá, by měl x \u003d y:
B) Žádné jiné prvky nemohou být ve vzájemném vztahu p současně.
Příklad 8.1.11.Zvažte inkluzní vztah na libovolné rodině množin. Od LsUl Y ^ X \u003d\u003e X \u003d Y, potom je inkluze e antisymetrický vztah.
Příklad 8.1.12.Dělitelnost na množině Znení symetrický ani antisymetrický. Protože poměr 4: 2, ale 2 × 4, poměr není symetrický. Vzhledem k tomu, že 2: (- 2) a (-2): 2, ale (-2) ^ 2, poměr není antisymetrický.
Na množině N přirozených čísel však máme antisymetrický vztah: Vjt ^ eN (x: y lu: x -\u003e x \u003d y). Zkontrolujte toto tvrzení pomocí definice dělitelnosti.
Poměr p na množině A volala tranzitivnípokud z čeho x je ve vztahu k p s y, a v je ve vztahu k p se z, z toho vyplývá, že V je ve vztahu k p se z:
Příklad 8.1.13.Vztah dělitelnosti je přechodný (jak na množině Z, tak na množině N): x: y l y: z \u003d\u003e x: z. Ukažme to. Nech být x: y a y: z. Pak x \u003d nya y \u003d kz pro některá celá čísla p a na. Pak x \u003d n (kz) \u003d (nk) z = mz, Kde texistuje celé číslo. proto xz.
Nastavený vztah zahrnutí je také tranzitivní: XcY l YcZ \u003d\u003e XezZ. Dokažte to.
Vztah "Čísla x a v opak “není tranzitivní. Protiklad: x \u003d 2, y \u003d -2, 2 \u003d 2. Pak jsou čísla 2 a (-2) opačná a také (-2) a 2 jsou opačná. Ale čísla x \u003d 2 a z \u003d 2 ns jsou naproti.
Příklad 8.1.14. Zvažme několik příkladů vztahů z předchozího odstavce.
Vztah v příkladu 8.1.3 je antireflexní a symetrický. Vztah z příkladu 8.1.4 je antireflexní a antisymetrický. Žádný z těchto vztahů není přechodný. Prokažte to příslušnými protiklady.
Některé vztahy, které mají současně několik vlastností, dostávají obecná jména. Z výše uvažovaných příkladů má vztah zahrnutí množin a vztah dělitelnosti na množině N současně vlastnosti reflexivity, antisymmegricity a transitivity. Tyto tři vlastnosti má také vztah "X menší nebo rovné v»Definováno na množině R (nebo na kterékoli z jejích podmnožin):
Nazývá se reflexivní, antisymetrický a tranzitivní vztah postoj řádu.
Hodně A, na kterém je dán řádový vztah p objednaná sada... Psát si (A, R).
V současné době je uspořádaná teorie množin velkou oblastí matematiky, která se věnuje celým knihám. Zmíníme pouze řadu funkcí konceptu „objednané množiny“.
Intuitivně jsou slova „uspořádaná množina“ často chápána v užším smyslu. Uvažujme uspořádané l-ku, složené z párově různých prvků. Například pět písmen (III, K, O, L, A) definuje slovo ŠKOLA. V tomto případě se slova „prvky zapisují v určitém pořadí“ chápou v tom smyslu, že jsme je očíslovali přirozenými čísly 1, 2, 3, 4, 5 a uspořádali je ve vzestupném pořadí čísel. Pojďme zobecnit tento příklad.
Nechť tam bude dána sada „-element“ A. Po nějakém číslování prvků a, a 2\u003e a „, ve skutečnosti skončíme s uspořádanou sadou definováním relačního vztahu následujícím způsobem:
Poměr je chápán takto: že prvek x spojené s jiným prvkem y, znamená, že x napsáno v n-tici vlevo v.
Příklad 8.1.15.Je uvedena sada /4\u003d(а,b.c,r). Uspořádané čtyři z jeho různých prvků (b, c, a, d) poskytnou následující relační vztah:
((b, b), (b, c), (b, a), (b, d), (c, c), (c, a), (c, d), (a, a), ( a, d), (d, d)).
Všimněte si, že objednávka nemusí mít takzvanou vlastnost linearity.
Příklad 8.1.16.Zvažte na scéně A \u003d (2,4,6,8) poměr dělitelnosti:. Nastavit tento vztah s více páry. Od roku A leží pouze přirozená čísla, potom: relace pořadí. Máme objednanou sadu A, :).
Takové pořadí nelze představovat jako uspořádané čtyři po sobě jdoucí prvky. Vztah můžete graficky znázornit pomocí teček a šipek: z bodu x přesně všipka vede právě tehdy x: y.
Zvažte čísla 6 a 4. Žádná z nich není dělitelná druhou. Říkají, že se jedná o nesrovnatelné prvky.
Pusťte na scénu A je dán vztah řádu p. Prvky * a vse nazývají srovnatelnýpokud platí alespoň jeden ze dvou vztahů hru nebo urx.
Objednejte p na scéně A volala lineárnípokud existují dva prvky sady A jsou srovnatelné. Volá se množina, na které je definován lineární řád lineárně uspořádáno (nebo řetěz).
Příklad 8.1.17.R je lineární uspořádání od Vx ^ yeR (x Proto (R,
objednaná sada.
Obecně platí, že vztah dělitelnosti pro přirozená čísla není lineární řád. Protiklad je uveden v příkladu 8.1.16. "
Pomsta, že jakékoli lineární uspořádání na konečné sadě je dáno číslováním jejích prvků. Aby se zdůraznilo, že objednávka nemusí být lineární, uspořádaná množina se obecně někdy nazývá částečně uspořádaná.