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:

$n+0=n$ ,

$k'+m=k+m'$ ,

$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$ ,

$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:

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

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

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

$k\cdot 0 = 0,$

$k\cdot m = 0$ wtedy i tylko wtedy, kiedy

$k=0\lor m=0,$

$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