Definiowanie przez indukcję w zbiorze liczb całkowitych ujemnych wraz z zerem

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

Definiowanie przez indukcję w zbiorze liczb całkowitych ujemnych wraz z zerem

Post autor: Jakub Gurak »

Niech \(\displaystyle{ A,B}\) będą niepustymi zbiorami.

Chcemy dla dowolnego elementu \(\displaystyle{ x}\) ze zbioru liczb całkowitych ujemnych wraz z zerem oraz dla dowolnego elementu \(\displaystyle{ a \in A}\) chcemy zdefiniować jeden element \(\displaystyle{ f\left( x,a\right) }\) ze zbioru \(\displaystyle{ B.}\) Możemy zrobić to w sposób indukcyjny. W tym celu definiujemy \(\displaystyle{ f\left( 0,a\right), }\) dla dowolnego \(\displaystyle{ a \in A}\) (formalnie rzecz biorąc używamy tu dodatkowej funkcji \(\displaystyle{ f _{0}: A \rightarrow B }\), a możemy przecież zdefiniować funkcję między dwoma niepustymI zbiorami; i, formalnie rzecz biorąc, w kroku zerowym używamy dowolnej takiej funkcji). Następnie dla dowolnego ustalonego \(\displaystyle{ a \in A}\) definiujemy \(\displaystyle{ f\left( -1,a\right)}\), na podstawie elementu \(\displaystyle{ a}\) i na podstawie wcześniejszej wartości \(\displaystyle{ f _{0}\left( a\right)}\) (która jest zdefiniowana dla dowolnego \(\displaystyle{ a \in A}\)), dalej definiujemy \(\displaystyle{ f\left( -1,a\right)}\), i tak dla dowolnego \(\displaystyle{ a \in A}\). W kroku \(\displaystyle{ n\in \ZZ _{-} \cup \left\{ 0\right\},}\) zakładamy, że zdefiniwana jest wartość \(\displaystyle{ f\left( n,a\right)}\), dla dowolnego ustalonego \(\displaystyle{ a \in A,}\) i na jej podstawie (oraz na podstawie elementów \(\displaystyle{ n}\) i \(\displaystyle{ a \in A}\)) definiujemy wartość na poprzedniku \(\displaystyle{ n ^{-}}\) liczby \(\displaystyle{ n}\), tzn. definiujemy \(\displaystyle{ f \left( n ^{-},a \right)}\), i tak dla dowolnego ustalonego \(\displaystyle{ a \in A.}\) Dzięki temu zdefiniujemy tą funkcję na całym zbiorze \(\displaystyle{ \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times A. }\)

Dla przykładu, zauważmy, że w zbiorze liczb całkowitych ujemnych wraz z zerem suma dwóch liczb z tego zbioru jest dalej w tym zbiorze, tzn. funkcja \(\displaystyle{ f:\left( \ZZ_{-} \cup \left\{ 0\right\}\right) \times \left( \ZZ _{-} \cup \left\{ 0\right\}\right) \rightarrow \ZZ _{-} \cup \left\{ 0\right\}, }\) dana jako:

\(\displaystyle{ f\left( x,y\right) = x+ y,}\)

jest działaniem wewnętrznym w zbiorze liczb całkowitych ujemnych wraz z zerem.

Okazuje się, że tą funkcję można zdefiniować indukcyjnie w następujący sposób:

\(\displaystyle{ \begin{cases} 0+n= n, \hbox { dla dowolnej liczby } n\in\ZZ _{-} \cup \left\{ 0\right\}; \\ n ^{-} + a= \left( n+a\right) -1=\left( n+a\right) ^{-};\end{cases} }\)

gdyż w zbiorze liczb całkowitych ujemnych wraz z zerem możemy zawsze odjąć jeden, bo w tym zbiorze nie ma liczby najmniejszej.

Przedstawię teraz formalizację tych obserwacji, a potem może o coś jeszcze spytam.


Niech \(\displaystyle{ A,B}\) będą niepustymi zbiorami,
a \(\displaystyle{ f _{0}: A \rightarrow B, \alpha : B \times \left[ \left( \ZZ _{-} \cup \left\{ 0\right\}\right) \times A \right] \rightarrow B }\) niech będą dowolnymi funkcjami.

Wykażemy, że istnieje dokładnie jedna funkcja \(\displaystyle{ h: \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times A \rightarrow B, }\)
spełniająca:

\(\displaystyle{ h\left( 0,a\right)= f _{0}\left( a\right)\textbf{*} , \hbox { dla dowolnego } a \in A ; }\) oraz:
\(\displaystyle{ h\left( x ^{-}, a \right) = \alpha \left( h\left( x,a\right); \left( x,a\right) \right)\textbf{*} ,\hbox{ dla dowolnych } x \in \ZZ _{-} \cup \left\{ 0\right\} \hbox{ i } a \in A. }\)

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ f _{0}: A \rightarrow B, }\) i niech \(\displaystyle{ \alpha : B \times \left[ \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times A \right] \rightarrow B. }\)

Definiujemy funkcję \(\displaystyle{ \alpha ': B \times \left( \NN \times A\right) \rightarrow B, }\) jako:

\(\displaystyle{ \alpha '\left( b, \left( n,a\right) \right) = \alpha \left( b, \left( -n,a\right) \right). }\)

Jak łatwo można się przekonać, funkcja \(\displaystyle{ \alpha '}\) jest dobrze określona.

Stosując do funkcji \(\displaystyle{ f _{0} }\) oraz do funkcji \(\displaystyle{ \alpha '}\) twierdzenie o definiowanie przez indukcje, którego treść jest

Kod: Zaznacz cały

https://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5%82ad_7:_Konstrukcja_von_Neumanna_liczb_naturalnych,_twierdzenie_o_indukcji,_zasady_minimum,_maksimum,_definiowanie_przez_indukcje
TUTAJ, na ważniaku otrzymujemy dokładnie jedną funkcję \(\displaystyle{ g:\NN \times A \rightarrow B,}\) spełniającą:

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

Zdefiniujmy funkcję \(\displaystyle{ h:\left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times A \rightarrow B}\), jako:

\(\displaystyle{ h \left( n,a\right)= g\left( -n,a\right). }\)

Funkcja \(\displaystyle{ h}\) jest oczywiście dobrze określoną funkcją.

I mamy:

\(\displaystyle{ h\left( n ^{-},a \right)= g\left( -n,a\right)=g \left( - \left( n-1\right), a \right)= g \left( -n+1, a\right) = \alpha '\left( g\left( -n,a\right) ; \left( -n,a\right) \right)= \alpha \left( g \left( -n,a\right); \left( - \left( - n\right)= n,a \right) \right)\stackrel {h\left( n,a\right) = g\left( -n,a\right) }{=} \\ =\alpha \left( h\left( n,a\right); \left( n,a\right) \right). }\)

Jak również mamy, dla dowolnego \(\displaystyle{ a \in A}\), mamy:

\(\displaystyle{ h\left( 0,a\right)= g\left( -0,a\right) = g\left( 0,a\right)= f _{0}\left( a\right).}\)

co kończy dowód istnienia takiej funkcji.


Aby pokazać, że taka funkcja jest jedyna, to weźmy dwie funkcje \(\displaystyle{ h _{1}, h _{2}: \left( \ZZ _{-} \cup \left[ 0\right] \right) \times A \rightarrow B}\), spełniające równości \(\displaystyle{ \textbf{*}}\) oraz \(\displaystyle{ \textbf{**},}\) i pokażmy, że są równe.

Mamy \(\displaystyle{ f _{0}: A \rightarrow B.}\)

Zdefiniujmy funkcję

\(\displaystyle{ \alpha ': B \times \left( \NN\times A\right) \rightarrow B, }\) jako:

\(\displaystyle{ \alpha '\left( b, \left( n,a\right) \right)= \alpha \left( b, \left( -n,a\right) \right) \in B. }\)

Z twierdzenia o definiowaniu przez indukcje dla liczb naturalnych wynika, że istnieje dokładnie jedna funkcja \(\displaystyle{ h': \NN \times A \rightarrow B,}\) spełniającą:

\(\displaystyle{ h'\left( 0,a\right)= f _{0}\left( a\right), }\) i
\(\displaystyle{ h' \left( n', a\right)= \alpha ' \left( h'\left( n,a\right) ; \left( n,a\right) \right) . }\)

Zdefiniujmy dwie funkcje:

\(\displaystyle{ h' _{1}, h' _{2}: \NN \times A \rightarrow B, }\) jako:

\(\displaystyle{ h' _{1} \left( n,a\right)= h _{1} \left( -n,a\right), }\) i podobnie:
\(\displaystyle{ h' _{2} \left( n,a\right) = h _{2} \left( - n,a\right). }\)

Wykażemy, że te funkcje spełniają odpowiednie obydwie równosci.

Mamy:

\(\displaystyle{ h' _{1}\left( 0,a\right)=h _{1}\left( -0,a\right)= h _{1} \left( 0,a\right)= f _{0} \left( a\right), \hbox { dla dowolnego } a \in A; }\)

oraz:

\(\displaystyle{ h' _{1}\left( n',a\right)= h _{1}\left( -n-1,a\right) = h _{1}\left( \left( -n\right) ^{-}, a \right) = \alpha \left( h _{1} \left( -n,a \right) \left( -n,a\right) \right) = \alpha ' \left( h _{1} \left( -n,a\right); \left( - \left( -n\right) = n,a\right) \right) \stackrel {h _{1} \left( -n,a\right)= h' _{1}\left( n,a\right) }{=} \alpha ' \left( h' _{1}\left( n,a\right); \left( n,a\right) \right). }\)

A więc funkcja \(\displaystyle{ h' _{1} }\) spełnia obydwie równości.

W sposób symetryczny pokazujemy, że funkcja \(\displaystyle{ h' _{2} }\) spełnia obydwie równości.

Ponieważ istnieje dokładnie jedna a więc tylko jedna funkcja spełniająca te obydwie równości, więc \(\displaystyle{ h' _{1}= h' _{2}. }\)

Aby pokazać, że \(\displaystyle{ h _{1}= h _{2}, }\) to weźmy parę \(\displaystyle{ \left( x,a\right) \in \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times A, }\) i pokażmy, że te funkcje na tej parze przyjmują te same wartości.

Mamy: \(\displaystyle{ \left( -x\right) \in \NN ,}\) a zatem \(\displaystyle{ \left( -x,a\right) \in \NN \times A, }\) więc ponieważ \(\displaystyle{ h' _{1}= h' _{2}, }\) to \(\displaystyle{ h' _{1} \left( - x,a\right) =h' _{2} \left( -x,a\right).}\)

A zatem:

\(\displaystyle{ h _{1}\left( x,a\right) = h _{1} \left( -\left( -x\right) ,a\right)= h' _{1} \left( -x,a\right)= h' _{2} \left( -x,a\right)= h _{2}\left( -\left( -x\right), a \right)= h _{2}\left( x,a\right), }\)

co wobec dowolności wyboru pary \(\displaystyle{ \left( x,a\right) \in \left( \ZZ _{-} \cup \left[ 0\right] \right) \times A ,}\) daje, że \(\displaystyle{ h _{1}= h _{2}.\square }\)


Jako przykład zastosowania tego twierdzenia możemy zdefiniować działanie dodawania w zbiorze liczb całkowitych ujemnych wraz z zerem, tzn. funkcję dwóch zmiennych \(\displaystyle{ f}\) daną jako:

\(\displaystyle{ f\left( x,y\right)= x+y. }\)

Aby taką funkcję zdefiniować w sposób indukcyjny stosujemy powyższe twierdzenie do zbiorów \(\displaystyle{ A= B= \ZZ _{-} \cup \left\{ 0\right\}, }\) oraz do funkcji \(\displaystyle{ f _{0}: A \rightarrow B, }\) danej jako:

\(\displaystyle{ f _{0}\left( a\right)= a, }\)

I do funkcji

\(\displaystyle{ \alpha: \ZZ _{-} \cup \left[ 0\right] \times \left[ \left( \ZZ _{-} \cup \left\{ 0\right\}\right) \times \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \right] \rightarrow \ZZ _{-} \cup \left\{ 0\right\} }\),

danej jako:

\(\displaystyle{ \alpha \left( b,\left( x,a\right) \right) =b-1=b ^{-} .}\)

Na mocy powyższego twierdzenia istnieje dokładnie jedna funkcja \(\displaystyle{ h: \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times \left( \ZZ _{-} \cup \left\{ 0\right\}\right) \rightarrow \ZZ _{-} \cup \left\{ 0\right\}}\), taka, że:

\(\displaystyle{ h\left( 0,n\right) =n,}\) i
\(\displaystyle{ h \left( n ^{-},a \right) = \alpha \left( h\left( n,a\right) ; \left( n,a\right) \right)= h\left( n,a\right)-1, }\)

czyli zapisując tą funkcję w sposób rekurencyjny:

\(\displaystyle{ \begin{cases} 0+n=n, \\ n ^{-}+a= \left( n+a\right) -1. \end{cases} }\)

Czyli jest to dodawanie w zbiorze liczb całkowitych ujemnych wraz z zerem . 8-)


I teraz spytam:

Jeśli mamy niepusty zbiór \(\displaystyle{ B,}\) to wydaje się, że funkcję na zbiorze liczb całkowitych i o wartościach w tym zbiorze \(\displaystyle{ B}\), możemy
taką funkcję zdefiniować indukcyjnie. W tym celu definiujemy wartość funkcji dla \(\displaystyle{ 0}\), i dalej na podstawie tej wartości definiujemy wartość funkcji dla \(\displaystyle{ x=1}\) oraz dla \(\displaystyle{ x=-1}\), itd. ... zakładając, że dla \(\displaystyle{ n \in \NN}\) funkcja ta jest określona dla liczb całkowitych od \(\displaystyle{ - n}\) do \(\displaystyle{ n,}\) definiujemy wartość funkcji dla \(\displaystyle{ - n-1}\) oraz dla \(\displaystyle{ n+1}\). Dzięki temu zdefiniujemy tą funkcję na całym zbiorze liczb całkowitych. Jest sens formalizować tą obserwację :?:

Wydaje się też, że dla dużych \(\displaystyle{ n \in \NN}\) skończony ciąg \(\displaystyle{ f _{1}, f _{2}, \ldots, f _{n} }\) możemy zdefiniować w sposób indukcyjny. W tym celu definiujemy najpierw wartość \(\displaystyle{ f _{1}}\), i dla dowolnego \(\displaystyle{ 1\le i< n}\) naturalnego, zakładając, że zdefiniowana jest wartość \(\displaystyle{ f\left(i \right)}\) definiujemy wartość \(\displaystyle{ f\left( i+1\right)}\) . Łatwo można przekonać się, że w ten sposób zdefiniujmy ciąg \(\displaystyle{ f _{1}, f _{2}, \ldots, f _{n} }\) Ma to tą zaletę, w przeciwieństwie do ręcznego zdefiniowania ciągu skończonego, że działa to również wtedy, gdy \(\displaystyle{ n}\) jest duże.
ODPOWIEDZ