Oczywiste fakty

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 630
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Oczywiste fakty

Post autor: Jakub Gurak » 22 maja 2019, o 05:35

Chciałbym tu zaprezentować parę dowodów teoriomnogościowych faktów "oczywistych".

Przypominam definicje dodawania liczb naturalnych:

\(\displaystyle{ 0+ n=n,}\) dla dowolnej liczby naturalnej \(\displaystyle{ n}\), oraz

\(\displaystyle{ n'+m=\left( n+m\right)'}\) dla dowolnych naturalnych n i m.

W aksjomatycznym podejściu do teorii mnogości wszystkie "oczywiste" fakty odnośnie liczb naturalnych należy dowieść z aksjomatów. Tak więc o dodawaniu liczb naturalnych wiemy na razie tylko tyle ile mówi powyższa definicja- resztę trzeba dowieść.

Jeśli suma dwóch liczb naturalnych jest równa \(\displaystyle{ 0=\emptyset}\), to obydwie muszą być równe \(\displaystyle{ 0}\).

Dowód:

Niech dla liczb naturalnych \(\displaystyle{ n,m}\) zachodzi \(\displaystyle{ n+m=0.}\) Jeśli \(\displaystyle{ n}\) jest następnikiem pewnej liczby naturalnej, to \(\displaystyle{ n= k'}\) dla pewnego naturalnego \(\displaystyle{ k}\), wtedy podstawiając pod sumę \(\displaystyle{ k'+m=0,}\) a \(\displaystyle{ k'+m}\) to jest równe na mocy definicji dodawania \(\displaystyle{ \left( k+ m\right)',}\) więc jako następnik sumy liczb naturalnych, czyli następnik liczby naturalnej jest to różne od \(\displaystyle{ 0}\), sprzeczność. Doprowadziło do tego założenie, że \(\displaystyle{ n}\) jest następnikiem pewnej liczby naturalnej. Wobec czego \(\displaystyle{ n}\) nie jest następnikiem żadnej liczby naturalnej. Ale mamy twierdzenie, że każda liczba naturalna jest zerem (zbiorem pustym ) lub następnikiem liczby naturalnej(chyba w moim Kompendium jest dowód, w rozdziale liczby naturalne). Wobec czego pozostaje tylko możliwość \(\displaystyle{ n=0}\), więc podstawiając za \(\displaystyle{ n+ m=0,}\) otrzymujemy \(\displaystyle{ 0+m=0}\), a \(\displaystyle{ 0+m}\) jest równe- na mocy definicji dodawania- \(\displaystyle{ m}\), czyli \(\displaystyle{ m=0}\) i \(\displaystyle{ n=0}\), co kończy dowód.\(\displaystyle{ \square}\)

Natomiast dowód przemienności dodawania składa się z kilku części:

Najpierw dowodzimy, że \(\displaystyle{ n+0=n}\) dla dowolnego \(\displaystyle{ n}\) naturalnego (indukcyjnie), mając to potem uzasadniamy, że dla dowolnych \(\displaystyle{ n,m}\) naturalnych \(\displaystyle{ n'+m=n+ m'}\) (indukcyjnie), i w końcu mając te dwa fakty uzasadniamy przemienność dodawania.

Definicja mnożenia:

\(\displaystyle{ 0 \cdot m=0,}\) oraz
\(\displaystyle{ n' \cdot m= \left( n \cdot m\right)+m.}\)

Dowodzi się, że dla dowolnego \(\displaystyle{ n}\) naturalnego \(\displaystyle{ n \cdot 1=n}\), oraz, że dla dowolnego \(\displaystyle{ n}\) naturalnego \(\displaystyle{ n \cdot 0=0}\), że mnożenie jest przemienne(również aby to udowodnić potrzebujemy paru faktów). A też sam dostrzegłem, że jeśli nie chcemy korzystać z przemienności dodawania(bo jego dowód składa się z kilku części), to nie jest oczywistym nawet, że \(\displaystyle{ n+1=n'.}\)

Niech \(\displaystyle{ x,y}\) będą zbiorami.

Definiujemy \(\displaystyle{ x \cup y= \bigcup\left\{ x,y\right\}.}\)

Suma ta, ma tą samą własność co suma naiwna- dowolny element występuję w sumie dwóch zbiorów, gdy występuję w którymś z nich, \(\displaystyle{ z \in x \cup y \Longleftrightarrow z \in x \vee z \in y.}\)

Przypominam dla dwóch rodzin zbiorów \(\displaystyle{ x,y}\): jeśli \(\displaystyle{ x \subset y}\) to \(\displaystyle{ \bigcup x \subset \bigcup y}\) (można chyba poczytać nieco więcej o tym w moim Kompendium, w drugim rozdziale Aksjomaty).

Oraz dla dowolnego zbioru \(\displaystyle{ x}\) mamy \(\displaystyle{ \bigcup\left\{ x\right\}=x.}\)

Wykażemy, w sposób zabawny, podstawowe własności sumy dwóch zbiorów.

Dla dowolnych zbiorów \(\displaystyle{ x,y}\) mamy:

1.\(\displaystyle{ x \cup y= y \cup x.}\)
2. \(\displaystyle{ x \subset x \cup y.}\)
3.\(\displaystyle{ y \subset x \cup y.}\)
4.\(\displaystyle{ x \cup x=x.}\)

Dowód:

1.Mamy \(\displaystyle{ \left\{ x,y\right\}=\left\{ y,x\right\},}\) a więc \(\displaystyle{ \bigcup\left\{ x,y\right\}= \bigcup\left\{ y,x\right\}}\), czyli \(\displaystyle{ x \cup y=y \cup x.}\)
2. Ponieważ \(\displaystyle{ \left\{ x\right\} \subset \left\{ x,y\right\},}\) więc również \(\displaystyle{ \bigcup\left\{ x\right\} \subset \bigcup\left\{ x,y\right\},}\) ponieważ \(\displaystyle{ \bigcup \left\{ x\right\}= x,}\) a więc \(\displaystyle{ x= \bigcup\left\{ x\right\} \subset \bigcup\left\{ x,y\right\}=x \cup y,}\) a więc \(\displaystyle{ x \subset x \cup y.}\)
3. Na podstawie poprzedniego punktu \(\displaystyle{ y \subset y \cup x}\), i na podstawie pierwszego punktu \(\displaystyle{ y \cup x= x \cup y,}\) a więc \(\displaystyle{ y \subset x \cup y.}\)
4.Mamy \(\displaystyle{ x= \bigcup\left\{ x\right\}.}\) Ponieważ \(\displaystyle{ \left\{ x\right\}=\left\{ x,x\right\},}\) więc \(\displaystyle{ \bigcup\left\{ x\right\} = \bigcup\left\{ x,x\right\}=x \cup x}\), więc \(\displaystyle{ x= x\cup x.}\)-- piątek, 24 maja 2019, 01:30 --Wczoraj, samodzielnie, ale za to w sposób analogiczny, w podobny sposób udowodniłem podobne fakty dla iloczynu dwóch zbiorów.

Przypominam, dla dwóch zbiorów \(\displaystyle{ x,y}\) definiujemy \(\displaystyle{ x\cap y= \bigcap\left\{ x,y\right\}.}\)

Iloczyn taki, ma to samo znaczenie, co używany iloczyn w naiwnej teorii mnogości, dowolny element należy do iloczynu dwóch zbiorów, gdy należy do obydwu zbiorów jednocześnie.

Przypominam, że dla dwóch rodzin zbiorów \(\displaystyle{ x,y,}\) jeśli \(\displaystyle{ \left\{ \right\} \neq x \subset y}\), to \(\displaystyle{ \bigcap x\supset \bigcap y,}\) czyli iloczyn większej rodziny zbiorów jest mniejszy (jeśli mniejsza rodzina nie jest pusta). Łatwo pokazać, że dla dowolnego zbioru \(\displaystyle{ x}\) mamy \(\displaystyle{ \bigcap \left\{ x\right\}=x.}\)

Możemy teraz, podobnie jak wcześniej, udowodnić, że:

Dla dowolnych zbiorów \(\displaystyle{ x,y}\) mamy:

\(\displaystyle{ 1. x\cap y=y\cap x.}\)
\(\displaystyle{ 2.x\supset x\cap y.}\)
\(\displaystyle{ 3. y\supset x\cap y.}\)
\(\displaystyle{ 4. x\cap x=x.}\)

Dowód:

1. Ponieważ \(\displaystyle{ \left\{ x,y\right\}=\left\{ y,x\right\}}\), więc również \(\displaystyle{ \bigcap\left\{ x,y\right\}= \bigcap \left\{ y,x\right\},}\) czyli \(\displaystyle{ x\cap y=y\cap x.}\)
2. Mamy \(\displaystyle{ \bigcap \left\{ x\right\}=x.}\) Ponieważ \(\displaystyle{ \left\{ \right\} \neq \left\{ x\right\} \subset \left\{ x,y\right\}}\), więc \(\displaystyle{ x=\bigcap \left\{ x\right\}\supset \bigcap \left\{ x,y\right\}=x \cap y,}\) a więc \(\displaystyle{ x\supset x\cap y.}\)
3. Na podstawie poprzedniego punktu \(\displaystyle{ y\supset y\cap x,}\) i na podstawie pierwszego punktu \(\displaystyle{ y\cap x=x\cap y,}\) a więc \(\displaystyle{ y\supset x\cap y.}\)
4.Mamy \(\displaystyle{ x= \bigcap \left\{ x\right\}.}\) Ponieważ \(\displaystyle{ \left\{ x\right\}=\left\{ x,x\right\}}\), więc \(\displaystyle{ \bigcap\left\{ x\right\}= \bigcap\left\{ x,x\right\}=x \cap x,}\) a więc \(\displaystyle{ x=x\cap x. \square}\)
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jakub Gurak
Użytkownik
Użytkownik
Posty: 630
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Oczywiste fakty

Post autor: Jakub Gurak » 24 lip 2019, o 01:47

Jeszcze dowód zasady minimum:

Przypominam, w konstrukcji von Neumanna liczb naturalnych definiujemy

\(\displaystyle{ n \le m \equiv n \subset m.}\) oraz
\(\displaystyle{ n<m\equiv n \in m.}\)

Na początku ustalmy zbiór \(\displaystyle{ X}\):

\(\displaystyle{ X=\{n\in\mathbb{N}\,:\, \bigwedge\limits_{x\subset\mathbb{N} \land x\cap n \neq \emptyset)} \bigcap x\in x\}.}\)

Zbiór \(\displaystyle{ X}\) jest zdefiniowany jako zbiór tych liczb naturalnych \(\displaystyle{ n}\), że dla dowolnego zbioru złożonego z liczb naturalnych \(\displaystyle{ x}\), jeśli \(\displaystyle{ x\cap n\neq \emptyset}\) (czyli zbiór \(\displaystyle{ x}\) ma liczbę naturalną silnie mniejszą od \(\displaystyle{ n}\)), to zbiór \(\displaystyle{ x}\) ma element najmniejszy(którym jest \(\displaystyle{ \bigcap x}\), bo \(\displaystyle{ \bigcap x \in x}\), czyli \(\displaystyle{ \bigcap x}\) jest w szczególności liczbą naturalną, i jest najmniejszą liczbą naturalną w \(\displaystyle{ x}\), bo ponieważ \(\displaystyle{ \bigcap x}\) zawiera się w każdym zbiorze rodziny \(\displaystyle{ x}\), czyli w każdym elemencie \(\displaystyle{ x}\), które są również liczbami naturalnymi, więc jest od nich mniejszy lub równy, czyli \(\displaystyle{ \bigcap x}\) jest najmniejszą liczbą naturalną w \(\displaystyle{ x}\)). Oczywiście, intuicyjnie, dla dowolnego \(\displaystyle{ n}\) naturalnego, dla dowolnego zbioru złożonego z liczb naturalnych \(\displaystyle{ x}\)- jest to prawda( albo \(\displaystyle{ m<n}\) jest najmniejszym elementem \(\displaystyle{ x}\), a jeśli nie to istnieje w \(\displaystyle{ x}\) liczba naturalna silnie mniejsza od \(\displaystyle{ m}\), która staje się kandydatem na najmniejszą liczbę naturalną w \(\displaystyle{ x}\), i tak ... po co najwyżej \(\displaystyle{ m}\) krokach dochodzimy do liczby naturalnej \(\displaystyle{ 0}\), która musi być najmniejsza w \(\displaystyle{ x}\) (konstrukcja może się skończyć wcześniej- to w najgorszym przypadku) ) Niemniej, to tylko intuicyjna obserwacja, formalnie wykazujemy indukcyjnie, że \(\displaystyle{ X=\mathbb{N}.}\)(dowód jest żmudny)

Aby dowieść twierdzenie, ustalmy dowolny niepusty zbiór \(\displaystyle{ z\subset\mathbb {N}}\). Pokażemy, że istnieje w nim liczba najmniejsza. Niewątpliwie istnieje \(\displaystyle{ n\in\mathbb{N}}\) takie, że \(\displaystyle{ n\in z}\)( skoro \(\displaystyle{ z}\) jest niepustym zbiorem liczb naturalnych, to ma w sobie przynajmniej jedną liczbę naturalną). Popatrzmy na \(\displaystyle{ n'}\)- następnik \(\displaystyle{ n}\). Ponieważ każda liczba naturalna należy do \(\displaystyle{ X}\), to również \(\displaystyle{ n' \in X}\). Zatem z definicji zbioru \(\displaystyle{ X}\), dla dowolnego zbioru \(\displaystyle{ x \subset \NN}\) jeśli zbiór \(\displaystyle{ x}\) ma liczbę naturalną silnie mniejszą od \(\displaystyle{ n'}\), to zbiór \(\displaystyle{ x}\) ma element najmniejszy, Zbiór \(\displaystyle{ z}\) ma w sobie liczbę naturalną \(\displaystyle{ n}\), która niewątpliwie jest silnie mniejsza od \(\displaystyle{ n'}\). Zatem, zgodnie z powyższym, zbiór \(\displaystyle{ z}\) ma element najmniejszy, co kończy dowód.\(\displaystyle{ \square}\)

Jakub Gurak
Użytkownik
Użytkownik
Posty: 630
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Re: Oczywiste fakty

Post autor: Jakub Gurak » 6 sty 2020, o 01:45

Jeszcze dowód zasady maksimum, tzn. chodzi o twierdzenie:

Jeśli \(\displaystyle{ \left\{ \right\} \neq x \subset \NN}\) jest niepustym zbiorem złożonym z liczb naturalnych ograniczonym z góry przez pewne \(\displaystyle{ n\in\NN}\), czyli przez liczbę naturalną większą lub równą od każdego elementu zbioru \(\displaystyle{ x}\), to zbiór \(\displaystyle{ x}\) posiada element największy.

Na początku ustalmy zbiór \(\displaystyle{ X}\):

\(\displaystyle{ X=\{n\in\mathbb{N}\,:\, \bigwedge\limits_{x\subset n \land x \neq \emptyset)} \bigcup x\in x\}.}\)

Zbiór \(\displaystyle{ X}\) jest zdefiniowany jako zbiór tych liczb naturalnych \(\displaystyle{ n}\), że dla dowolnego niepustego zbioru \(\displaystyle{ x}\) złożonego z liczb naturalnych silnie mniejszych od \(\displaystyle{ n}\), to zbiór \(\displaystyle{ x}\) ma element największy (którym jest \(\displaystyle{ \bigcup x}\), bo \(\displaystyle{ \bigcup x \in x}\), czyli \(\displaystyle{ \bigcup x}\) jest w szczególności liczbą naturalną, i jest największą liczbą naturalną w \(\displaystyle{ x}\), bo ponieważ \(\displaystyle{ \bigcup x}\) jest nadzbiorem każdego zbioru rodziny \(\displaystyle{ x}\), czyli każdego elementu \(\displaystyle{ x}\), które są również liczbami naturalnymi, więc jest od nich większy lub równy, czyli \(\displaystyle{ \bigcup x}\) jest największą liczbą naturalną w \(\displaystyle{ x}\)). Wykazujemy indukcyjnie, że \(\displaystyle{ X=\mathbb{N}.}\)

Niewątpliwie \(\displaystyle{ 0=\emptyset\in X}\), ponieważ \(\displaystyle{ \emptyset}\) nie posiada żadnych niepustych podzbiorów, a więc dla każdego niepustego podzbioru \(\displaystyle{ x \subset \emptyset}\) (a nie ma takich ), więc (możemy teraz powiedzieć co chcemy), więc \(\displaystyle{ \bigcup x\in x.}\)

Krok indukcyjny: Załóżmy, że \(\displaystyle{ n\in X}\), i dowiedźmy, że \(\displaystyle{ n'\in X.}\) W tym celu ustalmy dowolny niepusty zbiór \(\displaystyle{ x\subset n'. }\) Pokażemy, że \(\displaystyle{ \bigcup x\in x}\). Jeśli \(\displaystyle{ n\in x}\), to ponieważ \(\displaystyle{ x\subset n'}\), a pozostałe elementy zbioru \(\displaystyle{ n'}\) są podzbiorami zbioru \(\displaystyle{ n}\), więc otrzymujemy \(\displaystyle{ \bigcup x= \bigcup n'=n\in x.}\) Jeśli \(\displaystyle{ n\not\in x}\), to ponieważ \(\displaystyle{ x \subset n'=n \cup \left\{ n\right\}}\), więc \(\displaystyle{ x\subset n}\), i mamy \(\displaystyle{ x \neq \emptyset}\), więc na mocy założenia indukcyjnego otrzymujemy, że \(\displaystyle{ \bigcup x\in x}\). Krok indukcyjny został dowiedziony.

Na mocy zasady indukcji otrzymujemy, że \(\displaystyle{ X=\NN.}\)


Aby dowieść twierdzenie, ustalmy dowolny niepusty zbiór \(\displaystyle{ x\subset\mathbb{N}}\) ograniczony z góry. Niech \(\displaystyle{ n\in\NN}\) będzie jego ograniczeniem. Ponieważ każdy element zbioru \(\displaystyle{ x}\) jest mniejszy lub równy od \(\displaystyle{ n}\), więc \(\displaystyle{ x\subset n'.}\) Ponieważ każda liczba naturalna należy do \(\displaystyle{ X}\), to również \(\displaystyle{ n' \in X}\). Zatem, z definicji zbioru \(\displaystyle{ X}\), dla dowolnego niepustego zbioru \(\displaystyle{ z \subset n'}\) mamy \(\displaystyle{ \bigcup z\in z}\), czyli zbiór \(\displaystyle{ z}\) mam element największy. Widać, że zbiór \(\displaystyle{ x}\) spełnia te założenia, więc zgodnie z powyższym zbiór \(\displaystyle{ x}\) ma element największy, co kończy dowód.\(\displaystyle{ \square}\) :lol:

ODPOWIEDZ