10.1. Relációk
Definíció: A H és K halmazok H×K Descartes szorzatának bármely részhalmazát H és K közötti (binér) relációnak nevezzük. Jele: ς. Ha x eleme H-nak és y eleme K-nak, xςy azt jelenti, hogy az x xςy relációban áll y-nal.
A relációkat ábrázolhatjuk gráfokkal.
Az egyértelmű relációt leképezésnek nevezzük (xςy és xςz → y = z).
Ha a H halmaz minden eleme relációban áll a K halmaz pontosan egy elemével, akkor függvényről beszélünk.
A H halmazon értelmezett relációk (H×H részhalmaza) tulajdonságai:
- reflexív: H minden x elemére xςx.
- szimmetrikus: H minden x, y elemére, ha xςy , akkor yςx.
- antiszimmetrikus: H minden x, y elemére, ha xςy és yςx , akkor x = y.
- tranzitív: H minden x, y, z elemére, ha xςy és yςz, akkor xςz.
Példák:
- Az egyenesek merőlegessége: nem reflexív, szimmetrikus és nem tranzitív.
- Az ismerős reláció: nem reflexív, szimmetrikus és nem tranzitív.
- Egy versenyen a „legyőzte” reláció nem reflexív, antiszimmetrikus és tranzitív.
Ha a H halmazon értelmezett reláció reflexív, szimmetrikus és tranzitív, akkor ekvivalencia relációnak nevezzük.
Példák ekvivalencia relációra:
- Egyenlőség (törtek különböző alakjai, vektorok, stb.)
- Egybevágóság
- Hasonlóság
- Egyenesek párhuzamossága
- Adott számmal azonos maradékot adó természetes számok vannak relációban egymással.
- Osztálytárs
- Édestestvér
Ha a H halmazon értelmezett reláció reflexív, antiszimmetrikus és tranzitív, akkor rendezési relációnak nevezzük.
Példák rendezési relációra:
- N-ben az „a osztója b” (Érdekesség, hogy az „a osztója b” reláció az egész számok halmazán nem antiszimmetrikus, a páros számok halmazán pedig nem reflexív.)
- A H halmaz részhalmazain értelmezett „részhalmaz” reláció.
- N-ben a ≤ reláció (vigyázzunk, a < reláció nem reflexív).
Figyeljük meg, hogy a természetes számok halmazán értelmezett „a osztója b” rendezési reláció szerint a „legkisebb” természetes szám az 1, mert minden természetes számnak osztója, a „legnagyobb” természetes szám pedig a 0, mert a 0-nak minden természetes szám osztója.