Zasada abstrakcji

Zasada abstrakcji – twierdzenie matematyczne mówiące, że dowolnemu rozbiciu zbioru odpowiada pewna relacja równoważności, a każda relacja równoważności ustanawia pewne rozbicie zbioru.

Twierdzenie

Jeśli $A$ jest zbiorem niepustym i ${\mathcal {R}}$ jest relacją równoważnościową na tym zbiorze, to rodzina podzbiorów $\Pi =\{A_{x}:x\in A\}$ określona następująco:

$A_{x}=\{y\in A:y{\mathcal {R}}x\}$

jest rozbiciem zbioru $A$.

Twierdzenie to nazywane jest zasadą abstrakcji, a zbiory rodziny $\Pi$ klasami abstrakcji relacji ${\mathcal {R}}$.

Dowód

Ponieważ $\forall _{x\in A}x{\mathcal {R}}x,$ więc każdy element zbioru $A$ należy do pewnego zbioru rodziny $\Pi$ i żaden z tych zbiorów nie jest pusty. Jeśli $A_{x}\cap A_{y}\neq \emptyset ,$ to istnieje $z\in A_{x}\cap A_{y},$ skąd $x{\mathcal {R}}z\wedge z{\mathcal {R}}y.$ Zatem $x{\mathcal {R}}y,$ czyli $A_{x}=A_{y}$.

Twierdzenie odwrotne

Jeśli $A$ jest zbiorem niepustym i $\Pi =\{A_{x}:x\in A\}$ jest jego rozbiciem, to relacja ${\mathcal {R}}$ określona w zbiorze $A$ wzorem:

$x{\mathcal {R}}y\Leftrightarrow \exists _{t\in T}x,y\in A_{t}$

jest równoważnościowa.

Dowód

Jeśli $x\in A,$ to ponieważ $A=\bigcup _{t\in T},$ to dla pewnego $t$ $x\in A_{t},$ a stąd wynika, że $x{\mathcal {R}}x.$

Jeśli $x,y\in A,$ to $x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x.$ Wynika to z oczywistej implikacji: $x,y\in A_{t}\Rightarrow y,x\in A_{t}.$

Niech $x{\mathcal {R}}y\wedge y{\mathcal {R}}z.$ Istnieją $i,j\in T,$ dla których $x,y\in A_{i}\wedge y,z\in A_{j}.$ Jednak w tym wypadku $A_{i}\cap A_{j}\neq \emptyset ,$ ponieważ $y\in A_{i}\cap A_{j},$ skąd $A_{i}=A_{j},$ a więc $x{\mathcal {R}}z$.