Operacje na liczbach naturalnych

Definiowanie przez indukcję pozwala nam na wprowadzenie podstawowych operacji arytmetycznych na liczbach naturalnych. Jako pierwszą z tych operacji wprowadzimy dodawanie.

Dodawanie liczb naturalnych

Dodawanie jest funkcją dwuargumentową przekształcającą \( \mathbb{N} \times \mathbb{N} \) w \( \mathbb{N} \). Aby wykazać istnienie dodawania, korzystamy z twierdzenia o indukcji, kładąc za \( A \) i \( B \) zbiór liczb naturalnych \( \mathbb{N} \) i definiując \( f(n)=n \) oraz \( g(m,n,p) = m' \). Na mocy twierdzenia o definiowaniu przez indukcję istnieje funkcja \( h:\mathbb{N}^2 \rightarrow \mathbb{N} \) taka, że \( h(0,m) = m \) i \( h(n',m)= h(n,m)' \). Funkcja ta to dodawanie liczb naturalnych i będziemy używać zwyczajnej notacji \( h(n,m) = n+m \). Zgodnie z intuicją, dla dowolnej liczby naturalnej \( n \) mamy \( n' = n+1 \).

Jedyną udowodnioną w tej chwili własnością funkcji zapisywanej przez \( + \) są wynikające wprost z definicji własności. Wiemy, że,

\( 0+n = n, \)

dla każdego liczby naturalnej \( n \) oraz że,

\( n'+m = (n+m)', \) dla dowolnych liczb \( n \) i \( m \). Poniżej przedstawiamy parę podstawowych faktów dotyczących dodawania liczb naturalnych.

Fakt 7.1.

Jeśli suma dwóch liczb jest równa \( 0 \), to obie liczby muszą być równe \( 0 \).

Dowód

Załóżmy, że dla dwu liczb naturalnych \( n \) i \( m \) zachodzi \( n+m=0 \). Jeśli liczba \( n \) jest następnikiem jakiejś liczby naturalnej, to również \( n+m \) jest następnikiem jakiejś liczby i w związku z tym \( n+m\neq 0 \). Na podstawie Faktu 4.2. wnioskujemy, że \( n=0 \). Wtedy \( 0+m=m \) i otrzymujemy \( m=0 \), co należało wykazać.

Kolejny fakt mówi o łączności dodawania liczb naturalnych.

Fakt 7.2.

Dodawanie liczb naturalnych jest łączne. Formalnie:

\( \forall k \forall m \forall n\; (k\in\mathbb{N} \land m\in \mathbb{N} \land n\in \mathbb{N}) \Longrightarrow k+(m+n)=(k+m)+n. \)

Dowód

Dowód jest indukcją ze względu na \( k \).

Jeśli \( k=0 \), to \( 0+(m+n) = m+n \) oraz \( 0+m=m \) i w związku z tym \( (0+m)+n = m+n \), co należało pokazać.
Zakładamy, że równość jest prawdziwa dla \( k \) (dla

dowolnych \( m \) i \( n \)). Ustalmy dowolne liczby naturalne \( m \) i \( n \), wtedy:

\( k'+(m+n) = (k+(m+n))' = ((k+m) + n)' = (k+m)' +n = (k'+m) +n \)

gdzie druga równość wynika z założenia indukcyjnego, a wszystkie pozostałe równości z definicji funkcji \( + \).

Dzięki twierdzenie o indukcji matematycznej dodawanie jest łączne dla wszystkich liczb naturalnych.

Dalsze własności dodawania liczb naturalnych prezentujemy jako ćwiczenie.

Ćwiczenie 7.1

Dla dowolnych liczb naturalnych \( k,m \) i \( n \) udowodnij:

1. \( n+0=n \),

2. \( k'+m=k+m' \),

3. \( k+m = m+k \), czyli dodawanie jest przemienne,

4. jeśli \( k+n = m+n \), to \( k=m \), czyli dodawanie jest skracalne,

5. jeśli \( k>m \), to istnieje \( n>0 \) takie, że \( k=m+n \).

Rozwiązanie 1

Dowód 1

Dowodzimy przez indukcję na \( n \). Niewątpliwie \( 0+0= 0 \). Jeśli \( n+0 =n \), to \( n'+0=(n+0)' = n' \), gdzie druga równość wywodzi się z założenia indukcyjnego. Na mocy twierdzenia o indukcji \( n+0= n \), dla każdej liczby naturalnej \( n \).

Rozwiązanie 2

Dowód 2

Dowodzimy ten fakt przez indukcję na \( k \). Niewątpliwie, dla \( k=0 \) i dla dowolnego \( m \), mamy: \( 0'+m=(0+m)'=m'= 0+m' \). Pozostaje założyć, że fakt jest prawdą dla \( k \) i wykazać go dla \( k' \). Dla dowolnego \( m \):

\( k''+m = (k'+m)'=(k+m')=k'+m', \)

co dowodzi kroku indukcyjnego i całego faktu.

Rozwiązanie 3

Dowód 3

Przemienności dodawania dowodzimy przez indukcję na \( k \). Niewątpliwie, dla \( k=0 \) i dla dowolnego \( m \), mamy \( 0+m=m=m+0 \). Załóżmy teraz, że teza jest prawdziwa dla \( k \) i dla dowolnych \( m \). Ustalmy dowolne \( m \), wtedy:

\( k'+m = (k+m)' = (m+k)'= m'+k, \)

gdzie druga równość jest konsekwencją założenia indukcyjnego. Korzystając z poprzedniego ćwiczenia, dostajemy: \( m'+k=m+k' \), co dowodzi, że dla dowolnego \( m \) mamy \( k'+m=m+k' \). Używając twierdzenia o indukcji konkludujemy, że dodawanie w liczbach naturalnych jest przemienne.

Rozwiązanie 4

Dowód 4

Tę własność dowodzimy indukcją na \( n \). Jeśli \( n=0 \), to \( k+0=m+0 \) niewątpliwie implikuje, że \( k=m \). Załóżmy, że własność skracania zachodzi dla \( n \) (dla dowolnych \( k \) i \( m \)), wtedy:

\( k+n' = n'+k = (n+k)' = (k+n)' \)

i podobne rozumowanie jest prawdziwe dla \( m+n' \), dając,

\( (k+n)' = (m+n)'. \)

Na podstawie wcześniejszych ćwiczeń wiemy, że jeżeli następniki liczb są sobie równe, to liczby też muszą być równe, więc:

\( k+n = m+n. \)

Co, po zastosowaniu założenia indukcyjnego gwarantuje, że \( k=m \). Twierdzenie o indukcji powoduje, że dodawanie jest skracalne.

Rozwiązanie 5

Dowód 5

Dowodzimy tego faktu przez indukcję na \( k \). Jeśli \( k \) jest równe \( 0 \), to nie istnieje \( m < k \), czyli teza jest prawdziwa. Załóżmy teraz, że teza jest prawdziwa dla \( k \) i dla wszystkich \( m < k \). Ustalmy \( k' \) i dowolne \( m < k' \). Jeśli \( m=k \), to bierzemy \( n=1 \) i \( k' = m +1 \) dowodzi kroku indukcyjnego. Jeśli \( m < k \), to, na podstawie założenia indukcyjnego, istnieje \( n \) takie, że:

\( k = m+n. \)

Wtedy \( k' = (m+n)' = m+n' \), co otrzymujemy, korzystając z poprzednich identyczności. Krok indukcyjny został dowiedziony i, na podstawie twierdzenia o indukcji, fakt jest prawdą dla wszystkich liczb naturalnych.

Ćwiczenie 7.2

Wykaż, że dla dowolnych liczb naturalnych \( k \) i \( n \):

1. jeśli \( n \neq 0 \), to \( k+ n > k \),

2. \( k + n \geq k \).

Rozwiązanie 1

Dowód 1

Pierwszego punktu dowodzimy przez indukcję względem \( k \). Jeśli \( k=0 \) , to \( n = 0 + n > 0 \), dla dowolnego \( n\neq 0 \). Dla dowodu kroku indukcyjnego załóżmy, że dla każdego \( n\neq 0 \) mamy \( k+n > k \). Ustalmy dowolne \( n\neq 0 \), wtedy \( k'+n = (k+n)' \), korzystając z faktu, że \( k+n> k \) dostajemy:

\( k'+n > k', \)
co należało wykazać.

Rozwiązanie 2

Dowód 2

Aby wykazać nierówność rozpatrujemy przypadki ze względu na \( n \). Jeśli \( n\neq 0 \) z poprzedniego podpunktu otrzymujemy, że \( k+n>k \), czyli \( k+n\geq k \). Jeśli \( n=0 \), to \( k+0 = k \geq k \), co kończy dowód.

Mnożenie liczb naturalnych

Podobnie do dodawania możemy zdefiniować mnożenie. Stosujemy twierdzenie o definiowaniu przez indukcję do \( A=B=\mathbb{N} \) oraz \( f(n) = 0 \) i \( g(m,n,p) = m + p \). Twierdzenie o definiowaniu przez indukcję gwarantuje istnienie funkcji \( h:\mathbb{N}^2 \rightarrow \mathbb{N} \) takiej, że:

\( h(0,m) = 0 \)

oraz:

\( h(n',m) = h(n,m) + m. \)

Funkcję \( h \) definiującą mnożenie oznaczamy w notacji infiksowej symbolem \( \cdot \) tak, że \( n\cdot m = h(n,m) \). Podobnie jak dla dodawania musimy wykazać własności dotyczące mnożenia liczb naturalnych, posługując się wyłącznie powyższą definicją.

Fakt 7.3.

Dla dowolnej liczby naturalnej \( k \) mamy \( k\cdot 1 = k \).

Dowód

Dowód tego faktu jest indukcją ze względu na \( k \). Jeśli \( k=0 \), to \( 0\cdot 1 = 0 \). Jeśli równość jest prawdą dla \( k \), to \( k'\cdot 1 = k\cdot 1 + 1 \), co, na mocy założenia indukcyjnego, jest równe \( k+1=k' \). Dowiedliśmy kroku indukcyjnego, a co za tym idzie całej identyczności.

Ćwiczenie 7.3

Wykaż, że dla dowolnych liczb naturalnych \( k,m \) i \( n \) zachodzi:

1. \( k\cdot (m+n) = k\cdot m +k\cdot n \) - dodawanie jest rozdzielne względem mnożenia z prawej strony,

2. \( (k+m)\cdot n = k\cdot n + m\cdot n \) - dodawanie jest rozdzielne względem mnożenia z lewej strony,

3. \( k\cdot(m\cdot n) = (k\cdot m)\cdot n \) - mnożenie jest łączne,

4. \( k\cdot 0 = 0, \)

5. \( k\cdot m = 0 \) wtedy i tylko wtedy, kiedy \( k=0\lor m=0, \)

6. \( k\cdot m = m\cdot k \) - mnożenie jest przemienne,

7. jeśli \( k\cdot n = m\cdot n \) i \( n\neq 0 \) to \( k=m \).

Rozwiązanie 1

Dowód 1

Pierwszego faktu dowodzimy przez indukcję na \( k \). Jeżeli \( k=0 \), to zarówno \( 0\cdot (m+n) \) jak i \( 0\cdot m \) oraz \( 0\cdot n \) są równe zero i równość jest prawdziwa. Jeśli równość jest prawdziwa dla \( k \) i dla dowolnych \( m \) i \( n \), to dla \( k' \):

\( k'\cdot(m+n) =k\cdot(m+n) + (m + n) = (k\cdot m +k\cdot n) + (m +n) = \) na mocy założenia indukcyjnego i dalej:

\( = (k\cdot m +m) + (k\cdot n +n) = \)

używając przemienności i łączności dodawania. W końcu:

\( = k'\cdot m + k'\cdot n, \)

co należało pokazać dla kroku indukcyjnego. Twierdzenie o indukcji gwarantuje, że równość jest prawdą dla wszystkich \( k \).

Rozwiązanie 2

Dowód 2

Przedstawiamy dowód przez indukcję na \( k \). Jeśli \( k=0 \), to lewa strona równości jest równa \( (0+m)\cdot n= m\cdot n \), a prawa \( 0\cdot n + m\cdot n = 0 +m\cdot n = m\cdot n \), czyli równość jest prawdą. Jeśli równość jest prawdziwa dla \( k \) (przy dowolnych \( m \) i \( n \)) to dla \( k' \), (i dowolnych \( m \) i \( n \)):
\( (k'+m)\cdot n = (k+m)'\cdot n = (k+m)\cdot n + n=(k\cdot n + m\cdot n) + n = \)

korzystając z założenia indukcyjnego. Dalej, używając przemienności i łączności dodawania, dostajemy:

\( =(k\cdot n + n) + m\cdot n = k'\cdot n + m\cdot n, \)

co dowodzi kroku indukcyjnego i, co za tym idzie, prawdziwości tezy.

Rozwiązanie 3

Dowód 3

Dowód przez indukcję na \( k \). Jeśli \( k=0 \), to \( 0\cdot (m\cdot n) = 0 \), również \( 0\cdot m=0 \) i \( (0\cdot m)\cdot n=0 \), co dowodzi podstawy indukcji. Załóżmy teraz, że równość jest prawdą dla \( k \) i dla dowolnych \( m \) i \( n \). Ustalmy dowolne \( m \) i \( n \) i:

\( k'\cdot (m\cdot n) = k\cdot(m\cdot n) + (m\cdot n) = (k\cdot m)\cdot n + (m\cdot n)= \)

na mocy założenia indukcyjnego. Dalej:

\( = ((k\cdot m) +m)\cdot n = \)

na podstawie rozdzielności i:

\( = (k'\cdot m) \cdot n. \)

Co dowodzi kroku indukcyjnego i całej identyczności.

Rozwiązanie 4

Dowód 4
Dowód przez indukcję na \( k \). Jeśli \( k=0 \), to, oczywiście, \( 0\cdot 0 = 0 \) i teza jest spełniona. Załóżmy teraz, że \( k\cdot 0 = 0 \), mamy wtedy \( k'\cdot 0 = k\cdot 0 + 0 = 0 + 0 = 0 \) na podstawie założenia indukcyjnego i identyczności dotyczących dodawania.

Rozwiązanie 5

Dowód 5
Implikacja z prawej strony w lewą wynika z poprzedniego punktu i z definicji mnożenia. Dowodzimy implikacji w prawą stronę. Załóżmy, że \( k\cdot m = 0 \). Jeśli \( k=0 \), to implikacja jest prawdziwa. Jeśli \( k\neq 0 \), to, na podstawie Faktu 4.2., mamy: \( k=p' \), dla pewnego \( p \). Wtedy \( k\cdot m = p'\cdot m = p\cdot m + m = 0 \). Na podstawie Faktu 7.1. otrzymujemy \( m=0 \), co dowodzi implikacji w prawą stronę.

Rozwiązanie 6

Dowód 6

Aby dowieść przemienności mnożenia, stosujemy indukcję względem \( k \). Jeśli \( k=0 \), to \( 0\cdot m= 0 = m\cdot 0 \) (dla dowolnego \( m \)) na podstawie poprzedniego punktu. Załóżmy teraz, że teza jest prawdą dla \( k \) i dla dowolnych \( m \). Wtedy dla dowolnego \( m \) mamy:

\( k'\cdot m = k \cdot m + m = m \cdot k + m = \)

na podstawie założenia indukcyjnego. Dalej używamy rozdzielności i poprzednich punktów: \( m\cdot k + m\cdot 1 = m \cdot (k +1) = m\cdot k', \)

co należało wykazać. Krok indukcyjny jest dowiedziony, a co za tym idzie również cała identyczność.

Rozwiązanie 7

Dowód 7

Dowód jest indukcją ze względu na \( k \). Jeśli \( k=0 \), to \( 0\cdot n = m\cdot n \) implikuje, że \( m\cdot n =0 \). Ponieważ wiemy, że \( n\neq 0 \), to, używając poprzednich ćwiczeń, otrzymujemy: \( m=0 \), co dowodzi podstawy indukcji. Załóżmy teraz, że dowodzony fakt jest prawdą dla \( k \) (dla dowolnych \( m \) i \( n\neq 0 \)). Ustalmy dowolne \( m \) i \( n\neq 0 \) i załóżmy, że:

\( k'\cdot n = m \cdot n. \)

Liczba \( m \) nie może być równa zero, ponieważ \( k'\neq 0 \) i \( n\neq 0 \) i, co za tym idzie, \( k'\cdot n\neq 0 \). W związku z tym \( m=p' \), na podstawie Faktu 4.2.. W związku z tym, przekształcając powyższe równanie, dostajemy: \( k\cdot n + n = p \cdot n+n. \)
Używając, wcześniej wykazanej, skracalności dla dodawania liczb naturalnych otrzymujemy: \( k\cdot n= p \cdot n, \)
co, na mocy założenia indukcyjnego, implikuje \( k=p \), a więc \( k' = p'=m \), co należało wykazać.

Ćwiczenie 7.4

Wykaż, że dla dowolnych liczb naturalnych \( k \) i \( n \).

1. jeśli \( n > 1 \) i \( k\neq 0 \), to \( k\cdot n > k \),

2. jeśli \( n\neq 0 \), to \( k\cdot n \geq k \).

Rozwiązanie 1

Jeśli \( n>1 \), to \( n= p' \), dla pewnego \( p\neq 0 \), wtedy \( k\cdot n = n\cdot k = p'\cdot k = p\cdot k + k \), gdzie \( p\neq 0 \) i \( k\neq 0 \). Na podstawie wcześniejszych ćwiczeń dostajemy \( p\cdot k\neq 0 \) i w związku z tym \( p\cdot k + k> k \). Otrzymaliśmy \( k\cdot n > k \).

Rozwiązanie 2

Jeśli \( k=0 \), to \( k\cdot n = 0\cdot n = 0 \geq 0 = k \). Jeśli \( k\neq 0 \), to jedynym przypadkiem, w którym nie możemy zastosować poprzedniego twierdzenia jest \( n=1 \). Jeśli \( n=1 \), to, na podstawie Faktu 7.3. mamy, \( k\cdot 1 = k \), czyli teza jest prawdą również w tym przypadku.

Informatyka MIMUW