Relation (mängdlära)

En relation är en matematisk struktur som formellt definierar egenskaperna hos olika objekt och deras relationer. Vanliga exempel på samband i matematik är likhet (=) , delbarhet , likhet , parallellism och många andra.

Begreppet en relation som en delmängd av en kartesisk produkt är formaliserad i mängdteorin och har blivit utbredd i matematikens språk i alla dess grenar. Den mängdteoretiska synen på en relation kännetecknar den i termer av volym – vilka kombinationer av element den är fylld med; ett meningsfullt tillvägagångssätt betraktas i matematisk logik , där relationen är en propositionell funktion , det vill säga ett uttryck med obestämda variabler, varvid ersättningen av specifika värden gör det sant eller falskt. Relationer spelar en viktig roll i universell algebra , där det grundläggande studieobjektet för avsnittet är en uppsättning med en godtycklig uppsättning operationer och relationer. En av de mest slående tillämpningarna av tekniken för matematiska relationer i tillämpningar är relationsdatabashanteringssystem , metodologiskt baserade på formell relationalgebra .

Relationer klassificeras vanligtvis efter antalet relaterade objekt ( aritet ) och deras egna egenskaper såsom symmetri , transitivitet , reflexivitet .

Formella definitioner och notation

$n$ -lokal ( -ary ) relation definierad på mängder är en delmängd av den kartesiska produkten av dessa mängder: . Det faktum att element är förbundna med en relation betecknas med eller . $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$

Faktumet om kopplingen mellan objekt och en binär relation betecknas vanligtvis med infixnotationen : . Enstaka (unära) relationer motsvarar egenskaper eller attribut, för sådana fall används som regel inte relationsterminologin. Ibland används treställsrelationer ( ternära ), fyrställsrelationer (kvartära); relationer av obestämd hög aritet kallas "fler", "många placerade". $m_{1}\in M_{1}$ $m_{2}\in M_{2}$ ${\displaystyle R\subset M_{1}\times M_{2))$ ${\displaystyle m_{1}\,R\,m_{2))$

En universell relation är en relation som förbinder alla element i givna mängder, det vill säga sammanfaller med den kartesiska produkten:. En nollrelation är en relation som inte länkar några element, det vill säga en tom uppsättning :. ${\displaystyle R=M_{1}\times M_{2}\times \dots M_{n))$ ${\displaystyle R=\varnothing \subset M_{1}\times M_{2}\times \dots M_{n))$

En funktionell relation är en relation som bildar en funktion : är funktionell om det följer av exekveringen att ( det unika i värdet av funktionen säkerställs). ${\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$

Allmänna egenskaper och typer av binära relationer

De vanligaste relationerna i matematikens språk är binära över en uppsättning ( ), som oftast används med några vanliga egenskaper [1] : $R\subseteq M^{2}$

symmetri ( ) eller antisymmetri ( ), $a\,R\,b\Rightarrow b\,R\,a$ $a\,R\,b\,\wedge \,b\,R\,a\Rightarrow a\,=\,b$
reflexivitet ( ) eller antireflexivitet , $a\,R\,a$ $\neg \,(a\,R\,a)$
transitivitet ( ) eller antitransitivitet ( ), $a\,R\,b\land b\,R\,c\Högerpil a\,R\,c$ $a\,R\,b\land b\,R\,c\Högerpil \neg \,a\,R\,c$
anslutning ( ). $a\neq b\Rightarrow a\,R\,b\lor b\,R\,a$

Beroende på uppsättningen egenskaper hos binära relationer, bildas några allmänt använda typer av dem:

ekvivalensrelation - varje reflexiv , transitiv och symmetrisk relation;
förbeställningsrelationen är reflexiv och transitiv;
partiell ordningsrelation - reflexiv, transitiv och antisymmetrisk;
förhållande av strikt ordning - antireflexiv, transitiv, antisymmetrisk;
den linjära ordningsrelationen är sammankopplad, reflexiv, antisymmetrisk.

En viktig roll spelas av jämlikhetsrelationen - ekvivalensrelationen, utförd endast för två sammanfallande element.

Det kan finnas andra kombinationer av egenskaper hos relationer, till exempel transitiva och reflexiva, men har inte andra enkla egenskaper, delbarhetsrelationen på mängden naturliga tal , vanligtvis betecknad med symbolen , den består av par av formen , där delar sig jämnt. Ett exempel på en ternär relation är bildandet av en Pythagoras trippel med tre tal, att vara i relation till en Pythagoras fyrdubbla är ett exempel på en kvartär relation. $|$ $\langle x,y\rangle$ $x$ $y$

En lösare uppsättning egenskaper hos binära relationer tillämpas i grafteorin : en oriktad graf kan definieras som en uppsättning av hörn med en symmetrisk binär relation över sig, och en riktad graf som en uppsättning av hörn med en godtycklig binär relation över sig.

Algebror för relationer

Alla relationer över en kartesisk produkt bildar en boolesk algebra under de mängdteoretiska operationerna union , skärningspunkt och komplement . $n$ ${\displaystyle M_{1}\times \dots \times M_{n))$

Relationell algebra är ett slutet system av operationer på relationer i en relationsdatamodell .

Anteckningar

↑ Universella kvantifierare utelämnade i formler

Litteratur

Relation - artikel från Encyclopedia of Mathematics . D. M. Smirnov
Kolmogorov A. N. , Dragalin A. G. Introduktion till matematisk logik. - M . : Moscow Universitys förlag, 1982. - 120 s. — 29 500 exemplar.