Matematické Fórum

Já bych se teda nejdřív zeptal na jednodušší věc. Platí výrok P, existuje důkaz, že platí výrok P?

↑ check_drummer: Ak by bolo namiesto slova "existuje" v otázke "je známy", tak napríklad je dokázané, že prvočíselných dvojíc s rozdielom 2, 4 alebo 6 je nekonečne veľa. Ale dôkazy pre hodnotu 2, hodnotu 4 a hodnotu 6 známe nie sú.

Ja se v techle vecech moc nevyznam, ale mam dojem, ze existuji vyroky, ktere jsou nedokazatelne, ale soucasne i nevyvratitelne. Pokud je tomu tak, pak Q = non P pro nejake takove P by bylo protiprikladem.

check_drummer napsal(a):

Ahoj,
pohybujme se, řekněme, v predikátový logice (prvního řádu). Mějme dva výraroky P,Q a nechť existuje důkaz tvrzení "P nebo Q". Platí potom, že existuje důkaz tvrzení P nebo že existuje důkaz tvrzení Q?

Ne. Z toho, že je odvoditelný výrok [mathjax]P \vee Q [/mathjax]   nijak neplyne, že je odvoditelný výrok P, ani to, že je odvoditelný výrok Q.

Dva z logických axiomů (v systému přirozené dedukce) jsou axiomy instalace disjunkce. První: "je-li odvoditelné P, je odvoditelné [mathjax]P \vee Q [/mathjax]" a druhý "je-li odvoditelné Q, je odvoditelné [mathjax]P \vee Q [/mathjax]".

Ty to chceš obráceně a to nejde. Z výroku "číslo n je sudé nebo liché" přece nijak nedokážeš, že číslo n je sudé, ani to, že číslo n je liché. Můžeš si jedno z toho zavést jako axiom, ale tu teorii, kde by to platilo, bych opravdu rád viděl...

check_drummer napsal(a):

↑ MichalAld:
Z Godelovy věty o úplnosti ano, takže tu lze použít i k důkazu toho tvrzení výše...

Nelze. Godelovu větu bez [mathjax]P\Rightarrow P[/mathjax] nedokážeš. Takže pokud naopak  [mathjax]P\Rightarrow P[/mathjax] dokazuješ pomocí Goedelovy věty, jsi v logickém kruhu.

A jak je to tedy s těmi diofantickými rovnicemi?

Birchova a Swinnerton-Dyerova domněnka

Pro obecné diofantické rovnice bylo důkazem Matijasevičovy věty prokázáno, že nelze dokonce ani určit, zda rovnice má vůbec nějaké řešení.

Eratosthenes napsal(a):

↑ MichalAld:

To  nevím (teorie čísel není zrovna můj šálek), ale pokud bylo pro obecné diofantické rovnice dokázáno, že nelze dokonce ani určit, zda mají vůbec nějaké řešení, pak výrok "každá diof. rovnice má řešení" je nerozhodnutelný, tj. nedá se ani dokázat, ani vyvrátit.

To tak asi není, určitě existují diofantické rovnice, které řešení nemají a lze to prokázat.

Ale já myslím, že tohle je trochu jiný případ, a že ta Matijasevičova věta (zkoušel jsem to najít) tvrdí, že nelze naprogramovat algoritmus, který by v konečném čase (konečným počtem kroků) rozhodl, jesli daná diofantická rovnice má nebo nemá řešení. Ale článek co jsem o tom našel je na kupu stran, tedy příliš dlouhý na to, abych se to snažil pochopit.

U nějaké konkrétní rovnice to třeba rozhodnout dokážeme (když máme štěstí), ale nelze vymyslet postup, který by nám pro jakoukoliv rovnici dokázal říct, jestli řešení má nebo nemá. Ovšem rovnice vždycky řešení buď má nebo nemá. Nemůže to být nerozhodnutelné tvrzení, protože když bychom tedy přidali axiom že řešení nemá, a někdo to řešení po pár lahvích slivovice uhádl, tak bychom tu měli spor. Jen prostě nemáme způsob jak to řešení najít - a nemáme ani způsob, jak zjistit, jestli vůbec existuje. Případně jestli existuje v nějaké v nějaké ohraničené podmnožině (kde už bychom mohli v principu vyzkoušet všechny kombinace).


Mě jde prostě o tu myšlenku, že máme nějakou konkrétní rovnici, která zrovna řešení nemá, ale nejsme to schopní dokázat (konečným počtem kroků). Tedy že nejsme schopní dokázat něco, co ale ve skutečnosti platí.

Protože v matematice (předpokládám, já tomu vlastně vůbec nerozumím), která je postavená na rekurzi, musíme buď nalézt důkaz který je taky postavený na rekurzi (důkaz indukcí) nebo můžeme použít důkaz sporem. Protože jinak bychom museli projít nekonečně mnoho možností. A když se nám to nepodaří, tak to dokázat nemůžeme. To ale neznamená, že to neplatí... bůh by určitě dokázal zkontrolovat i nekonečně mnoho kombinací.

Eratosthenes napsal(a):

Ty to chceš obráceně a to nejde. Z výroku "číslo n je sudé nebo liché" přece nijak nedokážeš, že číslo n je sudé, ani to, že číslo n je liché. Můžeš si jedno z toho zavést jako axiom, ale tu teorii, kde by to platilo, bych opravdu rád viděl...

To netvrdím, já říkám, že z toho, že lze dokázat tvrzení "číslo n je sudé nebo číslo n je liché" plyne, že:
lze dokázat tvrzení "číslo n je sudé" nebo lze dokázat tvrzení "číslo n je liché".

↑ Stýv:
To vypadá zajímavě, zamyslím se nad tím.

↑ Eratosthenes:

Ve výrokové logice to mé tvrzení platí, v predikátové už ne....

Edit: Tak ani ve výrokové to neplatí...

↑ Eratosthenes:
Jestli to dobře chápu, tak MichalAld se ptá na to, zda z toho, že výrok P platí, tak je výrok P dokazatelný, což je něco jiného než že platí (nebo že je dokazatelný) výrok P=>P.

↑ check_drummer:

>> já říkám, že z toho, že lze dokázat tvrzení "číslo n je sudé nebo číslo n je liché" plyne, že lze dokázat tvrzení "číslo n je sudé" nebo lze dokázat tvrzení "číslo n je liché".

Nelze.

>> Nejdřív dokážu G. větu o úlnosti a pak to tvrzení o kterém píšu výše...

To bys musel G. větu o úlnosti dokázat bez použití P => P. A to se myslím nepodaří, 

>> Jestli to dobře chápu, tak MichalAld se ptá na to, zda z toho, že výrok P platí, tak je výrok P dokazatelný, což je něco jiného než že platí (nebo že je dokazatelný)

Už je z toho trochu guláš. Co znamená, že výrok "platí"? Zaplatí za mě v hospodě? Asi ne.

Znamená to tedy, že je pravdivý, anebo že je dokazatelný?  Obecně se má za to, že je to jedno, ale není.

Každý dokazatelný výrok je pravdivý. Ale ne každý pravdivý výrok je dokazatelný - viz např. axiom.