Reláció (halmazelmélet)

A reláció egy olyan matematikai struktúra , amely formálisan határozza meg a különböző objektumok tulajdonságait és kapcsolataikat. A matematikában az összefüggések gyakori példái az egyenlőség (=) , az oszthatóság , a hasonlóság , a párhuzamosság és még sok más.

A reláció, mint a karteziánus szorzat részhalmazának fogalma a halmazelméletben formalizálódott, és a matematika nyelvében minden ágában elterjedt. A reláció halmazelméleti nézete a térfogat szempontjából jellemzi – milyen elemkombinációkkal van kitöltve; értelmes megközelítést a matematikai logika tekint , ahol a reláció egy propozíciós függvény , azaz egy határozatlan változókkal rendelkező kifejezés, amelyre adott értékek helyettesítése igaz vagy hamissá teszi. A relációk fontos szerepet játszanak az univerzális algebrában , ahol a szakasz alapvető vizsgálati tárgya egy tetszőleges művelet- és relációhalmaz. A matematikai relációk technikájának egyik legszembetűnőbb alkalmazása az alkalmazásokban a relációs adatbázis-kezelő rendszerek , amelyek módszertanilag a formális relációs algebrán alapulnak .

A kapcsolatokat általában a kapcsolódó objektumok száma ( aritás ) és saját tulajdonságaik szerint osztályozzák, mint pl. szimmetria , tranzitivitás , reflexivitás .

Formális definíciók és jelölések

$n$ A halmazokon definiált -local ( -ary ) reláció ezeknek a halmazoknak a derékszögű szorzatának részhalmaza : . Azt a tényt, hogy az elemeket reláció köti össze, vagy jelöli . $n$ $R$ $M_{1},M_{2},\ldots ,M_{n}$ ${\displaystyle R\subseteq M_{1}\times M_{2}\times \dots M_{n))$ $n$ $\langle m_{1}\in M_{1},m_{2}\in M_{2},\dots m_{n}\in M_{n}\rangle$ $R$ $R(m_{1},m_{2},\dots ,m_{n})$ $(m_{1},m_{2},\dots ,m_{n})\in R$

Az objektumok és a bináris reláció közötti kapcsolat tényét általában az infix jelöléssel jelöljük : . Az egyedi (egyetlen) relációk tulajdonságoknak vagy attribútumoknak felelnek meg, ilyen esetekben általában nem használják a relációk terminológiáját. Néha háromhelyi relációt ( ternary ), négyhelyes relációt (negyedes) használnak; a végtelenül magas aritású kapcsolatokat "többszörösnek", "sokhelyűnek" nevezik. $m_{1}\in M_{1}$ $m_{2}\in M_{2}$ ${\displaystyle R\subset M_{1}\times M_{2))$ $m_{1}\,R\,m_{2}$

Az univerzális reláció egy adott halmaz összes elemét összekötő reláció, azaz egybeesik a derékszögű szorzattal:. A nullreláció olyan reláció, amely egyetlen elemet sem kapcsol össze, vagyis egy üres halmaz :. ${\displaystyle R=M_{1}\times M_{2}\times \dots M_{n))$ ${\displaystyle R=\varnothing \subset M_{1}\times M_{2}\times \dots M_{n))$

A funkcionális reláció olyan reláció, amely függvényt alkot : akkor funkcionális, ha a végrehajtásból az következik, hogy ( a függvény értékének egyedisége biztosított). ${\displaystyle R\subseteq M_{1}\times M_{2}\times \dots M_{n}\dots M_{n+1))$ $R(m_{1},\dots ,m_{n},x)$ $R(m_{1},\dots ,m_{n},y)$ $x=y$

A bináris relációk általános tulajdonságai és típusai

A matematika nyelvében a legelterjedtebb relációk egy halmaz feletti binárisak ( ), amelyeket leggyakrabban néhány közös tulajdonsággal használnak [1] : $R\subseteq M^{2}$

szimmetria ( ) vagy antiszimmetria ( ), $a\,R\,b\Jobbra b\,R\,a$ $a\,R\,b\,\wedge \,b\,R\,a\Rightarrow a\,=\,b$
reflexivitás ( ) vagy antireflexivitás , $a\,R\,a$ ${\megjelenítési stílus \neg \,(a\,R\,a)}$
tranzitivitás ( ) vagy antitranzitivitás ( ), $a\,R\,b\land b\,R\,c\Jobbra a\,R\,c$ $a\,R\,b\land b\,R\,c\Jobbra \neg \,a\,R\,c$
csatlakoztathatóság ( ). $a\neq b\Jobbra a\,R\,b\vagy b\,R\,a$

A bináris relációk tulajdonságainak halmazától függően néhány széles körben használt típus jön létre:

ekvivalenciareláció - bármilyen reflexív , tranzitív és szimmetrikus reláció;
az előrendelési reláció reflexív és tranzitív;
részleges rend reláció - reflexív, tranzitív és antiszimmetrikus;
szigorú rend kapcsolata - antireflexív, tranzitív, antiszimmetrikus;
a lineáris rend reláció összefüggő, reflexív, antiszimmetrikus.

Fontos szerepet játszik az egyenlőség relációja - az ekvivalencia reláció, amelyet csak két egybeeső elemre hajtanak végre.

A relációk tulajdonságainak más kombinációi is lehetnek, például tranzitív és reflexív, de nincs más egyszerű tulajdonsága, az oszthatósági reláció a természetes számok halmazán , általában szimbólummal jelölve, alakpárokból áll , ahol egyenletesen osztódik . Példa a hármas relációra egy Pitagorasz-hármas létrehozása három számmal, a Pitagorasz-négyeshez való viszony egy példa a negyedes relációra. $|$ $\langle x,y\rangle$ $x$ $y$

A bináris relációk tulajdonságainak lazább halmazát alkalmazzák a gráfelméletben : egy irányítatlan gráf definiálható olyan csúcsok halmazaként, amelyek felett szimmetrikus bináris reláció, az irányított gráf pedig olyan csúcsok halmazaként definiálható, amelyek fölött tetszőleges bináris kapcsolat van.

Relációalgebrák

A derékszögű szorzaton lévő összes reláció egy Boole-algebrát alkot az unió , a metszés és a komplement halmazelméleti műveletei alatt . $n$ ${\displaystyle M_{1}\times \dots \times M_{n))$

A relációs algebra egy relációs adatmodell relációira vonatkozó zárt műveletrendszer .

Jegyzetek

↑ Az univerzális kvantorok kimaradtak a képletekből

Irodalom

Relation - cikk az Encyclopedia of Mathematics - ból . D. M. Szmirnov
Kolmogorov A. N. , Dragalin A. G. Bevezetés a matematikai logikába. - M . : Moszkvai Egyetem Kiadója, 1982. - 120 p. — 29.500 példány.