Bizonyítás

A 19.2. Definíció utáni megjegyzés 3. és 5. pontjai alapján a $\sube$ reláció reflexív és antiszimmetrikus. Így már csak azt kell megmutatni, hogy teljesül a tranzitivitás is, azaz $\mathcal{S}$ tetszőleges $A$, $B$ és $C$ elemei esetén ha $A\sube B$ és $B\sube C$, akkor $A\sube C$. Ez viszont könnyedén adódik a részhalmaz definíciójából.

Legyen ugyanis $x$ egy tetszőleges elem az $S$ alaphalmazban. Mivel $A\sube B$, ezért ha $x\in A$ teljesül, akkor $x\in B$ is teljesül. Ugyanakkor $B\sube C$ is igaz, ezért egyúttal $x\in C$ is teljesül. Mivel azt kaptuk, hogy $x\in A$-ból következik $x\in C$, ezért valóban $A\sube C$.

Most térjünk át a $\sub$ relációra vonatkozó állításokra. Ez nyilvánvalóan nem reflexív, ugyanis $A\sub A$ a 19.2. Definíció alapján azt jelentené, hogy $A\sube A$ és $A\neq A$. Ez utóbbi nyilván lehetetlen, mivel minden halmaz azonos önmagával. De antiszimmetrikus sem lehet, máskülönben a 12.11. Definíció miatt $A\sub B$ és $B\sub A$ esetén $A=B$ következne. Ez ugye lehetetlen, mert például $A\sub B$ azt jelenti, hogy $A\sube B$ és $A\neq B$.

Végül megmutatjuk, hogy $\sub$ tranzitív. Tegyük fel, hogy $A\sub B$ és $B\sub C$. Ezek a feltételek a 19.2. Definíció alapján azt jelentik, hogy egyrészt $A\sube B$ és $B\sube C$, másrészt pedig $A\neq B$ és $B\neq C$. Az első két feltételből a $\sube$ reláció már bizonyított tranzitivitása miatt $A\sube C$ következik, tehát a $\sub$ reláció tranzitivitásához elegendő azt megmutatni, hogy $A\neq C$.

A $B\sube C$ tartalmazás miatt egyrészt tudjuk, hogy $B$ minden eleme $C$-nek is eleme. Másrészt $B\neq C$ miatt azt is tudjuk, hogy $C$-nek van olyan $x$ eleme, ami viszont nem eleme $B$-nek, azaz $x\notin B$. Azt kell igazolni, hogy $x\notin A$ is igaz. Ez viszont nyilvánvaló, máskülönben $A\sube B$ miatt $x\in B$ mégiscsak teljesülne, ami ellentmondás. A $\sub$-val jelölt szigorú tartalmazási reláció tehát valóban tranzitív.

∎