Përdoruesi:Rrezii/sandbox

Ky artikull ka të bëjë me nocionet themelore të relacioneve në matematikë.

Mënyra më e drejtpërdrejtë për të shprehur një marrëdhënie midis elementeve të dy bashkësive është përdorimi i çifteve të renditura i përbërë nga dy elementë të lidhur. Për këtë arsye, bashkësitë e çifteve të renditura quhen relacione binare. Me fjalë të tjera, një lidhje binare nga A në B është bashkësia R e çifteve të renditura, ku elementi i parë i çdo çifti të renditur vjen nga A dhe elementi i dytë vjen nga B. Bashkësia A quhet domena e relacionit, kurse ajo B quhet kodomena e relacionit. Nëse R ⊆ A × B, ne përdorim shënimin aRb për të treguar se (a, b ) ∈ R dhe a ̸R b për të treguar se (a, b) ∉ R. Për më tepër, kur (a, b) i përket relacionit R, thuhet se a është në relacion me b.

Termat korrespondencë, relacione diadike dhe relacione me dy vende janë sinonime për relacionet binare, megjithëse disa autorë përdorin termin "relacion binarë" për çdo nëngrup të një produkti kartezian X × Y pa iu referuar X dhe Y, dhe rezervojnë termin "korrespondencë" për një relacion binarë në lidhje me X dhe Y.

Marrëdhëniet binare përdoren në shumë degë të matematikës për të modeluar një shumëllojshmëri të gjerë konceptesh. Këto përfshijnë, ndër të tjera:

• relacionet "është më e madhe se", "është e barabartë me" dhe "ndan" në aritmetikë;
• relacioni "është kongruent me" në gjeometri;
• relacioni "është ngjitur me" në teorinë e grafeve;
• relacioni "është normal me" në algjebër lineare.

Funksionet si relacione

Figura 1. Funksioni si relacion

Një funksion f nga një bashkësi A në një bashkësi B cakton saktësisht një element të B për secilin element të A. Grafiku i f është bashkësia e çifteve të renditura (a, b) të tilla që b = f (a). Për shkak se grafiku i f është një nënbashkësi e A × B, ai është një relacion nga A në B. Për më tepër, grafiku i një funksioni ka vetinë që çdo element i A është saktësisht elementi i parë i një çifti të renditur të grafikut. Një relacion mund të përdoret për të shprehur një marrëdhënie një-me-shumë midis elementeve të bashkësive A dhe B, ku një element i A mund të lidhet me më shumë se një element të B. Një funksion përfaqëson një relacioni ku saktësisht një element i B është i lidhur me secilin element të A. Relacionet janë një përgjithësim i grafikëve të funksioneve; ato mund të përdoren për të shprehur një klasë shumë më të gjerë relacionesh midis bashkësive.

Relacionet në një bashkësi

Një relacion në një bashkësi A është një relacion nga A në A. Me fjalë të tjera, një relacion në një bashkësi A është një nënbashkësi e A × A.

Shembull

Le të jetë A bashkësia {1, 2, 3, 4}. Relacioni R është i përkufizuar si në vijim: R = {(a, b) ∣ a pjesëton b}. (a, b) është në R atëherë dhe vetëm atëherë nëse a dhe b janë numra të plotë pozitivë që nuk kalojnë 4, të tillë që a pjesëton b, ne shohim se R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4) }.

Çiftet në këtë relacion janë paraqitur si grafikisht ashtu edhe në formë tabelare në Figurë

Vetitë e relacioneve

Ka disa veti që përdoren për të klasifikuar relacionet në një bashkësi.

Në disa relacione, një element lidhet gjithmonë me vetveten. Për shembull, le të jetë R relacioni në bashkësinë e të gjithë njerëzve që përbëhet nga çifte (x, y) ku x dhe y kanë të njëjtën nënë dhe të njëjtën baba. Pastaj xRx për çdo person x.

• Një relacion R në një bashkësi A quhet refleksiv nëse (a, a) ∈ R për çdo element a ∈ A.

Në disa relacione një element lidhet me një element të dytë atëherë dhe vetëm atëherë nëse elementi i dytë lidhet edhe me elementin e parë.

• Një relacion R në bashkësinë A quhet simetrik nëse (b, a) ∈ R sa herë që (a, b) ∈ R, për të gjitha a, b ∈ A.
• Një relacion R në një bashkësi A e tillë që për të gjitha a, b ∈ A, nëse (a, b) ∈ R dhe (b, a) ∈ R, atëherë a = b quhet antisimetrik.

Le të jetë R relacioni i përbërë nga të gjitha çiftet (x, y) të nxënësve në shkollën tuaj, ku x ka më shumë kredite se y. Supozoni se x është e lidhur me y dhe y është e lidhur me z. Kjo do të thotë që x ka marrë më shumë kredite se y dhe y ka marrë më shumë kredite se z. Mund të konkludojmë që x ka marrë më shumë kredite se z, kështu që x lidhet me z.

• Një relacion R në një bashkësi A quhet transitiv nëse sa herë që (a, b) ∈ R dhe (b, c) ∈ R, atëherë (a, c) ∈ R, për të gjitha a, b, c ∈ A.

Kombinimi i relacioneve

Meqenëse relacionet janë bashkësi, ato mund të manipulohen duke përdorur operacione të bashkësive, duke përfshirë unionin, prerjen dhe komplementin, dhe duke përmbushur ligjet e një algjebre të bashkësive. Përtej kësaj, operacione si anasjellta e një relacioni dhe kompozimi i relacioneve janë të disponueshme, që plotësojnë ligjet e llogaritjes së relacioneve, për të cilat ka tekste shkollore nga Ernst Schröder, Clarence Lewis dhe Gunther Schmidt.

Unioni

Nëse R dhe S janë relacione binare mbi bashkësitë X dhe Y, atëherë R ∪ S = {(x, y) | xRy ose xSy} është lunioni i relacioneve R dhe S mbi X dhe Y.

Për shembull, ≤ është unioni i < dhe =, dhe ≥ është unioni i > dhe =.

Prerja

Nëse R dhe S janë relacione binare mbi bashkësitë X dhe Y, atëherë R ∩ S = {(x, y) | xRy dhe xSy} është prerja e relacioneve R dhe S mbi X dhe Y.

Për shembull, relacioni "pjestohet me 6" është kryqëzimi i relacioneve "pjesëtohet me 3" dhe "pjesëtohet me 2".

Kompozimi

Le të jetë R relacion nga një bashkësi A me një bashkësi B dhe S relacion nga B në një bashkësi C. Kompozimi i R dhe S është relacioni i përbërë nga çifte të renditura (a,c), ku a ∈A, c ∈ C, dhe për të cilin ekziston një element b ∈ B i tillë që (a, b) ∈R dhe (b, c ) ∈ S. Kompozimin e R dhe S shënojmë me S ◦R. Rendi i R dhe S në shënimin S ∘ R, i përdorur këtu përputhet me renditjen standarde të shënimeve për kompozimin e funksioneve.

Komplementi

Nëse R është një relacion binarë mbi bashkësitë X dhe Y, atëherë R = {(x, y) | jo xRy} (e shënuar gjithashtu me R ose ¬ R) është lkomplementi i R mbi X dhe Y.

Për shembull, = dhe ≠ janë komplement të njëri-tjetrit, siç janë ⊆ dhe ⊈, ⊇ dhe ⊉, dhe ∈ dhe ∉, < dhe ≥, dhe > dhe ≤.

Nëse X = Y, komplementi ka vetitë e mëposhtme:

• Nëse një relacion është simetrik, atëherë edhe komplementi është.
• Komplementi i një relacioni refleksiv është jorefleksiv - dhe anasjelltas.

Inverzi

Relacioni invers i relacionit R $\subseteq$ A x B është bashkësia R^-1 $\subseteq$ B x A që jepet me: R^-1 = {(b,a) | (a,b) ∈ R}.

Vërejmë se nëse R paraqet relacion të bashkësisë A në bashkësinë B atëherë R^-1 paraqet relacion të bashkësisë B në bashkësinë A.

Shembull

Le të jetë A = {1, 2, 3} dhe B = {1, 2, 3, 4}. Relacionet R1 = {(1, 1), (2, 2), (3, 3)} dhe R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} mund të kombinohen si në vijim:

R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)},

R1 ∩ R2 = {(1, 1)},

R1 − R2 = {(2, 2), (3, 3)},

R2 − R1 = {(1, 2), (1, 3), (1, 4)},

R2 ◦ R1 = {(1, 1), (1, 2), (1, 3), (1, 4)}.

Paraqitja e relacioneve

Ka shumë mënyra për të paraqitur një relacion ndërmjet bashkësive të fundme. Një mënyrë është të listoni çiftet e renditura të saj. Një mënyrë tjetër për të përfaqësuar një relacion është të përdorni një tabelë. Në këtë pjesë do të diskutojmë dy metoda për paraqitjen e relacioneve. Një metodë përdor matricat zero-një. Metoda tjetër përdor paraqitjet pikturale të quajtura grafikë të drejtuar.

Paraqitja nëpërmjet matricave

Një relacion ndërmjet bashkësive të fundme mund të përfaqësohet duke përdorur një matricë zero-një. Supozoni se R është relacion nga A = {a1, a2,…, am} në B = {b1, b2,…, bn}. Relacioni R mund të paraqitet me matricën MR = [mij], ku

mij = 1, nëse (ai, bj) ∈ R  ; mij = 0, nëse (ai, bj) ∉ R

Me fjalë të tjera, matrica zero-një që përfaqëson R ka 1 si hyrje (i, j) kur ai është i lidhur me bj, dhe një 0 në këtë pozicion nëse ai nuk është i lidhur me bj. (Një përfaqësim i tillë varet nga rënditjet e përdorura për A dhe B.)

Shembull

Janë dhënë A = {1, 2, 3} dhe B = {1, 2}. Le të jetë R relacioni nga A në B që përmban (a, b) nëse a ∈ A, b ∈ B dhe a > b. Pasi R = {(2, 1), (3, 1), (3, 2)}, matrica për R është

M_R =${\begin{bmatrix}0&0\\1&0\\1&1\end{bmatrix}}$

Njëshat në M_R tregojnë se çiftet (2, 1), (3, 1) dhe (3, 2) i përkasin R. Zerot tregojnë se asnjë nga çiftet tjera nuk i përkasin R.

Paraqitja nëpërmjet digrafeve

Figura 2. Relacioni i paraqitur nëpërmjet grafit të orientuar

Relacioni R në një bashkësi A përfaqësohet nga grafiku i drejtuar që ka elementet e A-së, kulmet dhe çiftet e renditura (a, b), ku (a, b) ∈ R, si skaje. Kjo paraqitje krijon një funksion bijektiv midis relacioneve në një bashkësi A dhe grafikëve të drejtuar me A si bashkësia e tyre e kulmeve. Grafikët e drejtuar japin një shfaqje vizuale të informacionit rreth relacioneve. Si të tilla, ato shpesh përdoren për të studiuar relacionet dhe vetitë e tyre.

Në figurën 2 shihet paraqitja e relacionit R={(1,2),(2,3),(2,5),(3,1),(4,5),(5,5)} nëpërmjet grafit të orientuar.

Relacionet e ekuivalencës

Një relacion në një bashkësi A quhet një relacion i ekuivalencës nëse është refleksiv, simetrik dhe transitiv. Relacionet e ekuivalencës janë të rëndësishme në të gjithë matematikën dhe shkencat kompjuterike. Dy elemente a dhe b që lidhen me një relacion ekuivalent quhen ekuivalente. Shënimi a ∼ b përdoret shpesh për të treguar se a dhe b janë elementë ekuivalent të përkufizuar sipas një relacioni të ekuivalencës. Që nocioni i elementeve ekuivalente të ketë kuptim, çdo element duhet të jetë ekuivalent me vetë-veten, pasi vetia refleksive garanton një marrëdhënie ekuivalente. Ka kuptim të thuhet që a dhe b janë të lidhura (jo vetëm që a lidhet me b) nga një relacion ekuivalent, sepse kur a lidhet me b, nga vetia simetrike, b lidhet me a. Për më tepër, pasi relacioni i ekuivalencës është transitiv, nëse a dhe b janë ekuivalentë, dhe b dhe c janë ekuivalentë, vijon që a dhe c janë ekuivalentë. Duhet të kemi kujdes gjatë shqyrtimit të relacionit refleksiv dhe jorefleksiv. Nëse një relacion nuk është refleksiv kjo nuk do të thotë se ai doemos është jorefleksiv. Po ashtu nëse relacioni nuk është simetrik, nuk do të thotë se ai doemos duhet të jetë antisimetrik.

Shembull

Le të jetë R relacioni në bashkësinë e numrave realë i tillë që aRb atëherë dhe vetëm atëherë nëse a − b është një numër i plotë.

Sepse a−a = 0 është një numër i plotë për të gjithë numrat realë a, atëherë aRa për të gjithë numrat realë a. Prandaj, R është refleksiv. Tani supozoni se aRb. Atëherë a−b është një numër i plotë, kështu që b−a është gjithashtu një numër i plotë. Prandaj, bRa. Nga kjo rrjedh se R është simetrik. Nëse aRb dhe bRc, atëherë a−b dhe b−c janë numra të plotë. Prandaj, a−c = (a−b) + (b−c) është gjithashtu një numër i plotë. Prandaj, aRc. Kështu, R është transitiv. Rrjedhimisht, R është një relacion i ekuivalencës.

Klasat e ekuivalencës

Le të jetë R një relacion i ekuivalencës në një bashkësi A. Bashkësia e të gjithë elementëve që janë të lidhur me një element a të A quhet klasa ekuivalente e a. Klasa e ekuivalencës së a me respekt të R shënohet me [a]_R. Me fjalë të tjera, nëse R është një lidhje ekuivalente në një bashkësi A, klasa e ekuivalencës së elementit a është

[a]_R = {s ∣ (a, s) ∈ R}.

Nëse b ∈ [a]_R, atëherë b quhet përfaqësues i kësaj klase të ekuivalencës. Çdo element i një klase mund të përdoret si përfaqësues i kësaj klase. Kjo do të thotë, nuk ka asgjë të veçantë për elementin e zgjedhur si përfaqësues i klasës.

Faktor bashkësia është bashkësia e klasëve të ekuivalencës. Unioni i klasave të ekuivalencës të R është e gjithë bashkësia A, sepse një element a i A është në klasën e vet të ekuivalencës, domethënë, [a]_R. Me fjalë të tjera,

$\bigcup [a]$_R = A , a∈A

Relacionet e rënditjes

Relacioni që është refleksiv, antisimetrik dhe transitiv quhet relacion i renditjes. Një bashkësi S së bashku me një renditje të pjesshme R quhet bashkësi pjesërisht e renditur dhe shënohet me (S, R).

Zakonisht, shënimi a $\preccurlyeq$ b përdoret për të treguar se (a, b) ∈ R në një bashkësi të rënditur (S, R). Ky shënim përdoret sepse relacioni më i vogël ose i barabartë në bashkësinë e numrave realè është shembulli më i njohur i renditjes së pjesshme dhe simboli $\preccurlyeq$ është i ngjashëm me simbolin ≤ . (Vini re se simboli përdoret për të treguar relacionet në çdo poset, jo vetëm me relacionin më pak ose e barabartë .) Shënimi a ≺ b tregon se a $\preccurlyeq$ b, por a ≠ b. Gjithashtu, themi “a është më pak se b” ose “b është më i madh se a” nëse a ≺ b. Elementet a dhe b të një relacioni (S, $\preccurlyeq$ ) quhen të krahasueshëm nëse a ≺ b ose b $\succ$ a. Kur a dhe b janë elementë të S të tillë që as a $\preccurlyeq$ b as b $\succcurlyeq$ a, a dhe b quhen të pakrahasueshëm. Si p.sh, numrat 3 dhe 9 janë të krahasueshëm, sepse 3 ∣ 9. Numrat e plotë 5 dhe 7 janë të pakrahasueshëm, sepse 5 ̸| 7 dhe 7 ̸| 5.

Nëse (S, $\preccurlyeq$) është një relacion dhe çdo dy elementë të S janë të krahasueshëm, S quhet relacion i renditur plotësisht ose relacion i renditur në mënyrë lineare, dhe quhet rend total ose rend linear. Relacioni i renditur plotësisht quhet edhe zinxhir. Relacioni (Z,≤) është i renditur plotësisht, sepse a ≤ b ose b ≤ a sa herë që a dhe b janë numra të plotë.

PARIMI I INDUKSIONIT TË MIRË STRUKTURUAR

Supozoni se S është një renditje e mirë strukturuar. Atëherë P(x) është e vërtetë për çdo x ∈ S, nëse

HAPI INDUKTIV: Për çdo y ∈ S, nëse P(x) është e vërtetë për çdo x ∈ S ku x ≺ y, atëherë P(y) është e vërtetë.

PROVA: Supozoni se nuk është rasti që P(x) është e vërtetë për çdo x ∈ S. Atëherë ekziston një element y ∈ S i tillë që P(y) është i gabuar. Rrjedhimisht, bashkësia A = {x ∈ S ∣ P(x) është false} nuk është bosh. Për shkak se S është i renditur mirë, A ka një element më të vogël a. Nga zgjedhja e a si element më i vogël i A, ne e dimë se P(x) është e vërtetë për çdo x ∈ S me x ≺ a. Kjo nënkupton nga hapi induktiv se P(a) është i vërtetë. Kjo kontradiktë tregon se P(x) duhet të jetë e vërtetë për çdo x ∈ S.