Poprawiłem dowód
: 19 wrz 2019, o 16:14
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.
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}\)
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.
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}\)