Matematické Fórum

↑↑ marie.kolinova:

Už to chápu.

Máme dokázat výrok pro n vektorů:

V(n):   n lineárně nezávislých vektorů není možné vyjádřit lin. kombinací n-1 vektorů

Výrok pro n+1 vektorů zní:

V(n+1): n+1 lineárně nezávislých vektorů není možné vyjádřit lin. kombinací n vektorů.

Máme dokázat implikaci  V(n) ==> V(n+1)

Důkaz : předpokládáme negaci V(n+1), tj. že to možné je (rovnost 1). A zjistíme, že n lineárně nezávislých vektorů je možné vyjádřit lin. kombinací n-1 vektorů, tj. odvodili jsme negaci V(n).

Implikaci  V(n) ==> V(n+1) jsme dokázali tím, že  jsme dokázali non V(n+1) ==> non V(n).

Dokázali jsme obměnu implikace, tj. použili jsme tzv. nepřímý důkaz, nikoliv důkaz sporem.

Čili důkaz je prováděn dobře, ale ve skriptu je popisována jiná důkazová technika, než která byla prováděna.

Vznesl bych v tomto smyslu dotaz na vyučujícího :-)

Eratosthenes napsal(a):

Implikaci  V(n) ==> V(n+1) jsme dokázali tím, že  jsme dokázali non V(n+1) ==> non V(n).

Já úplně nesouhlasím. Ano, dokázali jsme, že non V(n+1) ==> non V(n). Ale to nestačí. Zároveň jsme dokázali, že non V(1) neplatí (mě se teda víc líbí dokázat, že non V(2) neplatí) takže nemůže platit ani non V(n+1).


Celé to zní dost zmateně, takže bych navrhoval zavést nové výroky W(n) = non V(n) a W(n+1) = non V(n+1).

A pak jsme tedy dokázali, že když platí W(n+1) platí i W(n). Což je normální indukce, akorát směrem dolů. Což by tedy znamenalo, že když to platí pro nějaké n, musí to platit i pro všechna nižší. Jenže víme, že pro n=2 to neplatí, nebo že pro n=1 to neplatí, takže to nemůže platit ani pro ta vyšší. Takže W(n+1) neplatí. Tedy V(n+1) platí.

Každopádně souhlasím s tím, že text, který je k důkazu uveden tak nějak úplně neodpovídá tomu, co se tam dělá.

check_drummer napsal(a):

Ten spor je jasný, označme si to tvrzení co cheme dokázat jako V(n). Pro spor předpokládáme negaci indukčního kroku, tedy že pro nějaké n platí V(n) a nonV(n+1). Ale my jsme z nonV(n+1) odvodili nonV(n), což je spor. Taky by se to dalo chápat tak, že jsme dokázali obměnu implikace z indukčního kroku.

Hele, když to přeženu, tak to co tvrdíš (a autor skript vlastně taky) je toto:

1) Předpokládejme že platí výrok V(n).

2) Teď předpokládejme, že platí výrok non V(n+1)

3) Z výroku non V(n+1) plyne platnost výroku non V(n) - což je spor s předpokladem 1)


Jenže to je přece blbost, celé.
Bod 1) a bod 2) jsou už samy v rozporu. Mezi výroky V(n) a V(n+1) není žádný rozdíl, je přece úplně jedno, jaké číslo tam dosadíme. Takže jinými slovy tvrdíme, že výrok V(n) platí, pak že neplatí a pak že je to v rozporu s tím, že platí. Takhle to prostě nemůže být.


Podle mě je to ve skutečnost tak, že bod 1) má být jen to, že platí výrok V(1). A to není předpoklad, to lze dokázat.

Pánové, prosím, nechte toho.

Tíma založila ↑↑ marie.kolinova: a chtěla něco vyjasnit. Jasné jí to včera bylo a teď je v tom zase guláš. Takže tady a teď toho prosím nechejte a pokud to chce někdo dál rozebírat, ať si založí vlastní téma.

↑ MichalAld:
Chceme dokázat
(#) (pro všechna n)(V(n)=>V(n+1)).
Dokážeme ekvivaletní tvrzení (pro všechna n)(nonV(n+1)=>nonV(n)).
Případně budeme postupovat sporem a budeme předpokládat, že dokazované tvrzení (#) neplatí, tedy zvolíme nejmenší takové n0, pro které platí něgace tvrzení (#) uvnitř kvantifikátoru, tedy V(n0) a nonV(n0+1). Ale z nonV(n0+1) odvodíme nonV(n0), což je spor, protože V(n0) platí.

(Tvrzení V(n) je samo kvantifikovaný výraok, protože hovoří "o všech vektorech, jejichž počet je n ....".)

check_drummer napsal(a):

↑ Eratosthenes:
Ono ale v konkrétním případě jde o to jak je ten důkaz veden.

To jistě, ale tady byl problém v tom, že důkaz byl dle použitých rovnic veden nějak (správně), ale slovně byl popisován jiný typ důkazu. Takže jako celek to bylo zmatečné. Proto jsme to tak dlouho nemohli pochopit.

Mně je to takto jasné, téma zakládat nebudu, ale do případně založeného tématu se asi zapojím.

↑ MichalAld:
Není, zapomněl jsem na tu druhou negaci.

check_drummer napsal(a):

↑ MichalAld:
Chceme dokázat
(#) (pro všechna n)(V(n)=>V(n+1)).
Dokážeme ekvivaletní tvrzení (pro všechna n)(nonV(n+1)=>nonV(n)).
Případně budeme postupovat sporem a budeme předpokládat, že dokazované tvrzení (#) neplatí, tedy zvolíme nejmenší takové n0, pro které platí něgace tvrzení (#) uvnitř kvantifikátoru, tedy V(n0) a nonV(n0+1). Ale z nonV(n0+1) odvodíme nonV(n0), což je spor, protože V(n0) platí.

(Tvrzení V(n) je samo kvantifikovaný výrok, protože hovoří "o všech vektorech, jejichž počet je n ....".)

Takže teď už jsme možná dospěli ke shodě.

1) Dokážeme ekvivaletní tvrzení (pro všechna n)(nonV(n+1)=>nonV(n)).

Jen je třeba si uvědomit, že výrok V(n+1) zní přesně jako:
Neplatí, že je možné (n+1) nezávislých vektorů vytvořit lineární kombinací (n) vektorů.

Takže výrok non V(n+1) zní:
Neplatí, že neplatí, že že je možné (n+1) nezávislých vektorů vytvořit lineární kombinací (n) vektorů. Tedy že je možné možné (n+1) nezávislých vektorů vytvořit lineární kombinací (n) vektorů.

Z toho dokážeme výrok non V(n), tedy:
Je možné možné (n) nezávislých vektorů vytvořit lineární kombinací (n-1) vektorů.
Což tedy zpátky znamená, že:
Neplatí, že neplatí, že je možné možné (n) nezávislých vektorů vytvořit lineární kombinací (n-1) vektorů.

2) No a teď ještě musíme ukázat ten spor, tedy že pro nějaké konkrétní n, třeba 1, nebo 0, věta:
Neplatí, že je možné (n+1) nezávislých vektorů vytvořit lineární kombinací (n) vektorů.
platí. Tedy že to není možné.

↑ MichalAld:

Eratosthenes napsal(a):

Pánové, prosím, nechte toho.

Takže tady a teď toho prosím nechejte a pokud to chce někdo dál rozebírat, ať si založí vlastní téma.

check_drummer napsal(a):

↑ Eratosthenes:

Ok, založme další téma, pokud v tom někdo chce pokračovat.

No vždyť o tom to celé je, ta stránka v odkazovaných skriptech. Důkaz pro všechna n.

A nebo nerozumím tomu co říkáš.

check_drummer napsal(a):

↑ MichalAld:
Ten spor ale nedokazuješ tak že bys našel konkrétní n. je to spíš obměna implikace.

Jak to, že né? Našel jsem konkrétní n, třeba n=1, nebo n=2.

Zapomeňme co je v těch skriptech. Já jsem prostě našel n, pro které to neplatí.

Máme dokázané (indukcí) že když to platí pro (n), tak to platí i pro (n-1). Z čehož tedy automaticky plyne, že když to pro (n-1) neplatí, tak to neplatí ani pro (n).

A zároveň jsme dokázali, že to pro n=1 neplatí. Takže to neplatí ani pro žádné vyšší n.

Co je na tom špatně?

↑ MichalAld:
Pokud dokážeš indukcí ten krok z n do n-1, tak pak ano, ale pak už žádný spor nebude potřeba, už to bude dokázané. Ale nevím co myslíš tím "to" - dokazuješ to tvrzení co se chce dokázat (V), nebo jeho negaci? Dokazuješ pro všechna n V(n)=>V(n-1) a nebo nonV(n)=>nonV(n-1)?