Logika i teoria mnogości/Wykład 5.2

Z Studia Informatyczne
< Logika i teoria mnogości
Wersja z dnia 14:26, 16 wrz 2006 autorstwa Kubakozik (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 i istnieje zbiór zawierający wszystkie pary postaci gdzie i .

Dowód

Ustalmy dwa dowolne zbiory i . Jeśli lub to istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku jest zbiorem jednoelementowym to istnieje na podstawie aksjomatu pary. W dalszej częsci dowodu zakładamy że zbiory i są niepuste i że 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 jest elementem . 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 jest elementem , a elementem , 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 . 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 i są zbiorami i to zbiorem jest również ogół takich, że istnieje spełniające . Zbiór takich oznaczamy przez i nazywamy projekcją na pierwszą współrzędną.

Dowód

Zbiór istnieje na podstawie aksjomatów ZF i jest równy:

W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykład. AKS Dla dowolnej formuły nie posiadającej zmiennych wolnych innych niż i następująca formuła jest prawdą

Aby dowieść tą własność ustalmy dowolną formułę i dowolny zbiór . Stosujemy aksjomat wyróżniania do  (który istnieje na mocy Twierdzenia 5.1 (patrz twierdzenie 5.1.) i do formuły

otrzymując zbiór . Wymagany zbiór istnieje na mocy Twierdzenia 5.2 (patrz twierdzenie 5.2.) i jest równy .

Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji z iloczynu kartezjańskiego. Aby otrzymać stosujemy powyższe twierdzenie do , i wyrażenia mówiącego .