Logika i teoria mnogości/Wykład 5.2

Iloczyn kartezjański i podobne konstrukcje

Dla zainteresowanych

W definicji iloczynu kartezjańskiego (patrz Definicja 2.1) jest pewna nieścisłość. Konstrukcja iloczynu kartezjańskiego odwołuje się do aksjomatu wyróżniania w wersji nieuprawomocnionej. Konstrukcja, którą zobaczą państwo w tym rozdziale, usuwa tę poprzednią niedogodność.

Twierdzenie 5.1.

Dla dowolnych dwóch zbiorów $x$ i $y$ istnieje zbiór $x\times y$ zawierający wszystkie pary postaci $(w,z)$, gdzie $w\in x$ i $z\in y$. Dowód

Ustalmy dwa dowolne zbiory $x$ i $y$. Jeśli $x=\mathrm{\varnothing }$ lub $y=\mathrm{\varnothing }$, to $x\times y=\mathrm{\varnothing }$ istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku $x\cup y$ jest zbiorem jednoelementowym $\{z\}$, to $x\times y=\{\{\{z\}\}\}$ istnieje na podstawie aksjomatu pary. W dalszej części dowodu zakładamy, że zbiory $x$ i $y$ są niepuste i że $x\cup y$ ma więcej niż jeden element. Na podstawie aksjomatu zbioru potęgowego, aksjomatu unii i aksjomatu wycinania następujące zbiory istnieją:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned A &=\{z\in\mathcal{P}(x)\,|\, \exists w\; z =\{w\}\}, \\ B &=\{z\in\mathcal{P}(x\cup y)\,|\, \exists w \exists v\; (w \neq v \land z=\{v,w\})\},\\ C &=\{z\in\mathcal{P}(\mathcal{P}(y))\,|\, \exists v\; z=\{\{v\}\}=(v,v)\}. \end{align}}

Nasze założenia gwarantują, że żaden z powyższych zbiorów nie jest pusty. Kontynuując, możemy stworzyć:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0 &=\{z\in\mathcal{P}(A\cup B)\,|\, \exists w \exists v\; w\neq v \land z=\{\{w\},\{w,v\}\}=(w,v)\}, \end{align}}

w którym to zbiorze mamy pewność, że $w$ jest elementem $x$. Kontynuujemy, definiując:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0' &=\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(v,v)\}\}, \end{align}}

gdzie mamy pewność, że $w$ jest elementem $x$, a $v$ elementem $y$ oraz:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0'' &=\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(w,w )\}\}, \end{align}}

gdzie mamy pewność, że $w\in A\cap B$. Kończąc:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x\times y &=\{z\in\bigcup D_0' \,|\, \exists w \exists v\; w\neq v \land z=(w,v)\}\cup \{z\in\bigcup D_0'' \,|\, \exists w\; z=(w,w)\}. \end{align}}

Twierdzenie 5.2.

Jeśli $x,y$ i $z$ są zbiorami i $z\subseteq x\times y$, to zbiorem jest również ogół $v$ takich, że istnieje $w$ spełniające $(v,w)\in z$. Zbiór takich $v$ oznaczamy przez ${\pi }_1(z)$ i nazywamy projekcją na pierwszą współrzędną.

Dowód

Zbiór ${\pi }_1(z)$ istnieje na podstawie aksjomatów ZF i jest równy:

${\pi }_1(z)=\bigcup \{w\in \bigcup z|\mathrm{\exists }uw=\{u\}\}.$

W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykładzie 4 (patrz Wykład 4). Dla dowolnej formuły ${\phi }^{\prime }$ nieposiadającej zmiennych wolnych innych niż $z^{\prime }$ i ${x_1}^{\prime }$, następująca formuła jest prawdą:

$\mathrm{\forall }{x_1}^{\prime }\mathrm{\forall }{x}^{\prime }\mathrm{\exists }{y}^{\prime }\mathrm{\forall }{z}^{\prime }{z}^{\prime }\in y^{\prime }⟺(z^{\prime }\in x^{\prime }\wedge {\phi }^{\prime }).$

Aby dowieść tę własność, ustalmy dowolną formułę ${\phi }^{\prime }$ i dowolny zbiór ${x_1}^{\prime }$. Stosujemy aksjomat wyróżniania do $x=x\times \{{x_1}^{\prime }\}$ (który istnieje na mocy Twierdzenia 5.1 (patrz twierdzenie 5.1.) i do formuły

$\mathrm{\exists }{z}^{\prime }\mathrm{\exists }{x_1}^{\prime }z=(z^{\prime },{x_1}^{\prime })\wedge {\phi }^{\prime },$

otrzymując zbiór $y$. Wymagany zbiór $y^{\prime }$ istnieje na mocy Twierdzenia 5.2 (patrz twierdzenie 5.2.) i jest równy ${\pi }_1(y)$.

Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji z iloczynu kartezjańskiego. Aby otrzymać ${\pi }_2(z)$, stosujemy powyższe twierdzenie do ${x_1}^{\prime }=z$, $x=\bigcup \bigcup z$ i wyrażenia ${\phi }^{\prime }$ mówiącego $\mathrm{\exists }w(w,z^{\prime })\in {x_1}^{\prime }$.