Důkaz indukcí

Tento článek je o obecném matematickém principu společném různým důkazovým metodám. O nejpoužívanější metodě tohoto druhu pojednává článek Důkaz matematickou indukcí.

Důkaz indukcí je obecná metoda dokazování matematických vět. Spočívá v prokázání nějakého tvrzení typu „pro všechny objekty jisté třídy platí…“ způsobem, při němž se objekty dané třídy rozdělí do několika (většinou nekonečně mnoha) podtříd, které se uspořádají do posloupnosti a ukáže se o nich:

  1. (první krok) Pro všechny objekty z první podtřídy platí …
  2. (indukční krok) Jestliže platí … pro všechny objekty z předcházejících podtříd, pak platí … i pro všechny objekty z podtřídy bezprostředně za nimi následující.

Důkaz indukcí se typicky používá k důkazům takových univerzálních tvrzení (tj. tvrzení tvaru „Pro každé x platí…“), pro které existuje nějaký snadno dokazatelný speciální případ (tj. takové x, že o x platí…) a zároveň každý další složitější případ je v konečně mnoha krocích převeditelný na platnost pro speciální případ s tím, že počet kroků v tomto převedení se s rostoucí složitostí případu zvyšuje.

Souvislost s principem minimality

Princip indukce úzce souvisí s vlastnostmi uspořádání a relací vztahujících se k existenci minimálních prvků, jakými jsou dobrost nebo fundovanost. Princip indukce totiž může být také přeříkán následujícím způsobem nazývaným princip minimality: „Pokud dané tvrzení platí pro nějaký objekt, pak existuje podtřída obsahující objekt, pro nějž tvrzení platí, taková, že pro všechny objekty předchozích podtříd tvrzení neplatí.

Důkazy, že tyto dva principy vyjadřují tutéž skutečnost, se liší pro různé druhy indukcí. Podstata však zůstává vždy stejná:

  • Platí-li princip minimality, pak platí princip indukce:
    Nechť nějaké tvrzení splňuje jak první tak indukční krok principu indukce, ale neplatí pro něj závěr tohoto principu, tj. existuje objekt, pro nějž toto tvrzení neplatí. Pak tento objekt je takový, že pro něj platí negace tvrzení. Tedy podle principu minimality existuje podtřída obsahující objekt, pro nějž platí negace tvrzení, taková, že pro všechny objekty předcházejících podtříd neplatí negace tvrzení. Tedy existuje objekt, který je prvkem nějaké podtřídy takové, že pro všechny objekty předchozích podtříd tvrzení platí. Pak podle indukčního kroku platí i pro tento objekt, což je spor.
  • Platí-li princip indukce, pak platí princip minimality:
    Nechť existuje nějaký objekt, pro nějž dané tvrzení platí, ale neexistuje takový, pro nějž tvrzení platí a pro všechny objekty předcházejících podtříd neplatí. Pak jistě tvrzení neplatí pro žádný objekt z první podtřídy, neboť pro něj žádné předcházející podtřídy neexistují, a tedy by protiřečil výše zmíněnému. Tedy pro objekty z první podtřídy platí negace tvrzení. Nechť dále tvrzení neplatí pro žádné objekty podtříd předcházejících nějaké podtřídě zvolené. Pak také neplatí pro žádné objekty zvolené podtřídy, neboť jinak by to opět odporovalo výše zmíněnému. Ukázali jsme tedy, že pokud platí negace tvrzení pro všechny objekty z předcházejících podtříd, platí i pro všechny objekty podtřídy bezprostředně za nimi následující. Podle principu indukce pak platí negace tvrzení pro všechny objekty, tedy neexistuje objekt, pro nějž tvrzení platí, což je spor.

Druhy důkazů indukcí

Existuje mnoho druhů důkazů indukcí:

Související články

Read other articles:

Peta Socourt. Socourt merupakan sebuah komune di departemen Vosges yang terletak pada sebelah timur laut Prancis. Lihat pula Komune di departemen Vosges Referensi INSEE lbsKomune di departemen Vosges Les Ableuvenettes Ahéville Aingeville Ainvelle Allarmont Ambacourt Ameuvelle Anglemont Anould Aouze Arches Archettes Aroffe Arrentès-de-Corcieux Attignéville Attigny Aulnois Aumontzey Autigny-la-Tour Autreville Autrey Auzainvilliers Avillers Avrainville Avranville Aydoilles Badménil-aux-Bois ...

 

Perwakilan Iwakura. Kepala perwakilannya adalah Iwakura Tomomi, tampil dalam gambar ini sedang mengenakan pakaian Jepang tradisional. Perwakilan Iwakura atau Perwakilan Diplomatik Iwakura (岩倉使節団, Iwakura Shisetsudan) adalah sebuah perjalanan diplomatik Jepang di seluruh dunia, yang dilakukan pada tahun 1871 oleh oligarki zaman Meiji. Perwakilan Iwakura mengikuti beberapa perwakilan sebelumnya yang dikirimkan oleh Keshogunan, seperti Perwakilan Diplomatik Jepang ke Amerika Serikat (1...

 

Untuk perusahaan induk yang dipisah dari DowDuPont pada tahun 2019, lihat Dow Inc. The Dow Chemical CompanyJenisPerusahaan swastaIndustriBahan kimiaDidirikan1897; 126 tahun lalu (1897)PendiriHerbert Henry DowKantorpusatMidland, Michigan, Amerika SerikatWilayah operasiSeluruh duniaTokohkunciJim Fitterling, Chairman dan CEOHoward Ungerleider, CFOProdukBahan kimia, plastik, bahan kimia performa, katalis, pelapis, eksplorasi hidrokarbonIndukDow Inc.AnakusahaUnion Carbide CorporationRohm and ...

У этого топонима есть и другие значения, см. Рускеала. ДостопримечательностьГорный парк «Рускеала»фин. “Ruskeala”-vuoripuisto Горный парк «Рускеала» осенью 2014 года.Вид на затопленный мраморный карьер. 61°56′46″ с. ш. 30°34′53″ в. д.HGЯO Страна  Россия Местоположение Сорта...

 

Stromatolit dari zaman Proterozoikum. Proterozoikum adalah eon yang mewakili suatu periode sebelum merebaknya kehidupan kompleks pertama di muka Bumi. Masa ini berlangsung antara 2500 sampai 542 (± 1) juta tahun yang lalu dan tadinya merupakan bagian dari masa Prakambrium. Proterozoikum didahului oleh eon Arkean dan dilanjutkan oleh Fanerozoikum dan terdiri dari tiga era yang berturut-turut dari yang paling tua: Paleoproterozoikum, Mesoproterozoikum, dan Neoproterozoikum. Proterozoikum2500 �...

 

Sami Al-Jaber Pelatih sepak bola Saudi Sami Aljaber, 2013Informasi pribadiNama lengkap Sami Abdullah Al-JaberTanggal lahir 11 Desember 1972 (umur 51)Tempat lahir Riyadh, Arab SaudiTinggi 1,77 m (5 ft 9+1⁄2 in)Posisi bermain PenyerangKarier junior1986–1988 Al-HilalKarier senior*Tahun Tim Tampil (Gol)1988–2008 Al-Hilal 305 (143)2000–2001 → Wolverhampton (pinjaman) 4 (0)Tim nasional1992–2006 Arab Saudi 163 (43) * Penampilan dan gol di klub senior hanya dihitu...

American attorney and state judge (born 1967) Erica H. MacDonaldUnited States Attorney for the District of MinnesotaIn officeJune 11, 2018 – February 28, 2021PresidentDonald TrumpJoe BidenPreceded byAndrew M. LugerSucceeded byAndrew M. LugerJudge of the First Judicial District of MinnesotaIn officeJanuary 15, 2010 – June 5, 2018Appointed byTim Pawlenty Personal detailsBornErica Irene Hinkle (1967-02-03) February 3, 1967 (age 57)[1]Greenwich, CTEducationUnive...

 

Neolithic monument in County Meath, Ireland For other uses, see Newgrange (disambiguation). NewgrangeSí an BhrúMap of Ireland showing the location of NewgrangeLocationCounty Meath, IrelandTypepassage graveWidth76 metres (249 ft)Area1.1 acre (0.5 hectare)Heightup to 12 metres (39 ft)HistoryFoundedc. 3200 BCPeriodsNeolithicSite notesExcavation dates1962–1975ArchaeologistsMichael J. O'KellyOwnershipOffice of Public WorksPublic accessyes (guided tour only) UNESCO Wor...

 

Overview of the manufacturing industry of the United States of America This article is part of a series on theEconomy of theUnited States Economic history Agricultural history Banking history Petroleum history Shipbuilding Industrial Revolution in the United States History of the United States dollar Lumber history Tariff History United States dollar § History History by state Sectors Primary sector Agriculture Energy Petroleum Electricity Mining Fishing Forestry Water and sanitation Seconda...

Subprefecture and commune in Île-de-France, FranceProvinsSubprefecture and communeThe historic center of the lower town seen from the Caesar tower. Coat of armsLocation of Provins ProvinsShow map of FranceProvinsShow map of Île-de-France (region)Coordinates: 48°33′37″N 3°17′56″E / 48.5604°N 3.299°E / 48.5604; 3.299CountryFranceRegionÎle-de-FranceDepartmentSeine-et-MarneArrondissementProvinsCantonProvinsIntercommunalityProvinoisGovernment • Ma...

 

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています(詳細)。 数字の大字(だいじ)は、漢数字の一種。通常用いる単純な字形の漢数字(小字)の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券(「壱」が大字) 弐千円日本銀行券(「弐」が大字) 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Gereja di Nerchinsk Eparki Nerchinsk adalah sebuah eparki Gereja Ortodoks Rusia yang terletak di Nerchinsk, Federasi Rusia. Eparki tersebut didirikan pada tahun 2014.[1] Referensi ^ http://www.patriarchia.ru/db/text/3894999.html lbsKeuskupan Gereja Ortodoks RusiaPatriark MoskwaEparki di Rusia Abakan dan Khakassia Akhtubinsk Alapayevsk Alatyr Alexdanrov Almetyevsk Amur Anadyr Ardatov Arkhangelsk Armavir Arsenyev Astrakhan Balashov Barnaul Barysh Belgorod Belyov Bezhetsk Birobidzhan Bir...

Israeli scholar of Islamic studies (born 1936) Yohanan Friedmann Yohanan Friedmann (born 1936) is an Israeli scholar of Islamic studies. Biography Friedmann was born in Zákamenné, Czechoslovakia and immigrated to Israel with his parents in 1949. He attended high school at the Reali School in Haifa (1945-1950). In 1956 he began his undergraduate studies at the Hebrew University of Jerusalem, Department of Arabic Language and Literature, receiving his B.A. in 1959. In 1962 he finished a maste...

 

Student radio station at the University of Illinois at Urbana–Champaign WPGUUrbana, IllinoisBroadcast areaChampaign–UrbanaFrequency107.1 MHzBrandingWPGU 107.1ProgrammingFormatAlternativeOwnershipOwnerIllini Media CompanyHistoryFirst air dateDecember 3, 1953; 70 years ago (1953-12-03) on carrier current AM 640April 17, 1967; 57 years ago (1967-04-17) on FM radioCall sign meaningParade Ground UnitsTechnical informationFacility ID28283ClassAERP3,000 wattsH...

 

  لمعانٍ أخرى، طالع ألبان (توضيح). ألبانمعلومات عامةنسبة التسمية ألبانيا التعداد الكليالتعداد 8.3 مليون نسمةمناطق الوجود المميزةالبلد  القائمة ... ألبانياكوسوفوصربياتركيامقدونيا الشماليةإيطاليااليونانألمانياسويسراالولايات المتحدةهولنداالجبل الأسودالسويدالمم�...

For other uses, see Freedom (disambiguation). Ability to act or change without constraint Four Freedoms, a series of 1943 paintings by Norman Rockwell honoring Franklin D. Roosevelt's Four Freedoms, meant to describe the freedoms for which allied nations fought in World War II. Part of a series onLiberalism Schools Classical Conservative Cultural Democratic Feminist Equity Green Internationalist Muscular National Neo Ordo Radical Religious Christian Catholic Islamic Jewish Secular Social Tech...

 

Brand of tequila produced in Mexico Don JulioTypePremium tequilaManufacturerDiageoCountry of origin MexicoIntroduced1942Proof (US)80VariantsBlanco, Reposado, Añejo, 1942, Real, 70 Tequila Don Julio, S.A. de C.V.Company typePrivateIndustryDistilled beveragesFoundedAtotonilco El Alto, Jalisco, Mexico (1942)Key peopleDon Julio Gonzalez Estrada, founderProductsTequilaWebsitewww.donjulio.com Don Julio is a brand of tequila produced in Mexico. It is the largest brand in value and eighth large...

 

Not to be confused with NEXTAR. American media company Nexstar redirects here. For the telescope brand, see Celestron. For similarly spelled subjects, see Next Star (disambiguation). Nexstar Media Group, Inc.FormerlyNexstar Broadcasting Group, Inc. (1996–2017)Company typePublicTraded asNasdaq: NXST (Series A)Russell 1000 componentS&P 400 componentIndustryMedia (television stations)PredecessorsQuorum BroadcastingNewport TelevisionGrant BroadcastingCommunications Corporation of Ameri...

Garden square in Dublin, Ireland Pearse SquarePearse Square, November 2017LocationDublin, IrelandArea1.35 acresCreated1839Operated byDublin City Council Pearse Square (Irish: Cearnóg an Phiarsaigh) is a Georgian garden square in Dublin, Ireland. It is bounded on its southern side by Pearse Street.[1][2] History Originally named Queen's Square after the newly crowned British Queen Victoria, the square consists of 48 houses, built between 1838 and 1855.[3][4 ...

 

Real Sporting de GijónCalcio Los Rojiblancos Segni distintiviUniformi di gara Casa Trasferta Terza divisa Colori sociali Rosso, bianco Dati societariCittà Gijón Nazione Spagna ConfederazioneUEFA Federazione FEF CampionatoSegunda División Fondazione1905 Proprietario Grupo Orlegi Presidente Alejandro Irarragorri Allenatore Miguel Ángel Ramírez StadioEl Molinón(29 800 posti) Sito webwww.realsporting.com PalmarèsSi invita a seguire il modello di voce Il Real Sporting de Gijón, ...