Dokaz s konstrukcijo

Sestavimo matematične objekte katerih obstoj želimo dokazati, ali pa sestavimo objekte iz katerih je razvidno da nekaj velja.

Primer

Trditev:

Za vsak n>4 obstaja dvojiško drevo s tremi listi.

Dokaz:

Recimo da drevesa rišemo kot je prikazano na zgornji sliki in vozlišča označujemo tako, da dobimo povezan seznam, ki se na

koncu razdeli v 2 vozlišči.

n=120

Vozlišča od 1-118 so povezana v seznam.

119, 120 pa sta oba povezana s 118.

Pospološimo:

Primer

Trditev:

Števil na intervalu [0,1) je enako mnogo kot vseh realnih števil; |[0,1)|=||

Dokaz:

Množici imata enako moč, kadar med njima obstaja bijektivna preslikava.

Vsako realno število lahko zapišemo tako:

r = ±

Definiramo preslikavo:

kjer z s določimo predznak (s=0 če r0; s=1 če r<0).

Vidimo da s tem vsako število iz množice realnih števil lahko preslikamo na interval [0,1).

Velja:

1. (ker se 0.2 ne da preslikati v )

2. (ker velja [0,1) )

Iz tega lahko sklepamo, da

Dokaz s protislovjem

Predpostavimo nasprotje trditve, ki jo želimo potrditi in to privedemo do protislovja(nesmisla).

Primer

Trditev:

Obstaja neskončno število praštevil.

Dokaz:

Predpostavimo, da poznamo vsa praštevila:

P = {2,3,5,...,p}, kjer je p zadnje praštevilo

Po definiciji obstajajo le praštevila in sestavljena števila(taka, ki jih lahko razstavimo na prafaktorje).

Če pomnožimo vsa praštevila iz P in prištejemo 1 dobimo število, ki se ga ne da razstaviti na prafaktorje iz množice P:

q = 2 * 3 * 5 * ... * p + 1

Torej je q praštevilo(ker ni sestavljeno), ali pa je q število, sestavljeno iz prafakotorjev, ki jih ni v množici P.

Oboje pomeni, da v množici P nimamo vseh praštevil in očitno je, da to velja za vsako končno množico praštevil.

Primer

Trditev:

Naravnih števil je manj kot realnih:

Dokaz:

Predpostavimo nasprotno:

Ker so

Če je res , potem obstaja bijekcija med in (kar pomeni da lahko bijekcijo zapišemo s tabelo)

Dokaz z indukcijo

Dokazujemo neko splošno lastnost, ki velja za števno neskončno množico.

Izberemo indukcijsko predpostavko in pokažemo da velja za t.i. bazo indukcije(osnoven primer) in naredimo indukcijski korak (izpeljemo za večji primer).