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}\)
Oczywiste fakty
-
Jakub Gurak
- Użytkownik
- Posty: 1402
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 60 razy
- Pomógł: 83 razy
-
Jakub Gurak
- Użytkownik
- Posty: 1402
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 60 razy
- Pomógł: 83 razy
Oczywiste fakty
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}\)
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
- Posty: 1402
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 60 razy
- Pomógł: 83 razy
Re: Oczywiste fakty
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}\)
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}\)
-
Jakub Gurak
- Użytkownik
- Posty: 1402
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 60 razy
- Pomógł: 83 razy
Re: Oczywiste fakty
Dodano po 4 godzinach 55 minutach 39 sekundach:
Pokażemy teraz, że formuła
\(\displaystyle{ \left( \forall_{x} p(x)\right) \Rightarrow \exists_{x} p(x) }\) (*)jest prawdziwa w każdym odpowiednim dla niej modelu.
Dowód:
Rozważmy dowolny model \(\displaystyle{ M}\) odpowiedni dla powyższej formuły ( odpowiedni to znaczy taki, który ustala interpretacje symbolu predykatywnego \(\displaystyle{ p}\)). Jeśli w tym modelu nie jest prawdziwa formuła \(\displaystyle{ \forall_{x} p(x)}\), to cała implikacja jest prawdziwa. Pozostaje więc rozważyć przypadek, gdy prawdziwa jest formuła \(\displaystyle{ \forall_{x} p(x)}\). Aby pokazać, że \(\displaystyle{ \exists_{x} p(x)}\) jest prawdziwe w \(\displaystyle{ M}\), wystarczy wykazać, że istnieje w dziedzinie taka wartość, że podstawiona w miejsce \(\displaystyle{ x}\) uczyni predykat oznaczonym przez \(\displaystyle{ p}\) prawdziwym. Formuła \(\displaystyle{ \forall_{x} p(x)}\) jest prawdziwa w \(\displaystyle{ M}\), więc każda wartość podstawiona pod \(\displaystyle{ x}\) czyni predykat odpowiadający \(\displaystyle{ p}\) prawdziwym. Ponieważ dziedzina modelu \(\displaystyle{ M}\) zgodnie z definicją nie może być pusta, więc istnieje co najmniej jeden element dziedziny. Ponieważ w dziedzinie istnieje co najmniej jeden element, oraz ponieważ formuła \(\displaystyle{ p(x)}\) jest prawdziwa niezależnie od tego co podstawimy w miejsce \(\displaystyle{ x}\), więc dla tego elementu dziedziny on podstawiony w miejsce \(\displaystyle{ x}\) uczyni predykat oznaczony przez \(\displaystyle{ p}\) prawdziwym. A zatem rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce \(\displaystyle{ x}\) uczyni formułę \(\displaystyle{ p(x)}\) prawdziwą. A więc formuła \(\displaystyle{ \exists_{x} p(x)}\) również jest prawdziwa. Wobec tego cała implikacja jest prawdziwa w \(\displaystyle{ M}\). Pokazaliśmy więc, że formuła (*) jest prawdziwa w każdym odpowiednim dla niej modelu. \(\displaystyle{ \square}\)
Aksjomat zbioru pustego mówi, że \(\displaystyle{ \exists_{x}\forall{y} \quad y\not\in x.}\)
A więc istnieje zbiór \(\displaystyle{ x}\) (nieposiadający elementów), a więc taki, że każdy \(\displaystyle{ y}\) nie należy do tego zbioru pustego \(\displaystyle{ x}\).
Na ważniaku, po wprowadzeniu tego aksjomatu, piszą, że aksjomat zbioru pustego gwarantuje istnienie tylko jednego zbioru. Dalej piszą: jednoelementowy model \(\displaystyle{ \left\{ a\right\}}\), gdzie \(\displaystyle{ a\not\in a}\) spełnia aksjomat zbioru pustego. Spróbuje to krótko uzasadnić: istnieje \(\displaystyle{ x=a}\), ze dla każdego \(\displaystyle{ y}\) (w modelu, czyli dla \(\displaystyle{ y=a}\)) \(\displaystyle{ y\not\in x}\), gdyż podstawiając wartości oznacza to, że \(\displaystyle{ a\not\in a}\), co zachodzi z założenia.
Jeszcze jedne formalne spostrzeżenie:
Niech \(\displaystyle{ x}\) będzie zbiorem. Rozważmy nowy zbiór:
\(\displaystyle{ A=\left\{ z\in P(x)( z \subset x) \Bigl| \ \ \exists_{w} \quad z=\left\{ w\right\} \right\} .}\)
Zauważmy, że musi wtedy \(\displaystyle{ w\in x}\), gdyż \(\displaystyle{ z\subset x}\), więc \(\displaystyle{ \left\{ w\right\} \subset x}\), a więc musi \(\displaystyle{ w\in x}\). Mniej formalnie zbiór \(\displaystyle{ A}\) jest rodziną \(\displaystyle{ \left\{ \left\{ w\right\}\Bigl| \ \ w\in x\ \right\}}\) zbiorów jednoelementowych o elementach z \(\displaystyle{ x}\), jednak proszę zauważyć, że wcześniej w definicji \(\displaystyle{ A}\), nigdzie się ten zapis nie pojawia, (tzn. że \(\displaystyle{ w\in x}\)).
Wykażemy jeszcze, że dowolne dwie liczby naturalne von Neumanna różne nie są równoliczne.
Lemat: Jeśli z różnej od \(\displaystyle{ 0=\emptyset}\) liczby naturalnej von Neuamnna usuniemy jeden dowolny element, to powstały zbiór będzie równoliczny z \(\displaystyle{ (n-1)}\), tzn. z taką liczbą naturalną \(\displaystyle{ m}\), że \(\displaystyle{ m'=n.}\)
Dowód lematu:
Niech \(\displaystyle{ \emptyset=0\neq n\in\NN}\), niech \(\displaystyle{ k\in n}\). Pokażemy, że \(\displaystyle{ n \setminus \left\{ k\right\} \sim( n-1)}\), jeśli usunęliśmy \(\displaystyle{ k=n-1}\), to otrzymujemy zbiór \(\displaystyle{ (n-1)\sim (n-1).}\) Jeśli usunęliśmy \(\displaystyle{ k \neq (n-1)}\). to możemy zdefiniować funkcję \(\displaystyle{ f:n \setminus \left\{ k\right\} \rightarrow \left( n-1\right)}\) jako:
\(\displaystyle{ f(m)= \begin{cases} m,\hbox{ jeśli } m \neq (n-1), \\ k, \ \ jeśli m=n-1.\end{cases}}\)
Ponieważ identyczność \(\displaystyle{ f_1:n\setminus\left\{ k,n-1\right\} \rightarrow n \setminus \left\{ k,n-1\right\} }\) jest bijekcją, \(\displaystyle{ f_2:\left\{ n-1\right\} \rightarrow \left\{ k\right\}}\) jest bijekcją, więc również \(\displaystyle{ f}\) jest bijekcją. A więc \(\displaystyle{ n \setminus \left\{ k\right\} \sim (n-1).\square}\)
Dowód:
Niech \(\displaystyle{ n,m\in\NN}\) będą różne. Pokażemy, że \(\displaystyle{ n\not\sim m}\). Przypuśćmy zatem nie wprost, że istnieją liczby naturalne \(\displaystyle{ n,m\in\NN}\) różne, które są równoliczne. Rozważmy zbiór \(\displaystyle{ D}\):
\(\displaystyle{ D=\left\{ n\in\NN\Bigl| \ \ \bigvee\limits_{m\in\NN} \left( m \neq n \wedge n\sim m\right) \right\} .}\)
Na mocy naszego założenia istnieje liczba naturalna \(\displaystyle{ n}\) oraz liczba naturalna \(\displaystyle{ m}\) od niej różna, tak że są one równoliczne, a więc zbiór \(\displaystyle{ D}\) jest niepusty. Zbiór \(\displaystyle{ D}\) z określenia jest podzbiorem zbioru \(\displaystyle{ \NN}\). Zatem, na mocy zasady minimum zbiór \(\displaystyle{ D}\) ma liczbę najmniejszą \(\displaystyle{ n}\). wtedy \(\displaystyle{ n\in D}\), a zatem, z definicji tego zbioru otrzymujemy pewną liczbę naturalną \(\displaystyle{ m \neq n}\), taką, że \(\displaystyle{ n\sim m}\). Wtedy \(\displaystyle{ n,m}\) są rózne od \(\displaystyle{ 0=\emptyset}\), bo w przeciwnym razie, jedna z tych liczb naturalnych byłaby równoliczna ze zbiorem pustym, a więc również byłaby zbiorem pustym, a więc \(\displaystyle{ n=m=\emptyset}\), a \(\displaystyle{ n \neq m}\)-sprzeczność). Ponieważ \(\displaystyle{ n\sim m}\), więc istnieje bijekcja \(\displaystyle{ f:n \rightarrow m}\), rozważmy teraz nową funkcję \(\displaystyle{ g=f \cap \left[ \left( n-1\right) \times m \right]}\) (czyli obcięcie funkcji \(\displaystyle{ f}\) do zbioru \(\displaystyle{ (n-1) }\)). Ponieważ \(\displaystyle{ f}\) jest różnowartościowa, więc również \(\displaystyle{ g}\) bedzie róznowartościowa, i 'na' zbiór wartości, a zatem \(\displaystyle{ g_P\sim (n-1)}\). Ponieważ \(\displaystyle{ (n-1)\not\in (n-1)}\), więc również \(\displaystyle{ f(n-1)\not\in g_P.}\) Ponieważ \(\displaystyle{ f}\) jest różnowartościowa, to \(\displaystyle{ g_P=f_P \setminus\left\{ f(n-1)\right\}}\). Otrzymujemy zatem, że \(\displaystyle{ (n-1)\sim g_P=f_P \setminus\left\{ f(n-1)\right\} =m\setminus\left\{ f(n-1)\right\} }\) a ten ostatni zbiór jest równoliczny, na mocy lematu, z \(\displaystyle{ (m-1)}\), otrzymujemy zatem, że \(\displaystyle{ (n-1)\sim (m-1)}\), i ponieważ \(\displaystyle{ n \neq m}\), więc również \(\displaystyle{ (n-1) \neq (m-1)}\), a zatem z definicji zbioru \(\displaystyle{ D: (n-1)\in D}\), a ponieważ liczba naturalna \(\displaystyle{ n}\) była najmniejsza w \(\displaystyle{ D}\), to \(\displaystyle{ n \le n-1}\)- sprzeczność. \(\displaystyle{ \square}\) 
Pokażemy teraz, że formuła
\(\displaystyle{ \left( \forall_{x} p(x)\right) \Rightarrow \exists_{x} p(x) }\) (*)jest prawdziwa w każdym odpowiednim dla niej modelu.
Dowód:
Rozważmy dowolny model \(\displaystyle{ M}\) odpowiedni dla powyższej formuły ( odpowiedni to znaczy taki, który ustala interpretacje symbolu predykatywnego \(\displaystyle{ p}\)). Jeśli w tym modelu nie jest prawdziwa formuła \(\displaystyle{ \forall_{x} p(x)}\), to cała implikacja jest prawdziwa. Pozostaje więc rozważyć przypadek, gdy prawdziwa jest formuła \(\displaystyle{ \forall_{x} p(x)}\). Aby pokazać, że \(\displaystyle{ \exists_{x} p(x)}\) jest prawdziwe w \(\displaystyle{ M}\), wystarczy wykazać, że istnieje w dziedzinie taka wartość, że podstawiona w miejsce \(\displaystyle{ x}\) uczyni predykat oznaczonym przez \(\displaystyle{ p}\) prawdziwym. Formuła \(\displaystyle{ \forall_{x} p(x)}\) jest prawdziwa w \(\displaystyle{ M}\), więc każda wartość podstawiona pod \(\displaystyle{ x}\) czyni predykat odpowiadający \(\displaystyle{ p}\) prawdziwym. Ponieważ dziedzina modelu \(\displaystyle{ M}\) zgodnie z definicją nie może być pusta, więc istnieje co najmniej jeden element dziedziny. Ponieważ w dziedzinie istnieje co najmniej jeden element, oraz ponieważ formuła \(\displaystyle{ p(x)}\) jest prawdziwa niezależnie od tego co podstawimy w miejsce \(\displaystyle{ x}\), więc dla tego elementu dziedziny on podstawiony w miejsce \(\displaystyle{ x}\) uczyni predykat oznaczony przez \(\displaystyle{ p}\) prawdziwym. A zatem rzeczywiście istnieje taki element dziedziny, który podstawiony w miejsce \(\displaystyle{ x}\) uczyni formułę \(\displaystyle{ p(x)}\) prawdziwą. A więc formuła \(\displaystyle{ \exists_{x} p(x)}\) również jest prawdziwa. Wobec tego cała implikacja jest prawdziwa w \(\displaystyle{ M}\). Pokazaliśmy więc, że formuła (*) jest prawdziwa w każdym odpowiednim dla niej modelu. \(\displaystyle{ \square}\)
Aksjomat zbioru pustego mówi, że \(\displaystyle{ \exists_{x}\forall{y} \quad y\not\in x.}\)
A więc istnieje zbiór \(\displaystyle{ x}\) (nieposiadający elementów), a więc taki, że każdy \(\displaystyle{ y}\) nie należy do tego zbioru pustego \(\displaystyle{ x}\).
Na ważniaku, po wprowadzeniu tego aksjomatu, piszą, że aksjomat zbioru pustego gwarantuje istnienie tylko jednego zbioru. Dalej piszą: jednoelementowy model \(\displaystyle{ \left\{ a\right\}}\), gdzie \(\displaystyle{ a\not\in a}\) spełnia aksjomat zbioru pustego. Spróbuje to krótko uzasadnić: istnieje \(\displaystyle{ x=a}\), ze dla każdego \(\displaystyle{ y}\) (w modelu, czyli dla \(\displaystyle{ y=a}\)) \(\displaystyle{ y\not\in x}\), gdyż podstawiając wartości oznacza to, że \(\displaystyle{ a\not\in a}\), co zachodzi z założenia.
Jeszcze jedne formalne spostrzeżenie:
Niech \(\displaystyle{ x}\) będzie zbiorem. Rozważmy nowy zbiór:
\(\displaystyle{ A=\left\{ z\in P(x)( z \subset x) \Bigl| \ \ \exists_{w} \quad z=\left\{ w\right\} \right\} .}\)
Zauważmy, że musi wtedy \(\displaystyle{ w\in x}\), gdyż \(\displaystyle{ z\subset x}\), więc \(\displaystyle{ \left\{ w\right\} \subset x}\), a więc musi \(\displaystyle{ w\in x}\). Mniej formalnie zbiór \(\displaystyle{ A}\) jest rodziną \(\displaystyle{ \left\{ \left\{ w\right\}\Bigl| \ \ w\in x\ \right\}}\) zbiorów jednoelementowych o elementach z \(\displaystyle{ x}\), jednak proszę zauważyć, że wcześniej w definicji \(\displaystyle{ A}\), nigdzie się ten zapis nie pojawia, (tzn. że \(\displaystyle{ w\in x}\)).
Wykażemy jeszcze, że dowolne dwie liczby naturalne von Neumanna różne nie są równoliczne.
Lemat: Jeśli z różnej od \(\displaystyle{ 0=\emptyset}\) liczby naturalnej von Neuamnna usuniemy jeden dowolny element, to powstały zbiór będzie równoliczny z \(\displaystyle{ (n-1)}\), tzn. z taką liczbą naturalną \(\displaystyle{ m}\), że \(\displaystyle{ m'=n.}\)
Dowód lematu:
Niech \(\displaystyle{ \emptyset=0\neq n\in\NN}\), niech \(\displaystyle{ k\in n}\). Pokażemy, że \(\displaystyle{ n \setminus \left\{ k\right\} \sim( n-1)}\), jeśli usunęliśmy \(\displaystyle{ k=n-1}\), to otrzymujemy zbiór \(\displaystyle{ (n-1)\sim (n-1).}\) Jeśli usunęliśmy \(\displaystyle{ k \neq (n-1)}\). to możemy zdefiniować funkcję \(\displaystyle{ f:n \setminus \left\{ k\right\} \rightarrow \left( n-1\right)}\) jako:
\(\displaystyle{ f(m)= \begin{cases} m,\hbox{ jeśli } m \neq (n-1), \\ k, \ \ jeśli m=n-1.\end{cases}}\)
Ponieważ identyczność \(\displaystyle{ f_1:n\setminus\left\{ k,n-1\right\} \rightarrow n \setminus \left\{ k,n-1\right\} }\) jest bijekcją, \(\displaystyle{ f_2:\left\{ n-1\right\} \rightarrow \left\{ k\right\}}\) jest bijekcją, więc również \(\displaystyle{ f}\) jest bijekcją. A więc \(\displaystyle{ n \setminus \left\{ k\right\} \sim (n-1).\square}\)
Dowód:
Niech \(\displaystyle{ n,m\in\NN}\) będą różne. Pokażemy, że \(\displaystyle{ n\not\sim m}\). Przypuśćmy zatem nie wprost, że istnieją liczby naturalne \(\displaystyle{ n,m\in\NN}\) różne, które są równoliczne. Rozważmy zbiór \(\displaystyle{ D}\):
\(\displaystyle{ D=\left\{ n\in\NN\Bigl| \ \ \bigvee\limits_{m\in\NN} \left( m \neq n \wedge n\sim m\right) \right\} .}\)
Na mocy naszego założenia istnieje liczba naturalna \(\displaystyle{ n}\) oraz liczba naturalna \(\displaystyle{ m}\) od niej różna, tak że są one równoliczne, a więc zbiór \(\displaystyle{ D}\) jest niepusty. Zbiór \(\displaystyle{ D}\) z określenia jest podzbiorem zbioru \(\displaystyle{ \NN}\). Zatem, na mocy zasady minimum zbiór \(\displaystyle{ D}\) ma liczbę najmniejszą \(\displaystyle{ n}\). wtedy \(\displaystyle{ n\in D}\), a zatem, z definicji tego zbioru otrzymujemy pewną liczbę naturalną \(\displaystyle{ m \neq n}\), taką, że \(\displaystyle{ n\sim m}\). Wtedy \(\displaystyle{ n,m}\) są rózne od \(\displaystyle{ 0=\emptyset}\), bo w przeciwnym razie, jedna z tych liczb naturalnych byłaby równoliczna ze zbiorem pustym, a więc również byłaby zbiorem pustym, a więc \(\displaystyle{ n=m=\emptyset}\), a \(\displaystyle{ n \neq m}\)-sprzeczność). Ponieważ \(\displaystyle{ n\sim m}\), więc istnieje bijekcja \(\displaystyle{ f:n \rightarrow m}\), rozważmy teraz nową funkcję \(\displaystyle{ g=f \cap \left[ \left( n-1\right) \times m \right]}\) (czyli obcięcie funkcji \(\displaystyle{ f}\) do zbioru \(\displaystyle{ (n-1) }\)). Ponieważ \(\displaystyle{ f}\) jest różnowartościowa, więc również \(\displaystyle{ g}\) bedzie róznowartościowa, i 'na' zbiór wartości, a zatem \(\displaystyle{ g_P\sim (n-1)}\). Ponieważ \(\displaystyle{ (n-1)\not\in (n-1)}\), więc również \(\displaystyle{ f(n-1)\not\in g_P.}\) Ponieważ \(\displaystyle{ f}\) jest różnowartościowa, to \(\displaystyle{ g_P=f_P \setminus\left\{ f(n-1)\right\}}\). Otrzymujemy zatem, że \(\displaystyle{ (n-1)\sim g_P=f_P \setminus\left\{ f(n-1)\right\} =m\setminus\left\{ f(n-1)\right\} }\) a ten ostatni zbiór jest równoliczny, na mocy lematu, z \(\displaystyle{ (m-1)}\), otrzymujemy zatem, że \(\displaystyle{ (n-1)\sim (m-1)}\), i ponieważ \(\displaystyle{ n \neq m}\), więc również \(\displaystyle{ (n-1) \neq (m-1)}\), a zatem z definicji zbioru \(\displaystyle{ D: (n-1)\in D}\), a ponieważ liczba naturalna \(\displaystyle{ n}\) była najmniejsza w \(\displaystyle{ D}\), to \(\displaystyle{ n \le n-1}\)- sprzeczność. \(\displaystyle{ \square}\)
-
Jakub Gurak
- Użytkownik
- Posty: 1402
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 60 razy
- Pomógł: 83 razy
Re: Oczywiste fakty
Wczoraj zapisałem na kartce pewien dowód z ważniaka pewnego faktu mówiącego, że dodawanie liczb naturalnych jest skracalne. Przedstawię teraz dowód tego faktu (gdyż podoba mi się on, bo jest to dowód trochę nietypowy).
Przypomnijmy, można udowodnić, że dla dowolnych liczb naturalnych \(\displaystyle{ n}\) i \(\displaystyle{ m}\) mamy:
\(\displaystyle{ n'+m=n+m'.}\)
Natomiast my wykażemy, że dla dowolnych liczb naturalnych \(\displaystyle{ k,n}\) i \(\displaystyle{ m}\) zachodzi implikacja:
\(\displaystyle{ k+n=m+n \Longrightarrow k=m.}\)
Przedstawię teraz indukcyjny dowód tego faktu:
DOWÓD TEGO FAKTU:
Dowód jest indukcyjny ze względu na zmienną \(\displaystyle{ n}\).
Jeśli \(\displaystyle{ n=0}\), i \(\displaystyle{ k+0= m+0}\), to niewątpliwie \(\displaystyle{ k=m.}\)
Krok indukcyjny:
Przypuśćmy, że własność skracania zachodzi dla liczby naturalnej \(\displaystyle{ n}\) (i dla dowolnych \(\displaystyle{ k,m \in \NN}\) ). Pokażemy, że zachodzi dla \(\displaystyle{ n'.}\)
Niech \(\displaystyle{ k,m \in \NN}\).
Jeśli \(\displaystyle{ k+n'=m+n'}\), to na mocy przytoczonego prawa oraz na mocy przemienności dodawania:
\(\displaystyle{ k+n'=n'+k=\left( n+k\right)'=\left( k+n\right)'.}\)
Analogicznie udowadniamy, że \(\displaystyle{ m+n'= \left( m+n\right)'.}\)
A zatem:
\(\displaystyle{ \left( k+n\right)'= k+n'=m+n' =\left( m+n\right)'.}\)
Z własności liczb naturalnych (którą się dowodzi w aksjomatycznie skonstruowanym zbiorze liczb naturalnych ) wiemy, że jeśli następniki dwóch danych liczb naturalnych są równe, to te dane dwie liczby są równe, więc:
\(\displaystyle{ k+n= m+n}\),
i ponieważ, na mocy założenia indukcyjnego, własność skracania zachodzi dla \(\displaystyle{ n}\), więc otrzymujemy: \(\displaystyle{ k=m}\).
Krok indukcyjny został dowiedziony.
Zasada indukcji matematycznej kończy dowód tego faktu.\(\displaystyle{ \square}\)
Jeszcze jeden dowodzik:
Wykażemy że:
Dla dowolnych liczb naturalnych \(\displaystyle{ n}\) i \(\displaystyle{ m}\) mamy:
\(\displaystyle{ n \cdot m=0 \Longleftrightarrow n=0 \vee m=0.}\)
Przypomnijmy, dowodzi się, że dla dowolnej liczby naturalnej \(\displaystyle{ k}\), mamy:
\(\displaystyle{ k \cdot 0=0.}\)
Przypomnijmy, w pierwszym poście tego wątku udowodniłem, że jeżeli suma dwóch liczb naturalnych jest równa \(\displaystyle{ 0}\), to obydwie składniki tej sumy muszą być równe \(\displaystyle{ 0}\), w pierwszym poście tego wątku udowodniłem ten fakt.
Przypomnijmy, każda liczba naturalna różna od \(\displaystyle{ 0}\) jest następnikiem pewnej liczby naturalnej, można to łatwo udowodnić.
Przejdźmy do naszego dowodu.
DOWÓD TEGO FAKTU:
Implikacja z prawej strony do lewej wynika z przytoczonego faktu o mnożeniu liczby naturalnej przez \(\displaystyle{ 0}\) , tzn. jeśli \(\displaystyle{ n=0}\), to z definicji mnożenia od razu mamy \(\displaystyle{ n \cdot m=0}\), a jeśli \(\displaystyle{ m=0,}\) to przytoczony fakt daje, że \(\displaystyle{ n \cdot m=0.}\)
Dowodzimy implikacji z lewej strony do prawej:
Jeśli \(\displaystyle{ n \cdot m=0}\), to jeśli \(\displaystyle{ n=0}\), to implikacja jest prawdziwa.
Jeśli \(\displaystyle{ n \neq 0}\), to na mocy przytoczonego faktu o następnikach: liczba \(\displaystyle{ n}\) jest następnikiem pewnej liczby naturalnej \(\displaystyle{ k}\), tzn. \(\displaystyle{ n=k'}\). Wtedy:
\(\displaystyle{ 0=n \cdot m=k' \cdot m= k \cdot m+m}\),
i ponieważ \(\displaystyle{ \left( k \cdot m\right) }\), jako iloczyn dwóch liczb naturalnych, jest liczbą naturalną, więc mamy tu sumę dwóch liczb naturalnych- sumę równą \(\displaystyle{ 0}\), więc również obydwa składniki tej sumy muszą być równe \(\displaystyle{ 0}\), w szczególności \(\displaystyle{ m=0.\square}\)
I na koniec:
Przypomnijmy, jeśli \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są zbiorami, to zbiór \(\displaystyle{ x \cap y}\) można zdefiniować jako:
\(\displaystyle{ x \cap y= \bigcap\left\{ x,y\right\},}\)
jako przekrój uogólniony rodziny dwuelementowej \(\displaystyle{ \left\{ x,y\right\} .}\)
Można udowodnić, że taka definicja ma takie samo znaczenie jak przekrój dwóch zbiorów w naiwnej teorii mnogości, tzn. dla dowolnych zbiorów \(\displaystyle{ x,y}\) i \(\displaystyle{ z}\) mamy:
\(\displaystyle{ z \in x \cap y \Longleftrightarrow z \in x \wedge z \in y.}\)
Przypomnijmy: jedynym podzbiorem zbioru pustego jest on sam.
Wykażemy, że dla dowolnego zbioru \(\displaystyle{ x}\), mamy:
\(\displaystyle{ x \cap \emptyset =\emptyset.}\)
DOWÓD TEGO FAKTU:
Mamy, z definicji przekroju dwóch zbiorów: \(\displaystyle{ x \cap \emptyset= \bigcap \left\{ x, \emptyset\right\}}\) , a przekrój uogólniony jest podzbiorem każdego zbioru tej rodziny, a u nas rodzina ma dwa zbiory (lub ewentualnie jeden- gdy są równe), tzn. \(\displaystyle{ x}\) i \(\displaystyle{ \emptyset}\), w związku z czym \(\displaystyle{ x \cap \emptyset \subset \emptyset}\), a ponieważ jedynym podzbiorem zbioru pustego jest on sam, więc \(\displaystyle{ x \cap \emptyset =\emptyset.\square}\)
Z moich spostrzeżeń formalnych, to mam jeszcze coś odnośnie rozkładów, ale już muszę iść spać.
Przypomnijmy, można udowodnić, że dla dowolnych liczb naturalnych \(\displaystyle{ n}\) i \(\displaystyle{ m}\) mamy:
\(\displaystyle{ n'+m=n+m'.}\)
Natomiast my wykażemy, że dla dowolnych liczb naturalnych \(\displaystyle{ k,n}\) i \(\displaystyle{ m}\) zachodzi implikacja:
\(\displaystyle{ k+n=m+n \Longrightarrow k=m.}\)
Przedstawię teraz indukcyjny dowód tego faktu:
DOWÓD TEGO FAKTU:
Dowód jest indukcyjny ze względu na zmienną \(\displaystyle{ n}\).
Jeśli \(\displaystyle{ n=0}\), i \(\displaystyle{ k+0= m+0}\), to niewątpliwie \(\displaystyle{ k=m.}\)
Krok indukcyjny:
Przypuśćmy, że własność skracania zachodzi dla liczby naturalnej \(\displaystyle{ n}\) (i dla dowolnych \(\displaystyle{ k,m \in \NN}\) ). Pokażemy, że zachodzi dla \(\displaystyle{ n'.}\)
Niech \(\displaystyle{ k,m \in \NN}\).
Jeśli \(\displaystyle{ k+n'=m+n'}\), to na mocy przytoczonego prawa oraz na mocy przemienności dodawania:
\(\displaystyle{ k+n'=n'+k=\left( n+k\right)'=\left( k+n\right)'.}\)
Analogicznie udowadniamy, że \(\displaystyle{ m+n'= \left( m+n\right)'.}\)
A zatem:
\(\displaystyle{ \left( k+n\right)'= k+n'=m+n' =\left( m+n\right)'.}\)
Z własności liczb naturalnych (którą się dowodzi w aksjomatycznie skonstruowanym zbiorze liczb naturalnych ) wiemy, że jeśli następniki dwóch danych liczb naturalnych są równe, to te dane dwie liczby są równe, więc:
\(\displaystyle{ k+n= m+n}\),
i ponieważ, na mocy założenia indukcyjnego, własność skracania zachodzi dla \(\displaystyle{ n}\), więc otrzymujemy: \(\displaystyle{ k=m}\).
Krok indukcyjny został dowiedziony.
Zasada indukcji matematycznej kończy dowód tego faktu.\(\displaystyle{ \square}\)
Jeszcze jeden dowodzik:
Wykażemy że:
Dla dowolnych liczb naturalnych \(\displaystyle{ n}\) i \(\displaystyle{ m}\) mamy:
\(\displaystyle{ n \cdot m=0 \Longleftrightarrow n=0 \vee m=0.}\)
Przypomnijmy, dowodzi się, że dla dowolnej liczby naturalnej \(\displaystyle{ k}\), mamy:
\(\displaystyle{ k \cdot 0=0.}\)
Przypomnijmy, w pierwszym poście tego wątku udowodniłem, że jeżeli suma dwóch liczb naturalnych jest równa \(\displaystyle{ 0}\), to obydwie składniki tej sumy muszą być równe \(\displaystyle{ 0}\), w pierwszym poście tego wątku udowodniłem ten fakt.
Przypomnijmy, każda liczba naturalna różna od \(\displaystyle{ 0}\) jest następnikiem pewnej liczby naturalnej, można to łatwo udowodnić.
Przejdźmy do naszego dowodu.
DOWÓD TEGO FAKTU:
Implikacja z prawej strony do lewej wynika z przytoczonego faktu o mnożeniu liczby naturalnej przez \(\displaystyle{ 0}\) , tzn. jeśli \(\displaystyle{ n=0}\), to z definicji mnożenia od razu mamy \(\displaystyle{ n \cdot m=0}\), a jeśli \(\displaystyle{ m=0,}\) to przytoczony fakt daje, że \(\displaystyle{ n \cdot m=0.}\)
Dowodzimy implikacji z lewej strony do prawej:
Jeśli \(\displaystyle{ n \cdot m=0}\), to jeśli \(\displaystyle{ n=0}\), to implikacja jest prawdziwa.
Jeśli \(\displaystyle{ n \neq 0}\), to na mocy przytoczonego faktu o następnikach: liczba \(\displaystyle{ n}\) jest następnikiem pewnej liczby naturalnej \(\displaystyle{ k}\), tzn. \(\displaystyle{ n=k'}\). Wtedy:
\(\displaystyle{ 0=n \cdot m=k' \cdot m= k \cdot m+m}\),
i ponieważ \(\displaystyle{ \left( k \cdot m\right) }\), jako iloczyn dwóch liczb naturalnych, jest liczbą naturalną, więc mamy tu sumę dwóch liczb naturalnych- sumę równą \(\displaystyle{ 0}\), więc również obydwa składniki tej sumy muszą być równe \(\displaystyle{ 0}\), w szczególności \(\displaystyle{ m=0.\square}\)
I na koniec:
Przypomnijmy, jeśli \(\displaystyle{ x}\) i \(\displaystyle{ y}\) są zbiorami, to zbiór \(\displaystyle{ x \cap y}\) można zdefiniować jako:
\(\displaystyle{ x \cap y= \bigcap\left\{ x,y\right\},}\)
jako przekrój uogólniony rodziny dwuelementowej \(\displaystyle{ \left\{ x,y\right\} .}\)
Można udowodnić, że taka definicja ma takie samo znaczenie jak przekrój dwóch zbiorów w naiwnej teorii mnogości, tzn. dla dowolnych zbiorów \(\displaystyle{ x,y}\) i \(\displaystyle{ z}\) mamy:
\(\displaystyle{ z \in x \cap y \Longleftrightarrow z \in x \wedge z \in y.}\)
Przypomnijmy: jedynym podzbiorem zbioru pustego jest on sam.
Wykażemy, że dla dowolnego zbioru \(\displaystyle{ x}\), mamy:
\(\displaystyle{ x \cap \emptyset =\emptyset.}\)
DOWÓD TEGO FAKTU:
Mamy, z definicji przekroju dwóch zbiorów: \(\displaystyle{ x \cap \emptyset= \bigcap \left\{ x, \emptyset\right\}}\) , a przekrój uogólniony jest podzbiorem każdego zbioru tej rodziny, a u nas rodzina ma dwa zbiory (lub ewentualnie jeden- gdy są równe), tzn. \(\displaystyle{ x}\) i \(\displaystyle{ \emptyset}\), w związku z czym \(\displaystyle{ x \cap \emptyset \subset \emptyset}\), a ponieważ jedynym podzbiorem zbioru pustego jest on sam, więc \(\displaystyle{ x \cap \emptyset =\emptyset.\square}\)
Z moich spostrzeżeń formalnych, to mam jeszcze coś odnośnie rozkładów, ale już muszę iść spać.