Oczywiste fakty

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 734
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 49 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: 734
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 49 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: 734
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 49 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:

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

Re: Oczywiste fakty

Post autor: Jakub Gurak » 8 mar 2020, o 23:00

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}\) :lol:

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}\) :lol: 8-)

ODPOWIEDZ