2.4. A kétváltozós (binér) relációk fontosabb tulajdonságai
Bevezetésként lássunk néhány példát binér relációkra.
(1) Legyen
A = {1, 2, 3, 4, 5, 6}
és értelmezzük a
γ⊆AΧA
binér relációt a következőképpen:
γ = {(1,2), (1,4), (2,4), (2,5), (3,6), (4,5), (5,4), (5,5)}
A γ binér relációt ábrázolhatjuk egy irányított gráffal, ahol a gráf csúcsai (vagy csomópontjai) az 'A' halmaz elemeinek felelnek meg, és az a∈A pontból a b∈A pontba mutató irányított élt (nyilat) akkor és csak akkor ábrázoljuk, ha (a,b)∈γ teljesül.
Ennek megfelelően a γ relációt ábrázoló gráf a következő:
Feladat: próbáljunk meg olyan modelleket konstruálni, amelyekben a fenti relációhoz valamilyen jelentést rendelünk!
(2) Legyen most az 'A' halmaz a gyümölcsnevek halmaza, azaz legyen
A = {gyümölcsök nevei}
amelyre például "alma"∈A, "körte"∈A stb. teljesül.
A gyümölcsnevek halmazának (A) önmagával vett direkt szorzatán adjunk meg egy
θ⊆AΧA
relációt a következőképpen:
θ(a,b) ⇋ "az 'a' és 'b' gyümölcsnevek hossza megegyezik"
Ekkor például
θ("alma","alma"), azaz ("alma","alma")∈θ,
θ("barack","szilva"), azaz ("barack","szilva")∈θ,
θ("szilva","barack"), azaz ("szilva","barack")∈θ.
Ezzel szemben például
("alma","citrom")∉θ és
("dinnye","dió")∉θ.
A θ relációt véges 'A' halmaz esetén ábrázolhatjuk például irányított gráf formájában. Értelmezzük a θ relációt az
A={"alma", "banán", "barack", "citrom", "dinnye", "dió", "eper", "körte", "mogyoró", "narancs", "szilva"}
halmazon, és ábrázoljuk a θ relációt:
Vegyük észre, hogy az azonos hosszúságú gyümölcsnevek olyan diszjunkt⇒ és nem üres elemhalmazokba csoportosíthatók, amelyek együttesen "lefedik" az 'A' alaphalmazt (vagyis uniójuk az 'A' halmazt adja).
Ezeket az elemhalmazokat osztályoknak nevezzük.
(3) Vegyük végül az I = {piros, zöld, kék} alaphalmaz
A, B∈2I részhalmazait,
és ábrázoljuk a köztük értelmezett
A⊆B ⇋ "'A' részhalmaza 'B'-nek"
binér relációt táblázatos formában!
Rövidítésként "piros" helyett "p"-t, "zöld" helyett "z"-t, és "kék" helyett "k"-t fogunk használni.
Vegyük észre, hogy a táblázat által megjelenített tartalom minden három elemű halmaz esetében ugyanaz lesz.
Például p↔a, z↔b, és k↔c helyettesítéseket végrehajtva a táblázat megadja az I={a,b,c} halmaz összes részhalmazát és ezek tartalmazási viszonyait.
|
A⊆B
| ←B→
|
|
↓A↓
| ∅
| {p}
| {z}
| {k}
| {p,z}
| {p,k}
| {z,k}
| {p,z,k}
|
| ∅
|
|
|
|
|
|
|
|
|
| {p}
|
|
|
|
|
|
|
|
|
| {z}
|
|
|
|
|
|
|
|
|
| {k}
|
|
|
|
|
|
|
|
|
| {p,z}
|
|
|
|
|
|
|
|
|
| {p,k}
|
|
|
|
|
|
|
|
|
| {z,k}
|
|
|
|
|
|
|
|
|
| {p,z,k}
|
|
|
|
|
|
|
|
|
|
↑A↑
| ∅
| {p}
| {z}
| {k}
| {p,z}
| {p,k}
| {z,k}
| {p,z,k}
|
A fenti táblázat a korábban bevezetett
Φ⊆2IΧ2I
részhalmaz reláció⇒ két dimenziós megjelenítése három elemű I alaphalmaz esetén.
A fenti példák segítenek abban, hogy megfogalmazzuk a binér relációk legfontosabb tulajdonságait.
Legyen 'A' tetszőleges halmaz, amelyen értelmezett az '=' reláció.
Legyen továbbá
ρ⊆AΧA
kétváltozós (binér) reláció. Értelmezzük az alábbi tulajdonságokat:
(1) reflexivitás – irreflexivitás – egyik sem
- reflexivitás: minden a∈A elemre (a,a)∈ρ teljesül
(azaz minden elem relációban van önmagával)
Például a természetes számokon értelmezett
- oszthatóság ( | ) reflexív reláció, mivel minden természetes szám osztója önmagának
- egyenlőség ( = ) reflexív reláció, mivel minden természetes szám egyenlő önmagával
- irreflexivitás: minden a∈A elemre (a,a)∉ρ teljesül (másképpen megfogalmazva: nincs olyan a∈A elem, amelyre (a,a)∈ρ teljesül)
(azaz egyetlen elem sincs relációban önmagával)
Például a természetes számokon értelmezett
- "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk irreflexívek, mivel egyetlen természetes szám sem kisebb (vagy nagyobb) önmagánál
(2) szimmetria – antiszimmetria – aszimmetria – egyik sem
- szimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∈ρ teljesülése következik
(azaz a relációban álló elemek kölcsönösen relációban vannak egymással)
Például a természetes számokon értelmezett
- egyenlőség ( = ) szimmetrikus reláció
- antiszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ és (b,a)∈ρ egyszerre teljesül, akkor ebből a=b teljesülése következik (másképpen megfogalmazva: tetszőleges a, b∈A, a≠b elemekre (a,b)∈ρ teljesüléséből (b,a)∉ρ következik; antiszimmetrikus reláció esetében azonban létezhet olyan a∈A elem, amelyre (a,a)∈ρ teljesül, mivel a=a nyilvánvalóan teljesül)
(azaz egyetlen elem sincs kölcsönösen relációban egy másikkal, azonban önmagával relációban állhat)
Például a természetes számokon értelmezett
- "kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk antiszimmetrikusak (vagyis egyrészt ha két n,m∈ℕ természetes számra n≤m és m≤n (vagy n≥m és m≥n) egyszerre teljesül, akkor n=m, azaz a két szám azonos, nem lehetnek különbözőek; másrészt bármely n∈ℕ természetes szám relációban áll önmagával, mivel n≤n és n≥n teljesül)
-
aszimmetria: ha az a∈A és b∈A elemekre (a,b)∈ρ teljesül, akkor ebből (b,a)∉ρ teljesülése következik
(azaz egyetlen elem sincs kölcsönösen relációban egy másik elemmel, és nem állhat relációban önmagával sem)
Például a természetes számokon értelmezett
- "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk aszimmetrikusak (és korábban láttuk, hogy irreflexívek is)
Jegyezzük meg, hogy aszimmetrikus reláció esetében (a,a)∈ρ teljesüléséből (a,a)∉ρ következik, ami ellentmondás, vagyis nem létezik olyan a∈A elem, amelyre (a,a)∈ρ teljesül; tehát az aszimmetrikus reláció mindig irreflexív.
Mivel különböző elemekre mind aszimmetrikus, mind antiszimmetrikus reláció esetében teljesül, hogy (a,b)∈ρ teljesüléséből (b,a)∉ρ teljesülése következik, az aszimmetrikus relációk mindig antiszimmetrikusak.
A fenti két megállapítást úgy foglalhatjuk össze, hogy egy reláció akkor és csak akkor aszimmetrikus, ha antiszimmetrikus és irreflexív.
Az aszimmetrikus relációk mindig antiszimmetrikusak.
Végül jegyezzük meg, hogy mivel a szimmetria és antiszimmetria meghatározásakor nem kötöttük ki, hogy az a∈A és b∈A elemek különbözőek legyenek, egy egyelemű 'A' halmazon értelmezett ρ reflexív reláció egyszerre szimmetrikus és antiszimmetrikus (azonban nem aszimmetrikus). Egy egyelemű 'A' halmazon értelmezett ρ irreflexív reláció pedig egyszerre szimmetrikus és aszimmetrikus (vagyis antiszimmetrikus is).
(3) tranzitivitás – nem teljesülő tranzitivitás
- tranzitivitás: ha az a∈A, b∈A és c∈A elemekre
(a,b)∈ρ
és
(b,c)∈ρ
teljesül, akkor ebből
(a,c)∈ρ
teljesülése következik
(azaz ha egy elem relációban áll egy másikkal, ez pedig relációban áll egy harmadikkal, akkor az első elem relációban áll a harmadik elemmel is)
Például a természetes számokon értelmezett
- "kisebb, mint" ( < ), "nagyobb, mint" ( > ), "kisebb-egyenő, mint" ( ≤ ), "nagyobb-egyenlő, mint" ( ≥ ) és "egyenlő" ( = ) relációk tranzitívak
Nevezzük adott a∈A, b∈A és c∈A elemek esetén
– az a∈A és b∈A elemek között fennálló (a,b)∈ρ relációt, valamint a b∈A és c∈A elemek között fennálló (b,c)∈ρ relációt közvetlen kapcsolatoknak,
– az a∈A és c∈A elemek között fennálló (a,c)∈ρ relációt rövid útnak (vö. Zsoldos Péter: Ellenpont).
Ilyen elnevezések mellett a 'ρ' reláció tranzitivitása úgy is megfogalmazható, hogy minden olyan a∈A, b∈A, c∈A elemhármas esetén, amelyekre teljesül, hogy az 'a' és 'b', valamint a 'b' és 'c' elemek között közvetlen kapcsolat van, akkor létezik az 'a' és 'c' elemek között rövid út.
Emeljük ki, hogy a tranzitivitás meghatározásában az a∈A, b∈A és c∈A elemek nem feltétlenül különbözők.
A tranzitivitást egy vagy két relációban levő elem esetén a következőképpen értelmezhetjük:
- ha (a,b)∈ρ és (b,a)∈ρ teljesül, akkor tranzitív reláció esetén ebből c=a miatt (a,a)∈ρ teljesülése következik;
- ha (b,a)∈ρ és (a,b)∈ρ teljesül, akkor tranzitív reláció esetén ebből c=b miatt (b,b)∈ρ teljesülése következik;
- ha (a,a)∈ρ teljesül, akkor tranzitív reláció esetén ebből b=a és c=a miatt (a,a)∈ρ teljesülése következik;
- ha (a,a)∈ρ és (a,b)∈ρ teljesül, akkor tranzitív reláció esetén ebből c=b miatt (a,b)∈ρ teljesülése következik;
- ha (a,b)∈ρ és (b,b)∈ρ teljesül, akkor tranzitív reláció esetén ebből c=b miatt (a,b)∈ρ teljesülése következik.
A fentiek fontos következménye az, hogy
– ha az a∈A, és b∈A elemek kölcsönösen relációban állnak, akkor tranzitív reláció esetén teljesülnie kell az (a,a)∈ρ és (b,b)∈ρ relációknak is;
–
a tranzitivitást akkor is értelmezni tudjuk, ha az 'A' halmaz egy- vagy kételemű.
Végül jegyezzük meg, hogy egy egyelemű 'A' halmazon értelmezett ρ reláció mindig tranzitívnak tekinthető.
(4) trichotómia – nem teljesülő trichotómia
-
linearitás vagy trichotómia: tetszőleges a∈A és b∈A elemekre
vagy (a,b)∈ρ,
vagy (b,a)∈ρ,
vagy a=b
teljesül; tehát ha a≠b különböző elemek, akkor az (a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyiknek teljesülnie kell
(azaz bármely két különböző elem relációban áll egymással; az elemek közti reláció lehet kölcsönös is, és az elemek önmagukkal is relációban állhatnak)
A fenti relációk közül legalább egynek mindig teljesülnie kell, de egyszerre akár több is teljesülhet (vö. Vajda 1996: 36). Szigorúbb feltétel, hogy a≠b esetén az (a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül (pl. Dringó-Kátai 1986: 28, Bonifert-Kovácsné Győri 1987: 32).⇒
Például a természetes számokon értelmezett
- "kisebb-egyenlő, mint" ( ≤ ) és "nagyobb-egyenlő, mint" ( ≥ ) relációk trichotómak (és reflexívek)
- "kisebb, mint" ( < ) és "nagyobb, mint" ( > ) relációk trichotómak (és irreflexívek)
A trichotómia lényege szemléletesen fogalmazva az, hogy egy trichotóm reláció segítségével egy halmaz bármelyik két (különböző) eleme összehasonlítható egymással. (Aszimmetrikus vagy antiszimmetrikus reláció esetén ennek a halmazok rendezésekor⇒ lesz jelentősége.)
Végül jegyezzük meg, hogy egy egyelemű 'A' halmazon értelmezett ρ reláció mindig trichotóm.
A trichotómia fogalma nem egyértelműen jelenik meg a szakirodalomban. Például bevezethetjük az alábbi fogalmakat is (vö. MaYoR 2020):
- összefüggőség: tetszőleges a∈A és b∈A, a≠b elemekre az
(a,b)∈ρ és (b,a)∈ρ relációk közül legalább az egyik teljesül;
- dichotómia: tetszőleges a∈A és b∈A, a≠b elemekre az
(a,b)∈ρ és (b,a)∈ρ relációk közül pontosan az egyik teljesül.
A "megengedő" trichotómia esetében az összefüggőséget követeljük meg. A trichotómia "megengedő" meghatározása az a=b esetben nem mond semmit sem az elemek közti relációról (azaz mind (a,a)∈ρ, mind (a,a)∉ρ teljesülését megengedjük).
A "szigorú" trichotómia esetében a dichotómiát követeljük meg (amely magában foglalja az összefüggőséget). A "szigorú" trichotómia egyik elfogadott definíciója az, hogy bármely a, b∈I esetén a ρ(a,b), ρ(b,a) és a=b relációk közül pontosan egy teljesül; ebben az esetben, ha a=b, akkor sem ρ(a,b), sem ρ(b,a) nem teljesül, vagyis a reláció irreflexív. Ebben az értelemben például a < reláció trichotóm, de a ≤ reláció nem az.
Az egyes relációtulajdonságok szemléltetése gráfokkal
- reflexivitás: a gráf minden csomópontjához egy hurokél tartozik
- irreflexivitás: a gráf egyetlen csomópontjához sem tartozik hurokél
- szimmetria: a gráf minden összekötött (azaz relációban levő) csomópontját két, ellentétes irányú él köti össze (hurokélek is lehetségesek!)
- antiszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek azonban lehetségesek
- aszimmetria: nem létezik két olyan összekötött csomópont, amelyet két, ellentétes irányú él köt össze (azaz a gráfban a relációban levő csomópontokat legfeljebb egy él kötheti össze); hurokélek nem lehetségesek
- tranzitivitás: ha egy csomópontból egy másik csomóponton keresztül eljuthatunk egy harmadik csomópontba (a csomópontokat összekötő élek irányát követve), akkor az első csomópontból közvetlenül, egy lépésben (azaz egy összekötő élen keresztül) is eljuthatunk a harmadik csomópontba
- trichotómia: bármely két csomópont össze van kötve, és az összekötött csomópontok közül az egyikből mindig közvetlenül eljuthatunk a másik csomópontba; hurokélek lehetségesek (azonban a közvetlen visszajutást, azaz a két csomópontot ellentétes irányban összekötő párhuzamos éleket a trichotómia szigorúbb feltétele esetében nem engedjük meg)
