Optimální algoritmus výpočtu

[Logik]

Matematickou teorii, ve které se definuje algoritmem, bohužel neznám

Nevím, co se snažíš dokázat Ty, ale já dokazuju platnost algoritmu. Čili dokazuji, že funkce f, kterou vyčísluje ten algoritmus, je ekvivalentní s funkcí P.
Pokud dokazuješ něco o nějaké jiné funkci definované nějakou rekurkzí, můžeš, ale pak nechápu proč to děláš v tomto vlákně, tady je debata o důkazu algoritmu a tedy o funkci definované tímto algoritmem.

Jinak jestli nevíš, co je to fce definovaná algoritmem, tak to je Tvůj problém. Např. se dá definovat jako funkce, která jedefinovaná na množině vstupů algoritmu, pro který algoritmus doběhne a hodnota funkce pro daný vstup je výsledek algoritmu.

Druhá možnost jak definovat funkci pomocí algoritmu konstrukční: přes ekvivalenci TS a rekurzivně vyčíslitelných funkcí. Tzn. funkce definovaná algoritmem je taková funkce, která je ekvivalentní TS implementujícímu daný algoritmus.

Ať to uděláš jak checš, v každym případě musíš dokazovat něco o funkci, která je počítaná tak, jak počítá ten algoritmus. Takže tak funkce je tím algoritmem definovaná.

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.

Ano máš problém. Budeš totiž dokazovat tvrzení, které s algoritmem nesouvisí. No a?
Popř. pokud by v algoritmu bylo a-b, tak by důkaz prostě nešel provést - což neni divu, protože by algoritmus nefungoval...
Nebo (v tomto případě) dokážeš z definice funkce spor. A tak dokážeš, že taková fce neexistuje. No a?

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.

Ach jo. Tak znova. Dokazuji, že P(a) = f(a). Tak jaktože v důkazu nemá P(a) co dělat??

f(a) je definována jako
f(n) = min (f(i)+ f(j) ....)
protože tak vyčísluje tu funkci algoritmus.

Abych T(n) dokázal, tak
1) použiji indukční předpoklad, že f(k) = P(k) pro všechna f(k) v definici f(n) a tedy
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...)
2) použiju Lemma, že min (P(i)+ P(j)...) = P(n)
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...) = P(n)
      ◻   

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.

Teorii množin tolik neumim, ale to, co popisuješ je co vím modifikované tvrzení o
transfinitní indukci a nikoli o MI. Takže
1) to co popisuješ IMHO není matematická indukce
2) M podle předpokladu obsahuje sama sebe a tedy obsahuje prvek: množinu všech přirozených čísel. Množina všech přirozených čísel je první nekonečno. Takže prvkem M je nekonečno a tedy M není podmnožina N_0. Spor.

Tzn. žádná taková M neexistuje a toto tvrzení není ani matematická, ani transfinitní ani jiná indukce ale tvrzení o ničem.

To, že pevný bod dále nepoužiješ, tě netrápí: naučil ses, že indukce vyžaduje pevný bod.

Hele já asi končím. Todle nemá cenu. Prostě existuje věta o matematické indukci s danými předpoklady. Pokud někdo používá důkaz MI, znamená to (alespoň mezi všema lidma na MFF, co jsem se zatím setkal), že aplikují danou větu. V předpokladech MI je existence pevného bodu. Takže buď použiju větu o MI a musím dokázat tvrzení pro pevný bod, nebo nepoužiju větu o MI - ale pak nedokazuju matematickou indukcí. Žádná jiná možnost prostě není.

Btw. i v Tvém důkazu je vlastně pevný bod. Tvrdíš, že pro P(1) nepotřebuješ předpoklady. Jenže to je třeba taky dokázat (byť je to taky vcelku trivoš). Tím ale přistupuješ k P(1) jinak než ke všem ostatním. Takže také používáš pevný bod. A navíc protože nedokazuješ explicitně P(n_0) nemůžeš použít větu o MI, takže asi používáš nějakou svojí indukci. a tu bys měl dokázat.

Ono to totiž bez pevného bodu to nejde! Např platí   (a = a - 1) =>  ((a+1) = (a+1) - 1). To ale neznamená, že a = a - 1. Proto je pevný bod pro MI nutnost. Ona i ta věta o transfinitní indukci se pak musí užít s pevným bodem:
http://mathworld.wolfram.com/TransfiniteInduction.html

Pokud máš nějaké konkrétní výhrady k mému důkazu (kromě toho, že si pletu dojmy s pojmy),

Nesouhlasím s tím, že pokud
f(n) = min (f(i)+ f(j) ....)
pak tvrzení
P(n) = f(n) plyne okamžitě Lematu, aniž bys použil MI (popř. postup MI podobný). Pokud nesouhlasíš, tak to formálně dokaž.

PS: Co se týče mojeho matematického vzdělání, doporučil bych Ti se krotit, by ses neztrapnil.... :-) Ale to jen tak na okraj.... :-)

[Reklama]

[slowthinker]

Indukce

co popisuješ je co vím modifikované tvrzení o
transfinitní indukci a nikoli o MI. Takže
1) to co popisuješ IMHO není matematická indukce
2) M podle předpokladu obsahuje sama sebe a tedy obsahuje prvek: množinu všech přirozených čísel. Množina všech přirozených čísel je první nekonečno. Takže prvkem M je nekonečno a tedy M není podmnožina N_0. Spor.

1) matematická indukce není nic jiného než transfinitní indukce oříznutá na přirozená čísla.
2) to jsi mě dostal. Zapomněl jsem omezit implikaci na konečné množiny. Správně má ve větě být "pro každé konečné x platí:"

Btw. i v Tvém důkazu je vlastně pevný bod. Tvrdíš, že pro P(1) nepotřebuješ předpoklady. Jenže to je třeba taky dokázat (byť je to taky vcelku trivoš). Tím ale přistupuješ k P(1) jinak než ke všem ostatním. Takže také používáš pevný bod. A navíc protože nedokazuješ explicitně P(n_0) nemůžeš použít větu o MI, takže asi používáš nějakou svojí indukci. a tu bys měl dokázat.

Mluvíš o důkazu Lemmatu? V tom důkazu je pevný bod, ale nevyžaduje speciální důkaz. Důkaz Lemmatu funguje stejně pro jedničku jako pro libovolné n.
Používám tu větu o MI, na které jsi mě nachytal a kterou jsem opravil.

Ono to totiž bez pevného bodu to nejde! Např platí   (a = a - 1) =>  ((a+1) = (a+1) - 1). To ale neznamená, že a = a - 1. Proto je pevný bod pro MI nutnost. Ona i ta věta o transfinitní indukci se pak musí užít s pevným bodem:
http://mathworld.wolfram.com/TransfiniteInduction.html

Ta věta v odkazu není dobře zapsaná: není řečeno, pro jaká a má platit indukční krok 2.=>3.
Pokud pro a>=1, pak je pevný bod 1. potřeba (označím takovou indukci "verze s pevným bodem").
Pokud pro a>=0, pak není bod 1. potřeba (resp. je obsažený v indukčním kroku) (ozn. "verze bez pevného bodu").

Při důkazu verzí bez pevného bodu implikace "(a = a - 1) =>  ((a+1) = (a+1) - 1)" pro a=0 nefunguje, protože a nemá předchůdce. Takže žádný problém.

Mnou uvedená definice (transfinitní) indukce pro přirozená čísla/ordinály odpovídá verzi bez pevného bodu.

Mimochodem, věta v odkazu je věta o transfinitní indukci pro dobře uspořádané množiny, nikoli pro ordinály. Dobře uspořádaná množina nemusí být uspořádaná právě relací náležení, takže ten jednoduchý zápis věty o indukci pomocí relace náležení není pro dobře usp. množiny možný.

Tvůj/můj důkaz

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.

Ach jo. Tak znova.

"Znova"? Až doteď jsem se vyjadřoval k tvému indukčnímu kroku v příspěvku #104. A tam nebylo po f ani památky.
Teprve následující důkaz je formálně (téměř) v pořádku...

Dokazuji, že P(a) = f(a).
...
Abych T(n) dokázal, tak
1) použiji indukční předpoklad, že f(k) = P(k) pro všechna f(k) v definici f(n) a tedy
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...)
2) použiju Lemma, že min (P(i)+ P(j)...) = P(n)
f(n) = min (f(i)+ f(j) ....) = min (P(i)+ P(j)...) = P(n)

... až na to, že zapomínáš na jeden detail:

Nemužeš dokazovat, že
P(a) = f(a)
jestliže nevíš, zda f(a) existuje.
Ve skutečnosti dokazuješ
f(a) existuje a P(a) = f(a)

a pro rovnost
f(n) = min (f(i)+ f(j) ....)
musíš využít indukční předpoklad taky.
(ovšem pokud se na f nedíváš jako na funkci definovanou rekurzí, ale jako na funkci definovanou algoritmem, čeká tě ještě práce navíc.)

Nesouhlasím s tím, že pokud
f(n) = min (f(i)+ f(j) ....)
pak tvrzení
P(n) = f(n) plyne okamžitě Lematu, aniž bys použil MI (popř. postup MI podobný). Pokud nesouhlasíš, tak to formálně dokaž.

Důkaz: Z Lemmatu plyne, že P splňuje náš rekurzivní předpis P(n) = min (P(i)+ P(j) ....). Ale věta o definici rekurzí říká, že taková funkce je jen jedna, tedy P=f.
(Jak už jsem zmiňoval, rekurze je založena na indukci, takže s tou potřebou indukce máš pravdu.)

Edit:
Rozdíl mezi našimi dvěma důkazy:
Já používám větu o definici rekurzí, a ty dokazuješ větu o definici rekurzí pro náš specifický případ.
( jako bys zapomínal na úchylku matematiků převádět problémy na dříve vyřešené)


[off-topic]

• Napsal jsi: "PS: Co se týče mojeho matematického vzdělání, doporučil bych Ti se krotit, by ses neztrapnil.... :-) Ale to jen tak na okraj.... :-)"
  
  Dost jsem se divil, když jsem četl vedlejší vlákno. Tipoval jsem tě na fel nebo něco podobného, v žádném případě mff. Taky bych  předpokládal, že informatici mají v prvním ročníku semestr teorie množin (takhle to aspoň (prý ) bylo dřív).
  (No a o tvou matematiku jsem se otíral jenom proto, protože sis začal )

[/off-topic]

[ferren]

tohle tema me docela pobavilo. priznam se,po precteni zadani jsem taky zbrkle naletel a napadlo me to nejtrivialnejsi "temer" idealni reseni zminene prakticky v prvnich odpovedich. ano,pak jsem se zamyslel ano,mame tu NP. zbylych snad 8 stranek jsem jen zbezne proskakal,a mam na vas vsechny par poznamek. predne,puvodni tazatel asi nebude studentik,plni nejake pracovni zadani v e-shopu. suboptimalni reseni funguje v 99% pripadu,navic z praktickeho pohledu se slevova baleni resi procentualne vuci cene za 1 kus.v praci opravdu tezko vzniknou divoke cenove kombinace,kde ten nejtrivialnejsi algoritmus selhava.ani dost dobre v praxi nedochazi k nakupum radove vetsiho mnozstvi nez v tom nejvyhodnejsim balicku,protoze balicky tak nejak reprezentuji REALNE mozne nakupy. navic,zadavatele prace tj. e-shop netrapi,ze sem tam na zakaznikovi o trosku vic vydela, navic pokud je zakaznik vubec schopen poznat,ze mu to navrhlo nevhodnou kombinaci,tak si sam zvoli pro nej kombinaci lepsi. troufam si odhadnout, ze v realnem e-shopu tohle nenastane NIKDY.

takze,nic proti akademickym debatam o algoritmech,ale tohle je presne rozdil v skolnim a praktickem pristupu,a jako majitel e-shopu bych vas vsechny vyhodil ;-) kanon na vrabce bych v zivote nezaplatil....

[slowthinker]

  Je vidět, že jsi 8 stránek jen běžně proskákal, a tudíž nevíš o čem mluvíš. Optimální řešení je mnohem jednodušší než suboptimální.
(a aby bylo jasno: akademické debaty nejsou o tom, co je nejlepší řešení, ale jak formálně dokázat správnost tohoto nejlepšího řešení)

[ferren]

:-) jednodussi? mas pravdu,preskakoval jsem,ale co jsem nepreskocil,byly Tve prvni prispevky,zvlast jsem nepreskocil ten,kde uznavas ze nick sedi,ze jsi nad necim den premyslel...i tohle staci k tomu,abych si stale stal za tim uvedenym nejjednodusim resenim a zaverem, co bych udelal kdyz bych byl ja ten co takoveho developera plati ;-)))))) nic ve zlem.jednoduche reseni neni o cistote algoritmu,jeho slozitosti a delce kodu,ale o case,ktery nad nim clovek stravi...

[Reklama]

[Jaromír]

Koukám, že jediný funkční (a tudíž i nejlepší) algoritmus jsem tu dal já. Jinak ostatní tady o tom jenom tlachají...

[Logik]

Já používám větu o definici rekurzi....

Mě se zdá, že v každym postu používáš něco jinýho. Nejdřív si tvrdil, že používáš  matematickou indukci bez pevnýho bodu, pak zas že indukci nepoužíváš vůbec, pak užíváš omezenou transfinitní indukci, potom zas větu o definici funkce rekurzí.

Jinak ano, pomocí věty o definici rekurzí ten algoritmus jde dokázat taky (a je to vcelku hezký důkaz, asi i kratší než s použitím MI). Pro korektnost tam zas musíš definovat dobré uspořádání - takže taky je tam ještě nějaká práce, kterou neděláš u MI. A btw. to uspořádání Ti definuje nejmenší člen a ten je pak pevným bodem.
Nicméně je to jiný důkaz a tedy nevypovídá nic o tom, zdali pro důkaz pomocí MI potřebuješ pevný bod či nikoli.

Při důkazu verzí bez pevného bodu implikace "(a = a - 1) =>  ((a+1) = (a+1) - 1)" pro a=0 nefunguje, protože a nemá předchůdce. Takže žádný problém.

A co když to tvrdím na celých číslech? Tam každé číslo předchůdce má... Naopak právě to, že na celých číslech to nefunguje je důkaz toho, že potřebuješ nějaký pevný bod. Celá indukce funguje tak, že vezmeš nějakej pevnej bod, kde to tvrzení platí a pomocí indukčního kroku infikuješ platností ostatní.

 To, že teorie množin popisuje aritmetiku ještě neznamená, že se při používání výsledků TEMNA nemusí dbát jisté opatrnosti na to, jak se aplikuje. Proto je imho jednodušší dokazovat pomocí MI, kde máš větu s naprosto jasným mustrem důkazu.

TI říká pouze něco o vlastnostech přirozených čísel, MI rozvnou o tvrzeních, aplikovaných na ně. Takže pokud chceš užít TI (respektive navíc omezenou na přirozená čísla, což si vyžádá další práci navíc) musíš kus toho, co je ve větě o MI již dokázaný dokázat ručně. V rámci toho se Ti může stát, že dokážeš i platnost tvrzení v pevném bodě (ten tam opět je, ani TI by nefungovala bez pevného bodu - tzn. bez tvrzení, P(n_0), které lze dokázat bez předpokladu P(n)).
 To však neznamená, že Ti to ušetří práci, ani že tam ten pevný bod není (právě předpoklad uspořádání množiny je v podstatě ekvivalentní předpokladu existence pevného bodu).

PS: Jinak existenci f ověřovat nemusím, protože P existuje, dokážu-li tedy ekvivalenci P a f, musí existovat i f.

jaromir: :-) :-) Ne, tys jen postoval myšlenkově nejjednodušší algoritmus kterej je pomalej a tak ostatní nezajímá.... Ale jasně, seš king...

ferren: rozdíl v akademickém a praktickém přístupu je v tom, že zatímco akademici se dokážou bavit, tak "praktici" všechno počítaj na peníze? Sice nejsem čistej akademik, ale jestli to tak je, tak se na ten doktorát určitě přihlásim...

[slowthinker]

Mě se zdá, že v každym postu používáš něco jinýho. Nejdřív si tvrdil, že používáš  matematickou indukci bez pevnýho bodu, pak zas že indukci nepoužíváš vůbec, pak užíváš omezenou transfinitní indukci, potom zas větu o definici funkce rekurzí.

Říkal jsem, že na důkaz Lemmatu nepotřebuješ indukci. A ty tři ostatní věci jsou plus minus jedno a to samé.

A co když to tvrdím na celých číslech? Tam každé číslo předchůdce má...

Tvrdit to můžeš, ale nemůžeš to dokazovat žádnou indukcí, protože ta funguje pouze pro dobře uspořádané množiny.
Dobře uspořádané množiny samozřejmě počátek (=pevný bod) vždy mají. Jiná věc je, že pro tento počátek není vždy nutné provádět separátní důkaz.

TI říká pouze něco o vlastnostech přirozených čísel, MI rozvnou o tvrzeních, aplikovaných na ně. Takže pokud chceš užít TI (respektive navíc omezenou na přirozená čísla, což si vyžádá další práci navíc)

Ale já nepoužívám TI, používám MI. Jenom jsem mimochodem konstatoval, že
MI = TI omezená na přirozená čísla

Jinak TI a MI říká to samé, jenom to říká o jiné množině. "Říkat něco o tvrzeních, aplikovaných na přirozená čísla" to není součást indukce, to je jenom přílepek:
MI indukce (ve smyslu teorie množin) říká, že má-li M, která je podmnožinou N, nějakou vlastnost, je pak rovna celému N. Nic víc.
Při řešení problému pak definujeme M ={n z N; tvrzení T(n) platí}. a použijeme MI.
(a přijde mi odvážné říkat minulému řádku "práce navíc")

PS: Jinak existenci f ověřovat nemusím, protože P existuje, dokážu-li tedy ekvivalenci P a f, musí existovat i f.

To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...

[TomK]

Indukce bez pevného bodu neobstojí. Stačí ten příklad jen trochu upravit, aby byl korektně definován i pro 0:
Dokazuju tvrzení: a = a+1
Indukční krok, tj. (a = a + 1) =>  ((a+1) = (a+1) + 1), je triviální dokázat, přesto je snad zřejmé, že uvedené tvrzení neplatí.

[Logik]

Říkal jsem, že na důkaz Lemmatu nepotřebuješ indukci.

Nikoli. Říkal jsi:

Pokud je f(n) definována korektně, P(n) = f(n) plyne okamžitě z Lemmatu, na to indukci nepotřebuješ.

Což jsi se pak snažil obhájit tím, že použiješ větu o konstrukci rekurzí. Která se sama dokazuje indukcí....

Jinak TI a MI říká to samé, jenom to říká o jiné množině.

IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objekt a TEMNO se mj. na zkoumání spočetnejch věcí moc nehodí (byť je na něco nutná). V TEMNU se používá transfinitní indukce, protože ta se týká toho, čemu se TEMNO mj. věnuje hlavně - nekonečnejm množinám. Je možný, že někdo MI v rámci teorie množin definuje, to je pak ale nejspíše z didaktickejch důvodů, aby člověku nepřišla TI tak divná.
S google jsem našel všehovšudy jedinou zmíňku - a to pouze ve formě s pevným bodem, v podstatě parafrázi věty o matematický indukci
http://ufal.mff.cuni.cz/~pajas/vyuka/logika_temno_2x2.pdf

Když se řekne matematická indukce, tak se tím prostě myslí věta o matematický indukci (respektive o slabym a silnym principu). Je to jak s tou složitostí - můžeš si vymejšlet vlastní definice a názvosloví - pak ale budeš mluvit o koze a ostatní o voze.

Tvrdit to můžeš, ale nemůžeš to dokazovat žádnou indukcí, protože ta funguje pouze pro dobře uspořádané množiny.

Dík TomK, opravils mi to perfektně :-).

Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:
a) buďto MI v analýze je něco jinýho než MI v temnu (což je zjevně blbost)
b) nebo MI v temnu vyžaduje pevný bod.

Při řešení problému pak definujeme M ={n z N; tvrzení T(n) platí}. A použijeme MI

Co to znamená a použijeme MI. To znamená ověřit předpoklady. Předpoklad pak je, že je-li x podmnožinou a ordinálem (tos tam taky zapoměl, bez toho to imho nejde), pak je i prvkem. To celé bys měl ověřit prostředky TEMNA (axiomy, množiny, ne žádný čísla a podobný "výdobytky civilizace"). Vopruz.
Ty bys prostě chtěl mixovat "vágnost" aplikovaný matematiky s tím největším formalismem, co snad existuje. Promiň, ale vznikne mišmaš.

To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...

Proč ne? Indukcí mám přeci zajištěnou existenci f(i) a f(j). Ten důkaz zároveň dokazuje existenci i rovnost.
Nikde nepoužívám nic, co by předem nebylo dobře definovaný - vždyť sáms psal, že v podstatě trochu kopíruju větu o konstrukci rekurzí.

[slowthinker]

Dokazuju tvrzení: a = a+1
Indukční krok, tj. (a = a + 1) =>  ((a+1) = (a+1) + 1), je triviální dokázat, přesto je snad zřejmé, že uvedené tvrzení neplatí.

To je ale to samé v bledě modrém. Matyáš napsal indukční krok pro a, tohle je stejný indukční krok, jenom zapsaný pro a+1. Pro a+1=0 nelze  důkaz použít, protože a neexistuje.

Důkaz indukcí "bez pevného bodu" vyžaduje abys ukázal
platí-li tvrzení pro všechny předchůdce a, platí i pro a.
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.

IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objekt

O přirozených číslech a MI se mluvit musí, jinak by teorie množin nemohla sloužit jako základ ostatních matematických oborů.
Mimochodem, někdy někde jsem viděl Godel-Bernaysovu teorii množin, včetně pasáže o přirozených číslech a definice MI (včetně "Fin(x)",  na které jsem o pár příspěvků výše zapomněl).

Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:
a) buďto MI v analýze je něco jinýho než MI v temnu (což je zjevně blbost)
b) nebo MI v temnu vyžaduje pevný bod.

MI definovaná pro celá čísla? Tomu nerozumím.
a) souhlasím, nevidím žádný rozdíl, kromě toho, že v analýze se zřejmě vždy pracuje s konstrukcí M ={n z N; tvrzení T(n) platí}
a indukce "s pevným bodem"-"bez pevného bodu" jsou jak v MA tak v TeMnu, navíc jsou obě indukce v podstatě jedno a to samé
b) chceš snad říct, že ta věta nefunguje, ani po opravách?

Co to znamená a použijeme MI. To znamená ověřit předpoklady. Předpoklad pak je, že je-li x podmnožinou a ordinálem (tos tam taky zapoměl, bez toho to imho nejde), pak je i prvkem. To celé bys měl ověřit prostředky TEMNA (axiomy, množiny, ne žádný čísla a podobný "výdobytky civilizace"). Vopruz.

Máš pravdu, zapomněl jsem, že x má být ordinál.

Číslo 2 nebo pojmy "funkce", "matematická indukce" jsou nějak teorií množin definované. Jakmile je definuji, mohu je pak normálně používat, bez axiomů.
Teorie množin není žádná uzavřená exotická část matematiky, naopak se "spojitě" rozvětvuje do ostatních disciplín matematiky.

A v každém matematickém odvětví, ať je to teorie množin nebo analýza nebo cokoli jiného, mohu dělat důkazy čistě formální jen jako posloupnost formulí na základě výrokové a predikátové logiky (vopruz), nebo jako mix přirozeného jazyka a matematických symbolů (což je nejběžnější), ale i zcela bez matematických symbolů.
Takže když řeknu
matematická indukce říká: platí-li, že (jsou-li v podmnožině přirozených čísel všichni předchůdci n (ve smyslu uspořádání relací náležení), je tam také n), jsou v této podmnožině všechna přirozená čísla
tak je to taky teorie množin, i když pouze neformální.

To bys ale nesměl začít psát důkaz rovností
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...

Proč ne? Indukcí mám přeci zajištěnou existenci f(i) a f(j). Ten důkaz zároveň dokazuje existenci i rovnost.
Nikde nepoužívám nic, co by předem nebylo dobře definovaný - vždyť sáms psal, že v podstatě trochu kopíruju větu o konstrukci rekurzí.

Napsal jsem hloupost, je jedno z které strany začneš. V každém případě f nemůžeš používat, pokud nevíš, jestli existuje jako celek: existence f(i), f(j) nestačí.

To znamená, že formálně je to takhle: rovnicí
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
nedokazuješ
P=f
nýbrž
jestliže f existuje, pak P=f.
(pozn. důkaz tohoto tvrzení odpovídá důkazu jednoznačnosti funkce definované rekurzí)

K tomu musíš dokázat, že f existuje, ale to je jasné, stačí do předpisu dosadit P.
(
pozn. naopak u rekurze je důkaz existence funkce složitější. Takže není tak úplně pravda, jak jsem říkal, že kopíruješ důkaz věty o definici rekurzí.

Jenomže tvůj důkaz se rekurzi (resp. existenční části důkazu věty o definici rekurzí) stejně nevyhne:
Máš funkci definovanou předpisem na základě svých vlastních hodnot v jiných bodech. Víš sice, že existuje právě jedna funkce daná předpisem, ale nevíš, jestli lze na základě toho předpisu sestavit algoritmus, který funkci vyčíslí.
Zřejmě platí následující tvrzení:
jestliže je předpis rekurzivní, tj. jestliže pro každé n je hodnota funkce určena na základě hodnot předchůdců, lze na základě tohoto předpisu algoritmus sestavit.
Důkaz tohoto tvrzení bude zřejmě analogický s existenční částí důkazu věty o definici rekurzí.

Takže i když se zkusíš vyhnout rekurzi, použiješ myšlenky jak existenční tak jednoznačnostní části důkazu věty o rekurzi.
)

[TomK]

To je ale to samé v bledě modrém. Matyáš napsal indukční krok pro a, tohle je stejný indukční krok, jenom zapsaný pro a+1. Pro a+1=0 nelze  důkaz použít, protože a neexistuje.

Je to v podstatě to samé. Ale tvrdím, že ta implikace platí pro všechna přirozená nebo i celá čísla. Konkrétně pro nulu vypadá takto: (0)+1=(0) => (0+1)+1=(0+1), opět lze i jednoduše dokázat.

Důkaz indukcí "bez pevného bodu" vyžaduje abys ukázal
platí-li tvrzení pro všechny předchůdce a, platí i pro a.
Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.

S tímhle souhlasím. Ale platí-li to pro 0 bez jakýchkoliv předpokladů, dělá to z nuly to, co je v této diskuzi označováno jako pevný bod (nejsem si jistý, jestli korektně, zatím jsem se s touto terminologií nesetkal, ale možná jde jen o mou neznalost). Možná je celý spor ohledně indukce jen o nejasné definici pevného bodu.

[slowthinker]

S tímhle souhlasím. Ale platí-li to pro 0 bez jakýchkoliv předpokladů, dělá to z nuly to, co je v této diskuzi označováno jako pevný bod (nejsem si jistý, jestli korektně, zatím jsem se s touto terminologií nesetkal, ale možná jde jen o mou neznalost).

Ano, to jsem říkal. Pevný bod je tam vždy, jde jen o to, jestli je třeba pro nulu/počátek/pevný bod dělat zvlášť důkaz.
Pokud indukční krok funguje od počátku (nic=>0), tak to není třeba, pokud až od počátku+1 (0=>1), je třeba udělat zvlášť důkaz pro počátek.
Jinak terminologii si tu asi děláme vlastní...

[Logik]

Terminologii si tu právě děláš vlastní ty. Jediný co já používám "nestandardně" je termín pevný bod - nikdo nikdy co jsem na MFF zažil jeho potřebu nezpochybňoval, takže myslím nějaký extra název nemá - všude se bere jako fakt.

Pro a=0 to znamená, že důkaz musí fungovat, aniž by bylo možné se opřít o jakéhokoli předchůdce.

A sme doma. A že takové bod (tvrzení) existuje musíš ukázat, jinak není důkaz korektní. jinými slovy - musíš věnovat extra pozornost existenci pevného bodu.

MI definovaná pro celá čísla? Tomu nerozumím.

No indukci můžeš použít i pro všechna záporná čísla, pro čísla větší než -10 atd....  Co je na tom k nechápání? Jediné co potřebuješ je platnost pro n0 a indukční krok.

Teorie množin není žádná uzavřená exotická část matematiky,

Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?

naopak se "spojitě" rozvětvuje do ostatních disciplín matematiky.

Nikoli. Např. analýza má svoje vlastní axiomy a pracuje pozue s nimi. TEMNO se snaží vytvořit logické teorie a modely, které by splňovali axiomy této teorie, není však pravda, že TEMNO = Analýza.
V TEMNU často jdou dokázat tvrzení, která v analýze nejdou - a v každém temnu a v každém modelu jiná tvrzení!

Číslo 2 nebo pojmy "funkce", "matematická indukce" jsou nějak teorií množin definované.

V každé teorii množin jsou definovány jinak, mají třeba i jiný model, popř. mají víc možných modelů, jdou pro ně dokázat různě silná tvrzení... Takže jestli chceš použít TEMNO, tak bys nejdříve měl říct kteoru vlastně teorii používáš a co pro ni platí.

Jakmile je definuji, mohu je pak normálně používat, bez axiomů.

Jo, ale furt sou to objekty TEMNA. Tzn. např. věta o MI pracuje s podmnožinou. Tzn. abys byl korektní, tak to musíš dokázat pro všechny ordinální konečné podmnožiny dané množiny (jestli Ti je od pohledu jasné, že veškeré ordinální podmnožiny N musí být přirozená čísla, tak mě teda ne - existují i pěkně divoký modely ZFC TEMNA. Pozor, netvrdim, že to tak neni, jen že to není "zřejmé"). Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" jako v analýze.

Používat na důkaz algoritmu TEMNO je jako používat v rámci pascalu strojovej kód. Jde to, ale je to zdlouhavější, nečitelnější, musíš se omezit na jednu konkrétní architekturu (rozuměj teorii množin) a explicitně uvést kterou. Za to můžeš dostat výsledky, které by s packalem nešly. Ale psát tak věci, co se dají napsat v pascalu, je blbina a nikdo to nedělá.
 

a) souhlasím, nevidím žádný rozdíl, kromě toho, že v analýze se zřejmě vždy pracuje s konstrukcí M ={n z N; tvrzení T(n) platí}

No právě takhle se v MA s MI nepracuje. V MA se pracuje s větou o slabíém či silném principu MI, které jsou založeny tuším na axiomech indukce.
MA je postavená na svejch axiomech o číslech, takže něco jako relace náležení ordinálů a z ní vyplývající princip indukce se tam prostě nepoužívá, má vlastní princip indukce a nějaká množina n, pro který platí daný tvrzení se tam prostě nekonstruuje. Nebo jsem to alespoň za svejch x let na mff nikdy nikoho neviděl dělat.

A v každém matematickém odvětví, ať je to teorie množin nebo analýza nebo cokoli jiného, mohu dělat důkazy... ....tak je to taky teorie množin, i když pouze neformální.

Ano, jde programovat eshop v strojovém kódu. Já bych to nedělal.
Stejně tak jde si nad assemblerem napsat vlastní "hezčí" jazyk a ten používat. Zaprvý je to ztráta času a za druhý Ti nikdo nebude rozumět.

Mimochodem, někdy někde jsem viděl Godel-Bernaysovu teorii množin, včetně pasáže o přirozených číslech a definice MI (včetně "Fin(x)",  na které jsem o pár příspěvků výše zapomněl).

A už je to tady - tak používáme ZFC nebo GB? A co axiom výběru? Ano nebo ne? A jaký model teda používáme? To všechno musíš říct, aby byl tvůj důkaz  korektní a vůbec srozumitelnej....

Napsal jsem hloupost, je jedno z které strany začneš. V každém případě f nemůžeš
používat, pokud nevíš, jestli existuje jako celek: existence f(i), f(j) nestačí.

Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?
Nebo jsou povolené a nepovolené užití f? Zase báťuška?
Koukni se někde na důkaz věty o konstrukci rekurzí. Kupodivu v důkazu, že existuje f ji používaj...
Je to jako s řešením kvadratický rovnice. Taky ji řešíš, i když třeba nemá řešení. Tzn. děláš s ní úpravy, aniž bys bys věděl, že existuje řešení, když třeba z obou stran odečteš x, tak to x vůbec nemusí existovat. Ale platí, že řešení rovnice před úpravou - existuje-li - je shodné s řešením po úpravě a naopak.

Zřejmě platí následující tvrzení:
jestliže je předpis rekurzivní, tj. jestliže pro každé n je hodnota funkce určena na základě hodnot předchůdců, lze na základě tohoto předpisu algoritmus sestavit.

Právě si napsal větu o konstrukci rekurzí. A ta kupodivu platí. (algoritmus je funkce, viz věta o ekvivalenci TS a částečně rekurzivních funkcí).
Navíc zaměňuješ "existenci" s definičním oborem (repektive množinou vstupů, na kterých se TS zastaví). Pokud je předpis fce daný, jde algoritmus sestavit vždy, akorát ne vždy se zastaví.

[slowthinker]

Indukce

A sme doma. A že takové bod (tvrzení) existuje musíš ukázat, jinak není důkaz korektní. jinými slovy - musíš věnovat extra pozornost existenci pevného bodu.

Právě že obecně nemusíš
Např. tvůj důkaz
f(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)

Matematické teorie

Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?
...
A už je to tady - tak používáme ZFC nebo GB? A co axiom výběru? Ano nebo ne? To všechno musíš říct, aby byl tvůj důkaz  korektní a vůbec srozumitelnej...

Myslím tu teorii množin, kterou vám přednášeli na mff v prvním ročníku, a o kterou se opírá většina přednášek na mff, včetně MA. To znamená ZFC nebo GB, které jsou ekvivalentní.
Na úroveň axiomů jsme se tu v debatě nedostali, takže je jedno, z které z těch dvou teorií vycházíme, a axiom výběru jsme nepotřebovali, takže nemusíme řešit, jestli jej povolujeme nebo ne.

Jo, ale furt sou to objekty TEMNA. Tzn. např. věta o MI pracuje s podmnožinou. Tzn. abys byl korektní, tak to musíš dokázat pro všechny ordinální konečné podmnožiny dané množiny.
...
Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" jako v analýze.

Indukci v teorii množin lze zapsat jak pomocí podmnožin, tak pomocí relace < (sám jsi uváděl odkaz na takovou definici), a pořád je to indukce a teorie množin.
Relaci < musím nejprve definovat, ale jakmile to udělám, je to stejné < jako v analýze.
(Mimochodem i relaci podmnožina musím nejprve definovat)
Jakmile odvodím příslušné vlastnosti přirozených čísel a definuji 2 = {0,{0}}, je dvojka stejná dvojka jako v analýze.

MA je postavená na svejch axiomech o číslech, takže něco jako relace náležení ordinálů a z ní vyplývající princip indukce se tam prostě nepoužívá, má vlastní princip indukce a nějaká množina n, pro který platí daný tvrzení se tam prostě nekonstruuje.
...
Nikoli. Např. analýza má svoje vlastní axiomy a pracuje pozue s nimi. ...
V TEMNU často jdou dokázat tvrzení, která v analýze nejdou - a v každém temnu a v každém modelu jiná tvrzení!

(aby nedošlo znovu k nedorozumění, mluvím o stále o GB/ZFC:)

Rád se nechám poučit. Jaké vlastní axiomy má MA? (Vím, že termín "axiom" se občas používá v rámci definic, ale to nejsou skutečné axiomy.)
Já chápu analýzu jako čistou nadstavbu nad teorií množin, to znamená pouze jako definice a věty. (A upřímně řečeno o některých definicích/větách ani nevím, jestli ještě spadají do teorie množin nebo jinam. Např. definici reálných čísel jsem viděl jak v teorii množin tak v analýze.)

A zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.

Důkazy

Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?
Nebo jsou povolené a nepovolené užití f? Zase báťuška?

Říkají to základní matematické principy. f jsi definoval tak, že nevíš, zda existuje.
V důkazu můžeš pracovat pouze s existujícími objekty. Pokud nevíš jestli objekt existuje, musíš si pomoci předpokladem jeho existence.

Když řešíš rovnici, tak vyjdeš z předpokladu, že existuje řešení x a odvodíš, že pak x=a. Tím jsi ukázal, že a je jediným řešením, které připadá v úvahu, ale ne že je řešením, to musíš ještě ověřit.

Jestli si myslíš, že se někde v důkazu věty o konstrukci rekurzí používá f, aniž by se vědělo, zda existuje, tak mi to místo ukaž.