Binárne vzťahy, vlastnosti relácií. Vzťahy ekvivalencie, poriadku a tolerancie. Binárne vzťahy - MT1102: Lineárna algebra (Úvod do matematiky) - Podniková informatika Je vzťah a vzťah ekvivalencie
KURZOVÁ PRÁCA
"Vzťah ekvivalencie"
Úvod
Kapitola 1. Pojem postoj. Definícia, typy, príklady vzťahov
Kapitola 2. Rozdelenie do tried. Faktor-set. Vzťah ekvivalencie. Operácie s ekvivalenciami.
Kapitola 3. Vzťahy v školskej matematike
Záver
Zoznam použitých zdrojov
Úvod
Táto práca je venovaná štúdiu pojmu vzťahy vo všeobecnosti a najmä vzťahom ekvivalencie. Tieto pojmy sú v kurze algebry základné a zároveň ich možno odvodiť zo všeobecne akceptovaných každodenných pojmov rovnosti, podobnosti a poriadku. Vďaka tomu je možné ich predstaviť starším školákom bez toho, aby ste sa vŕtali v teórii, na konkrétnych príkladoch zo školského kurzu matematiky.
Prvá kapitola práce v kurze bude venovaná pojmu vzťahy vo všeobecnosti, metódam špecifikácie vzťahov, algebraickej a geometrickej interpretácii vzťahov. Uvedie sa niekoľko množinovo-teoretických operácií s vzťahmi. Uvažuje sa o základných vlastnostiach vzťahov a význame týchto vlastností pre geometrické a algebraické metódy upresňovania vzťahov. Kapitola je umiestnená na 7 listoch.
Druhá kapitola tejto práce odhaľuje význam vzťahu ekvivalencie. Je dokázaná veta o ekvivalencii definícií. Uvádza sa niekoľko príkladov. Sú predstavené koncepty rozdelenia do tried a množín faktorov. Je definovaných aj niekoľko ďalších dôležitých vzťahov.
Tretia kapitola je venovaná úvahám o niektorých vzťahoch predstavených na súboroch objektov známych a zrozumiteľných každému stredoškolskému študentovi. Vlastnosti vzťahov ekvivalencie, tolerancie a poriadku sú jasne znázornené. Uvádza sa záver o možnosti zavedenia týchto pojmov v triede matematických krúžkov. Kapitola obsahuje 5 listov.
Kapitola 1. Pojem postoj. Definícia, typy, príklady vzťahov
Definícia postoja. Metódy na definovanie vzťahov
Ak hovoríme jazykom zrozumiteľným pre školáka, definovať vzťah znamená naznačiť, medzi akými predmetmi sa napĺňa.
Napríklad vzťah „byť bratom“ bude plne definovaný, ak vytvoríme zoznam všetkých dvojíc ľudí, z ktorých jeden je bratom druhého.
Vzťah je možné definovať nielen pre dvojice objektov (binárne), ale aj pre trojice, štvorice atď.
Príkladom trojmiestneho (ternárneho) vzťahu sú algebraické operácie. Napríklad vzťah „tvor súčet“ má zmysel pre trojice čísel (x, y, z) a je splnený v prípade, keď x + y = z.
Prejdime k prísnejšej definícii.
Nech A a B sú ľubovoľné neprázdne množiny.
Definícia 1.1. Kartézsky súčin množiny A a množiny B je množina A x B, ktorej prvkami sú všetky možné dvojice (a, b), pričom prvý prvok je prevzatý z množiny A a druhý z množiny B. Dva takéto dvojice sa považujú za rovnocenné, ak ich a prvý a druhý prvok: (a, b) = (c, d) a = c a b = d.
Príklad 1.1. Ak A = (0, 1, +) a B = (□, o, , +), potom
A B - ((0, □), (0, o), (0. ), (0, +), (1, □), (1, o), (1, ), (1, +), ( +, □), (+, o), (+, ), (+, +)). Jednoduchá úvaha potvrdzuje platnosť nasledujúcich vzťahov:
=
=
=
4) A je podmnožinou B a C je podmnožinou D, potom podmnožinou
Definícia 1.3. Binárny vzťah medzi množinami A a B je ľubovoľná podmnožina karteziánskeho súčinu A x B, teda ľubovoľný prvok množiny P(A x B) všetkých podmnožín množiny A x B.
Ak |A| = m, |B|=n, potom karteziánsky súčin A x B bude pozostávať z m rôznych párov. V tomto prípade | P(A x B) | = 2 mn, - to je celkový počet všetkých možných binárnych vzťahov medzi množinami A a B.
Binárne vzťahy budeme označovať malými gréckymi písmenami. Ak (a, b) p, potom prvok a hovoríme vo vzťahu k prvku b vo vzťahu ρ.
Spomedzi všetkých vzťahov medzi množinami A a B vynikajú: prázdny vzťah Ø, ktorý neobsahuje ani jeden pár; univerzálny vzťah obsahujúci všetky možné dvojice, teda samotný kartézsky súčin A a B Pre každý vzťah ρ P(A x B) prebiehajú inklúzie
ρ A x B
Existujú dva vhodné spôsoby, ako reprezentovať vzťahy medzi prvkami konečných množín:
) pomocou binárnych booleovských matíc;
) pomocou grafov.
Nech A = (a 1, a 2, …a m), B = (b 1, b 2, …b m), ρ A x B
Zostrojme maticu M(ρ) rozmeru m x n nasledovne. Riadky tejto matice označíme prvkami množiny A umiestnenými v určitom pevnom poradí a podobne označíme stĺpce prvkami množiny B. Potom dáme ako prvky matice M(ρ):
Tu sú 0, 1 prvky binárnej Booleovej algebry B 2 . Prvok teda predstavuje logický význam výroku „dvojica patrí do vzťahu ρ“.
Je zrejmé, že rozdielnym vzťahom medzi množinami A a B zodpovedajú rôzne binárne booleovské matice. Zdôrazňujeme, že poradie prvkov v A a B je raz a navždy pevne dané.
Nech M-n-prvková množina a ρ je relácia na nej. Vzťah na M môže byť špecifikovaný maticou n x n. Matica, pre ktorú a ij = 0 definuje prázdny vzťah Ø, ktorý nie je splnený pre žiadny pár.
Matica, pre ktorú a ij = 1 udáva úplný vzťah M x M, ktorý je splnený pre všetky dvojice.
Osobitnú úlohu zohráva aj matica ||δ i j ||, kde
Symbol sa nazýva Kroneckerov symbol. Táto matica zodpovedá takzvanému diagonálnemu vzťahu E alebo vzťahu rovnosti: (x, y), ak x a y sú rovnakým prvkom množiny.
Je tiež užitočné zaviesť antidiagonálny vzťah pomocou podmienky:
Pre prázdne, úplné, diagonálne a antidiagonálne vzťahy nastáva kuriózna vlastnosť - ich matice nezávisia od voľby číslovania prvkov množiny M. Inými slovami, ak je vzťah ρ taký, že pre akúkoľvek voľbu číslovania v M matrice || a ij || sa zhodujú, potom je ρ buď úplné, prázdne, diagonálne alebo antidiagonálne.
Vzťah môžete reprezentovať iným spôsobom:
Nech je opäť ρ M x M. Definujme (orientovaný) graf G(ρ) takto: Množina vrcholov tohto grafu bude tvoriť množinu M, v tomto prípade sa z vrcholu a i do vrcholu b j nakreslí hrana a iba ak 
, a ak (a i, a i), tak v bode a i nakreslíme slučku opúšťajúcu a vchádzajúcu do toho istého bodu.
Prázdny vzťah zodpovedá grafu bez šípok a slučiek, diagonálny vzťah je opísaný grafom, v ktorom sú len slučky (obrázok 1.1). Úplný vzťah je daný úplným grafom (všetky vrcholy sú spojené so všetkými vrcholmi, obr. 1.2).
ryža. 1.1 
ryža. 1.2
Graf je geometrickým znázornením vzťahu, rovnako ako je graf geometrickým znázornením funkcie. Geometrický jazyk je užitočný, keď je graf celkom jednoduchý. Naopak, z hľadiska vzťahov je pohodlnejšie študovať a popisovať grafy s veľkým počtom vrcholov.
II. Funguje ako vzťahy
Za špeciálny prípad vzťahov možno považovať aj funkcie. Nech je vzťah na množine M taký, že na každé xM pripadá práve jeden prvok y M, pre ktorý (x, y) . Každý prvok xM je teda spojený s nejakým y M definovaným touto podmienkou. Tento vzťah sa nazýva funkcia alebo mapovanie. Množina párov, pre ktoré (x, y) sa nazýva graf funkcie.
Príklad: Ak M je číselná os a vzťah je rovnosť x = y, potom graf pozostáva zo všetkých bodov tvaru (x, x) a je osou súradnicového uhla (graf funkcie y = X). Ak je vzťah splnený pre tie dvojice, pre ktoré y = sin x, potom je grafom tejto funkcie obyčajná sínusoida.
Naša definícia grafu je teda zovšeobecnením obvyklého grafu numerických funkcií.
III. Operácie na vzťahoch.
Keďže vzťahy medzi množinami A a B nie sú ničím iným ako podmnožinami množiny A x B, sú pre ne definované všetky množinovo-teoretické operácie.
Definícia 1.4. Priesečník vzťahov ρ a δ je priesečníkom zodpovedajúcich podmnožín. Je jasné, že (x, y) vtedy a len vtedy, ak súčasne (x, y) 
.
Definícia 1.5. Zjednotenie vzťahov ρ a δ je zjednotením zodpovedajúcich podmnožín. Je jasné, že (x, y) vtedy a len vtedy, ak je splnený aspoň jeden zo vzťahov (x, y).
Dôležitú úlohu zohráva operácia označovaná ρδ - súčin vzťahov. Táto operácia je definovaná nasledovne: vzťah (x, y) je ekvivalentný skutočnosti, že existuje z, pre ktoré platí (x, z) 
IV. Vlastnosti vzťahov.
Definícia 1.6. Vzťah ρ sa nazýva reflexívny, ak je vždy splnený medzi objektom a ním samým: (x, x).
Reflexívne vzťahy sú vždy reprezentované vo forme matíc s jednotkami na hlavnej diagonále. V grafe reprezentujúcom reflexný vzťah má každý vrchol slučku.
Definícia 1.7. Vzťah ρ sa nazýva antireflexný, ak z (x, y) vždy vyplýva x ≠ y.
Vzťah „byť brat“, „byť starší“ je antireflexívny.
Matica reprezentujúca antireflexný vzťah má na hlavnej diagonále nuly a príslušný graf určite nemá žiadne slučky.
Definícia 1.8. Vzťah ρ sa nazýva symetrický, ak (x, y) vždy implikuje (y, x).
V matici reprezentujúcej symetrický vzťah sú prvky umiestnené symetricky vzhľadom na hlavnú uhlopriečku navzájom rovné a ij = a ji.
V príslušnom stĺpci je spolu s každou šípkou šípka v opačnom smere. Symetrický vzťah môže byť reprezentovaný ako neorientovaný graf.
Definícia 1.9. Vzťah ρ sa nazýva asymetrický, ak aspoň jeden z dvoch vzťahov (x, y) alebo (y, x) nie je splnený.
Pre prvky matice to vedie k rovnosti: a ij ∙a ji =0
V príslušnom grafe nemôžu byť šípky spájajúce dva vrcholy v opačnom smere.
Veta 1.1: Ak je vzťah asymetrický, potom je antireflexný.
Definícia 1.10. Relácia ρ sa nazýva antisymetrická, ak sú vzťahy (x, y) a (y, x) splnené súčasne len vtedy, keď x = y.
Pre prvky matice to vedie k rovnosti: a ij ∙a ji =0, keď i≠j
Definícia 1.11. Relácia ρ sa nazýva tranzitívna, ak z toho, že platia vzťahy (x, z) a (z, y), vyplýva, že (x, y). Indukciou z toho vyplýva nasledujúca vlastnosť: ak (x, z 1), (z 1, z 2) ... (z n -1, y) potom (x, y).
Táto vlastnosť je dobre interpretovaná v grafe: ak sú body x a y spojené cestou v smere šípok, potom existuje šípka vedúca priamo z vrcholu x k vrcholu y.
ekvivalenčná relačná matematika
Kapitola 2. Rozdelenie do tried. Vzťah ekvivalencie. Ekvivalenčné vlastnosti. Súprava faktorov
Rozdelenie do tried. Vzťah ekvivalencie
Definícia 2.1. Zameniteľné nazvime tie a len tie objekty danej množiny M, ktoré majú rovnakú množinu formálnych znakov, ktoré sú v danej situácii podstatné.
Označme M x množinu všetkých objektov zameniteľných s objektom x. Je zrejmé, že x M x a spojenie všetkých M x (pre všetky možné x z M) sa zhodujú s úplnou množinou M:
Predstierajme to 
. To znamená, že existuje nejaký prvok z, ktorý súčasne patrí do a a . Takže x je zameniteľné so z a z je zameniteľné s y. Preto je x zameniteľné s y, a teda s akýmkoľvek prvkom z. Teda . Spätné prepínanie je znázornené rovnakým spôsobom. Množiny vyskytujúce sa v zjednotení (2.1) sa teda buď nepretínajú, alebo sa úplne zhodujú.
Definícia 2.2. Systém neprázdnych podmnožín (M 1, M 2,….) množiny M nazveme delením tejto množiny, ak
Samotné množiny sa nazývajú triedy oddielov.
Definícia 2.3. Vzťah ρ na množine M sa nazýva ekvivalencia (alebo relácia ekvivalencie), ak existuje rozdelenie (M 1, M 2,...) množiny M tak, že (x, y) je splnené vtedy a len vtedy, ak x a y patria do nejakej všeobecnej triedy M i danej partície.
Nech (M 1, M 2,….) je delením množiny M. Na základe tohto delenia určíme vzťah ρ na M: (x, y), ak x a y patria do nejakej všeobecnej triedy M i tento oddiel. Je zrejmé, že vzťah ρ je ekvivalencia. Nazvime ρ vzťah ekvivalencie zodpovedajúci danému oddielu.
Definícia 2.4. Ak v každej podmnožine M i vyberieme prvok x i v nej obsiahnutý, potom sa tento prvok bude nazývať štandardom pre každý prvok y zahrnutý v tej istej množine M i . Podľa definície predpokladajme, že vzťah ρ* „byť štandardom“ (x i, y) je splnený
Je ľahké vidieť, že ekvivalenciu ρ zodpovedajúcu danému rozdeleniu možno definovať takto: (z, y), ak z a y majú spoločnú normu (x i, z) a (x i, y).
Príklad 2.1: Uvažujme ako M množinu nezáporných celých čísel a rozdeľme jej na množinu M 0 párnych čísel a množinu M 1 nepárnych čísel. Zodpovedajúci vzťah ekvivalencie na množine celých čísel je označený takto:
a znie: n je porovnateľné s m modulo 2. Je prirodzené, že ako štandardy volíme 0 pre párne čísla a 1 pre nepárne čísla. Podobne, rozdelením tej istej množiny M na k podmnožín M 0, M 1,... M k -1, kde M j pozostáva zo všetkých čísel, ktoré po delení k dávajú zvyšok j, dospejeme k vzťahu ekvivalencie:
čo platí, ak n a m majú rovnaký zvyšok pri delení k.
Je prirodzené zvoliť zodpovedajúci zvyšok j ako štandard v každom M j.
II. Súprava faktorov
Nech je vzťah ekvivalencie. Potom podľa vety existuje rozdelenie (M 1, M 2,....) množiny M na triedy navzájom ekvivalentných prvkov - takzvané triedy ekvivalencie.
Definícia 2.5. Množinu tried ekvivalencie vzhľadom na vzťah označujeme M/ a čítame ako podielovú množinu množiny M vzhľadom na vzťah.
Nech φ: M → S je surjektívne zobrazenie množiny M na nejakú množinu S.
Pre ľubovoľné φ: M → S - surjektívne zobrazenie existuje vzťah ekvivalencie na množine M taký, že M/ a S možno dať do korešpondencie jedna ku jednej.
III. Ekvivalenčné vlastnosti
Definícia 2.6. Relácia ρ na množine M sa nazýva relácia ekvivalencie, ak je reflexívna, symetrická a tranzitívna.
Veta 2.1: Ak je relácia ρ na množine M reflexná, symetrická a tranzitívna, existuje rozdelenie (M 1 , M 2 ,….) množiny M také, že (x, y) platí práve vtedy, ak x a y patrí do nejakej všeobecnej triedy M i danej partície.
Obrátene: Ak je dané rozdelenie (M 1, M 2,....) a binárna relácia ρ je daná ako „patrí do všeobecnej triedy rozdelenia“, potom je ρ reflexívne, symetrické a tranzitívne.
dôkaz:
Uvažujme reflexívny, symetrický a tranzitívny vzťah ρ na M. Nech sa pre ľubovoľný skladá zo všetkých z, pre ktoré (x, z) ρ
Lema 2.1: Pre ľubovoľné x a y buď alebo 
Z lemy a reflexivity vzťahu ρ vyplýva, že množiny tvaru tvoria predelenie množiny M. (Toto rozdelenie môžeme prirodzene nazvať predelením zodpovedajúcim pôvodnému vzťahu). Nech teraz (x, y) ρ. To znamená, že y. Ale aj x kvôli (x, x) ρ. Preto sú oba prvky zahrnuté v . Takže ak (x, y) ρ, potom x a y sú zahrnuté do všeobecnej triedy rozdelenia. Naopak, nech u a v. Ukážme, že (u, v) ρ V skutočnosti máme (x, u) ρ a (x, v) ρ. Preto symetriou (u, x) ρ. Tranzitivita z (u, x) ρ a (x, v) ρ vyplýva (u, v) ρ. Prvá časť vety bola dokázaná.
Nech je daný dielik (M 1, M 2,….) množiny M. spojenie všetkých tried oddielov sa zhoduje s M, potom je ľubovoľné x zahrnuté do nejakej triedy . Z toho vyplýva, že (x, x) ρ, t.j. ρ - reflexné. Ak x a y sú v nejakej triede, potom y a x sú v tej istej triede. To znamená, že (x, y) ρ implikuje (y, x) ρ, t.j. vzťah je symetrický. Nech teraz platí (x, y) ρ a (y, z) ρ. To znamená, že x a y sú v nejakej triede a y a z sú v nejakej triede. Triedy majú spoločný prvok y, a preto sa zhodujú. To znamená, že x a z sú zahrnuté v triede, t.j. (x, z) platí ρ a vzťah je tranzitívny. Veta je dokázaná.
IV. Operácie s ekvivalenciami.
Tu definujeme niektoré množinové operácie na ekvivalenciách a uvádzame ich dôležité vlastnosti bez dôkazu.
Pripomeňme si, že relácia je pár (), kde M je množina prvkov vstupujúcich do vzťahu a je množina párov, pre ktoré je relácia splnená.
Definícia 2.7. Priesečník vzťahov (ρ 1, M) a (ρ 2, M) je vzťah definovaný priesečníkom príslušných podmnožín. (x, y) ρ 1 ρ 2 vtedy a len vtedy, ak obe (x, y) ρ 1 a (x, y) ρ 2 .
Veta 2.2: Priesečník ρ 1 ρ 2 ekvivalencií ρ 1 ρ 2 je sám osebe vzťahom ekvivalencie.
Definícia 2.8. Zjednotenie relácií (ρ 1, M) a (ρ 2, M) je relácia definovaná zjednotením zodpovedajúcich podmnožín. (x, y) ρ 1 ρ 2 práve vtedy, ak (x, y) ρ 1 alebo (x, y) ρ 2 .
Veta 2.3: Aby spojenie ρ 1 ρ 2 ekvivalencií ρ 1 ρ 2 bolo samo osebe vzťahom ekvivalencie, je potrebné a postačujúce, aby
ρ 1 ρ 2 =ρ 1 ρ 2
Definícia 2.9. Priamy súčet vzťahov (ρ 1, M 1) a (ρ 2, M 2) sa nazýva pomer). Priamy súčet sa označí (ρ 1, M 1) (ρ 2, M 2).
Ak teda (ρ 1, M 1) (ρ 2, M 2)= (), potom M=.
Veta 2.4: Ak , a vzťahy sú ekvivalencie, potom priamy súčet vzťahov (ρ 1, M 1) (ρ 2, M 2) = (), je tiež ekvivalenciou.
V. Typy vzťahov
Predstavme si niekoľko dôležitejších typov vzťahov. Príklady budú uvedené v tretej kapitole.
Definícia 2.10. Vzťah ρ na množine M sa nazýva tolerancia, ak je reflexná a symetrická.
Definícia 2.11. Relácia ρ na množine M sa nazýva relácia prísneho poriadku, ak je antireflexívna a tranzitívna.
Definícia 2.12. Relácia striktného usporiadania ρ sa nazýva dokonalé prísne usporiadanie, ak pre ľubovoľnú dvojicu prvkov x a y z M platí buď (x, y) alebo (y, x).
Definícia 2.13. Relácia ρ na množine M sa nazýva relácia nestriktného poriadku, ak ju možno znázorniť v tvare:
Kapitola 3. Vzťahy v školskej matematike
Vzťahy medzi geometrickými objektmi
Mnohé známe pojmy zo školskej matematiky sú v podstate názvami binárnych vzťahov a základné vety s nimi spojené vyjadrujú vlastnosti týchto vzťahov.
Príklad 3.1. Nech M je množina všetkých priamok v rovine. Pomer X || Y znamená, že čiary X a Y sú rovnobežné. Stanovme niektoré vlastnosti tohto vzťahu.
Postoj || antireflexný. V skutočnosti žiadna priamka nie je rovnobežná sama so sebou.
Postoj || symetricky, je to zrejmé zo skutočnosti, že v definícii rovnobežnosti sú obe čiary rovnaké.
Postoj || takmer tranzitívny. menovite: ak X || Y a Y || Z, potom buď X || Z alebo pikantné X a Z sú rovnaké. Ak by to tak nebolo, potom by sa priamky X a Z pretínali. Ale, ako je známe z geometrie, ak sa priamka Z pretína s jednou z rovnobežiek X, potom sa pretína aj s ďalšou z rovnobežiek Y, t.j. nebolo by možné mať vzťah Y || Z.
Vzťah rovnobežnosti medzi priamymi čiarami teda ešte nemá dobré vlastnosti. Ale to, čo bolo povedané vyššie, uľahčuje predstavu, aký druh vzťahu, podobný paralelizmu, bude vzťahom ekvivalencie. Konkrétne definujeme vzťah
Čo sa vykonáva, keď sú čiary rovnobežné alebo sa zhodujú. Podľa definície X ||| X pre ľubovoľnú priamku X. Symetria vzťahu ||| je tiež zrejmé. Nakoniec, ak X||| Y a Y ||| Z, potom X ||| Z. Skutočne, ak X || Y a Y = Z, potom X || Z; ak X = Y a Y || Z, potom X || Z. Nakoniec, ak X || Y a Y || Z, potom, podľa toho, čo bolo povedané skôr, buď X = Z alebo X || Z. Vo všetkých prípadoch máme X ||| Z.
Postoj ||| na množine čiar vyzerá v algebraickej forme veľmi prirodzene. Ak v rovine zadáte karteziánske súradnice x a y, potom každá priamka, ktorá nie je kolmá na os Ox (nie je vertikálna), je daná rovnicou y=kx+b. Inými slovami, ľubovoľný riadok (s uvedenou výnimkou) je definovaný dvojicou čísel (k, b). Nech je priamka X daná rovnicou y=kx+b a priamka Y rovnicou y=k’x+b’. Potom je vzťah X|||Y splnený práve vtedy, ak k=k’ (k je dotyčnica uhla sklonu priamky k osi Ox). Vzťah X||Y znamená, že k=k‘ a zároveň b≠b‘, t.j. priame čiary sú rôzne. Pre zvislé čiary môžeme dať k=∞ () a podmienka k=k’bude stále znamenať X|||Y. Táto zhoda však nie je veľmi pekná, keďže pre k=∞ nemáme druhý parameter, ktorý by rozlišoval rovnobežky.
V analytickej geometrii je daná univerzálnejšia (normálna) forma špecifikácie priamky: x cos α + y sin α - p = 0, ktorá opisuje priamku akéhokoľvek druhu. Tu p je dĺžka kolmice zníženej od začiatku k priamke, α je uhol sklonu tejto kolmice k osi x.
Každý riadok je teda spojený s dvojicou čísel (α, p), kde 0 ≤ α< 2π и 0 ≤ р < +∞. Соотношение X|||Y означает, что для соответствующих прямых α = α’ или α = α’ + π. Каждой прямой соответствует точка на плоскости параметров α и р, лежащая в области, изображенной на рисунке 3.2. Пары вертикальных прямых α=const и α+ π=const (0 ≤ α < π) суть классы эквивалентности отношения |||.
Príklad 3.2. Na množine priamych čiar v rovine existuje ďalší dôležitý vzťah: X ┴Y (X je kolmé na Y). Vzťah kolmosti má nasledujúce dôležité vlastnosti:
1. Antireflexivita. Nemožné X ┴ X.
2. Symetria. Ak X ┴ Y, potom Y ┴ X.
3. Ak X ┴ Y a Y ┴ Z, potom je to nemožné pre X ┴ Z. Z X ┴ Y a Y ┴ Z samozrejme vyplýva, že X ||| Z. Naopak, ak X ||| Z, potom existuje spoločná kolmica Y na priamky X a Z, t.j. také Y, že X┴Y a Y┴Z.
Oba posledné výroky znamenajú, že druhá mocnina pomeru kolmosti je pomer ||| - „vylepšený paralelizmus“:
┴ ┴ = ┴ 2 =|||.
Príklad 3.3. Zaveďme ďalší vzťah X na Y na M, to znamená, že priamky majú aspoň jeden spoločný bod, t.j. pretínajú alebo sa zhodujú. Je zrejmé, že vzťah Per je reflexívny, symetrický, ale nie tranzitívny a je vzťahom tolerancie.
Vyberme si určitý bod P v rovine a uvažujme množinu K p všetkých priamok prechádzajúcich týmto bodom. Je ľahké vidieť, že Kp je trieda tolerancie. Všetky priamky z Kp majú totiž spoločný bod, a to samotný bod P. Na druhej strane žiadna priamka X nezahrnutá do Kp sa nepretína s nejakou priamkou z Kp, konkrétne s priamkou prechádzajúcou bodom. P rovnobežne s X.
Príklad 3.4. Nech je teraz M množina všetkých trojuholníkov v rovine. Rovnosť a podobnosť trojuholníkov sú vzťahy ekvivalencie.
Príklad 3.5. Označme M k množinu kružníc v rovine a definujme vzťah X |= Y podmienkou, že kružnica X je vo vnútri kružnice Y. Tento vzťah je antireflexný, tranzitívny, t.j. je prísny poriadok. Toto poradie nie je dokonalé, pretože Existujú kruhy, z ktorých žiadny neleží vo vnútri toho druhého.
Príklad 3.6. Množine všetkých priamok priradíme označenie M Potom môžeme uvažovať o vzťahu medzi priamkami a kružnicami. Príkladom takéhoto vzťahu je vzťah X Cas Y - priamka X sa dotýka kruhu Y.
II. Vzťahy medzi rovnicami.
Nech sa teraz množina M skladá z rovníc v tvare:
f(x)=g(x) (α)
Množinu všetkých koreňov rovnice α označíme Rα.
Napríklad pre rovnicu
x 2 = x 3 (α 1)
Rα 1 = (0,1). Pre rovnicu
cos x = hriech x (α 2)
Rα 2 = (…). Pre rovnicu
X2 = -1 (α 3)
Rα 3 =Ø. Pre rovnicu
(1+ x) 2 = x 2 +2x+1 (α 4)
Ra4=(-∞, +∞).
Príklad 3.7. Uveďme si teraz vzťahy medzi rovnicami: rovnice α a β nazývame ekvivalent α ≈ β, ak Rα = Rβ.
Z toho, že rovnosť množín je vzťah ekvivalencie, ľahko vyplýva, že vzťah ≈ je vzťah ekvivalencie. V školskom kurze sa študujú transformácie rovníc, ktoré transformujú rovnicu α na ekvivalentnú rovnicu β.
Príklad 3.8. Rovnica α nie je silnejšia ako rovnica β: α => β, ak je Rα obsiahnuté v Rβ. V tomto prípade hovoríme, že rovnica β nie je slabšia ako α.
Vzťah => je reflexívny a tranzitívny, t.j. je kvázi poriadok. Z α => β a β => α vyplýva ekvivalencia: α ≈ β. Naopak, z ekvivalencie α ≈ β vyplýva, že α => β a β => α. Teda ≈ = =>=> -1 .
Príklad 3.9. Na množine rovníc, ktoré majú aspoň jeden koreň, je ľahké určiť prirodzený tolerančný vzťah - prítomnosť spoločných koreňov: Rα ∩ Rβ ≠ Ø.
Príklad 3.10. Môžeme tiež zaviesť vzťah efektívnej ekvivalencie. Rovnice α a β sa budú nazývať efektívne ekvivalentné, ak každá z nich môže byť transformovaná na druhú pomocou konečného počtu ekvivalentných transformácií (povolené techniky z pevného zoznamu).
Vzhľadom na prechodnosť vzťahu žiadny počet aplikácií takýchto techník neporušuje ekvivalenciu. Preto sú efektívne ekvivalentné rovnice ekvivalentné, čo možno nazvať zahrnutím jedného vzťahu do druhého.
Uvažované príklady vzťahov názorne ilustrujú pojem vzťahov, vrátane vzťahov ekvivalencie, ich vlastnosti sú ľahko overiteľné nástrojom školskej matematiky a sú celkom jasné. Preto je možné starším školákom študujúcim v matematických krúžkoch predstaviť pojem vzťahy.
Záver
Binárne vzťahy sú veľmi pohodlným a jednoduchým aparátom na riešenie veľmi rôznorodých problémov. Jazyk binárnych (a všeobecnejšie) vzťahov je veľmi pohodlný a prirodzený pre matematickú lingvistiku, matematickú biológiu a množstvo ďalších aplikovaných (pre matematiku) oblastí. To sa dá veľmi ľahko vysvetliť tým, že geometrický aspekt teórie binárnych vzťahov je jednoducho teória grafov. Ale akokoľvek je geometrická teória grafov známa a dobre pokrytá v literatúre, algebraické aspekty teórie vzťahov sú tak slabo prezentované.
Medzitým sa dá algebra vzťahov vysvetliť celkom verejne. Aby sa to naučili aj starší školáci študujúci v matematických krúžkoch.
V tejto práci sa skúmali pojmy vzťah a ekvivalencia, rozoberali sa niektoré ich vlastnosti, uvádzali sa geometrické interpretácie a názorné príklady.
Zoznam použitých zdrojov
1. Bogomolov A.M., Saliy V.N. Algebraické základy teórie diskrétnych systémov. - M.: Veda. Fizmatlit, 1997. -368 s.
2. Shrader Yu.A. Rovnosť. Podobnosť. Objednať. - M.: Nauka, 1971.-256 s.
Kostrikin A.I. Úvod do algebry. - M.: Nauka, 1977.-334 s.
B.L. van der Waerden. Moderná algebra. v 2 zväzkoch T.1.- M., OGIZ GOSTEKHIZDAT, 1947 -339 s.
V mnohých výpočtových problémoch sa veľké množiny berú a delia takým spôsobom, aby bolo možné študovať všetky situácie, ktoré nás zaujímajú, pomocou niekoľkých dobre zvolených príkladov.
Definícia 1: Nech A ¹ Æ a (A i ),i= súbor podmnožín takých, že A= . Potom sa nazýva kolekcia týchto podmnožín potiahnuté súpravy A.
Napríklad (A, B) je prekrytie AÈB; (A, AÈB, B, C)-krycie AÈBÈC.
komentár: Vo všeobecnosti môže byť pokrytie nekonečné. Z hľadiska štúdia konkrétnych vlastností však táto situácia nespôsobuje nadšenie.
Definícia 2: Rozdelením neprázdnej množiny A sa nazýva jej pokrytie tak, že ak i¹ j, potom A i ÇA j =Æ.
Napríklad (A, A') je oddiel U.
(AÇB, AÇB’, A’ÇB, A’ÇB’) – priečka U,
(A\B, AÇB, B\A) – oddiel AÈB.
Rozdelenie neprázdnej množiny môžete usporiadať pomocou vzťahov, ktoré sa správajú ako vzťahy rovnosti na množine čísel alebo množín.
Definícia 3: Binárna relácia na množine sa nazýva vzťah ekvivalencie, ak je reflexívny, symetrický a tranzitívny.
Príklady:
1. Na množine všetkých trojuholníkov: ((x, y)| x a y majú rovnakú plochu)
2. Na množine všetkých programov: ((a, b)| a, b vypočítajte rovnakú funkciu na konkrétnom stroji)
Definícia 4: Nech R je vzťah ekvivalencie na množine A a xОA. Trieda ekvivalencie generovaná x množina (y| xR y)=[x] R sa nazýva.
Definícia 5: Volá sa akýkoľvek prvok triedy ekvivalencie reprezentatívny túto triedu. Kompletný systém zástupcov volá sa skupina zástupcov, jeden z každej triedy.
Príklad 3:
N sú prirodzené čísla, s je pevný prvok. Zapnuté Z vzťah je definovaný: r s = ((x, y) | x-y=ns, nО Z). Postoj porovnania modulo s (zápis: xºy(mod s)).
Je ľahké skontrolovať, či porovnávacia relácia modulo s je reláciou ekvivalencie na množine Z.
Nech je napríklad s=10. potom:
= {11,21,-9,10 976 631,.... }
= {66,226,-24,... }
V skutočnosti existuje len 10 tried ekvivalencie pre tento vzťah a čísla 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 tvoria úplný systém zástupcov. Triedy ekvivalencie založené na tomto vzťahu ekvivalencie sa nazývajú triedy zrážok modulo s.
Definícia 6: Faktor-set množiny A vzhľadom na vzťah ekvivalencie R sa nazýva množina všetkých tried ekvivalencie vzhľadom na tento vzťah a označuje sa A/R.
Množina tried zvyškov modulo s je označená Z s.
Vyskytuje
Veta (o delení): Nech R je relácia ekvivalencie na neprázdnej množine A. Potom je podielová množina A/R delením množiny A.
dôkaz:
"xОA(xО[x] R). Musíme dokázať, že každý prvok množiny A patrí práve do jednej triedy. To znamená, že dokážeme, že ak majú triedy aspoň jeden spoločný prvok, potom sa zhodujú. Nech cО[ a] a cО [b] Nech xО [a], ale potom x R a, a R c, c R b Þ x R b ) Takže [a] М [b] ] М [a].
Q.E.D.
Platí to aj naopak. Nech S je delenie množiny A a R s je binárna relácia na A tak, že: R=((x,y)ïx a y patria rovnakému prvku množiny), potom R, budeme volať – vzťah určený predelom S.
Veta (spätne): Vzťah R na A, definovaný rozdelením S, je vzťah ekvivalencie na A a A/R s = S. (nezávisle)
Cvičenia:
1. Nech A je konečná množina. Ktoré vzťahy ekvivalencie dávajú najväčší a najmenší počet tried ekvivalencie.
2. Ak (A 1 , A 2 , ..., A n ) je delenie A a A konečné, potom .
Objednávkový vzťah.
Z pojmu rovnosti (napríklad čísel) vzniká matematický pojem ekvivalencie. A z pojmu nerovnosti vzniká ďalší typ vzťahu, ktorý sa nazýva vzťahy poriadku.
Definícia 1: Čiastočná objednávka na množine A je binárna relácia, ktorá je reflexná, antisymetrická a tranzitívna.
Čiastočný poriadok je zovšeobecnením vzťahu £ k R. Môžeme zaviesť pojem prísny poriadok , zodpovedajúce vzťahu< на R. Отношение строгого порядка - только транзитивно(оно еще и антирефлексивно).
Ak je dané £, potom môžeme definovať<: a
Množinu, na ktorej je daný poradový vzťah, označíme
(X, £) (alebo (X,<), если порядок строгий).
Definícia 2: Volá sa množina, na ktorej je daný vzťah poriadku čiastočne objednané.
Príklad: A je súbor. ( P (A),Í), je ľahké skontrolovať, či vzťah Í je objednávkový vzťah na P (A).
Definícia 3: Nazýva sa vzťah rádu R na A kompletné ( lineárne ) v poradí, ak " x, yÎA (xR y Ú yR x). Množina (A, R) sa nazýva lineárne usporiadaná.
Príklady:
1. pomer £ ku R je úplný objednávkový vzťah. teda ( R,£) - lineárne usporiadané.
2. a tu ( P (A),Í) nie je lineárne usporiadaný
3. x£y Û y x na súprave N nie je v úplnom poriadku
Definícia 4: nechajte (A, £) je čiastočne objednaná sada. Element AOA sa nazýva najmenší/najväčší/ v A, ak " xОA (a£ x) /x £ a /. Prvok bОА sa nazýva minimum /maximum/ ak " xÎA (x£ a Þ x=a) /a £ x Þ a=x /.
Úloha: Dokážte, že pre lineárne usporiadanú množinu sa pojmy najväčšieho (najmenšieho) a maximálneho (minimálneho) prvku zhodujú. Uveďte príklad čiastočne usporiadanej množiny, kde sa nezhodujú.
Zloženie vzťahov
Nech sú dané množiny A, B a C a vzťahy S medzi A a B (čiže SÌA´B) a R medzi B a C (RÌB´C). Definujme nový vzťah medzi A a C takto:
Definícia 1: Množina všetkých párov (x, y) takých, že existuje zÎB také, že (x, z) О S a (z, y) О R sa nazýva zloženie vzťahov S a R. Určené: R o S . Teda R o S Ì A ´ C .
R oS = ((x, y) | $zÎB((x,z)ÎSÙ(z,y)ÎR)) alebo x R o Sy Û $zÎB(xSzÙzRy).
Príklad 1 : Nech A=(1, 2, 3), B=(1, 2, 3, 4, 5, 6), C=(3, 6, 9, 12), s =((1,2), (2 ,4), (3,6)), r=((1,3), (2,6), (3,9), (4,12)). Potom r o s = ((1,6), (2,12)).
Znázornime situáciu na obrázku:
Príklad 2 : Nech s a r sú vzťahy na N také že
S = ((x,x+1)ïxО N) a r = ((x2,x)ïxО N). Potom D r = (x 2 xО N)=(1,4,9,16,25,...) a Ds= N.
D r o s = (xïxО NÙ x+1=y2)=(3,8,15,24,...).
V prípade, že je vzťah definovaný na množine, môže byť kombinovaný sám so sebou:
sos = s2 = ((x,x+2)½xО N) a ror = r2 = ((x4,x)½x0 N}.
Pomocou tohto zápisu môžeme definovať n-tú mocninu vzťahu:
, kde nО N, n > 1.
Napríklad pre vzťahy z príkladu 2 máme:
, 
Chcel by som doplniť analógiu o násobenie. Aby sme to dosiahli, zavedieme nasledujúcu prirodzenú definíciu:
Definícia 2: Binárne vzťahy sú tzv rovný, ak sú rovnaké ako podmnožiny, teda R=S if"x,y((x,y)ÎRÛ(x,y)ÎS).
Je jasné, že vzťahy musia byť definované na rovnakých množinách.
Veta (vlastnosti zloženia vzťahov): Pre všetky binárne vzťahy R, S, T platia nasledujúce rovnosti:
1. (RoS)oT = Ro(SoT)
2. (RoS)-1 = S-1 alebo R-1
dôkaz:
1) Pre ľubovoľné x a y máme:
x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt))ÙtRy) $t((xSoTt)ÙtRy) º xRo(SoT)y.
2) x(RoS) -1 yº yRoSx º $z(ySzÙzRx) º $z(xR -1 zÙzS -1 y) º xS -1 aleboR -1 y.
Q.E.D.
komentár: ak R je vzťah na množine A, potom je jasné, že I A aleboR=RoI A =R. To znamená, že I A sa pri násobení čísel správa ako jedna. Nemožno však urobiť úplnú analógiu. Pretože napríklad komutivita nemá miesto vo všeobecnom prípade, pretože RoS možno definovať, ale SoR nie. Rovnako ako rovnosť R -1 aleboR=RoR -1 = I A nemá vždy zmysel.
Uzavretie vzťahu
Pojem uzáver je základný matematický pojem a používa sa vo väčšine odvetví matematiky. Ukážme si tento koncept na všeobecnom príklade: zoberme si objekt x 0 a proces P, ktorý, keď sa aplikuje postupne, generuje určitú množinu, a teda definuje postupnosť x 1 , x 2 , ..., x n , . .. takže x 1 ÎP(x 0), x 2 ÎP(x 1),..., x n ÎP(x n -1),... 
Definícia 1: volá sa množina obsahujúca všetky prvky všetkých postupností, ktoré je možné získať pomocou procesu P a počnúc x 0 uzavretie procesu P relatívne k x 0 .
Je jasné, že výsledkom bude nájdenie P n (x 0) pre niektoré n. Toto n Nevieme vopred, závisí to od samotného procesu. Navyše, ak vezmeme živel r od tejto uzávierky a budeme na ňu aplikovať proces R, potom nezistime nic nove. To znamená, že súpravu nemožno týmto spôsobom rozširovať - je uzavretá!
Príklad : Vezmite štvorec S, označený ABCD, a zvážte proces r, ktorý pozostáva z otočenia štvorca v smere hodinových ručičiek o 90°:
| |
| |
| |
| |
| |
Nech je vzťah A definovaný na nejakej množine. potom:
Definícia 2: Tranzitívny uzáver vzťah A na danej množine sa nazýva vzťah A +:
Z netranzitívneho vzťahu A na určitej množine teda možno zostrojiť tranzitívny A + .
Príklady:
1. r - pomer na N: r=((x, y)| y=x+1), potom r + =((x, y)| x 2.s na Q: s=((x, y)| x 3.t na Q: t=((x, y)| x×y=1), potom r + =((x, x)| x¹0) 4. Nech L je množina staníc londýnskeho metra; L = (a, b, c) po sebe idúce stanice. N=((x, y)| y nasleduje x). okrem toho (a, a), (b, b), (c, c), (a, c) ОN2. To znamená N + = L´L Všeobecne povedané, tranzitívny uzáver nie je reflexívny (príklad 2). Nech A je relácia na X. Nech A 0 =I X . Definícia 3: Reflexné zapínanie A* vzťahy A sa nazývajú vzťah Príklady:
1. r*=((x, y)| x£y) I. Rozdelenie do tried. Vzťah ekvivalencie Definícia 2.1. Zameniteľné nazvime tie a len tie objekty danej množiny M, ktoré majú rovnakú množinu formálnych znakov, ktoré sú v danej situácii podstatné. Označme M x množinu všetkých objektov zameniteľných s objektom x. Je zrejmé, že x M x a spojenie všetkých M x (pre všetky možné x z M) sa zhodujú s úplnou množinou M: Predstierajme to. To znamená, že existuje nejaký prvok z, ktorý súčasne patrí do a a. Takže x je zameniteľné so z a z je zameniteľné s y. Preto je x zameniteľné s y, a teda s akýmkoľvek prvkom z. Teda. Spätné prepínanie je znázornené rovnakým spôsobom. Množiny vyskytujúce sa v zjednotení (2.1) sa teda buď nepretínajú, alebo sa úplne zhodujú. Definícia 2.2. Systém neprázdnych podmnožín (M 1, M 2,….) množiny M nazveme delením tejto množiny, ak Samotné množiny sa nazývajú triedy oddielov. Definícia 2.3. Relácia c na množine M sa nazýva ekvivalencia (alebo relácia ekvivalencie), ak existuje rozdelenie (M 1, M 2,...) množiny M také, že (x, y) platí práve vtedy, ak x a y patrí do nejakej všeobecnej triedy M i danej partície. Nech (M 1 , M 2 ,….) je delením množiny M. Na základe tohto delenia určíme vzťah od c do M: (x, y), ak x a y patria do nejakej všeobecnej triedy M i tohto oddielu. Je zrejmé, že vzťah s je ekvivalentný. Zavolajme vzťah ekvivalencie zodpovedajúci danému oddielu. Definícia 2.4. Ak v každej podmnožine M i vyberieme prvok x i v nej obsiahnutý, potom sa tento prvok bude nazývať štandardom pre každý prvok y zahrnutý v tej istej množine M i . Podľa definície predpokladajme, že vzťah c* „byť štandardom“ (x i, y) je splnený Je ľahké vidieť, že ekvivalenciu c zodpovedajúcu danému oddielu možno definovať takto: (z, y), ak z a y majú spoločnú normu (x i, z) a (x i, y). Príklad 2.1: Uvažujme ako M množinu nezáporných celých čísel a rozdeľme jej na množinu M 0 párnych čísel a množinu M 1 nepárnych čísel. Zodpovedajúci vzťah ekvivalencie na množine celých čísel je označený takto: a znie: n je porovnateľné s m modulo 2. Je prirodzené, že ako štandardy volíme 0 pre párne čísla a 1 pre nepárne čísla. Podobne, rozdelením tej istej množiny M na k podmnožín M 0, M 1,... M k-1, kde M j pozostáva zo všetkých čísel, ktoré po delení k dávajú zvyšok j, dospejeme k vzťahu ekvivalencie: čo platí, ak n a m majú rovnaký zvyšok pri delení k. Je prirodzené zvoliť zodpovedajúci zvyšok j ako štandard v každom M j. II. Súprava faktorov Nech je vzťah ekvivalencie. Potom podľa vety existuje rozdelenie (M 1, M 2,....) množiny M na triedy navzájom ekvivalentných prvkov - takzvané triedy ekvivalencie. Definícia 2.5. Množinu tried ekvivalencie vzhľadom na vzťah označujeme M/ a čítame ako podielovú množinu množiny M vzhľadom na vzťah. Nech μ: M > S je surjektívne zobrazenie množiny M na nejakú množinu S. Pre ľubovoľné μ: M > S - surjektívne zobrazenie existuje vzťah ekvivalencie na množine M taký, že M/ a S možno dať do korešpondencie jedna ku jednej. III. Ekvivalenčné vlastnosti Definícia 2.6. Relácia c na množine M sa nazýva relácia ekvivalencie, ak je reflexívna, symetrická a tranzitívna. Veta 2.1: Ak je relácia c na množine M reflexná, symetrická a tranzitívna, existuje delenie (M 1 , M 2 ,….) množiny M také, že (x, y) platí práve vtedy, ak x a y patrí do nejakej všeobecnej triedy M i danej partície. A naopak: Ak je dané rozdelenie (M 1, M 2,....) a binárny vzťah c je daný ako „patrí do všeobecnej triedy rozdelenia“, potom je c reflexívne, symetrické a tranzitívne. dôkaz: Uvažujme reflexívny, symetrický a tranzitívny vzťah c k M. Nech pre ľubovoľný pozostáva zo všetkých z, pre ktoré (x, z) c Lema 2.1: Pre ľubovoľné x a y buď alebo Z lemy a reflexivity vzťahu c vyplýva, že množiny tvaru tvoria predel množiny M. (Túto priečku možno prirodzene nazvať predelením korešpondujúcim s pôvodným vzťahom). Nech teraz (x, y) c. To znamená, že y. Ale aj x na základe (x, x) c. Preto sú zahrnuté oba prvky. Takže ak (x, y) c, potom x a y sú zahrnuté do všeobecnej triedy oddielov. Naopak, nech u a v. Ukážme, že (u, v) c V skutočnosti máme (x, u) c a (x, v) c. Preto symetriou (u, x) c. Podľa tranzitivity z (u, x) c a (x, v) c nasleduje (u, v) c. Prvá časť vety bola dokázaná. Nech je daný dielik (M 1, M 2,….) množiny M. spojenie všetkých tried oddielu sa zhoduje s M, potom je ľubovoľné x zahrnuté do niektorej triedy. Z toho vyplýva, že (x, x) c, t.j. s - reflexne. Ak x a y sú v nejakej triede, potom y a x sú v tej istej triede. To znamená, že (x, y) c implikuje (y, x) c, t.j. vzťah je symetrický. Nech teraz platí (x, y) c a (y, z) c. To znamená, že x a y sú v nejakej triede a y a z sú v nejakej triede. Triedy majú spoločný prvok y, a preto sa zhodujú. To znamená, že x a z sú zahrnuté v triede, t.j. (x, z) platí a vzťah je tranzitívny. Veta je dokázaná. IV. Operácie s ekvivalenciami. Tu definujeme niektoré množinové operácie na ekvivalenciách a uvádzame ich dôležité vlastnosti bez dôkazu. Pripomeňme si, že relácia je pár (), kde M je množina prvkov vstupujúcich do vzťahu a je množina párov, pre ktoré je relácia splnená. Definícia 2.7. Priesečník vzťahov (c 1, M) a (c 2, M) je vzťah definovaný priesečníkom príslušných podmnožín. (x, y) z 1 z 2 vtedy a len vtedy, ak (x, y) z 1 a (x, y) z 2 súčasne. Veta 2.2: Priesečník ekvivalencií s 1 s 2 s 1 s 2 je sám o sebe vzťahom ekvivalencie. Definícia 2.8. Zjednotenie relácií (s 1, M) a (s 2, M) je relácia definovaná zjednotením zodpovedajúcich podmnožín. (x, y) s 1 s 2 vtedy a len vtedy, ak (x, y) s 1 alebo (x, y) s 2. Veta 2.3: Aby zjednotenie ekvivalencií s 1 s 2 bolo samo osebe vzťahom ekvivalencie, je potrebné a postačujúce, aby od 1 z 2 = od 1 z 2 Definícia 2.9. Priamy súčet vzťahov (c 1, M 1) a (c 2, M 2) sa nazýva pomer). Priamy súčet sa označí (c 1, M 1) (c 2, M 2). Ak teda (c 1, M 1) (c 2, M 2) = (), potom M =. Veta 2.4: Ak a vzťahy sú ekvivalencie, potom priamy súčet vzťahov (c 1, M 1) (c 2, M 2) = (), je tiež ekvivalenciou. V. Typy vzťahov Predstavme si niekoľko dôležitejších typov vzťahov. Príklady budú uvedené v tretej kapitole. Definícia 2.10. Vzťah c na množine M sa nazýva tolerancia, ak je reflexná a symetrická. Definícia 2.11. Relácia c na množine M sa nazýva relácia prísneho poriadku, ak je antireflexívna a tranzitívna. Definícia 2.12. Relácia striktného poriadku c sa nazýva dokonalé striktné usporiadanie, ak pre ľubovoľnú dvojicu prvkov x a y z M platí buď (x, y) alebo (y, x). Definícia 2.13. Relácia c na množine M sa nazýva relácia nestriktného poriadku, ak môže byť reprezentovaná v tvare: kde na M je striktné poradie a E je diagonálny vzťah. Prednáška 22. Ekvivalencia a poradové vzťahy na množine 1. Vzťah ekvivalencie. Súvislosť medzi vzťahom ekvivalencie a rozdelením množiny do tried. 2. Poriadkový vzťah. Prísne a neprísne vzťahy usporiadania, lineárne vzťahy usporiadania. Objednávanie súprav. 3. Hlavné závery Pozrime sa na množinu zlomkov X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) vzťah rovnosti. Tento vzťah: Reflexívne, keďže každý zlomok je rovný sám sebe; Symetricky, keďže z toho, že zlomok m/n rovný zlomku p/q, z toho vyplýva, že zlomok p/q rovný zlomku m/n; Prechodník, keďže z toho, že zlomok m/n rovný zlomku p/q a zlomok p/q rovný zlomku r/s, z toho vyplýva, že zlomok m/n rovný zlomku r/s. Hovorí sa, že vzťah rovnosti zlomkov je vzťah ekvivalencie. Definícia. Relácia R na množine X sa nazýva relácia ekvivalencie, ak má súčasne vlastnosti reflexivity, symetrie a tranzitivity.
Príkladmi vzťahov ekvivalencie sú vzťahy rovnosti geometrických útvarov, vzťah rovnobežnosti čiar (za predpokladu, že zhodné čiary sa považujú za rovnobežné). Prečo sa v matematike vyčleňuje tento typ vzťahu? Uvažujme vzťah rovnosti zlomkov definovaných na množine X= (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) (obr. 106). Vidíme, že množina je rozdelená na tri podmnožiny: (1/2, 2/4, 3/6), (1/3, 2/6), (1/4). Tieto podmnožiny sa nepretínajú a ich spojenie sa zhoduje s množinou X, tie. máme predel zostavy X do tried. To nie je náhoda. Vôbec, ak je na množine X daný vzťah ekvivalencie, potom to generuje rozdelenie tejto množiny na párovo disjunktné podmnožiny (triedy ekvivalencie). Zistili sme teda, že vzťah rovnosti na množine zlomkov (1/2, 1/3, 1/4, 2/4, 2/6, 3/6) zodpovedá rozdeleniu tejto množiny do tried ekvivalencie. , z ktorých každý pozostáva z rovnakých zlomkov medzi sebou. Opak je tiež pravdou: ak akýkoľvek vzťah definovaný na množine X generuje rozdelenie tejto množiny do tried, potom ide o reláciu ekvivalencie. Zvážte napríklad na scéne X =(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) vzťah „mať rovnaký zvyšok pri delení 3“. Vygeneruje rozdelenie množiny X do tried: jedna zahrnie všetky čísla, ktoré po delení 3 ostanú zvyšok 0 (sú to čísla 3, 6, 9), druhá - čísla, ktoré po delení 3 ostanú zvyšok 1 (sú to čísla 1, 4 , 7 , 10) a v treťom - všetky čísla, pri delení 3 je zvyšok 2 (sú to čísla 2, 5, 8). Výsledné podmnožiny sa totiž nepretínajú a ich spojenie sa zhoduje s množinou X. V dôsledku toho je na množine definovaný vzťah „majú rovnaký zvyšok pri delení 3“. X, je vzťah ekvivalencie. Všimnite si, že tvrdenie o vzťahu medzi vzťahom ekvivalencie a rozdelením množiny do tried potrebuje dôkaz. Dávame to dole. Povedzme, že ak má vzťah ekvivalencie názov, potom sa triedam priradí zodpovedajúci názov. Napríklad, ak je na množine segmentov špecifikovaný vzťah rovnosti (a je to vzťah ekvivalencie), potom sa množina segmentov rozdelí na triedy rovnakých segmentov (pozri obr. 99). Vzťah podobnosti zodpovedá rozdeleniu množiny trojuholníkov do tried podobných trojuholníkov. Takže ak máme vzťah ekvivalencie na určitej množine, môžeme túto množinu rozdeliť do tried. Môžete to však urobiť aj opačne: najprv rozdeľte množinu na triedy a potom definujte vzťah ekvivalencie, berúc do úvahy, že dva prvky sú ekvivalentné vtedy a len vtedy, ak patria do rovnakej triedy príslušného oddielu. Princíp rozdelenia množiny do tried pomocou nejakého vzťahu ekvivalencie je dôležitým princípom matematiky. prečo? Po prvé, ekvivalent - to znamená ekvivalentný, zameniteľný. Preto sú prvky rovnakej triedy ekvivalencie vzájomne zameniteľné. Zlomky, ktoré sú v rovnakej triede ekvivalencie (1/2, 2/4, 3/6), sú teda z hľadiska vzťahu rovnosti na nerozoznanie a zlomok 3/6 možno nahradiť iným, napríklad 1. /2. A toto nahradenie nezmení výsledok výpočtov. Po druhé, keďže v triede ekvivalencie sú prvky, ktoré sú z hľadiska nejakého vzťahu nerozoznateľné, domnievame sa, že triedu ekvivalencie určuje ktorýkoľvek jej zástupca, t. ľubovoľný prvok tejto triedy. Akákoľvek trieda rovnakých zlomkov môže byť špecifikovaná zadaním ľubovoľného zlomku patriaceho do tejto triedy. Určenie triedy ekvivalencie jedným zástupcom umožňuje namiesto všetkých prvkov množiny študovať množinu jednotlivých zástupcov z tried ekvivalencie. Napríklad vzťah ekvivalencie „mať rovnaký počet vrcholov“ definovaný na množine mnohouholníkov generuje rozdelenie tejto množiny na triedy trojuholníkov, štvoruholníkov, päťuholníkov atď. Vlastnosti vlastné určitej triede sa zvažujú na jednom z jej predstaviteľov. Po tretie, rozdelenie množiny do tried pomocou vzťahu ekvivalencie sa používa na zavedenie nových konceptov. Napríklad pojem „zväzok čiar“ možno definovať ako pojem, ktorý je spoločný pre paralelné čiary. Vo všeobecnosti každý koncept, s ktorým osoba pracuje, predstavuje určitú triedu ekvivalencie. „Stôl“, „dom“, „kniha“ - všetky tieto pojmy sú zovšeobecnené predstavy o mnohých konkrétnych objektoch, ktoré majú rovnaký účel. Ďalším dôležitým typom vzťahu je poriadkové vzťahy. Definícia. Relácia R na množine X sa nazýva relácia poriadku, ak má súčasne vlastnosti antisymetrie a tranzitivity
.
Príklady vzťahov poradia zahŕňajú: vzťah „menej ako“ na množine prirodzených čísel; vzťah je „kratší“ na množine segmentov, pretože sú antisymetrické a tranzitívne. Ak má relácia objednávky aj vlastnosť spojitosti, potom sa hovorí, že ide o reláciu lineárne poradie. Napríklad vzťah „menej ako“ na množine prirodzených čísel je vzťahom lineárneho poriadku, pretože má vlastnosti antisymetrie, tranzitivity a spojitosti. Definícia. Množina X sa nazýva usporiadaná, ak má vzťah usporiadania.
Množinu N prirodzených čísel možno teda usporiadať špecifikovaním vzťahu „menej ako“. Ak je na množine definovaný vzťah objednávky X, má vlastnosť spojitosti, potom to hovoríme lineárne objednáva kopa X. Napríklad množinu prirodzených čísel možno usporiadať pomocou vzťahu „menej ako“ aj vzťahu „viacero“ – obe sú vzťahmi usporiadania. Ale vzťah „menej ako“ má na rozdiel od vzťahu „viacero“ aj vlastnosť spojitosti. To znamená, že vzťah „menej ako“ usporiada množinu prirodzených čísel lineárne. Nemali by sme si myslieť, že všetky vzťahy sa delia na vzťahy ekvivalencie a vzťahy poriadku. Existuje veľké množstvo vzťahov, ktoré nie sú ani vzťahmi ekvivalencie, ani vzťahmi poriadku. Uvažujme vzťah rovnosti na množine zlomkov X = ( ). Tento vzťah: Reflexívne, keďže každý zlomok je rovný sám sebe; Symetricky, keďže zo skutočnosti, že zlomok sa rovná zlomku, vyplýva, že zlomok sa rovná zlomku; Prechodník, keďže zo skutočnosti, že zlomok sa rovná zlomku a zlomok sa rovná zlomku, vyplýva, že zlomok sa rovná zlomku. O vzťahu rovnosti zlomkov hovoríme, že ide o vzťah ekvivalencie. Definícia. Relácia R na množine X sa nazýva relácia ekvivalencie, ak má súčasne vlastnosti reflexivity, symetrie a tranzitivity.
. Príkladmi vzťahov ekvivalencie sú vzťahy rovnosti geometrických útvarov, vzťah rovnobežnosti čiar (za predpokladu, že zhodné čiary sa považujú za rovnobežné). Prečo sa v matematike vyčleňuje tento typ vzťahu? Uvažujme vzťahy rovnosti zlomkov definované na množine X = ( ). (Obr.7). Vidíme, že množina je rozdelená na tri podmnožiny: Vôbec ak je na množine X daný vzťah ekvivalencie, potom to generuje rozdelenie tejto množiny na párovo disjunktné podmnožiny (triedy ekvivalencie).
Tak sme zistili, že vzťah rovnosti na množine zlomkov X = ( ) zodpovedá rozdeleniu tejto množiny do tried ekvivalencie, z ktorých každá pozostáva zo vzájomne rovnakých zlomkov. Opak je tiež pravdou: ak akýkoľvek vzťah definovaný na množine X generuje rozdelenie tejto množiny do tried, potom ide o reláciu ekvivalencie.
Uvažujme napríklad o množine X = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) vzťah „mať rovnaký zvyšok, keď je delený 3“. Vygeneruje rozdelenie množiny X do tried: jedna bude zahŕňať všetky čísla, ktorých zvyšok pri delení 3 je 0 (sú to čísla 3, 6, 9), druhá obsahuje čísla, ktoré po delení 3 zostanú zvyšok 1 ( toto sú čísla 1, 4, 7, 10) a v treťom - všetky čísla, pri delení 3 je zvyšok 2 (sú to čísla 2, 5, 8). Výsledné podmnožiny sa totiž nepretínajú a ich spojenie sa zhoduje s množinou X. V dôsledku toho je vzťah „mať rovnaký zvyšok pri delení 3“ definovaný na množine X vzťahom ekvivalencie. Všimnite si, že tvrdenie o vzťahu medzi vzťahom ekvivalencie a rozdelením množiny do tried potrebuje dôkaz. Dávame to dole. Povedzme, že ak má vzťah ekvivalencie názov, potom sa triedam priradí zodpovedajúci názov. Napríklad, ak je vzťah rovnosti špecifikovaný na množine segmentov (a je to vzťah ekvivalencie), potom je množina segmentov rozdelená do tried rovnakých segmentov (pozri obr. 4). Vzťah podobnosti zodpovedá rozdeleniu množiny trojuholníkov do tried podobných trojuholníkov. Takže ak máme vzťah ekvivalencie na určitej množine, môžeme túto množinu rozdeliť do tried. Môžete to však urobiť aj opačne: najprv rozdeľte množinu na triedy a potom definujte vzťah ekvivalencie, berúc do úvahy, že dva prvky sú ekvivalentné vtedy a len vtedy, ak patria do rovnakej triedy príslušného oddielu. Princíp rozdelenia množiny do tried pomocou nejakého vzťahu ekvivalencie je dôležitým princípom matematiky. prečo? Po prvé, ekvivalent - to znamená ekvivalentný, zameniteľný. Preto sú prvky rovnakej triedy ekvivalencie vzájomne zameniteľné. Zlomky, ktoré sa nachádzajú v rovnakej triede ekvivalencie, sú teda na nerozoznanie z hľadiska vzťahu rovnosti a zlomok možno nahradiť iným napr. Po druhé, keďže v triede ekvivalencie sú prvky, ktoré sú z hľadiska nejakého vzťahu nerozoznateľné, domnievame sa, že triedu ekvivalencie určuje ktorýkoľvek jej zástupca, t. ľubovoľný prvok tejto triedy. Akákoľvek trieda rovnakých zlomkov môže byť špecifikovaná zadaním ľubovoľného zlomku patriaceho do tejto triedy. Určenie triedy ekvivalencie jedným zástupcom umožňuje namiesto všetkých prvkov množiny študovať kolekciu jednotlivých zástupcov z tried ekvivalencie. Napríklad vzťah ekvivalencie „mať rovnaký počet vrcholov“ definovaný na množine mnohouholníkov generuje rozdelenie tejto množiny na triedy trojuholníkov, štvoruholníkov, päťuholníkov atď. Vlastnosti vlastné určitej triede sa zvažujú na jednom z jej predstaviteľov. Po tretie, rozdelenie množiny do tried pomocou vzťahu ekvivalencie sa používa na zavedenie nových konceptov. Napríklad pojem „zväzok čiar“ možno definovať ako pojem, ktorý je spoločný pre paralelné čiary. Vo všeobecnosti každý koncept, s ktorým osoba pracuje, predstavuje určitú triedu ekvivalencie. „Stôl“, „dom“, „kniha“ - všetky tieto pojmy sú zovšeobecnené predstavy o mnohých konkrétnych objektoch, ktoré majú rovnaký účel. Ďalším dôležitým typom vzťahu je objednávkový vzťah. Definuje sa nasledovne. Definícia. Relácia R na množine X sa nazýva relácia poriadku, ak má súčasne vlastnosti antisymetrie a tranzitivity.
Príklady vzťahov poradia zahŕňajú: vzťahy „menej ako“ na množine prirodzených čísel; vzťah „kratšie“ na množine segmentov, pretože sú antisymetrické a tranzitívne. Ak má vzťah poriadku aj vlastnosť spojitosti, potom sa hovorí, že ide o vzťah lineárneho poriadku. Napríklad vzťah „menej ako“ na množine prirodzených čísel je vzťahom lineárneho poriadku, pretože má vlastnosti antisymetrie, tranzitivity a spojitosti. Definícia. Množina X sa nazýva usporiadaná, ak má vzťah usporiadania.
Množinu N prirodzených čísel možno teda usporiadať špecifikovaním vzťahu „menej ako“. Ak má relácia poriadku definovanú na množine X vlastnosť spojitosti, hovorí sa, že lineárne usporiada množinu X. Napríklad množinu prirodzených čísel možno usporiadať pomocou vzťahu „menej ako“ aj vzťahu „viacero“ – obe sú vzťahmi usporiadania. Ale vzťah „menej ako“ má na rozdiel od vzťahu „viacero“ aj vlastnosť spojitosti. To znamená, že vzťah „menej ako“ usporiada množinu prirodzených čísel lineárne. Nemali by sme si myslieť, že všetky vzťahy sa delia na vzťahy ekvivalencie a vzťahy poriadku. Existuje veľké množstvo vzťahov, ktoré nie sú ani vzťahmi ekvivalencie, ani vzťahmi poriadku.
. Teda 
.
Tieto podmnožiny sa nepretínajú a ich spojenie sa zhoduje s množinou X, to znamená, že máme rozdelenie množiny X do tried. To nie je náhoda.