496
Odkladiště / Re:Podivné diskuse na Zdroják.cz
« kdy: 26. 01. 2014, 01:33:07 »
Pro mě osobně je pozdrav implicitní, ale chápu že pro někoho to tak není.
Ometat někomu že pozdravil/nepozdravil je ale nanejvýš zvrhlé.
Tato sekce Vám umožňuje zobrazit všechny příspěvky tohoto uživatele. Prosím uvědomte si, že můžete vidět příspěvky pouze z oblastí Vám přístupných.
Druhá vec, je ta matika naozaj taká neuveriteľne ťažká, ako sa o nej hovorí alebo je to len "hoax" pochádzajúci od študentov, ktorý strávili viac času v krčme než učením?Pro někoho je matematika těžká, pro někoho lehká.
Ano? Jenže jaksi v analýze existují pouze menší čísla, nic jiného, zatímco v TEMNU je těch podmnožin trochu více (např. {{0}}). Takže při tvrzení o podmnožinách množiny musíš udělat více práce, než při tvrzení o číslech menších než n.Já už nevím, jak to jinak říct.
Pamatuješ si to špatně, splývají ti matematické pojmy.CitaceRád se nechám poučit. Jaké vlastní axiomy má MA?Mimo axiomy predikátové logiky s rovností axiomy definující vlastnosti tělesa reálných čísel a operací nad nimi (doufám, že si to pamatuju +- přesně).CitaceA zajímal by mě příklad tvrzení, které nelze dokázat v analýze, ale v teorii množin ano.http://cs.wikipedia.org/wiki/Goodsteinova_v%C4%9Bta
Pro jedničku tvrzení platí nezávisle na předchůdcích.Citacef(n)=min (f(i)+ f(j) ....)=min (P(i)+ P(j) ....)=P(n)Pokud neukážeš, že existuje bod, tzn. n_0, pro které tvrzení platí nezávisle na platnosti tvrzení pro jiné n, je důkaz nekorektní. Protože takovej důkaz prostě nerozlišíš od důkazu, že a+1=a.
funguje i pro počátek, tedy pro n=1. Je zbytečné dokazovat zvlášť, že P(1)=f(1)
Že to ukážeš (skoro) stejným tvrzením jako indukční krok je druhá věc, ale ukázat to prostě musíš.
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íš
Která teorie množin? ZFC? Vopěnkova alternativní? Goldstein-bernsteinova? A s jakým modelem?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í.
...
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...
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.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.
...
Atd. postě přirozený číslo v ZFC není až tak "jednoduchá věc" 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.(aby nedošlo znovu k nedorozumění, mluvím o stále o GB/ZFC:)
...
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í!
Takže f nemůžu ani definovat, protože k její definici musím prostě použít musím?Říkají to základní matematické principy. f jsi definoval tak, že nevíš, zda existuje.
Nebo jsou povolené a nepovolené užití f? Zase báťuška?
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.
Dokazuju tvrzení: a = a+1To 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.
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í.
IMHO v teorii množin se o matematické indukci v podstatě nemluví. Přirozený čísla jako objekt v TEMNU je vcelku nezajímavej objektO 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ů.
Navíc MI (z věty o slabém principu) je definovaná pro n ze Z, takže jsou dvě možnosti:MI definovaná pro celá čísla? Tomu nerozumím.
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.
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.
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čí.CitaceTo bys ale nesměl začít psát důkaz rovností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.
f(n) = min (f(i)+ f(j) ....)
Musel bys začít z druhé strany P(n)=...
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í.
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.
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
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í
co popisuješ je co vím modifikované tvrzení o1) matematická indukce není nic jiného než transfinitní indukce oříznutá na přirozená čísla.
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.
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.
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:Ta věta v odkazu není dobře zapsaná: není řečeno, pro jaká a má platit indukční krok 2.=>3.
http://mathworld.wolfram.com/TransfiniteInduction.html
"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.Citacetak 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).... až na to, že zapomínáš na jeden detail:
...
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)
Nesouhlasím s tím, že pokudDů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.
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ž.
Panove, mohl bych vas o neco poprosit? Zajimalo by me vase vzdelani (kde, co a rocnik/dosazeny titul)Já mám základní školu. Titul mi tam bohužel nedali.. Od vsech...
Tak to jsem rád, že jsi konečně uznal nepravdivost svého dřívějšího tvrzeníCitaceHabala 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.
Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce.
f(n) není definována korektně nebo nekorektně. f(n) je definována algoritmem.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).
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,
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.
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.
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š.
Ty jsi mě napadal, že nemůžu použít tudle indukci a musím použít jinou.(pozn. na upřesnění: já říkal "tohle je jiná indukce", ne co musíš použít. Pro mě za mě si použij třeba pouze axiomy teorie množin s Hilbertovskou logikou a nic víc.)
K tomu, abys toto tvrzení dokázal tu indukci potřebuješ.
Pokud nevěříš mě, tak si přečti to, co jsem už asi pěštrát postoval:
http://math.feld.cvut.cz/habala/teaching/dma/dmknih03.pdf
Formálněji: Máš funkci danou předpisem:Přesněji:
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 n prvky,
existuje-li, jinak nekonečno.
...
Chceš dokázat, že pro každé n z N platí tvrzení T(n).
P(n) = f(n)
K tomu, abys toto tvrzení dokázal tu indukci potřebuješ. Protože pro každé n potřebuješ aplikovat ono lema + indukční předpoklad, že f(a) a f(b) jsou minimální košíky pro a/b prvků.
A pokud jde o to, že nikde dál nepoužiješ předpoklad pro nulu, tak to je MI úplnej šumák.Obecně pro jakoukoli úvahu platí, že je nesmyslné vytvářet pevný bod, od kterého se stejně nebudu nikdy odrážet. Navíc není pravda, že pro MI je třeba mít pevný bod (vysvětlím dále).
Pro MI je prostě potřeba mít nějakej pevnej bod, z kterýho začneš. Jelikož se bod pro nulu sestrojí nejjednodušeji a zároveň nezesložití indukční krok, je velmi vhodné začít z něho. Je úplně jedno, jestli ho pak někdy použiješ nebo ne.
A proto klidně můžu MI užít. Ale tady je jednodušší to tvrzení dokázat jinak, takže užití MI není nejvhodnější, byť možné.Souhlasím. Do důkazu pro sqrt(n^2)=abs(n) je možné přicpat indukční kroky pro každé n, a nepoužívat je. Důkaz se tím ale bezdůvodně zkomplikuje.
...co je to košík. Definujeme ho tedy jako n-rozměrný vektorový prostor nad pologrupou jejíž hodnoty jsou počet balení, kde bázi tvoří jednotlivá balení.Technická poznámka: Formálně vektorový prostor nad pologrupou (která není současně tělesem) nesestavíš. Množina košíků tedy není podprostorem vektorového prostoru, ale jde o část podprostoru - lineární kombinace s koeficienty z N_0.
Není-li možný záporný počet balení, pak je danou grupou grupa N_0 a obor hodnot v(k) a tedy definiční obor f(n) je taktéž N_0.Technická poznámka: Pokud úloha zní, že chci v košíku "přesně" x ks zboží a ne "alespoň" x ks, nemusí být obor hodnot v(k) celé N_0. Představ si "bázi" tvořenou jediným balením s 2 ks zboží.
v T(-55) je užito f(-55), ta je však definovaná taktéž pouze nad N_0. Tvrzení tedy nemá smysl. (stejně jako nemá smysl tvrzení, ve kterém je dělení nulou.(Pozn.: Přesněji bys měl říct "je užito P(-55)": Funkci f pro Lemma+ nepotřebuješ.)
Druhou věc, kterou jsem tvrdil bylo, že neexistuje jiná indukce. Pokud je slabý a silný princip indukce EKVIVALENTNÍ, nemůže být JINÝ. protože kdyby byl jiný, nemohl by být ekvivalentní.To, že jsou dvě věci ekvivalentní přece neznamená, že nemohou být jiné. To bys mohl úplně stejně tvrdit, že neexistuje žádná matematická indukce, protože ji lze odvodit ze základních důkazních metod. Ano, každý důkaz indukcí můžeš přepsat tak, že formálně půjde o důkaz bez použití indukce, jenomže ten princip indukce tam bude pořád vidět.
Máš pravdu, moje chyba. Nechápu takovou triviální věc a opovažuju se tady poučovat.CitacePokud povolíš košík s nulovým počtem balení, nevidím důvod proč nepovolit i se záporným počtem balení. Ale o to, jestli povolit nebo nepovolit tu vůbec nejde. To tvrzení pravdivé je...Nevidíš důvod u takhle triviální věci a poučuješ tady lidi o (vzhledem k tomu) poměrně složitejch věcech jako je korektnost MI a teorie složitosti a NP-úplnosti?
Pokud povolíš košík se záporným počtem kusů, tak můžeš např. udělat košík s jedním kusem jako 1x3kusy + (-1)x2kusy.
Co třeba důkaz MI že pro posloupnostU důkazu matematickou indukcí, kterým budu dokazovat, že pro každé přirozené n platí sqrt(n^2)=abs(n), dokonce žádný "indukční krok" nebude potřebovat indukční premisu, a důkazu to taky nijak nevadí...
a0=1
a_2i=2*a_(2i-2)
a_2i-1=1
Platí:Je-li i je sudé pak a_i=2^(i/2) jinak a_i=1
Tam dokonce nejen A(1), ale dokonce každej druhej indukční krok nebude potřebovat indukční premisu. Vadí to snad nějak tomu důkazu? Nebo jako nesmím použít MI, když v některejch krocích nepoužiju premisu?
nějakej první krok udělat musím a P(1) je složitější než P(0)Tak já ti prozradím pointu:
...
Ano, v prvním kroku indukce je tento předpoklad zbytečný