b'\n_START_ARTICLE_\nMatematisk induktion\n_START_SECTION_\nBevis med hj\xc3\xa4lp av v\xc3\xa4lordningsaxiomet\n_START_PARAGRAPH_\nDet \xc3\xb6vergripande beviset kan utf\xc3\xb6ras med en matematisk metod som kallas mots\xc3\xa4gelsebevis (latin: Reductio ad absurdum). F\xc3\xb6rst antas att motsatsen till det som skall bevisas \xc3\xa4r sann och sedan visas att detta leder till en mots\xc3\xa4gelse; ett p\xc3\xa5st\xc3\xa5ende som inte kan vara sant:_NEWLINE_Antag att A inte \xc3\xa4r lika med m\xc3\xa4ngden av alla positiva heltal. D\xc3\xa5 finns positiva heltal som inte tillh\xc3\xb6r m\xc3\xa4ngden A. Antag att dessa \xc3\xa4r elementen i  m\xc3\xa4ngden B; en icke-tom m\xc3\xa4ngd best\xc3\xa5ende av positiva heltal. Enligt v\xc3\xa4lordningsaxiomet f\xc3\xb6r de positiva heltalen inneh\xc3\xa5ller B ett minsta element, m. _NEWLINE_Eftersom m\xc3\xa4ngden A inneh\xc3\xa5ller talet 1, kan elementet m inte vara talet 1; det \xc3\xa4r d\xc3\xa4rf\xc3\xb6r st\xc3\xb6rre \xc3\xa4n talet 1. D\xc3\xa5 \xc3\xa4r elementet m - 1 ett positivt heltal som \xc3\xa4r mindre \xc3\xa4n talet m. Talet m - 1 kan inte tillh\xc3\xb6ra m\xc3\xa4ngden B, eftersom m - 1 d\xc3\xa5 vore det minsta elementet i B. D\xc3\xa4rf\xc3\xb6r m\xc3\xa5ste talet m - 1 tillh\xc3\xb6ra m\xc3\xa4ngden A. Men om elementet m - 1 ligger i m\xc3\xa4ngden A, ligger det efterf\xc3\xb6ljande talet (m - 1) + 1 ocks\xc3\xa5 i m\xc3\xa4ngden A, det vill s\xc3\xa4ga att talet m ligger i m\xc3\xa4ngden A. _NEWLINE_Det finns s\xc3\xa5ledes ett element m, som b\xc3\xa5de tillh\xc3\xb6r och inte tillh\xc3\xb6r m\xc3\xa4ngden A, vilket \xc3\xa4r en mots\xc3\xa4gelse. _NEWLINE_Det var d\xc3\xa4rf\xc3\xb6r fel att anta att m\xc3\xa4ngden A inte var lika med m\xc3\xa4ngden av positiva heltal._NEWLINE_Principen om matematisk induktion \xc3\xa4r d\xc3\xa4rmed bevisad.\n_START_SECTION_\nExempel\n_START_PARAGRAPH_\nInduktionsbevis anv\xc3\xa4nds ofta f\xc3\xb6r att bevisa att n\xc3\xa5got \xc3\xa4r sant f\xc3\xb6r alla naturliga tal.'