Poprawiłem dowód

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

Poprawiłem dowód

Post autor: Jakub Gurak »

Mam na myśli dowód twierdzenia o definiowaniu przez indukcję, z ważniaka:

Niech \(\displaystyle{ A,B}\) będą niepustymi zbiorami. A \(\displaystyle{ f:A \rightarrow B, g:B \times \left( \NN \times A\right) \rightarrow B}\) dowolnymi funkcjami. Wtedy istnieje unikalna (jedyna) funkcja \(\displaystyle{ h:\NN \times A \rightarrow B}\) spełniająca:

\(\displaystyle{ h\left( 0,a\right)=f\left( a\right), \hbox{ dla każdego } a\in A,}\)
\(\displaystyle{ h\left( n',a\right)=g\left( h\left( n,a\right),\left( n,a\right) \right), \hbox{ dla każdego } a\in A \hbox{ i każdego } n\in\NN.}\)

Dowód:

Niech \(\displaystyle{ f:A\rightarrow B, g:B \times \left( \NN \times A\right) \rightarrow B.}\) Rozważmy zbiór \(\displaystyle{ H}\):

\(\displaystyle{ \displaystyle{H= \left\{ h \subset \left( \NN \times A\right) \times B\Bigl| \ \ \bigvee\limits_{m\in \NN} h:m' \times A \rightarrow B \wedge \textbf{ (*)} \right\},}}\)

gdzie:

\(\displaystyle{ h\left( 0,a\right)=f\left( a\right)\hbox{ dla każdego } a\in A,}\)
\(\displaystyle{ h\left( n',a\right)=g\left( h\left( n,a\right),\left( n,a\right) \right), \hbox{ dla każdego } a\in A \hbox{ i każdego } n\in m. \textbf{ (*)}}\)

Czyli zbiór \(\displaystyle{ H}\), to zbiór krótszych fragmentów dla których twierdzenie zachodzi- dokładniej \(\displaystyle{ H}\) jest zbiorem funkcji, określonych na zbiorach postaci \(\displaystyle{ \left\{ 0,1, \ldots, m\right\} \times A}\), gdzie \(\displaystyle{ m\in\NN}\), spełniających odpowiednie równości z tezy twierdzenia. Funkcja, której szukamy, powinna być określona na całym zbiorze \(\displaystyle{ \NN \times A.}\)

Najpierw wykażemy, że dla każdego \(\displaystyle{ m}\) naturalnego istnieje w \(\displaystyle{ H}\) funkcja określona na zbiorze \(\displaystyle{ m' \times A}\), lub równoważnie, dla każdego \(\displaystyle{ m}\) naturalnego istnieje funkcja \(\displaystyle{ h:m' \times A \rightarrow B}\) spełniająca równości \(\displaystyle{ \textbf{ (*)}}\) . Dowód jest indukcyjny:

Jeśli \(\displaystyle{ m=0}\), to funkcja \(\displaystyle{ h:\left\{ 0\right\} \times A \rightarrow B}\), określona jako: \(\displaystyle{ h\left( 0,a\right)=f\left( a\right)}\) oczywiście spełnia te równości (drugą równość spełnia w sposób pusty).

Załóżmy, że warunek zachodzi dla \(\displaystyle{ m}\). To oznacza, że istnieje funkcja \(\displaystyle{ h:m' \times A \rightarrow B}\) spełniająca \(\displaystyle{ \textbf{ (*)}}\). Ustalmy ją, i rozważmy funkcję \(\displaystyle{ h': \left( m'\right)' \times A \rightarrow B}\) określoną:

\(\displaystyle{ h'\left( n,a\right) = \begin{cases} h\left( n,a\right), \hbox{ gdy } n\in m' \\ g\left( h\left( \color{red}{m} ,a\right),\left( \color{red} {m} ,a\right) \right) \hbox{ gdy } n= m'.\end{cases}}\)

Na ważniaku, w tym miejscu, pojawia się dla funkcji \(\displaystyle{ e:m' \times A \rightarrow B}\) spełniającej \(\displaystyle{ \textbf{ (*)}}\) pojawia się funkcja \(\displaystyle{ e'\left( n,a\right)=g\left( e\left( \color \green{n},a\right),n,a \right) }\) dla \(\displaystyle{ n=m'.}\) Proszę zauważyć, że funkcja \(\displaystyle{ e}\) nie jest określona na \(\displaystyle{ n=m' }\), gdyż \(\displaystyle{ m'\not\in m'}\), (w konstrukcji von Neumanna liczb naturalnych).

Po tej poprawce, chyba wszystko tu już jest dobrze określone. Pokażemy, że funkcja \(\displaystyle{ h'}\) spełnia żądane równości.

Niewątpliwie, ponieważ \(\displaystyle{ 0\in m'}\), więc z definicji funkcji \(\displaystyle{ h'}\) otrzymujemy \(\displaystyle{ h'(0,a)=h(0,a)=f(a).}\) A więc funkcja \(\displaystyle{ h'}\) spelnia pierwszą równość. Pokażemy, że spełnia też drugą. Czyli pokażemy, że

\(\displaystyle{ h'(n',a)=g(h'(n,a),(n,a)) \hbox{ dla każdego } a\in A \hbox{ i każdego } n\in m'.}\)

Niech \(\displaystyle{ a\in A, n\in m'.}\) Wtedy jeśli \(\displaystyle{ n'\in m'}\), to z definicji funkcji \(\displaystyle{ h'}\) mamy:

\(\displaystyle{ h'(n',a)=h(n',a)=g(h(n,a),(n,a)).}\) Pozostaje sprawdzić czy: \(\displaystyle{ h'(n.a)=h(n,a)}\). Ale ponieważ \(\displaystyle{ n'\in m'}\), więc \(\displaystyle{ n<n'<m'}\), więc \(\displaystyle{ n\in m'}\), więc z definicji funkcji \(\displaystyle{ h'}\) rzeczywiście \(\displaystyle{ h'(n.a)=h(n,a)}\) i żądana równość zachodzi.

Jeśli \(\displaystyle{ n'\not\in m'}\), to pozostaje \(\displaystyle{ n'=m'}\). Wtedy \(\displaystyle{ n=m}\). Wtedy z definicji \(\displaystyle{ h' }\) otrzymujemy: \(\displaystyle{ h'(n',a)=g(h(n,a),(n,a)).}\) Ponieważ \(\displaystyle{ n=m}\), więc \(\displaystyle{ n\in m',}\) a więc \(\displaystyle{ h'(n,a)=h(n,a)}\), i w efekcie

\(\displaystyle{ h'(n',a)=g(h(n,a),(n,a))=g(h'(n,a),(n,a)).}\)

A więc równość zachodzi. A więc warunek jest spełniony dla \(\displaystyle{ m'}\). Na podstawie zasady indukcji, z każdym \(\displaystyle{ m}\) naturalnym istnieje w \(\displaystyle{ H}\) funkcja określona na \(\displaystyle{ m' \times A}\), lub, inaczej mówiąc, z każdym \(\displaystyle{ m}\) naturalnym istnieje funkcja \(\displaystyle{ h_m:m' \times A \rightarrow B}\) spełniająca równości \(\displaystyle{ \textbf{ (*)}}\).

Teraz już jest chyba dobrze. :lol:

Wykazujemy też, że dla dowolnych dwóch funkcji w \(\displaystyle{ H}\) jedna jest rozszerzeniem drugiej. Pokazujemy, że poszukiwaną funkcją jest zbiór \(\displaystyle{ \bigcup H.}\)W sposób ciekawy można przeprowadzić też dowód jedyności takiej funkcji.

CIEKAWY DOWÓD:

Niech \(\displaystyle{ x,y:\NN \times A \rightarrow B}\) będą funkcjami spełniającymi tezę twierdzenia. Pokażemy, że \(\displaystyle{ x=y}\). W tym celu niech \(\displaystyle{ (n,a)\in\NN\times A}\). Wtedy oczywiście \(\displaystyle{ n\in\NN, a \in A}\). Ponieważ funkcję \(\displaystyle{ x,y}\) są określone na całym zbiorze \(\displaystyle{ \NN\times A}\), i spełniają żądane równości, więc te funkcje obcięte do zbioru \(\displaystyle{ n'\times A}\) są elementami \(\displaystyle{ H}\)- oznaczmy je \(\displaystyle{ x_{|n},y_{|n}.}\) Wobec czego jedna z nich jest rozszerzeniem drugiej (mówiłem, że to trzeba by wcześniej wykazać, ( głównie też w innym celu), przy okazji tu korzystamy z tego), czyli na tych samych argumentach przyjmują te same wartości, są określone na \(\displaystyle{ n'\times A}\), więc w szczególności \(\displaystyle{ x_{|n}(n,a)=y_{|n}(n,a)}\), więc lewa strona tej równości jest równa \(\displaystyle{ x(n,a),}\) a prawa podobnie \(\displaystyle{ y(n,a)}\). Wynika stąd \(\displaystyle{ x(n,a)=y(n,a)}\), co wobec dowolności wyboru pary \(\displaystyle{ (n,a) }\)daje, że \(\displaystyle{ x=y.\square}\) :D :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Poprawiłem dowód

Post autor: Jakub Gurak »

Dzięki temu twierdzeniu możemy formalnie zdefiniować dodawanie liczb naturalnych.

Połóżmy za \(\displaystyle{ A=B=\NN}\), \(\displaystyle{ f(n)=n}\), \(\displaystyle{ g(m,(n,a))=m'}\). Na mocy tego twierdzenia istnieje jedyna funkcja \(\displaystyle{ h:\NN\times\NN \rightarrow \NN}\) taka, że \(\displaystyle{ h(0,m)=m}\) dla każdego \(\displaystyle{ m}\) naturalnego, oraz taka, że \(\displaystyle{ h(n',m)=(h(n,m))'}\) dla każdych \(\displaystyle{ n,m}\) naturalnych. Funkcja ta to dodawanie liczb naturalnych, więc będziemy używać dalej zwyczajnej notacji \(\displaystyle{ h(n,m)=n+m}\). Możemy zatem zapisać, że

\(\displaystyle{ 0+m=m}\), dla każdej liczby naturalnej \(\displaystyle{ m}\), oraz że

\(\displaystyle{ n'+m=(n+m)'}\), dla dowolnych naturalnych \(\displaystyle{ n,m.}\)

Przekonajmy się najpierw, ze ta definicja pozwala dodać do siebie (i to poprawnie) dowolne dwie liczby naturalne( nie widać tego (to, że arytmetycznie poprawnie może widać), gdyż ta definicja dodawania odwołuje się do samej siebie). Myślę, że warto wiedzieć jak działa dodawanie jako cała funkcja na \(\displaystyle{ \NN\times\NN.}\)

Na mocy pierwszej własności możemy zsumować \(\displaystyle{ 0+n}\), czyli \(\displaystyle{ 0+0,0+1,0+2,0+3,\ldots}\)

Możemy zatem zsumować \(\displaystyle{ 1+n}\), dla dowolnego \(\displaystyle{ n}\) naturalnego.

\(\displaystyle{ 1+n=0'+n=\left( 0+n\right)'=n'.}\)

Druga równość wynika z definicji dodawania(a dokładniej jej drugiej części), a ostatnia z uzasadnionej już równości \(\displaystyle{ 0+n=n}\)( albo na podstawie pierwszej części definicji dodawania).

Arytmetycznie oczywiście się zgadza, ale zwróćmy uwagę, że \(\displaystyle{ 1+n}\) jest zdefiniowane tu jako \(\displaystyle{ n'}\) ( czyli jedna operacja wzięcia następnika, gdzie jest to pojęcie pierwotne względem dodawania, a samo dodawanie odwołuje się do samego siebie).

Zatem możemy zsumować \(\displaystyle{ 1+n}\), czyli
\(\displaystyle{ 1+0,1+1,1+2,1+3,\ldots}\)

Możemy, zgodnie z tą definicją, zsumować \(\displaystyle{ 2+n}\), dla dowolnego \(\displaystyle{ n}\) naturalnego.

\(\displaystyle{ 2+n=1'+n=\left( 1+n\right)'=\left( n'\right)'}\), gdzie druga równość wynika z drugiej części definicji dodawania, a kolejna z udowodnionej poprzednio równości \(\displaystyle{ 1+n=n'.}\)

Arytmetycznie się zgadza, ale znowu zwróćmy uwagę, że \(\displaystyle{ 2+n}\) zostało uzyskane jako \(\displaystyle{ \left( n'\right)'}\)- dwukrotne wzięcie następnika, a nie za pomocą odwoływania się do samego dodawania(które jawnie nie podaję jak zsumować \(\displaystyle{ n+m}\)).

Zatem możemy zsumować \(\displaystyle{ 2+n}\), czyli
\(\displaystyle{ 2+0,2+1,2+2,2+3,\ldots}\)

Jeżeli możemy zsumować \(\displaystyle{ m+n=\left( \left( n'\right)'\ldots\right) '}\), gdzie \(\displaystyle{ m}\) jest dowolne naturalne, i dalej \(\displaystyle{ n}\) jest dowolne naturalne- \(\displaystyle{ m}\) krotnie bierzemy następnik, to możemy również zsumować \(\displaystyle{ m'+n}\) (z dowolnym naturalnym \(\displaystyle{ n}\)).

\(\displaystyle{ m'+n=\left( m+n\right)'=\left( \overbrace{\left( \left( n'\right)'\ldots\right) '}^{m}\right) '}\)

gdzie pierwsza równość wynika z definicji dodawania, a druga z założenia indukcyjnego.

Arytmetycznie w porządku (odpowiada to liczbie \(\displaystyle{ m+n+1}\)), i znowu wyraziliśmy \(\displaystyle{ m'+n}\), za pomocą \(\displaystyle{ (m+1)}\)-krotnego brania następnika.

Pokazaliśmy zatem, że jeżeli możemy zsumować \(\displaystyle{ m+n}\), czyli

\(\displaystyle{ m+0,m+1,m+2,m+3,\ldots}\)

to możemy zsumować \(\displaystyle{ m'+n}\)

\(\displaystyle{ m'+0,m'+1,m'+2,m'+3,\ldots}\)

Widać więc, że dodawanie działa dla dowolnych dwóch liczb naturalnych ( w sposób poprawny), na zasadzie podobnej do zasady indukcji.

Kto by pomyślał, że to takie złożone. :lol:

Niemniej jednak, formalnie wszystkie inne własności (poza naszą definicją) funkcji \(\displaystyle{ +}\) należy dowieść z aksjomatów teorii mnogości, nawet taki fakt, że jeśli suma dwóch liczb naturalnych jest równa \(\displaystyle{ 0}\), to obydwie muszą być równe \(\displaystyle{ 0}\), co przedstawiłem tu.

O dodawaniu wiemy tylko tyle ile mówi powyższa definicja, resztę trzeba dowieść.


Możemy też dzięki temu twierdzeniu o definiowaniu przez indukcję możemy też formalnie zdefiniować mnożenie.

Biorąc \(\displaystyle{ A=B=\NN}\),oraz \(\displaystyle{ f(n)=0, g(m,(n,k))=m+k}\), z twierdzenia o definiowaniu przez indukcję mamy funkcję \(\displaystyle{ h:\NN \times \NN \rightarrow \NN}\) taką, że

\(\displaystyle{ h(0,m)=0}\), dla każdej liczby naturalnej \(\displaystyle{ m}\),

oraz

\(\displaystyle{ h(n',m)=h(n,m)+m}\), dla kązdych naturalnych \(\displaystyle{ n,m.}\)

Funkcja ta to mnożenie liczb naturalnych, więc będziemy używać dalej zwyczajnej notacji \(\displaystyle{ h(n,m)=n \cdot m}\). Możemy zatem zapisać, że

\(\displaystyle{ 0 \cdot m=0}\), dla każdej liczby naturalnej \(\displaystyle{ m}\), oraz że

\(\displaystyle{ n' \cdot m=(n \cdot m)+m}\), dla dowolnych naturalnych \(\displaystyle{ n,m.}\)

Przekonajmy się najpierw, ze ta definicja pozwala wymnożyć przez siebie (i to poprawnie) dowolne dwie liczby naturalne.

Możemy wymnożyć \(\displaystyle{ 0 \cdot m=0}\) na mocy pierwszej części definicji mnożenia. A więc

\(\displaystyle{ 0 \cdot 0,0 \cdot 1,0 \cdot 2,\ldots }\)

Możemy zatem wymnożyć \(\displaystyle{ 1 \cdot m}\) dla dowolnego \(\displaystyle{ m}\) naturalnego:

\(\displaystyle{ 1 \cdot m=0' \cdot m=(0 \cdot m)+m=0+m=m,}\)

gdzie druga równość wynika z definicji mnożenia, następna z poprzedniej uzasadnianej równości, ostatnia z definicji dodawania.

Arytmetycznie oczywiście dobrze, możemy zatem wymnożyć:

\(\displaystyle{ 1 \cdot 0,1 \cdot 1,1 \cdot 2,1 \cdot 3,\ldots}\)

Możemy zatem wymnożyć \(\displaystyle{ 2 \cdot m}\) dla dowolnego \(\displaystyle{ m}\) naturalnego:

\(\displaystyle{ 2 \cdot m=1' \cdot m=(1 \cdot m)+m=m+m.}\)

Arytmetycznie dobrze, ale zwróćmy uwagę, że określiliśmy to przez dodawanie, które możemy wykonać, a nie przez odwoływanie się do samego mnożenia(aby mnożenie wykonać).

Możemy zatem wymnożyć \(\displaystyle{ 2 \cdot m}\), tzn.

\(\displaystyle{ 2 \cdot 0, 2 \cdot 1,2 \cdot 2, \ldots}\)

Jeśli \(\displaystyle{ n}\) jest naturalne, i dla dowolnego \(\displaystyle{ m}\) naturalnego możemy wymnożyć \(\displaystyle{ n \cdot m=\overbrace{\left( m+m+\ldots+m\right)}^{n} }\), to \(\displaystyle{ n'}\) możemy wymnożyć przez dowolne naturalne \(\displaystyle{ m}\):

\(\displaystyle{ n' \cdot m=(n \cdot m)+m= \overbrace{\left( m+m+\ldots+m\right)}^{n} +m,}\)

gdzie pierwsza równość pochodzi z definicji mnożenia, a druga z założenia indukcyjnego.

Otrzymujemy \(\displaystyle{ (n+1)}\)krotnie dodane \(\displaystyle{ m}\), czyli arytmetycznie w porządku, i wyraziliśmy to za pomocą znanego dodawania.

Pokazaliśmy zatem, że jeżeli możemy wymnożyć \(\displaystyle{ n \cdot m}\), czyli

\(\displaystyle{ n \cdot 0,n \cdot 1,n \cdot 2,n \cdot 3,\ldots}\)

to możemy wymnożyć \(\displaystyle{ n' \cdot m}\)

\(\displaystyle{ n' \cdot 0,n' \cdot 1,n' \cdot 2,n' \cdot 3,\ldots}\)

Widać więc, że mnożenie działa dla dowolnych dwóch liczb naturalnych ( w sposób poprawny), na zasadzie podobnej do zasady indukcji.

Znowu jednak, formalnie o mnożeniu wiemy tylko tyle ile mówi powyższa definicja, resztę trzeba dowieść. Kto by pomyślał, że to takie złożone. :lol:
ODPOWIEDZ