Logika i teoria mnogości/Wykład 5.2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 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ęści 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ą:

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

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

gdzie mamy pewność, że jest elementem , a elementem oraz:

gdzie mamy pewność, że . Kończąc:

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ładzie 4 (patrz Wykład 4). Dla dowolnej formuły nieposiadają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 .