Equivalentierelatie

Naïeve verzamelingenleer: Relaties

Equivalentierelatie

Equivalentierelatie

Een equivalentierelatie op een verzameling is een binaire relatie die reflexief, symmetrisch en transitief is.

In de meeste gevallen noteren we de relatie met het \(\boldsymbol{\sim}\) symbool en soms met het \(\boldsymbol{\equiv}\) symbool.

Dus, voor een verzameling \(X\) is \(\sim\) een equivalentierelatie op \(X\) als

Voor iedere \(x\in X\): \(x\sim x\);
Voor alle \(x,y\in X\): als \(x\sim y\), dan \(y\sim x\);
Voor alle \(x,y,z\in X\): als \(x\sim y\) en \(y\sim z\), dan \(x\sim z\).

Voorbeelden

Gelijkheid op een zekere verzameling

Gelijkvormigheid van driehoeken

Parellelliteit of gelijkheid van lijnen in het vlak

Congruentie van gehele getallen modulo een vast gekozen natuurlijk getal \(m\) gedefinieerd door \(a\equiv b\; (\mathrm{mod\;}m)\) dan en slechts dan als \(a-b\) deelbaar is door \(m\).

De relatie op \(\mathbb{Z}\times \bigl(\mathbb{N}\backslash\{0\}\bigr)\) gedefinieerd door \((p,q)\sim(r,s)\) dan en slechts dan als \(p\cdot s=r\cdot q\). Als je bij \((p,q)\) denkt aan het quotiënt \(p/q\), dan is de equivalentierelatie een manier om breuken met dezelfde getalswaarde te identificeren.

Equivalentieklasse

Equivalentieklasse

Gegeven een equivalentierelatie \(\sim\) op een verzameling \(X\) definiëren we de equivalentieklasse \(E_x\) van een element \(x\in X\) als de verzameling \(E_x=\{y\in X\mid x\sim y\}\).

Andere gangbare notaties voor de equivalentieklasse van \(x\in X\) bij de equivalentierelatie \(\sim\) zijn \([x]_{\sim}\) (of simpelweg \([x]\)) en \(x/{\sim}\).

Voorbeelden

We bekijken de equivalentierelatie op \(\mathbb{R}\) gedefinieerd door \(x\sim y\) dan en slechts dan als \(x-y\in \mathbb{Z}\). Dan: \(E_0=\{x\mid x-0\in \mathbb{Z}\} =\mathbb{Z}\), \(E_{\pi}=\{x\mid x-\pi\in \mathbb{Z}\}=\{\pi+k\mid k\in \mathbb{Z}\}\).

We bekijken de equivalentierelatie op \(\mathbb{N}\) gedefinieerd door \(x\sim y\) dan en slechts dan als \(x+y\) even is. Dan zijn er 2 equivalentieklassen: \(E_0=\{0,2,4,\ldots\}\) en \(E_1=\{1,3,5,\ldots\}\).

We bekijken de equivalentierelatie op \(\mathbb{N}\) gedefinieerd door \(x\sim y\) dan en slechts dan als \(x-y\) is een drievoud. Dan zijn er 3 equivalentieklassen: \(E_0=\{0,3,6,\ldots\}\), \(E_1=\{1,4,7,\ldots\}\) en \(E_2=\{2,5,8,\ldots\}\).

Stel dat \(\sim\) een equivalentierelatie is op een niet-lege verzameling is \(X\) is. Voor iedere \(x,y\in X\) waarvoor \(E_x\cap E_y\neq \emptyset\) geldt dat \(E_x=E_y\). Een direct gevolg is dat

Stel \(z\in E_x\), d.w.z. \(x\sim z\). Omdat \(E_x\cap E_y=\neq \emptyset\) bestaat er een \(w\in E_x\cap E_y\). Omdat \(w\in E_x\) geldt \(x\sim w\). Omdat ook \(w\in E_y\) geldt \(y\sim w\). Omdat een equivalentierelatie symmetrisch is, geldt dan ook \(w\sim x\) en \(w\sim y\). Omdat een equivalentierelatie transitief is, volgt uit \(y\sim w\), \(w\sim x\) en \(x\sim z\) dat \(y\sim z\) en dus \(z\in E_y\). Conclusie: \(E_x\subset Y_y\). Op dezelfde manier kunnen we aantonen dat \(E_y\subset E_x\). Daarom \(E_x=E_y\).

Partitie van een niet-lege verzameling

Partitie

Een partitie van een niet-lege verzameling \(X\) is een verzameling \(\mathcal{A}\) van deelverzamelingen van \(X\) die aan de volgende drie voorwaarden voldoet:

iedere verzameling \(A\in \mathcal{A}\) is niet leeg;
\(\cup_{A\in \mathcal{A}}A = X\);
Voor alle \(A,B\in\mathcal{A}\): als \(A\cap B\neq \emptyset\), dan \(A=B\).

Voorbeelden

\(\mathcal{A}=\bigl\{\mathbb{Z}^{-},\{0\},\mathbb{Z}^{+}\bigr\}\) is een partitie van \(\mathbb{Z}\).

M.b.v. intervalnotatie:
\(\mathcal{A}=\bigl\{[n,n+1) \mid n\in \mathbb{Z}\bigr\}\) is een partitie van \(\mathbb{R}\).

Quotiëntverzameling van een equivalentierelatie Stel dat \(\sim\) een equivalentierelatie op een niet-lege verzameling \(X\) is. Dan is de geïndexeerde verzameling \(\{E_x\mid x\in X\}\) een partitie van \(X\). Dit heet ook wel de quotiëntverzameling \(X/\!\sim\) van \(X\) m.b.t. \(\sim\).

Omgekeerd, als \(\mathcal{A}\) een partitie van een niet-lege verzameling \(X\) en we voor \(x,y\in X\) definiëren \(x\sim y\) dan en slechts dan als \(x,y\in A\) voor een zekere \(A\in \mathcal{A}\), dan is \(\sim\) een equivalentierelatie op \(X\).

Het bewijs komt er op neer dat je de drie eigenschappen van een partitie nagaat.

Omdat een equivalentie relatie reflexief is, geldt voor iedere \(x\in X\) dat \(x\sim x\) en dus dat \(E_x\neq \emptyset\).
Stel \(x\in X\), dan \(x\in E_x\). Hieruit volgt: \(X\subset\cup_{y\in X}E_y\). De omgekeerde inclusie \(\cup_{y\in X}E_y\subset X\) volgt uit het feit dat \(E_y\subset X\) voor iedere \(y\in X\). Dus: \(X=\cup_{y\in X}E_y\).
Stel \(x,y\in X\) zodanig dat \(E_x\cap E_y\neq \emptyset\), dan \(E_x=E_y\) omdat volgens bovenstaande stelling \(\{E_x\mid x\in X\}\) een partitie van \(X\) is.

Voorbeeld 1 Op \(X=\{1,2,3,4\}\) definiëren we de equivalentierelatie \(\sim\) door \[1\sim 1,\quad 2\sim 2,\quad 3\sim 3,\quad 4\sim 4,\quad 1\sim 3,\quad 3\sim 1\text.\] Dan hebben we de volgende equivalentieklassen \[[1] = \{1,3\},\quad [2] = \{2\},\quad [3] = \{1,3\},\quad [4] = \{4\}\text.\] Merk op dat \([1] = [3]\).

\(X/\!\sim\; = \bigl\{[1], [2], [4]\bigr\}\) is een partitie van \(X\) en dit is dus de quotiëntverzameling \(X/\!\sim\).
We hadden ook \(\bigl\{[2], [3], [4]\bigr\}\) kunnen gebruiken; dat maakt niets uit.

Voorbeeld 2 Op \(\mathbb{Z}\) definiëren we de equivalentierelatie door \[m\sim n\text{ dan en slechts dan als }m-n\text{ deelbaar is door }3\text.\] Dan hebben we de volgende equivalentieklassen \[\begin{aligned}\; [0] &= \{\ldots, -6, -3, 0, 3, 6, \ldots\},\\[0.25cm] [1] &= \{\ldots, -5, -2, 1, 4, 7, \ldots\},\\[0.25cm] [2] &= \{\ldots, -4, -1, 2, 5, 7, \ldots\}\end{aligned}\] \(\mathbb{Z}/\!\sim\;= \bigl\{[0], [1], [2]\bigr\}\) is een partitie van \(\mathbb{Z}\) en dit is dus de quotiëntverzameling \(\mathbb{Z}/\!\sim\).
In de wiskunde wordt deze verzameling meestal aangeduid met \(\mathbb{Z}_3\).