Logika i teoria mnogości/Algebra zbiorów

Podstawowe wiadomości

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

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

$a,b,...,f\in A$ jest skrótem zapisu $a\in A\land b\in A\land ...\land 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ść) $\Phi$ np. podzielność przez 7 można zdefiniować zbiór $A$ w następujący sposób :

$x\in A\Leftrightarrow \Phi (x)$

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

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

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

$\{x\in B:\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 $\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\Leftrightarrow \forall x~(x\in A\implies x\in B)$

Mówimy wtedy, że zbiór A jest podzbiorem zbioru B. Jeśli ponadto $A\not =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\land B\subset C\implies A\subset C$
• $A\subset B\land B\subset A\implies 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\backslash B$

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

• $x\in A\cup B\Leftrightarrow x\in A\lor x\in B$
• $x\in A\cap B\Leftrightarrow x\in A\land x\in B$
• $x\in A\backslash B\Leftrightarrow x\in A\land x\notin B$

Ponadto zbiory są rozłączne, jeśli $A\cap B=\emptyset$.

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

Dopełnieniem zbioru A nazywamy $X\backslash A$, co można zapisać przez $\backslash A$ lub $A'$ 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)\Leftrightarrow (a=c)\land (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\land b\in B\}$