2016-01-25

Indukzio matematikoaren inguruan



Proposizio partikularretatik abiatuta proposizio orokorrak lortzeko jarraitutako prozesuari indukzioa deritzogu. Prozesu hau sarri erabiltzen dugu gure egunerokotasunean, gertaera partikularretan oinarrituta lege orokorrak inferitzeko; askotan justifikazio gabeko ondorioak ezarriz. Arrazoibide induktiboa besterik gabe aplikatzeak baditu bere  arriskuak, gezurrezkoak diren ondorioetara eraman gaitzakeelako.

Adibide 1
  1. 70 bostaren multiploa da
  2.  0-z amaitzen diren zenbakiak 5aren multiploak dira.

(1) proposizio partikularretik egiazkoa den (2) proposizio orokorra ondorioztatu da.

Adibide 2
  1.  70 bostaren multiploa da
  2.   Bi zifrako zenbaki guztiak 5aren multiploak dira.
Kasu honetan, ordea, (1) proposizio partikularretik gezurrezkoa den (2) proposizio orokorra ondorioztatu da.

 
Nola jokatu beharko genuke indukzioa aplikatzerakoan gezurrezko ondorioak ekiditzeko?

Erantzuna Indukzio Finituaren edo Indukzio Matematikoaren Printzipioak ematen digu. Metodo honek honela dio:

Izan bedi N zenbaki arrunten multzoan definituriko propietatea edo proposizioa: P(n). Aipatutako propietatea n zenbaki arrunt guztietarako egiaztatzen da baldin ondorengo bi baldintzak betetzen badira:
  1. P(n) egia da n=1 denean.
  2. Edozein n=k izanik, P(k) egiazkoa izateak (hipotesia), P(k+1) ere egia izatea dakar (tesia).


Aurreko baldintza bakoitzak bere esanahi propioa du. Lehenengo baldintzak indukzioarako oinarria ezartzen duen bitartean, bigarrenak orokortzeko justifikazioa ematen digu.

Lehenengo baldintza egiaztatu ezean, ez dago indukzio metodoa aplikatzerik oinarria falta delako. Bestela, "n = n +1, edozein zenbaki arrunt bere hurrengoaren berdina da" moduko baieztapen absurdoa egiaztatu ahal izango genuke:

n = k kasurako k = k + 1 egia dela suposatuko dugu. Bi aldeetan 1 batuz, k + 1 = k + 2; hau da,  n = k + 1 kasuan ere egiaztatzen da. Beraz, hasierako baiztapena "egia" da ("Zenbaki arrunt guztiak berdinak dira").

Bestetik, lehenengo baldintza betetzen bada eta bigarrena ez; orduan, nahiz eta idukzioa aplikatzeko oinarrik egon, ez dago orokortzeko justifikaziorik. 

Leonard Eulerrek zenbaki lehenak sortzen zituen P(n) = n^2 +n +41 polinomioa aurkitu zuen. Orduan, pentsa daiteke adierazpen honek zenbaki lehenak sortuko dituela n arrunt guztietarako. Hala da n-ren lekuan 0, 1, 2, 3,... eta 39 ordezkatzerakoan, zenbaki lehenak sortzen ditu. Baina, n = 40 denean zenbaki konposatua (P(40) = 1.681 = 41·41) ematen du.

Hau da, kasu partikularrek indukziorako oinarria finkatzen dute, baina ez dute inolaz ere justifikatzen lege orokor bat ondorioztatzerik.

Teoremaren lehenengo baldintzan n-ri "1" balioa emanez hasi gara; baina, hau ez da derrigorra. Nahitaezko dena da emandako proposizioa lehenengo elementu (n0) baterako egia izatea, indukzio prozesuak hasiera izan dezan. Beraz, n0 izan daiteke 1, 5, 20, 100,..., baita 0 eta negatiboa ere.
Indukzioaren printzioioa aplikatu ahal izateko ondo ordenatua den multzo bat bat behar da; hau da, ordenatua eta elementu minimoa izan behar du. Adibidez, 3 baino handiagoak diren zenbaki arrunten multzoa, zenbaki bakoitien multzoa, bostaren multiploak, etabar.
 



Aznenik, zenbait kasutan Indukzio Metodoaren baliokidea den aldaera bat erabili ohi da, Indukzio Metodo Osoa edo Indukzio Matematiko Sendoa. Metodo honetan, indukzioaren oinarrian lehenengo kasua (n0) baino kasu gehiago egiaztatu beharko dugu eta pauso induktiboan edo hipotesis induktiboan P(n0), P(n0+1), P(n0+2),..., P(k-1) eta P(k) egia direla suposatu dugu.  

Honela enuntzia daiteke:

Izan bedi P(n) proposizioa, non n zenbaki osoa eta positiboa den. Gainera, bitez n0 eta n1 (n0 = n1 edo n0 txikiago n1 ) bi zenbaki, biak osoak eta positiboak. Orduan:

  1. Baldin, P(n0), P(n0+1), P(n0+2),..., P(n1-1) eta P(n1) egia badira.
  2. Eta edozein n=k handiago edo berdin n1 izanik, P(n0), P(n0+1), P(n0+2),..., P(k-1) eta P(k) egiazkoak izateak, P(k+1) ere egia izatea baldin badakar.
Orduan, P(n) proposizioa egiaztatzen da n0 baino handiago edo berdinak diren n-ren balio guztientzat.

 Hona hemen adibide batzuk:



Bukatzeko, aurreko sarrera batean proposatutako "bi koloreen problema" eta beronen egiaztapena indukzioaren laguntzaz.


BI KOLOREEN PROBLEMA

 
 Marraztu orri batean nahi beste zuzen; argi dago,zuzen kopuru finitoa izango dugula. Adibidez,

Hainbat eskualdetan geratu da banatu orria. Mapa baten antzera eskualde bakoitza herrialde bat da. Bi kolore (gorria eta berdea) erabiliko ditugu mapa hau koloreztatzeko, baina baldintza bati jarraituz: muga zati bat (puntu bat ez da muga zatia) partekatzen duten herrialdeen kolorea desberdina izatea nahi da.

Gure adibidean, margotzeko era bat ondorengoa da:



Kasu honetan soluzio bat aurkitu dugu. Baina herrialde kopurua edozein izanda ere:


Posiblea al da margotzea jarritako baldintza errespetatuz? 

Nola?


Baiezko kasuan, bururatzen al zaizu estrategia edo prozedura bat, pausoz-pausoz jarraituta helburua lortzea ahalbideratuko duena?


Egiaztapena
 
  1. n=1 denean, hau da zuzen bakar bat marrazten bada, orria bi zatitan banatuta geratzen da; argi dagoenez, bi eremuak kolore desberdinez margotu daitezke.
  2. Demagun n=k zuzen marraztuta daudenean eremuak margotu ditzakegula eskatutako baldintzak errespetatuz (hipotesia).
  3. n=k+1 zuzenekin ea posiblea ote den nahi dugu egiaztatu (tesia).

Egiaztapena burutzeko ondorengo pausoak emango ditugu:

  • Hasiera batean k+1 zuzen marraztuko ditugu.
  • Ondoren, zuzen bat ezabatuko dugu (edozein).
  • Oraingoan, k zuzen daude eta hipotesiz koloreztatu dezakegu eskaturiko baldintzen arabera. Margotu eremuak.
  • Lehen ezabatutako zuzena berriz marraztu. Azken zuzen honek orri osoa bi zatitan banatzen du.
  • Zati batean dauden eremu itxi guztien kolorea aldatu (gorria berdez eta alderantziz)
  • Beste zatiko koloreak utzi aldatu barik.
  • Amaitu dugu, k+1 zuzenekin ere orria margotu dezakegu eskaturiko baldintzak errespetatuz. 
Emandako pausoak irudietan:

Indukzioz ebatzi eta egiaztatu ahal izan dugu bi koloreen problema.
*****