Relációk halmazokon

A relációk a halmazelméletben két halmaz elemei közötti kapcsolatokat írnak le. Egy reláció nem más, mint egy halmaz a Descartes-szorzatból: ha A és B halmazok, akkor R ⊆ A × B. Ez azt jelenti, hogy a reláció az A és B elemei közötti kapcsolatok összessége.

Ha (a,b) ∈ R, akkor azt mondjuk, hogy az „a elem relációban áll b-vel”.

Relációk típusai

• Reflexív: minden elem önmagával relációban áll. Példa: „≤” reláció az egész számokon.
• Szimmetrikus: ha (a,b) ∈ R, akkor (b,a) ∈ R is. Példa: „ismerős” reláció emberek között.
• Tranzitív: ha (a,b) ∈ R és (b,c) ∈ R, akkor (a,c) ∈ R. Példa: „≤” reláció az egész számokon.
• Antiszimmetrikus: ha (a,b) ∈ R és (b,a) ∈ R, akkor a = b. Példa: „≤” reláció az egész számokon.

Ha egy reláció reflexív, szimmetrikus és tranzitív, akkor azt ekvivalenciarelációnak nevezzük. Az ekvivalenciarelációk halmazt ekvivalenciaosztályokra bontanak.

Megoldott példa

Legyen A = {1,2,3}, és definiáljunk egy R relációt így: R = {(1,1), (2,2), (3,3), (1,2), (2,1)}. Vizsgáljuk meg a tulajdonságait!

• Reflexív? Igen, mert minden elem önmagával relációban áll: (1,1), (2,2), (3,3) ∈ R.
• Szimmetrikus? Igen, mert ha (1,2) ∈ R, akkor (2,1) ∈ R is.
• Tranzitív? Igen, mert minden olyan esetre, ahol (a,b) ∈ R és (b,c) ∈ R, igaz, hogy (a,c) ∈ R. Vizsgáljuk meg: (1,2) ∈ R és (2,1) ∈ R, tehát (1,1) ∈ R-nek kell lennie, ami teljesül. További párok, például (2,3) vagy (3,1), nem állnak fenn, így nincs más eset, amit ellenőrizni kell.
• Antiszimmetrikus? Nem, mert (1,2) és (2,1) is benne van, pedig 1 ≠ 2.

Ez a reláció tehát reflexív, szimmetrikus és tranzitív, így ekvivalenciareláció. Az ekvivalenciaosztályok: {1,2} és {3}.

Alkalmazások

• Rendezési relációk: pl. ≤, <, amelyek antiszimmetrikusak és tranzitívek.
• Ekvivalenciarelációk: pl. „azonos születési év” emberek között.
• Adatbázisok: kapcsolatok modellezése két táblázat elemei között.
• Gráfelmélet: a relációk gráfként is ábrázolhatók, ahol az elemek pontok, a relációk élek.

Összefoglalás

A relációk lehetővé teszik, hogy kapcsolatokat írjunk le halmazok elemei között. A legfontosabb tulajdonságok: reflexív, szimmetrikus, tranzitív, antiszimmetrikus. Ezek kombinációja határozza meg, hogy a reláció például rendezés vagy ekvivalenciareláció.

Gyakorló feladat