Zasada abstrakcji

Zasada abstrakcji, zasada identyfikacji elementów równoważnych – 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 niepustym zbiorem i $ℛ$ jest relacją równoważności w tym zbiorze, to rodzina podzbiorów $\mathrm{\Pi }=\{A_x:x\in A\}$ określona następująco

$A_x=\{y\in A:yℛx\}$

jest rozbiciem zbioru $A$, czyli ustala podział zbioru $A$ na niepuste i rozłączne podzbiory.

Zbiory należące do rodziny $\mathrm{\Pi }$ nazywane są klasami abstrakcji relacji $ℛ$.

Dowód

Ponieważ relacja równoważności $ℛ$ jest zwrotna, dla każdego $x\in A$ zachodzi $x\in A_x.$ Stąd każdy element zbioru $A$ należy do pewnego zbioru z rodziny $\mathrm{\Pi }$ i żaden z tych zbiorów nie jest pusty. Ponadto, jeśli pewne dwa zbiory $A_x$ i $A_y$ nie są rozłączne, to istnieje $z\in A_x\cap A_y,$ które spełnia $xℛz\wedge zℛy.$ Wtedy z przechodniości relacji $ℛ$ wynika, że $xℛy,$ czyli dla każdego $z$ takiego, że $zℛx$ zachodzi również $zℛy$ (z przechodniości). Wobec tego $A_x\subseteq A_y.$ Analogicznie można wykazać, że $A_y\subseteq A_x,$ zatem $A_x=A_y.$

Twierdzenie odwrotne

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

$xℛy⟺{\mathrm{\exists }}_{t\in A}x,y\in A_t$

jest relacją równoważności.

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ℛx.$

Jeśli $x,y\in A,$ to $xℛy\Rightarrow yℛx.$ Wynika to z oczywistej implikacji: $x,y\in A_t\Rightarrow y,x\in A_t.$

Niech $xℛy\wedge yℛ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\ne \mathrm{\varnothing },$ ponieważ $y\in A_i\cap A_j,$ skąd $A_i=A_j,$ a więc $xℛz$.

Zastosowania

Z zasady abstrakcji często korzysta się w matematyce wtedy, gdy występuje potrzeba zdefiniowania nowych typów obiektów.

Konstrukcja liczb całkowitych

W zbiorze $\mathbb{N}\times \mathbb{N}$ można wprowadzić taką relację równoważności $\approx ,$ że Szablon:Wzór Łatwo sprawdzić, że tak zdefiniowana relacja jest zwrotna i symetryczna. Ponadto jest ona przechodnia, ponieważ z równości Szablon:Wzór wynika $(a+d)+(c+f)=(c+b)+(e+d),$ co daje $a+f=e+b,$ czyli $(a,b)\approx (e,f).$

Na mocy zasady abstrakcji relacja $\approx$ dzieli zbiór $\mathbb{N}\times \mathbb{N}$ na niepuste i rozłączne zbiory nazywane klasami abstrakcji. Zbiór liczb całkowitych $\mathbb{Z}$ można zdefiniować jako zbiór tych właśnie klas abstrakcji. Klasa abstrakcji, do której należą $(0,0)$, $(1,1)$, $(2,2)$ etc. wyznacza liczbę całkowitą $0.$ Klasy, do których należą pary $(n,n+k)$ dla $n,k\in \mathbb{N}$ i $k>0$ wyznaczają liczby ujemne $-k.$

Na tak określonych klasach abstrakcji określa się działania Szablon:Wzór i dowodzi się, że ich wyniki nie zależą od wyboru reprezentantów klas abstrakcji oraz, że tak określone działania mają odpowiednie własności.