Indukcja matematyczna

[edytuj]

Z Wikipedii

Skocz do: nawigacji, szukaj

W matematyce, termin indukcja matematyczna używany jest na określenie szczególnej metody dowodzenia twierdzeń (w najbardziej typowych przypadkach o liczbach naturalnych) ale także jest on używany na oznaczenie konstrukcji pewnych obiektów.

Wbrew nazwie, argumenty oparte na indukcji matematycznej nie są rozumowaniami indukcyjnymi, lecz dedukcyjnymi. Najstarszy znany dowód indukcyjny był podany przez Francesco Maurolico w pracy Arithmeticorum libri fuo w 1575. Maurolico udowodnił przez indukcję, że suma pierwszych n nieparzystych liczb naturalnych wynosi n².

Intuicje [edytuj]

Efekt domina

Zarówno definicje indukcyjne jak i twierdzenie o indukcji matematycznej można porównać do rozumowań krok po kroku, gdzie kroki są ponumerowane liczbami naturalnymi. Sedno dowodów indukcyjnych leży w uzasadnieniu, że w pierwszym kroku dane stwierdzenie jest prawdziwe, oraz że dla każdego
z prawdziwości twierdzenia dla kroku n wynika prawdziwość twierdzenia dla kroku n+1.

Często używaną ilustracją dla tego typu argumentacji jest efekt domina. Wyobraźmy sobie że ustawiliśmy szereg kamieni używanych do gry w domino tak, że stoją one jeden za drugim na krótszym boku. Musimy się upewnić, że popchnięcie jednego kamienia spowoduje jego przewrócenie, oraz zakładamy że dowolna ilość kamieni ustawiona jeden za drugim przewróci się po popchnięciu pierwszego z nich. Możemy teraz udowodnić dowodząc krok indukcyjny, że szereg powiększony o jedną kostkę dostawioną na końcu także się przewróci.

Twierdzenia o indukcji matematycznej [edytuj]

Następujące twierdzenia są natychmiastową konsekwencją bardzo intuicyjnej własności liczb naturalnych, stwierdzającej że w każdym niepustym zbiorze liczb naturalnych jest liczba najmniejsza.

Wersja podstawowa [edytuj]

Przypuśćmy, że P(n) jest pewnym wyrażeniem (czyli formułą w jakimś języku) w którym jedyną zmienną wolną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

(a) P(1) jest zdaniem prawdziwym oraz

(b) dla każdego
zachodzi implikacja

.

Wówczas P(n) jest prawdziwe dla każdej liczby naturalnej
.

Wariant zwany indukcją zupełną [edytuj]

Przypuśćmy, że P(n) jest pewnym wyrażeniem, w którym jedyną zmienną wolną jest n i dziedzina tej zmiennej zawiera wszystkie liczby naturalne. Załóżmy, że

(c) dla każdej liczby naturalnej
zachodzi implikacja

.

Wówczas P(n) jest prawdziwe dla każdego
.

Aksjomat czy twierdzenie? [edytuj]

Powyżej używaliśmy określenia Twierdzenie o Indukcji, ale w wielu źródłach można spotkać określenie Aksjomat Indukcji. Jaki jest więc rzeczywisty status indukcji: jest to twierdzenie czy też aksjomat? Odpowiedź na to pytanie zależy od kontekstu w którym jest ono stawiane.

W matematyce elementarnej, zastosowaniach matematyki czy też w matematyce dyskretnej dominuje tendencja do mówienia o Twierdzeniu o Indukcji Matematycznej, także z tego powodu, że w tych rozważaniach unika się przesadnej formalizacji. Często wprowadzając indukcję matematyczną podaje się wówczas dowód twierdzenia o indukcji przy założeniu dobrego uporządkowania liczb naturalnych (tzn zakładając, że każdy niepusty podzbiór zbioru liczb naturalnych zawiera element najmniejszy).

W logice, natomiast, (szczególnie gdy liczby naturalne są wprowadzane w oparciu o aksjomatykę Peano), traktujemy indukcję jako aksjomat (jeden z aksjomatów arytmetyki Peano). Zwykle chcemy aby rozwijana teoria była sformalizowana w logice pierwszego rzędu - w tym wypadku mamy do czynienia nie z jednym aksjomatem, ale z nieskończoną listą aksjomatów (indeksowanych formułami). Tak więc dla każdej formuły Φ wprowadzamy następujący aksjomat:

(gdzie S jest jedno argumentowym symbolem funkcyjnym, oznaczającym funkcję "następnika"). Należy zwrócić uwagę, że ta nieskończona lista aksjomatów jest wciąż znacznie słabsza od często formułowanej zasady indukcji w której kwantyfikuje się po wszystkich predykatach:

jeśli 0 jest elementem zbioru
oraz zbiór ten spełnia warunek
, to
.

Twierdzenie o definiowaniu indukcyjnym [edytuj]

Ważną konsekwencją zasady indukcji jest następujące twierdzenie uzasadniające poprawność definiowania rekurencyjnego:

Niech A będzie niepustym zbiorem i niech U będzie zbiorem wszystkich ciągów skończonych o wyrazach w A. Przypuśćmy, że dana jest funkcja
. Wówczas istnieje jedyna funkcja
taka, że dla każdej liczby naturalnej
mamy

.

Przypomnijmy, że symbol
oznacza obcięcie funkcji, a więc
jest zawężeniem funkcji g do pierwszych n liczb naturalnych (czyli jest to ciąg skończony długości n).

Jak stosujemy indukcję [edytuj]

Jeśli T(n) oznacza pewne twierdzenie mówiące o liczbach naturalnych n, to aby udowodnić, że twierdzenie to jest prawdziwe dla każdej liczby naturalnej n nie mniejszej od n₀ (samo n₀ może być równe 1 albo być inną ustaloną liczbą naturalną), wystarczy:

• dowieść, że jest ono prawdziwe dla liczby n₀, to znaczy sprawdzić, że zachodzi T(n₀).

• dla każdej liczby naturalnej n nie mniejszej od n₀, wychodząc z założenia, że twierdzenie to jest prawdziwe dla liczby n, wyprowadzić, że jest ono prawdziwe dla n + 1, chodzi bowiem o to, aby wykazać, że dla każdej liczby naturalnej n nie mniejszej od n₀ prawdziwa jest implikacja:
  

Dowód indukcyjny

[edytuj]

Z Wikipedii

Skocz do: nawigacji, szukaj

Dowód indukcyjny to rozumowanie matematyczne korzystające z zasady indukcji matematycznej.

Zwykle dowody indukcyjne stosowane są w dziedzinach blisko związanych z teorią liczb naturalnych, nie brak jednak dowodów indukcyjnych w innych dziedzinach matematyki. Poprawne rozumowanie indukcyjne wymaga nie tylko wykonania kroku indukcyjnego (porównaj: indukcja matematyczna), ale także podania co najmniej jednego szczególnego przypadku prawdziwości twierdzenia, które się dowodzi.

Przykład dowodu indukcyjnego [edytuj]

Twierdzenie:

Dowód

1.Sprawdzenie prawdziwości twierdzenia dla n=1

Powyższa równość jest prawdziwa, zatem twierdzenie jest prawdziwe dla n=1

2.Założenie indukcyjne. Zakładamy, że twierdzenie jest prawdziwe dla pewnej dodatniej liczby naturalnej k.

3.Teza indukcyjna. Twierdzenie dla k+1

4.Krok indukcyjny. Pokażemy, że jeśli twierdzenie jest prawdziwe dla k to jest prawdziwe także dla k+1

Na mocy założenia:
. Otrzymujemy zatem:

Sprawdziliśmy prawdziwość twierdzenia dla n=1; następnie przy założeniu, że twierdzenie jest prawdziwe dla k, pokazaliśmy, że jest ono prawdziwe dla k+1. Stąd, na mocy zasady indukcji matematycznej, twierdzenie jest prawdziwe dla wszystkich liczb naturalnych większych lub równych 1.

Funkcja różnowartościowa

[edytuj]

Funkcja różnowartościowa (injekcja, funkcja 1-1) to funkcja, która dla dowolnych dwóch różnych argumentów przyjmuje różne wartości.

Definicja formalna [edytuj]

Funkcja
jest różnowartościowa wtedy i tylko wtedy, gdy

.

W dowodach różnowartościowości funkcji (albo jej braku) stosuje się często równoważną formę powyższego warunku wynikającą z własności implikacji:

.

Przykłady [edytuj]

• Identyczność na dowolnym zbiorze (czyli odwzorowanie
  ),

• 
  , dla
  ,

• Każda funkcja liniowa różna od stałej, czyli każda funkcja postaci
  , gdzie
  .

Funkcja "na"

[edytuj]

Z Wikipedii

(Przekierowano z Surjekcja)

Skocz do: nawigacji, szukaj

W suriekcji każdemu elementowi przeciwdziedziny odpowiada co najmniej jeden element dziedziny

Funkcja „na” (surjekcja) - funkcja przyjmująca jako swoje wartości wszystkie elementy przeciwdziedziny.

Definicja [edytuj]

Niech X oraz Y będą dowolnymi zbiorami. Funkcja
odwzorowuje zbiór X na zbiór Y wtedy i tylko wtedy, gdy każdy element zbioru Y jest wartością funkcji w pewnym punkcie. Za pomocą notacji logicznej zapisuje się to jako:

,

co oznacza się często jako
lub
.

Warunkiem równoważnym jest pokrywanie się przeciwdziedziny z obrazem dziedziny, f(X) = Y, inaczej
.

Uwaga [edytuj]

Należy pamiętać, że to wybór przeciwdziedziny decyduje o suriektywności lub jej braku. Przyjrzyjmy się następującym funkcjom:

określonej wzorem f₁(x) = x² oraz

określonej wzorem f₂(x) = x².

Tylko druga z powyższych funkcji jest suriekcją, mimo że są one określone tym samym wzorem.

Zauważmy ponadto, że dowolna funkcja jest suriekcją, jeśli jako zbiór Y przyjmiemy zbiór jej wartości.

Przykłady [edytuj]

Niech
będzie zmienną rzeczywistą, wówczas poniższe funkcje są suriekcjami:

• 
  dla
  na
  ,

• 
  dla
  na
  ,

• 
  dla
  na
  ,

• 
  dla
  na
  ,

• 
  ,

• 
  .

Funkcja wzajemnie jednoznaczna

[edytuj]

Z Wikipedii

(Przekierowano z Bijekcja)

Brak wersji przejrzanej

Skocz do: nawigacji, szukaj

Bijekcja umożliwia jednoczesne sparowanie wszystkich elementów odwzorowywanych zbiorów.

Funkcja wzajemnie jednoznaczna (bijekcja) - funkcja będąca jednocześnie funkcją różnowartościową i "na". Innymi słowy, bijekcja to funkcja (relacja przyporządkowująca każdemu elementowi dziedziny dokładnie jeden element obrazu) taka, że każdemu elementowi obrazu odpowiada dokładnie jeden element dziedziny.

Definicja formalna [edytuj]

W teorii mnogości bijekcja definiowana jest jako podzbiór
iloczynu kartezjańskiego zbiorów X i Y, który spełnia następujące warunki:

• 
  .

• 
  .

• 
  .

• 
  .

Słownie: każdy element dziedziny musi być w relacji z dokładnie jednym elementem przeciwdziedziny i odwrotnie.

Wnioski [edytuj]

• Przeciwdziedzina jest równa obrazowi funkcji, Y = f(X).

• Funkcja jest bijekcją wtedy i tylko wtedy, gdy istnieje funkcja do niej odwrotna - również i ona jest bijekcją.

Grupa bijekcji [edytuj]

 Osobny artykuł: grupa permutacji.

Ponieważ działanie składania bijekcji danego zbioru jest łączne i jest ono automorfizmem, a każda bijekcja posiada jednoznacznie określoną do niej funkcję odwrotną, to spełnione są aksjomaty grupy. Grupę taką nazywa się grupą bijekcji tego zbioru i są to historycznie pierwsze rozważane grupy.

8

---