youproof.orgDeep Math. Human Access.

Bizonyítás

Az ekvivalenciareláció definíciója alapján azt kell igazolnunk, hogy a ∼\sim reláció reflexív, szimmetrikus és tranzitív.

A reflexivitás nyilván teljesül, hiszen tetszőleges (a;b)(a;b) számpár esetén (a;b)∼(a;b)(a;b)\sim (a;b). Ez ugyanis a 13.2. Tétel miatt épp azt jelenti, hogy a+b=b+aa+b=b+a, amely az összeadás műveletének kommutativitása miatt (11.8. Tétel) természetesen igaz.

A szimmetria is nyilván teljesül. Tegyük fel ugyanis, hogy tetszőleges (a;b)(a;b) és (c;d)(c;d) számpárok esetén (a;b)∼(c;d)(a;b)\sim (c;d). Ez a 13.2. Tétel miatt azt jelenti, hogy a+d=b+ca+d=b+c. A kommutativitás miatt természetesen ekkor c+b=d+ac+b=d+a is igaz. Ez viszont ismét a 13.2. Tétel miatt épp azt jelenti, hogy (c;d)∼(a;b)(c;d)\sim (a;b).

Végül a tranzitivitás is könnyen adódik. Tegyük fel ugyanis, hogy valamely (a;b)(a;b), (c;d)(c;d) és (e;f)(e;f) számpárokra (a;b)∼(c;d)(a;b)\sim (c;d) valamint (c;d)∼(e;f)(c;d)\sim (e;f) is teljesül. Ebből a 13.2. Tétel alapján az alábbi két egyenletet írhatjuk fel:

a+d=b+cc+f=d+e\begin{aligned}a+d&=b+c \\ c+f&=d+e \end{aligned}

Adjuk össze a két egyenletet:

a+d+c+f=b+c+d+ea+d+c+f=b+c+d+e

Ám ekkor a 12.18. Lemma miatt az egyenlet mindkét oldalát (c+d)(c+d)-vel egyszerűsíthetjük:

a+f=b+ea+f=b+e

Ez viszont a 13.2. Tétel szerint épp azt jelenti, hogy (a;b)∼(e;f)(a;b)\sim (e;f). A ∼\sim tehát valóban egy ekvivalenciareláció az N×N\N\times \N halmaz felett.

∎