Ekvivalenciareláció

A matematikában ekvivalenciareláció (vagy röviden ekvivalencia) alatt olyan relációt értünk, amely egyszerre reflexív, szimmetrikus és tranzitív.

Definíció

Legyen ∼ {\displaystyle \sim } tetszőleges reláció az A {\displaystyle A} halmazon. Azt mondjuk, hogy a ∼ {\displaystyle \sim } reláció ekvivalenciareláció, ha az alábbi három feltétel teljesül:

  • a ∼ {\displaystyle \sim } reláció reflexív, azaz minden a ∈ A {\displaystyle a\in A} esetén a ∼ a {\displaystyle a\sim a} teljesül,
  • a ∼ {\displaystyle \sim } reláció szimmetrikus, azaz minden a , b ∈ A {\displaystyle a,b\in A} esetén ha a ∼ b {\displaystyle a\sim b} teljesül, akkor b ∼ a {\displaystyle b\sim a} is teljesül,
  • a ∼ {\displaystyle \sim } reláció tranzitív, azaz minden a , b , c ∈ A {\displaystyle a,b,c\in A} esetén ha a ∼ b {\displaystyle a\sim b} és b ∼ c {\displaystyle b\sim c} teljesül, akkor a ∼ c {\displaystyle a\sim c} is teljesül.

Tulajdonságok

  • Minden ∼ {\displaystyle \sim } ekvivalenciareláció egyértelműen meghatároz egy osztályozást azon az A {\displaystyle A} halmazon, amelyen a reláció definiálva van: az a , b ∈ A {\displaystyle a,b\in A} elemek pontosan akkor kerülnek egy osztályba ebben az osztályozásban, ha a ∼ b {\displaystyle a\sim b} teljesül.
  • Fordítva: valamely A {\displaystyle A} halmaz minden osztályozása egyértelműen meghatároz egy ekvivalenciarelációt az adott halmazon. Ennél az ekvivalenciarelációnál pontosan azok az elemek állnak relációban egymással, amelyek az osztályozásnak ugyanabban az osztályában vannak.

Példák

  • A legegyszerűbb és legfontosabb példa az egyenlőségreláció
  • A logikai ekvivalencia a logikában
  • Izomorfizmus az absztrakt algebrában
  • Kongruencia a számelméletben
  • Az "úttal való elérhetőség" gráfok csúcsai között.
  • Síkidomok egybevágósága és hasonlósága.

Hivatkozások

  • Rédei László: Algebra I., Akadémiai Kiadó, Budapest, 1954
  • Szendrei Ágnes: Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged, 1994

További információk

  • Alice és Bob - 13. rész: Alice és Bob eladósodik
  • Alice és Bob - 18. rész: Alice és Bob felcsavarja a számegyenest