Články označené ako BrandCom sú pripravené a publikované v spolupráci s komerčnými partnermi. Hoci redakcia TRENDU nie je ich autorom, ich obsah považuje za prínosný pre čitateľa a preto umožnila ich publikovanie. Viac o BrandCom

Russellov paradox, úplnosť verzus konzistentnosť

14.04.2010 | Michal Lehuta

Diskusia (6 reakcií)

15.04.2010 | TYTO

Dôležité vlastnosti teórii a logických systémov:
KONZISTENTNOSŤ (Consistency)
–syntakticky: množina viet (formúl, výrokov) M je konzistentná vtt z množiny M nemožno odvodiť takú vetu S, že platí S a zároveň nonS.
–sémanticky: množina výrokov (propositions) M je konzistentná vtt množina M logicky neimplikuje žiadny taký výrok S, že platí S a zároveň nonS.

NEZÁVISLOSŤ (Independence)
–(základný pojem logiky a axiomatiky): výrok p je nezávislý od množiny výrokov M vtt M logicky neimplikuje p. Množina výrokov (axióm) je vzájomne nezávislá vtt ak žiadny z jej prvkov nie je logicky implikovaný zvyšnými prvkami.

ÚPLNOSŤ (Completeness)
–úplnosť teórie (metamatematický termín): teória je úplná vtt všetky vety jazyka tejto teórie sú teorémami tejto teórie. Ak predpokladáme klasický pojem pravdivosti, teória je úplná vtt ak pre každú vetu S jazyka tejto teórie je buď S alebo nonS teorémou tejto teórie. (Príklady: prvorádová Peanova aritmetika je neúplná, ale druhorádová Peanova aritmetika je úplná)
– úplnosť logického kalkulu (metalogický termín): logický kalkul je slabo úplný vtt ak každá logická pravda kalkulu je logickou teorémou, t. j. ak kalkul dokazuje každú logicky platnú vetu svojho jazyka. Logický kalkul je silne úplný vtt existuje odvodenie vety S z množiny premís M vždy, keď S je logickým dôsledkom M.

KOMPAKTNOSŤ (Compactness)
– (sémantická vlastnosť logických systémov v modernej logike a v teórii modelov): formálny systém je kompaktný vtt sémantická konzistentnosť každej množiny formúl je konečne (finitne) determinovaná, t. j. množina je konzistentná vždy, keď sú konzistentné jej konečné podmnožiny. Ekvivalentne, systém je kompaktný vtt veta S je logickým dôsledkom nejakej konečnej podmnožiny množiny viet M vždy, keď S je logickým dôsledkom množiny viet M. (príklady: výroková logika je kompaktná (Gödel), prvorádová logika je kompaktná (Malcev), klasická druhorádová logika nie je kompaktná)

ROZHODNUTEĽNOSŤ (Decidability)
– (základný pojem teórie vypočítateľnosti a metamatematiky): množina (napr. čísel alebo formúl v nejakom formálnom jazyku) je rozhodnuteľná vtt existuje rozhodovacia procedúra pre členstvo v nej, t. j. algoritmus, ktorý pre každú vhodnú položku určí, či je alebo nie je prvkom tejto množiny. Množina je polo-rozhodnuteľná (semi-decidable) vtt existuje procedúra, ktorá spoľahlivo potvrdí, že daná položka je prvkom, ak je skutočne prvkom, no vôbec nemusí vyprodukovať odpoveď, keď je konfrontovaná s ne-prvkom. Veta S je v danej teórii T (alebo danou teóriou) rozhodnuteľná vtt buď S alebo nonS je dokázateľná v T.

KOREKTNOSŤ (SOUNDNESS) (logického kalkulu)
–(termín metalogiky): logický kalkul je slabo korektný vtt každá jeho logická teoréma je logickou pravdou. Kalkul je silne korektný vtt každá veta S odvoditeľná z množiny premís M je logickým dôsledkom M.

KOREKTNOSŤ (SOUNDNESS) (teórie)
– teória je sound vtt každá z jej teorém je pravdivá v intendovanej štruktúre. (Príklad: každá teoréma prvorádovej Peanovej aritmetiky je pravdivá v intendovanej štruktúre prirodzených čísel)

KATEGORICKOSŤ (Categoricity, výraz – O. Veblen 1904 pri axiomatizácii reálnych čísel)
–(vlastnosť formálnych teórií v teórii modelov): teória je kategorická vtt teória má model a všetky jej modely sú vzájomne izomorfné. (Akékoľvek dve štruktúry, ktoré spĺňajú axiómy danej teórie – t. j. ktoré sú jej modelmi – sú izomorfné). Ekvivalentne, teória je kategorická vtt táto teória má – up to isomorphism – jeden jediný model. (Príklady: druhorádová Peanova aritmetika je kategorická (Dedekind, 1888))

15.04.2010 | TYTO

Výroková logika
1. je konzistentná
2. je úplná
3. korektná
4. je rozhodnuteľná (tabuľková metóda)
5. kompaktná (Gödel)

Prvorádová logika (PL)
1. je slabo i silne úplná (dôkaz využíva axiómu výberu: plynie z Gödelovej Teorémy o úplnosti 1930: každá konzistentná množina viet prvorádového kalkulu alebo kvantifikačného jazyka má model = sémantická úplnosť deduktívneho systému pre kvantifikátorovú logiku)
2. je korektná
3. nie je rozhodnuteľná, ale je polo-rozhodnuteľná
4. je kompaktná
5. v PL žiadny systém majúci nekonečný model nie je kategorický (upward Löwenheim-Skolem)

Druhorádová logika (DL)
1. nie je kompaktná
2. v DL (na rozdiel od PL) sú kategoricky charakterizovateľné napr. tieto matematické štruktúry: Prirodzené čísla, Reálne čísla, Euklidovský priestor; okrem toho v DL možno charakterizovať tieto matematické pojmy: konečnosť, spočítateľnosť, minimálny uzáver, well-foundedness, kardinalita, dobré usporiadanie, ktoré v PL nemožno.
3. vzťah vyplývania nie je v DL efektívny, t. j. pre DL neexistuje rekurzívne enumerable, korektný a úplný deduktívny systém (čiže nie je kalkulom, efektívnym kánonom usudzovania), (množina logických právd akéhokoľvek druho-rádového jazyka nie je recursive enumerable)
4. ak je deduktívny systém pre DL korektný (sound = nedajú sa v ňom odvodiť vety, ktoré nie sú logickými pravdami) a teorémy sú rekurzívne enumerovateľné (= existujú efektívne procedúry, ktoré robia zoznam axióm a kontrolujú dedukcie), tak je neúplný (t. j. existujú logické pravdy, ktoré v ňom nie sú odvoditeľné)

Prvorádová Peanova aritmetika
1. nie je úplná
2. nie je kategorická
3. nie je konečne (finitne) axiomatizovateľná (C. Ryll-Nardzewski), ale je rekurzívne axiomatizovateľná

Druhorádová Peanova aritmetika
1. nie je úplná (v metalogickom zmysle, Gödel 1931)
2. je kategorická
3. je finitne axiomatizovateľná (t. j. deduktívne uzavretá (closure) vzhľadom na nejakú konečnú množinu jej axióm)

S pozdravom
Fedor Blaščák

16.04.2010 | Michal Lehuta

dakujem, na to si budem musiet vyhradit trochu casu aby som si to presiel :) ale k tym ostatnym "zaverom" - vychodne filozofie, postmodernizmus, ideologie, zivot ako taky - suvisi to podla vas s Godelom?

16.04.2010 | TYTO

s Godelom celkom urcite suvisi napr. veta o rekurzii, algoritmizacia apod., teda nieco co chce matematický výcvik na úrovni, dobrú pamäť, dost casu a disciplínu. Pokial viem, ani vo vychodnych ani postmodernych filozofiach sa tato kombinacia narokov neobjavuje. Takze by tie asociacie mali byt skor nejaky omyl. Ale ktovie.
Je vzdy dobre (z filozofickeho uhla pohladu) vyjasnit si vopred, co od jednotlivych pripadov, ked davame nieco do suvislosti s niecim inym, vlastne chceme. Co s tym zamyslame? Suvislosti su vlastne vysvetlenia, takze minimalne by sme od tychto snah mali ocakavat, ze nam prinesu bud vacsiu istotu, v tom, co uz volajako pozname (ale neni istota), alebo prinesu nieco nove (o com vsak zaroven mame aspon nejake tusenie, ze si to vieme takym a takym sposobom overit.).

08.08.2010 | landrass

neviem, preco som sem zabludil, alE nejako som sa sem dostal, azbytocne vam nicim vase kruhy, ale toto mi zas pripomenulo otazku, ze co bolo prv, ci vajce alebo sliepka...ci je uplnost v konzistencii, alebo konzistencia v uplnosti....ci su hrusky jablka, alebo jablka hrusky...toto sa teraz studuje na vysokzch skolach, alebo co?

08.08.2010 | landrass

ale, ked filozofujete nad takymito otazkami, skustesa zamysliet, ako vplyva cena ropy nacenu benzinu...spravte si graf cien ropy a porovnajte ich s cenou benzinu trebars za polednych 15 rokov a budete sa cudovat argumentom Slovnaftu preco potrebuju zdvihat ceny...hehehe

Michal Lehuta

Michal Lehuta
  • Počet článkov: 80
  • Priemerná čítanosť: 5375
  • Priemerná diskutovanosť: 16
  • RSS blogu

O blogu

Reportér-analytik týždenníka TREND. Pracoval aj v kancelárii Rady pre rozpočtovú zodpovednosť, v TREND Analyses, a pre inštitút INEKO. Ako konzultant spolupracuje aj s projektom Demagog.sk. Vyštudoval spoločenské vedy a medzinárodné vzťahy na Jacobs University Bremen.