Logika i teoria mnogości/Wykład 5.2

Iloczyn kartezjański i podobne konstrukcje

Dla zainteresowanych

W definicji 2.1 zaprezentowanej w rozdziale 2 (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 $\displaystyle x$ i $\displaystyle y$ istnieje zbiór $\displaystyle x\times y$ zawierający wszystkie pary postaci $\displaystyle (w,z)$ gdzie $\displaystyle w\in x$ i $\displaystyle z\in y$.

Dowód

Ustalmy dwa dowolne zbiory $\displaystyle x$ i $\displaystyle y$. Jeśli $\displaystyle x=\emptyset$ lub $\displaystyle y=\emptyset$ to $\displaystyle x\times y=\emptyset$ istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku $\displaystyle x\cup y$ jest zbiorem jednoelementowym $\displaystyle \{z\}$ to $\displaystyle x\times y=\{\{\{z\}\}\}$ istnieje na podstawie aksjomatu pary. W dalszej częsci dowodu zakładamy że zbiory $\displaystyle x$ i $\displaystyle y$ są niepuste i że $\displaystyle 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)\}. \endaligned}

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)\}, \endaligned}

w którym to zbiorze mamy pewność, że $\displaystyle w$ jest elementem $\displaystyle 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)\}\}, \endaligned}

gdzie mamy pewność, że $\displaystyle w$ jest elementem $\displaystyle x$, a $\displaystyle v$ elementem $\displaystyle 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 )\}\}, \endaligned}

gdzie mamy pewność, że $\displaystyle 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)\}. \endaligned}

Twierdzenie 5.2.

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

Dowód

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

$\displaystyle \pi _{1}(z)=\bigcup \{w\in \bigcup z\,|\,\exists u\;w=\{u\}\}.$

W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykład. AKS Dla dowolnej formuły $\displaystyle \varphi '$ nie posiadającej zmiennych wolnych innych niż $\displaystyle z'$ i $\displaystyle x_{1}'$ następująca formuła jest prawdą

$\displaystyle \forall x_{1}'\forall x'\exists y'\forall z'\;z'\in y'\iff (z'\in x'\land \varphi ').$

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

$\displaystyle \exists z'\exists x_{1}'\;z=(z',x_{1}')\land \varphi '$

otrzymując zbiór $\displaystyle y$. Wymagany zbiór $\displaystyle y'$ istnieje na mocy Twierdzenia 5.2 (patrz twierdzenie 5.2.) i jest równy $\displaystyle \pi _{1}(y)$.

Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji z iloczynu kartezjańskiego. Aby otrzymać $\displaystyle \pi _{2}(z)$ stosujemy powyższe twierdzenie do $\displaystyle x_{1}'=z$, $\displaystyle x=\bigcup \bigcup {z}$ i wyrażenia $\displaystyle \varphi '$ mówiącego $\displaystyle \exists w\;(w,z')\in x_{1}'$.