Dowód przez wyczerpanie - Proof by exhaustion

Dowód przez wyczerpanie , znany również jako dowód przez przypadek , analiza dowodu przez przypadek , całkowita indukcja lub metoda brutalnej siły , jest metodą dowodu matematycznego , w której zdanie , które ma zostać udowodnione , jest podzielone na skończoną liczbę przypadków lub zbiory równoważnych przypadków . i gdzie każdy rodzaj sprawy jest sprawdzany, aby sprawdzić, czy dana propozycja jest aktualna. Jest to metoda bezpośredniego dowodu . Dowód przez wyczerpanie zazwyczaj składa się z dwóch etapów:

  1. Dowód, że zbiór spraw jest wyczerpujący; tzn. że każde wystąpienie twierdzenia, które ma być udowodnione, odpowiada warunkom (co najmniej) jednego z przypadków.
  2. Dowód każdego z przypadków.

Rozpowszechnienie komputerów cyfrowych znacznie zwiększyło wygodę korzystania z metody wyczerpywania (np. pierwszy wspomagany komputerowo dowód twierdzenia o czterech kolorach w 1976 r.), chociaż takie podejście można również zakwestionować na podstawie matematycznej elegancji . Systemy eksperckie można wykorzystać do uzyskania odpowiedzi na wiele postawionych im pytań. Teoretycznie dowód metodą wyczerpania może być stosowany, gdy liczba przypadków jest skończona. Jednakże, ponieważ większość zbiorów matematycznych jest nieskończona, metoda ta jest rzadko używana do wyprowadzania ogólnych wyników matematycznych.

W izomorfizmie Curry'ego-Howarda dowód przez wyczerpanie i analiza przypadku są związane z dopasowaniem wzorców w stylu ML .

Przykład

Dowód przez wyczerpanie może być użyty do udowodnienia, że ​​jeśli liczba całkowita jest sześcianem idealnym , to musi być wielokrotnością 9, 1 większą niż wielokrotnością 9 lub 1 mniejszą niż wielokrotność 9.

Dowód :
każdy doskonały sześcian jest sześcianem pewnej liczby całkowitej n , gdzie n jest wielokrotnością 3, 1 większą niż wielokrotnością 3 lub 1 mniejszą niż wielokrotność 3. Tak więc te trzy przypadki są wyczerpujące:

  • Przypadek 1: Jeśli n = 3 p , to n 3 = 27 p 3 , co jest wielokrotnością 9.
  • Przypadek 2: Jeśli n = 3 p  + 1, to n 3 = 27 p 3  + 27 p 2  + 9 p  + 1, czyli o 1 więcej niż wielokrotność 9. Na przykład, jeśli n  = 4 to n 3 = 64 = 9×7 + 1.
  • Przypadek 3: Jeśli n = 3 p  − 1, to n 3 = 27 p 3  − 27 p 2  + 9 p  − 1, czyli o 1 mniej niż wielokrotność 9. Na przykład, jeśli n = 5 to n 3 = 125 = 9×14 − 1. QED

Elegancja

Matematycy wolą unikać dowodów przez wyczerpanie dużą liczbą przypadków, które są postrzegane jako nieeleganckie . Ilustracją tego, jak takie dowody mogą być nieeleganckie, jest przyjrzenie się następującym dowodom, że wszystkie współczesne letnie igrzyska olimpijskie odbywają się w latach podzielnych przez 4:

Dowód : pierwsze współczesne letnie igrzyska olimpijskie odbyły się w 1896 r., a następnie co 4 lata (pomijając wyjątki, takie jak sytuacje, w których nie odbyły się igrzyska z powodu I i II wojny światowej, a Igrzyska Olimpijskie w Tokio w 2020 r. zostały przełożone na 2021 r. COVID-19 pandemii .). Ponieważ 1896 = 474 × 4 jest podzielne przez 4, następne igrzyska olimpijskie byłyby w roku 474 × 4 + 4 = (474 ​​+ 1) × 4, co również jest podzielne przez cztery i tak dalej (jest to dowód indukcji matematycznej ). Dlatego stwierdzenie jest udowodnione.

Dowodem na to może być także zmęczenie, wyliczając każdy rok, w którym odbyły się Letnie Igrzyska Olimpijskie i sprawdzając, czy każdy z nich można podzielić przez cztery. W sumie 28 Letnich Igrzysk Olimpijskich w 2016 roku jest dowodem wyczerpania z 28 przypadkami.

Oprócz tego, że jest mniej elegancki, dowód przez wyczerpanie będzie również wymagał dodatkowej walizki za każdym razem, gdy odbywają się nowe letnie igrzyska olimpijskie. Należy to skontrastować z dowodem przez indukcję matematyczną, która udowadnia twierdzenie w nieskończoność w przyszłość.

Liczba spraw

Nie ma górnego limitu liczby przypadków dozwolonych w dowodzie przez wyczerpanie. Czasami są tylko dwa lub trzy przypadki. Czasami mogą być tysiące, a nawet miliony. Na przykład rygorystyczne rozwiązanie łamigłówki szachowej końcowej partii może wymagać rozważenia bardzo dużej liczby możliwych pozycji w drzewie gry tego problemu.

Pierwszy dowód twierdzenia o czterech kolorach był dowodem wyczerpania z 1834 przypadkami. Dowód ten był kontrowersyjny, ponieważ większość przypadków była sprawdzana za pomocą programu komputerowego, a nie ręcznie. Najkrótszy znany dowód twierdzenia o czterech kolorach wciąż ma ponad 600 przypadków.

Ogólnie rzecz biorąc, prawdopodobieństwo błędu w całym dowodzie wzrasta wraz z liczbą przypadków. Dowód z dużą liczbą przypadków sprawia wrażenie, że twierdzenie jest prawdziwe tylko przez przypadek, a nie z powodu jakiejś podstawowej zasady lub związku. Inne rodzaje dowodów — takie jak dowód przez indukcję ( indukcja matematyczna ) — są uważane za bardziej eleganckie . Istnieje jednak kilka ważnych twierdzeń, dla których nie znaleziono innej metody dowodu, takie jak:

Zobacz też

Uwagi