Logika i teoria mnogości/Algebra zbiorów

Podstawowe wiadomości

Jeśli a jest elementem zbioru $A$, zapisujemy to $a\in A$.

Zamiast $\mathrm{\neg }a\in A$, w skrócie zapisujemy $a\notin A$.

$a,b,...,f\in A$ jest skrótem zapisu $a\in A\wedge b\in A\wedge ...\wedge f\in A$.

Zbiory definiuje się poprzez określenie ich elementów. Z aksjomatu jednoznaczności wynika, że jeśli dwa zbiory mają te same elementy, to są identyczne. Elementy zbioru można określić przez ich wyliczenie, w ten sposób $\{a,b,c,d\}$ to zbiór zawierający jedynie a, b, c i d. Zbiór można również zdefiniować za pomocą warunku, który muszą spełniać jego elementy. Mając więc jakiś warunek (własność) $\mathrm{\Phi }$ np. podzielność przez 7 można zdefiniować zbiór $A$ w następujący sposób :

$x\in A\iff \mathrm{\Phi }(x)$

Tak zdefiniowany zbiór $A$ można zapisać również :

$A=\{x:\mathrm{\Phi }(x)\}$ (co czytamy "zbiór $A$ to zbiór takich x, że spełniony jest warunek $\mathrm{\Phi }(x)$")

Zbiór elementów x należących do zbioru $B$ i spełniających warunek $\mathrm{\Phi }$ oznaczamy przez

$\{x\in B:\mathrm{\Phi }(x)\}$

Rodziny zbiorów

Zbiory również mogą być elementami innych zbiorów. Nazywa się je rodzinami zbiorów.

Przyjmuje się, że nie istnieje taka rodzina zbiorów $\{A_n:n\in \mathbb{N}\}$, że $A_{n+1}\in A_n$, skąd w szczególności wynika $\mathrm{\neg }(A\in A)$.

Inkluzja

Piszemy $A\subset B$, jeśli każdy element zbioru A jest też elementem zbioru B, tzn. :

$A\subset B\iff \mathrm{\forall }x(x\in A⟹x\in B)$

Mówimy wtedy, że zbiór A jest podzbiorem zbioru B. Jeśli ponadto $A=B$, to A jest podzbiorem właściwym zbioru B. Relacja $A\subset B$ nazywana jest inkluzją. Ma ona następujące własności:

• $A\subset A$
• $A\subset B\wedge B\subset C⟹A\subset C$
• $A\subset B\wedge B\subset A⟹A=B$

Działania na zbiorach

Ze zbiorów A i B możemy utworzyć nowe zbiory:

• sumę : $A\cup B$
• iloczyn : $A\cap B$
• różnicę :$A\mathrm{\setminus }B$

Określa się je w następujący sposób:

• $x\in A\cup B\iff x\in A\vee x\in B$
• $x\in A\cap B\iff x\in A\wedge x\in B$
• $x\in A\mathrm{\setminus }B\iff x\in A\wedge x\notin B$

Ponadto zbiory są rozłączne, jeśli $A\cap B=\mathrm{\varnothing }$.

Jeżeli wszystkie zbiory są podzbiorami pewnego zbioru, to zbiór ten nazywamy przestrzenią i oznaczamy przez $X$.

Dopełnieniem zbioru A nazywamy $X\mathrm{\setminus }A$, co można zapisać przez $\mathrm{\setminus }A$ lub $A^{\prime }$ lub $A^c$.

Różnicą symetryczną określamy $A\dot{-}B=(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A)$

Para uporządkowana. Uporządkowane krotki

Przez parę uporządkowaną rozumiemy $(a,b)$, która spełnia pewną szczególną własność :

$(a,b)=(c,d)\iff (a=c)\wedge (b=d)$

Konstrukcję za pomocą zbiorów obiektu o takiej własności podał polski matematyk Kazimierz Kuratowski. Wygląda ona następująco :

$\{\{a\},\{a,b\}\}$

Uporzadkowaną trójką nazywamy zbiór $((a,b),c)$.

Uporządkowaną n-tką (krotką) $(a_1,...,a_n)$ nazywamy zbiór $((...((a_1,a_2),a_3)...),a_n)$.

Iloczyn kartezjański

Iloczyn kartezjański $A\times B$ definiujemy następująco :

$A\times B=\{(a,b):a\in A\wedge b\in B\}$