relationsmängden

relationsmängden är ett begrepp inom diskret matematik som beskriver alla binära relationer på en given mängd. Om man har en mängd A är en binär relation på A en delmängd av produkten A×A, dvs ett antal ordnade par där varje förstekomponent och every andra komponent kommer från A. Mängden av alla sådana relationer kallas relmängden Rel(A), och Rel(A) är exakt kraftmängden P(A×A).

Om antalet element i A är n, finns det n^2 möjliga ordnade par i A×A. Eftersom varje par kan vara med eller inte i en relation, finns det 2^(n^2) olika relationer i Rel(A). Varje relation R i Rel(A) kan ses som en uppsättning av ordnade par eller, equivalently, som en n×n boolesk matris där entry (i,j) är 1 om och endast om (i,j)∈R. En grafisk tolkning är en riktad graf med n noder där pilarna correspond till de par som tillhör R.

Vanliga egenskaper hos binära relationer inkluderar reflexivitet (varje a i A relaterad till sig själv), symmetri (om aRb så bRa) och transitivitet (om aRb och bRc så aRc). Om en relation uppfyller dessa tre egenskaper kallas den ofta en ekvivalensrelation; en delordning (partiell ordning) kräver reflexivitet, antisymmetri och transitivity. Inom Rel(A) kan man undersöka sådana speciella relationer och deras strukturer.

Rel(A) utgör även en Boolean algebra när man betraktar union, snitt och komplement av relationer, eftersom Rel(A) är just kraftmängden över A×A. Man kan också definiera operationer som komposition av relationer och omvänd relation. Användningsområden inkluderar grafteori, databaslogik och semantisk modellering där relationer representerar kopplingar mellan objekt.