[slovíčkaření]
Habala v tom článku taky říká, že silná indukce existuje, a ty mu to popíráš.
Popírám to ve smyslu, že silnou indukcí lze dokázat jinou množinu tvrzení než slabou.
Tak to jsem rád, že jsi konečně uznal nepravdivost svého dřívějšího tvrzení
Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce.
[/slovíčkaření]
f(n) není definována korektně nebo nekorektně. f(n) je definována algoritmem.
f(0) = 0
f(n) = min( i(n), f(a) + f(b): a+b = n), a,b,n je z N, i(n) = nejnižší cena balení s i prvky,
Matematickou teorii, ve které se definuje algoritmem, bohužel neznám. Já používám teorii množin, kde se může definovat rekurzí, kterážto je úzce spojena s principem indukce. (pokud bys nevěděl o čem mluvím, podívej se do článku, který jsi už 5x postnul).
Připadá mi ale, že moje definice rekurzí bude odpovídat tvé definici algoritmem, takže v tom asi nebude žádná potíž.
Potíž je v tom, že definice rekurzí/algoritmem nemusí být definována korektně - zaměn v definici třeba "a+b" za "a-b", a máš zásadní problém.
Korektnost dokážeš právě indukcí.
Pokud se podívám na tvůj indukční krok pro 0 (tak jak je na začátku #104)
"Je-li P(0) nejnižší cena košíku s nula prvky, pak nejnižší cena košíku s jedním prvekm je minimum množiny vzniklé sjednocením množin A, B.
A = { Nejnižší cena balení s jedním prvkem }
B = { P(i) + P(1-i), kde i a 1 - 1 jsou přirozené }"tak vidím, že v důkazu nemá P co dělat (P je takto použito v Lemmatu a sám jsi uznal, že pro Lemma indukce není třeba), na jeho místě má být f.
Osobně odhaduji, že intuitivně důkaz asi chápeš, jenom ho nedokážeš zformalizovat, protože máš zřejmě zkušenosti jenom s intuitivní matematikou a s formální matematikou ne. Odhaduji, že jsi asi chtěl vyjádřit toto:
"Je-li f(0) definováno, pak je definováno i f(1). Důkaz: f(1) je minimum množiny vzniklé sjednocením množin A, B, A= ..."Potom by důkaz byl formálně v pořádku.
Já preferuju, že si udělám byť nepotřebný pevný bod, který mám dokázán hned a použiju již existující větu. To je taková úchylka matematiků, že když vyřešej jeden příklad, tak ostatní na něj převáděj.
Zapomněl jsi na drobný detail: Matematici převádějí, pokud je převádět skutečně třeba.
Tohle je tvůj způsob uvažování:
Máš dokázat, že pro každé n z N platí sqrt(n^2)=abs(n).
Znáš matematickou indukci.
Víš o úchylce matematiků, převádět problémy na dříve vyřešené věci.
Pro důkaz proto použiješ matematickou indukci.
Dokážeš nejprve pevný bod sqrt(1^2)=abs(1).
To, že pevný bod dále nepoužiješ, tě netrápí: naučil ses, že indukce vyžaduje pevný bod.
Pak dokážeš indukční krok. To, že že indukční předpoklad nepotřebuješ, tě netrápí: naučil ses, že indukce vyžaduje indukční krok.
Prosím, přestaň psát nějaké dojmy a používej matematicku. Jak je definovaná věta o MI? Platí-li P(n_0) a P(n_0) ... P(n) => P(n+1), pak....
Tak jaktože není pevný bod potřeba? K tomu, abys použil větu, musíš splnit všechny předpoklady.
Neměl by se tolik ohánět matematikou, pokud neznáš matematické základy a teorii množin.
Budeš se možná divit, ale "čistá" věta o indukci (a obecněji transfinitní indukci) v teorii množin pevný bod nepotřebuje: nejjednodušší verze věty o indukci zní takto:
Je-li M podmnožina N_0 taková, že
pro každé x platí: x je podmn. M => x je prvkem M (toto je "indukční krok")
pak M = N_0.Pevný bod (neboli "0 je prvkem M") tam samozřejmě je schovaný, plyne však z "indukčního kroku", a není třeba jej samostatně uvádět.
Podobně je tomu u "slowthinkerova důkazu" (nebo jak mu říkáš): pevný bod tam je, ale protože je zabudován v indukčním kroku, není třeba jej zvlášť dokazovat.
Ano, můžeš si jestli chceš zopakovat důkaz věty o MI aplikovanej na tento konkrétní příklad, tím si dokázat slowthinkerovu větu o matematické indukci problému batohu a tu pak aplikovat bez pevného bodu. Pravda, bude diskutabilní, jestli vůbec jde o indukci (ta v sobě inherentně nese potřebu pevného bodu, viz schéma axiomu o induxi) a bude to asi desetkrát složitější a daleko méně čitelné, ale jde to.
To, že něcomu nerozumíš, neznamená, že je to 10x složitější, než to co chápeš.
"slowthinkerův důkaz" je v podstatě tvůj důkaz, správně naformulovaný a ořezaný o všechny zbytečnosti.
Shrnutí:
Shrnutí chyb ve tvém důkazu (první chyba je fatální, druhá důkaz zbytečně komplikuje):
- v indukčním kroku používáš P na místě f
- zcela zbytečně do důkazu přidáváš krok 0->1
Pokud máš nějaké
konkrétní výhrady k mému důkazu (kromě toho, že si pletu dojmy s pojmy), sem s nimi. (pokud se v něm neorientuješ, protože je rozesetý po vlákně, můžu ti ho znovu zformulovat)
159 Odpovědí
54065 Zhlédnutí