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ą:

$\begin{array}{rl}A& =\{z\in {𝒫}(x)|\mathrm{\exists }wz=\{w\}\},\\ B& =\{z\in {𝒫}(x\cup y)|\mathrm{\exists }w\mathrm{\exists }v(w\ne v\wedge z=\{v,w\})\},\\ C& =\{z\in {𝒫}({𝒫}(y))|\mathrm{\exists }vz=\{\{v\}\}=(v,v)\}.\end{array}$

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

$\begin{array}{rl}{D}_0& =\{z\in {𝒫}(A\cup B)|\mathrm{\exists }w\mathrm{\exists }vw\ne v\wedge z=\{\{w\},\{w,v\}\}=(w,v)\},\end{array}$

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

$\begin{array}{rl}{D_0}^{\prime }& =\{z\in {𝒫}(D_0\cup C)|\mathrm{\exists }w\mathrm{\exists }vw\ne v\wedge z=\{(w,v),(v,v)\}\},\end{array}$

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

$\begin{array}{rl}{D_0}^{″}& =\{z\in {𝒫}(D_0\cup C)|\mathrm{\exists }w\mathrm{\exists }vw\ne v\wedge z=\{(w,v),(w,w)\}\},\end{array}$

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

$\begin{array}{rl}x\times y& =\{z\in \bigcup {D_0}^{\prime }|\mathrm{\exists }w\mathrm{\exists }vw\ne v\wedge z=(w,v)\}\cup \{z\in \bigcup {D_0}^{″}|\mathrm{\exists }wz=(w,w)\}.\end{array}$

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 }$.