Přednáška 4 - zcu.cz

Přednáška 4 - zcu.cz

Pednka 6 Smantika PL1 Interpretace, modely, smantick tabla Pravdivost formule, interpretace, ohodnocen Otzka je formule A pravdiv? m tedy smysl a tehdy, kdy dodme v interpretaci a pi ohodnocen volnch promnnch. Interpretan struktura je n-tice: U, R1,...,Rn, F1,...,Fm, kde F1,...,Fm jsou funkce nad zvolenm universem diskursu piazen funknm symbolm formule a R1,...,Rn jsou relace nad universem piazen prediktovm symbolm.

Jak urme pravdivost formule v interpretan struktue, i zkrcen v interpretaci? Pravdivost formule, Definice 3.1.5 interpretace, ohodnocen Vyhodnocujeme formuli zevnit: A. B. C. A. nejdve urme prvky univerza oznaen termy, pak pravdivostn hodnoty atomickch formul a nakonec pravdivostn hodnotu sloen formule Vyhodnocen term: e je valuace (ohodnocen), kter kad individuov promnn piazuje prvek univerza: e(x) U.

Ohodnocenm e term indukovanm ohodnocenm promnnch e, je prvek univerza, kter je induktivn definovn takto: e(x) = e(x) e(f (t1, t2,...,tn)) = F (e(t1), e(t2),...,e(tn)), kde F je funkce piazen v dan interpretaci funknmu symbolu f. Pravdivost formule, Definice 3.1.5 interpretace, ohodnocen B. Vyhodnocen pravdivostn hodnoty formule 1. 2. 3. Atomick: |=I P(t1,...,tn) [e] formule je pravdiv v Interpretaci I pi ohodnocen e, jestlie plat e(t1), e(t2),...,e(tn) R, kde R je relace piazen

symbolu P (kme tak R je obor pravdivosti P) Vrokov-logicky sloen, tj. A, A B, A B, A B, A B, dtto Vrokov Logika Tvaru xA(x), xA(x): |=I xA(x)[e], jestlie pro libovoln individuum i U plat |=I A[e(x/i)], kde e(x/i) je valuace stejn jako e a na to, e piazuje promnn x individuum i |=I xA(x)[e], jestlie existuje alespo jedno individuum i U takov, e plat |=I A[e(x/i)], kde e(x/i) ... Kvantifiktory Z definice kvantifiktor je zejm, e nad konenm univerzem U = {a1,,an}, plat nsledujc ekvivalence formul: x A(x) A(a1) A(an) x A(x) A(a1) A(an) A tedy veobecn kvantifiktor je zobecnnm konjunkce a existenn kvantifiktor je zobecnnm disjunkce a zjevn plat: x A(x) x A(x), x A(x) x A(x)

de Morganovy zkony Splnitelnost a pravdivost v interpretaci Formule A je splniteln v interpretaci I, jestlie existuje ohodnocen e promnnch takov, e plat |=I A[e]. Formule A je pravdiv v interpretaci I, zname |=I A, jestlie pro vechna mon ohodnocen e plat, e |=I A[e]. Model formule A je interpretace I, ve kter je A pravdiv (tj. pro vechna ohodnocen volnch promnnch). Formule A je splniteln, jestlie existuje interpretace I, ve kter je splnna, tj. jestlie existuje interpretace I a valuace e takov, e |=I A[e].

Formule A je tautologi (logicky pravdiv), zname |= A, jestlie je pravdiv v kad interpretaci. Formule A je kontradikc, jestlie neexistuje interpretace I, kter by formuli A splovala, tj. neexistuje interpretace a valuace, ve kter by byla A pravdiv: |I A[e]. Splnitelnost a pravdivost v interpretaci A: x P(f(x), x) B: x P(f(x), x) C: P(f(x), x) Interpretace I: U=N, f x2, P relace > Plat, e: |=I B. Formule B je v N, x2, > pravdiv. Formule A a C jsou v N, >, x2 splnny, ale nejsou v n pravdiv: pro

e0(x) = 0, e1(x) = 1 nen 0,0, 1,1 prvkem >, ale pro e2(x) = 2, e3(x) = 3, atd., jsou dvojice 4,2, 9,3, prvkem relace >. Formule A, C nejsou v N, x2, > pravdiv: |I A[e0], |I A[e1], |I C[e0], |I C[e1], pouze je: |=I A[e2], |=I A[e3], |=I C[e2], |=I C[e3], Przdn universum ? Pedstavme si interpretaci nad universem U = x P(x) je pravda i nepravda?

dle definice kvantifiktoru je to nepravda, nebo nenajdeme dn individuum, kter spluje P, pak je ale pravda x P(x), tj. x P(x), ale to je nepravda spor Nebo je to pravda, protoe neexistuje prvek univerza, kter by neml vlastnost P, pak ale m bt tak pravda x P(x), co je nepravda spor Podobn pro x P(x) dojdeme ke sporu, a to chpeme jako pravda i nepravda Proto volme vdy neprzdn universum Logika pro pust svt by byla nesmysln

Existenn kvantifiktor + implikace ? Existuje nkdo takov, e je-li to gnius, pak jsou vichni gniov Tato vta neme bt nepravdiv ! |= x (G(x) x G(x)) V kad interpretaci I bude platit: Je-li obor pravdivosti GU prediktu G roven celmu universu (GU = U), pak je formule v I pravdiv, nebo je pravdiv podformule x G(x), tedy i G(x) x G(x). Je-li GU vlastn podmnoinou U (GU U), pak sta nalzt jeden prvek (valuaci x), kter nele v GU a formule G(x) x G(x) je v I pravdiv, nebo nen pravdiv antecedent G(x).

9 Existenn kvantifiktor + konjunkce ! Podobn formule x (P(x) Q(x)) je skoro tautologie. Je pravdiv v kad interpretaci I takov, e PU U, nebo pak je |=I P(x) Q(x) [e] pro e(x) PU

nebo QU = U, nebo pak je |=I P(x) Q(x) pro vechny valuace e Tedy tato formule je nepravdiv pouze v takov I, kde PU = U a QU U. Proto vty typu Nkter P jsou Q analyzujeme jako x (P(x) Q(x)). Veobecn kvantifiktor + konjunkce ? Implikace ! x [P(x) Q(x)] je skoro nesplniteln !

Je nepravdiv v kad interpretaci I, ve kter je PU U nebo QU U. Tedy pravdiv je pouze v takov I, kde PU = U a Q U = U ! Proto vty typu Vechna P jsou Q analyzujeme jako x [P(x) Q(x)] Pro vechna individua plat, e je-li to P, pak je to tak Q. (Pak je PU QU definice podmnoiny) Splnitelnost a pravdivost v interpretaci Formule A(x) s volnou promnnou x Je-li A(x) v I pravdiv, pak je |=I x A(x) Je-li A(x) v I splnna, pak je |=I x A(x). Formule P(x) Q(x), P(x) Q(x) s volnou promnnou x definuj prnik a sjednocen obor pravdivosti PU, QU. Pro libovoln P, Q, PU, QU a interpretaci I tedy plat: |=I x [P(x) Q(x)] iff PU QU

|=I x [P(x) Q(x)] iff PU QU |=I x [P(x) Q(x)] iff PU QU = U |=I x [P(x) Q(x)] iff PU QU Model mnoiny formul, vyplvn !!! Model mnoiny formul {A1,,An} je takov

interpretace I, ve kter jsou pravdiv vechny formule A1,...,An. Formule B logicky vyplv z A1, , An, zname A1,,An |= B, jestlie B je pravdiv v kadm modelu mnoiny formul A1,,An. Tedy pro kadou interpretaci I, ve kter jsou pravdiv formule A1, , An (|=I A1,, |=I An) plat, e je v n pravdiv i formule B (|=I B). Okolnosti z vodn definice vyplvn (viz pednka 1) tedy chpeme v PL1 jako interpretace (prediktovch a funknch symbol relacemi a funkcemi nad universem). Vyplvn v PL1 !!! P(x) |= x P(x), avak formule P(x) x P(x) nen tautologi. Proto: A1,...,An |= Z |= (A1 An Z) plat jen pro uzaven formule, tzv. sentence. x P(x) P(a) rovn nen tautologi, pravidlo x P(x) | P(a) nezachovv pravdivost, nen ve

shod s vyplvnm. Pklad interpretace, ve kter nejsou pravdiv: U = N, P sud sla, a 3 Smantick oven platnosti sudku sudek je platn, pokud je zvr pravdiv ve vech modelech pedpoklad. Ale, tchto model me bt nekonen mnoho! Pesto meme na zklad logickho tvaru model pedpoklad (tedy mnoinovch vah) ovit, zda zaruuj pravdivost zvru. Smantick oven platnosti sudku Pklad:

Vechny opice (P) maj rdy banny (Q) Judy (a) je opice Judy m rda banny x [P(x) Q(x)] P(a) -------------------Q(a) QU PU a Relace a vztahy Vroky s jedno-argumentovm prediktem (charakterizujcm njakou vlastnost) zkoumal ji ve starovku Aristoteles. Teprve Gottlob Frege (zakladatel modern

logiky) vak zavedl formln prediktovou logiku (s ponkud jinm jazykem, ne pouvme dnes) s vce-argumentovmi predikty (charakterizujcmi vztahy) a kvantifiktory. Gottlob Frege 1848 1925 Nmeck matematik, logik a filosof, psobil na universit v Jen. Zakladatel modern logiky 18 Smantick oven platnosti sudku

Marie m rda pouze vtze Karel je vtz ------------------------------------- Marie m rda Karla x [R(m,x) V(x)], V(k) R(m,k) ? neplatn RU U U: { , , , } VU U: {i1, i2, , Karel,, in} Dvojice nemus bt prvkem RU, pravdivost pedpoklad to nezaruuje. Bt vtzem je zde pouze nutn podmnka pro to, aby (vybrav) Marie mla nkoho rda, ale nen dostaten.

Smantick oven platnosti sudku Marie m rda pouze vtze Karel nen vtz ------------------------------------ Marie nem rda Karla platn x [R(m,x) V(x)], V(k) R(m,k) ? RU U U: {, , , , } VU U: {i1, i2, , Karel, Karel,, in} Kdyby byla dvojice prvkem RU, pak by musel bt (dle prvn premisy) Karel prvkem VU, ale to nen mon dle druh premisy.

Pravdivost pedpoklad zaruuje pravdivost zvru. Smantick oven sprvnosti sudku Kdo zn Marii a Karla, ten Marii lituje. x [(Z(x,m) Z(x,k)) L(x,m)] Nkte nelituj Marii, akoliv ji znaj. x [L(x,m) Z(x,m)] |= Nkdo zn Marii, ale ne Karla. x [Z(x,m) Z(x,k)] Znzornme, jak budou obory pravdivosti predikt Z a L, tj. relace ZU a LU, aby byly pravdiv premisy: ZU = {, i1,m, i1,k, i2,m, i2,k,,,m, } 1. premisa

2. premisa LU = {, i1,m, ...., i2,m,........., ,m, } Smantick oven sprvnosti sudku Kdo zn Marii a Karla, ten Marii lituje. x [(Z(x,m) Z(x,k)) L(x,m)] Nkte nelituj Marii, akoliv ji znaj. x [L(x,m) Z(x,m)]

|= Nkdo zn Marii, ale ne Karla. Nyn dokeme platnost sporem: pedpokldejme, e vichni, kdo jsou ve vztahu Z k m (tedy i prvek ), jsou tak v Z ke k (negace zvru). ZU = {, i1,m, i1,k, i2,m, i2,k,,,m, ,k, } 1. p. x [Z(x,m) Z(x,k)] 2. p. 1.p.

LU = {, i1,m, ..., i2,m,................, ,m, ,m, } spor 22 Nkter dleit tautologie PL1 |= xAx Ax/t term t je substituovateln za x v A |= Ax/t xAx De Morgan |= x Ax x Ax |= x Ax x Ax Zkony distribuce kvantifiktor: |= x [A(x) B(x)] [x A(x) x B(x)] |= x [A(x) B(x)] [x A(x) x B(x)] |= x [A(x) B(x)] [x A(x) x B(x)]

|= x [A(x) B(x)] [x A(x) x B(x)] |= [xA(x) xB(x)] x [A(x) B(x)] |= x [A(x) B(x)] [x A(x) x B(x)] Smantick zdvodnn: Nech AU, BU jsou obory pravdivosti A, B x[A(x) B(x)] [xA(x) xB(x)] Je-li prnik (AU BU) = U, pak mus bt jak AU, tak BU rovny celmu universu U a naopak x[A(x) B(x)] [xA(x) xB(x)] Je-li sjednocen (AU BU) , pak mus bt AU nebo BU neprzdn (AU nebo BU ) a naopak. |= x[A(x) B(x)] [xA(x) xB(x)] Je-li AU BU, pak je-li AU = U, je tak BU = U. |= x[A(x) B(x)] [xA(x) xB(x)] Je-li AU BU, pak je-li AU , je tak BU . |= x[A(x) B(x)] [xA(x) xB(x)] Je-li prnik (AU BU) , pak mus bt jak AU, tak BU neprzdn (AU a BU ). |= [xA(x) xB(x)] x[A(x) B(x)]

Je-li AU = U nebo BU = U, pak je tak sjednocen (AU BU) = U Nkter dleit tautologie PL1 Formule A neobsahuje voln promnnou x: |= x[A B(x)] [A xB(x)] |= x[A B(x)] [A xB(x)] |= x[B(x) A] [xB(x) A] |= x[B(x) A] [xB(x) A] |= x[A B(x)] [A xB(x)] |= x[A B(x)] [A xB(x)] |= x[A B(x)] [A xB(x)] |= x[A B(x)] [A xB(x)] Zkony komutace kvantifiktor: |= xyA(x,y) yxA(x,y) |= xyA(x,y) yxA(x,y)

|= xyA(x,y) yxA(x,y) ale ne naopak! Smantick zdvodnn: Nech AU, BU jsou obory pravdivosti A, B, x nen voln v A x[A B(x)] [A xB(x)] zejm x[A B(x)] [A xB(x)] zejm x [B(x) A] [x B(x) A] x [B(x) A] x [B(x) A]: doplnk BU je cel universum nebo A: x B(x) A x B(x) A x B(x) A x[B(x) A] [xB(x) A] x [B(x) A] x [B(x) A]: doplnk BU je neprzdn nebo A: x B(x) A x B(x) A x B(x) A Smantick tabla v prediktov logice Dkazy logick pravdivosti a platnosti sudku v prediktov logice 1. du

Typick lohy Dokzat logickou pravdivost formule PL1: Dokzat platnost sudku v PL1: formule F je pravdiv ve vech interpretacch, tj. kad interpretace je jejm modelem |= F

P1, , Pn |= Q pro uzaven formule iff |= (P1 Pn Q) formule Q je pravdiv ve vech modelech mnoiny pedpoklad P1, , Pn Co vyplv z danch pedpoklad? P1, , Pn |= ? Typick lohy Jejich een rozborem (nekonen) mnoiny model je obtn, smantick dkazy jsou pracn Proto hledme jin metody Jednou z nich je metoda smantickch tabel Obdoba, zobecnn stejn metody ve vrokov logice Tedy pevod na disjunktivn / konjunktivn normln formy

Smantick tabla v PL1 VL dkaz logick pravdivosti. Pm dkaz pouijeme konjunktivn normln formu Nepm dkaz disjunktivn normln formu Aplikaci metod VL brn to, e formule me bt uzaven kvantifiktory. Jak se jich zbavit? Pouijeme pravidla: x A(x) | A(x / t), kde t je term substituovateln za x ve formuli A, nejastji t = x

(x)A(x) | A(a), kde a je vhodn konstanta (dosud v dkazovm postupu nepouita) Pravidla pro odstrann kvantifiktor x A(x) | A(x / t), term t substituovateln za x Je-li obor pravdivosti AU = U, pak prvek e*(t) le v AU Zachovv pravdivost, OK (x)A(x) | A(a), kde a je vhodn konstanta Je-li obor pravdivosti AU , pak prvek e*(a) nemus leet v AU Nezachovv pravdivost !! x (y) B(x,y) | B(a, b), kde a, b jsou vhodn konstanty

Jestlie ke kadmu x existuje y takov, e dvojice le v BU, nemus tam leet prv dvojice Nezachovv pravdivost !! Odstrann existennho kvantifiktoru vak zachovv splnitelnost: je mono interpretovat konstanty a, b tak, aby byla formule na prav stran pravdiv, pokud je pravdiv formule vlevo, proto musme pout dkaz sporem, tj. disjunktivn tabla Smantick tabla v PL1 disjunktivn Pklad. Dkaz logick pravdivosti formule: |= x [P(x) Q(x)] [x P(x) x Q(x)]

Dkaz sporem (nesplnitelnosti formule): x [P(x) Q(x)] x P(x) x Q(x) (poad!) 2. 3. 1. x [P(x) Q(x)], P(a) Q(a), P(a), Q(a) x [P(x) Q(x)], P(a), P(a), Q(a) x [P(x) Q(x)], Q(a), P(a), Q(a) + + Ob vtve se uzavely, jsou nesplniteln, pvodn f. je Tautologie Metoda disjunktivnho tabla

|=? x [P(x) Q(x)] [x P(x) x Q(x)] Znegujeme: x [P(x) Q(x)] x P(x) x Q(x) x [P(x) Q(x)], P(a), Q(b) P(a) Q(a), P(b) Q(b), P(a), Q(b) P(a), P(b) Q(b), P(a), Q(b) 1.odstrann - rzn konst. ! 2. odstrann Q(a), P(b) Q(b), P(a), Q(b) P(a), P(b), P(a), Q(b) P(a), Q(b), P(a), Q(b) Q(a), P(b), P(a), Q(b) Q(a), Q(b), P(a), Q(b)

Formule nen logicky pravdiv, 3. vtev nen uzaven Tablo me bt nekonen F: x y P(x,y) x P(x,x) x y z ([P(x,y) P(y,z)] P(x,z)) Promnn x je kvantifikovna veobecnm kvantifiktorem Musme tedy zkouet vechna x: a , a , a , 1 2 3 Pro y musme volit vdy jinou konstantu: P(a1, a2), P(a1, a1) P(a2, a3), P(a2, a2), P(a2, a1) P(a3, a4), P(a3, a3), P(a3, a2) P(a4, a5), P(a4, a4), P(a4, a3) Problm logick pravdivosti nen v PL1 rozhodnuteln

Tablo me bt nekonen 1. 2. F: x y P(x,y) x P(x,x) x y z ([P(x,y) P(y,z)] P(x,z)) Jak je formule F? Je to splniteln, kontradikce, i logicky pravdiv? Zkusme najt model: U=N PU = relace < (oste men) 1 2 3 4 5 ... Je splniteln Me mt formule F konen model? U = {a1, a2, a3, ... ? }

K a1 mus existovat prvek a2 takov, e P(a1, a2), a2 a1 K a2 mus existovat prvek a3 takov, e P(a2, a3), a3 a2, ale tak a3 a1 jinak by bylo P(a1, a2) P(a2, a1), tedy P(a1, a1). K a3 mus existovat prvek a4 takov, e P(a3, a4), a4 a3, ale tak a4 a2 jinak by bylo P(a2, a3) P(a3, a2), tedy P(a2, a2). Atd. do nekonena Platnost sudku - sporem x [P(x) Q(x)] x Q(x) |= x P(x) x [P(x) Q(x)], x Q(x), x P(x) sporn? x [P(x) Q(x)], Q(a), x P(x) x [P(x) Q(x)], x P(x), [P(a) Q(a)], Q(a), P(a) P(a), Q(a), P(a) Q(a), Q(a), P(a) + + Ob vtve se uzavely, mnoina pedpoklad a negovan zvr je sporn, tedy sudek je platn

Platnost sudku (sporem) x [P(x) Q(x)] x Q(x) |= x P(x) dn velryba nen ryba. Ryby existuj. -------------------------------------------Nkter individua nejsou velryby. Mnoina tvrzen: {dn velryba nen ryba, ale ryby existuj, vechno jsou velryby} je sporn. Oven nesplnitelnosti Jist holi hol prv ty, kdo se nehol sami Hol tento holi sm sebe? x y [H(y,y) H(x,y)] |= ? H(y,y) H(a,y), H(y,y) H(a,y) odstrann H(a,a) H(a,a), H(a,a) H(a,a) odstrann H(a,a), H(a,a) H(a,a), H(a,a), H(a,a) H(a,a) H(a,a), H(a,a) H(a,a), H(a,a) +

Prvn vta je sporn, plyne z n cokoliv. Tedy, takov holi prost neexistuje. Shrnut smantick tabla v Smantick tabla pouvme pro nepm dkaz sporem pevodem PL1 do disjunktivn normln formy

(tj. vtven znamen disjunkci, rka konjunkci) Problmem jsou uzaven formule s kvantifiktory, musme se kvantifiktor njak zbavit Nejprve odstranme existenn kvantifiktory tak, e promnnou (kter nen v rozsahu veobecnho kvantifiktoru) nahradme novou konstantou, kter se jet v jazyce nevyskytovala Pak odstraujeme veobecn kvantifiktory tak, e promnnou nahrazujeme postupn vemi konstantami Pokud je existenn vzan promnn x v rozsahu kvantifiktoru veobecnho (pes y), musme za y postupn zkouet dosazovat vechny konstanty a za promnnou x dosazovat vdy novou konstantu Pokud se tablo uzave, je formule i mnoina formul sporn Pklady na smantick tabla |= xy P(x,y) yx P(x,y) negace: xy P(x,y) yx P(x,y) yP(a,y), xP(x,b) x/a, y/b (pro vechna, tedy i pro a, b) P(a,b), P(a,b)

+ Pklady na smantick tabla |= [x P(x) x Q(x)] x [P(x) Q(x)] negace: [x P(x) x Q(x)] x [P(x) Q(x)] x P(x), P(a), Q(a) x Q(x), P(a), Q(a) xP(x),P(a),P(a),Q(a) + xQ(x),Q(a),P(a),Q(a) +

Gottlob Frege Friedrich Ludwig Gottlob Frege (b. 1848, d. 1925) was a German mathematician, logician, and philosopher who worked at the University of Jena. Frege essentially reconceived the discipline of logic by constructing a formal system which, in effect, constituted the first predicate calculus. In this formal system, Frege developed an analysis of quantified statements and formalized the notion of a proof in terms that are still accepted today. Frege then demonstrated that one could use his system to resolve

theoretical mathematical statements in terms of simpler logical and mathematical notions. Bertrand Russell showed that of the axioms that Frege later added to his system, in the attempt to derive significant parts of mathematics from logic, proved to be inconsistent. Nevertheless, his definitions (of the predecessor relation and of the concept of natural number) and methods (for deriving the axioms of number theory) constituted a significant advance. To ground his views about the relationship of logic and mathematics, Frege conceived a comprehensive philosophy of language that many philosophers still find insightful. However, his lifelong project, of showing that mathematics was reducible to logic, was not successful. Stanford Encyclopedia of Philosophy 42 http://plato.stanford.edu/entries/frege/ Bertrand Russell 1872-1970

Britsk filosof, logik, esejista Bertrand Russell Bertrand Arthur William Russell (b.1872 - d.1970) was a British philosopher, logician, essayist, and social critic, best known for his work in mathematical logic and analytic philosophy. His most influential contributions include his defense of logicism (the view that mathematics is in some important sense reducible to logic), and his theories of definite descriptions and logical atomism. Along with G.E. Moore, Russell is generally recognized as one of the founders of analytic philosophy. Along with Kurt Gdel, he is also regularly credited with being one of the two most important logicians of the twentieth century. Kurt Gdel (1906-Brno, 1978-Princeton)

Nejvt logik 20. stolet, ptel A. Einsteina, proslavil se vtami o neplnosti teorie aritmetiky Russell's Paradox Russell's paradox is the most famous of the logical or set-theoretical paradoxes. The paradox arises within naive set theory by considering the set of all sets that are not members of themselves. Such a set appears to be a member of itself if and only if it is not a member of itself, hence the paradox. http://plato.stanford.edu/entries/russellparadox/ Russell's Paradox Some sets, such as the set of all teacups, are not members of themselves. Other sets, such as the set

of all non-teacups, are members of themselves. Call the set of all sets that are not members of themselves "R." If R is a member of itself, then by definition it must not be a member of itself. Similarly, if R is not a member of itself, then by definition it must be a member of itself. Discovered by Bertrand Russell in 1901, the paradox has prompted much work in logic, set theory and the philosophy and foundations of mathematics. Russell's Paradox R mnoina vech normlnch mnoin, kter nejsou prvky sebe sama Otzka: Je R R? Je R normln? vede ke sporu. Symbolicky: xR (xx) definice mnoiny R Poloen otzka Je R R? vede ke sporn formuli (kontradikci): RR RR, nebo: Odpov Ano R nen normln (RR), pak dle definice mnoiny R nem bt R prvkem R, tj. RR

Odpov Ne R je normln (RR), pak je ale dle definice RR (R je mnoina vech normlnch mnoin) Russell wrote to Gottlob Frege with news of his paradox on June 16, 1902. The paradox was of significance to Frege's logical work since, in effect, it showed that the axioms Frege was using to formalize his logic were inconsistent. Specifically, Frege's Rule V, which states that two sets are equal if and only if their corresponding functions coincide in values for all possible arguments, requires that an expression such as f(x) be considered both a function of the argument x and a function of the argument f. In effect, it was this ambiguity that allowed Russell to construct R in such a way that it could both be and not be a member of itself. Russell's Paradox

Russell's letter arrived just as the second volume of Frege's Grundgesetze der Arithmetik (The Basic Laws of Arithmetic, 1893, 1903) was in press. Immediately appreciating the difficulty the paradox posed, Frege added to the Grundgesetze a hastily composed appendix discussing Russell's discovery. In the appendix Frege observes that the consequences of Russell's paradox are not immediately clear. For example, "Is it always permissible to speak of the extension of a concept, of a class? And if not, how do we recognize the exceptional cases? Can we always infer from the extension of one concept's coinciding with that of a second, that every object which falls under the first concept also falls under the second? These are the questions," Frege notes, "raised by Mr Russell's communication." Because of these worries, Frege eventually felt forced to abandon many of his views about logic and mathematics. Of course, Russell also was concerned about the contradiction. Upon learning that Frege agreed with him about the significance of the result, he immediately began writing an appendix for his own soon-to-be-released Principles of Mathematics. Entitled "Appendix B: The Doctrine of Types," the appendix represents Russell's first detailed attempt at providing a principled method for avoiding what was soon to become known as "Russell's paradox." 50

Russell's Paradox The significance of Russell's paradox can be seen once it is realized that, using classical logic, all sentences follow from a contradiction. For example, assuming both P and ~P, any arbitrary proposition, Q, can be proved as follows: from P we obtain P Q by the rule of Addition; then from P Q and ~P we obtain Q by the rule of Disjunctive Syllogism. Because of this, and because set theory underlies all branches of mathematics, many people began to worry that, if set theory was inconsistent, no mathematical proof could be trusted completely. Russell's paradox ultimately stems from the idea that any coherent condition may be used to determine a set. As a result, most attempts at resolving the paradox have concentrated on various ways of restricting the principles governing set existence found within naive set theory, particularly the so-called Comprehension (or Abstraction) axiom. This axiom in effect states that any propositional function, P(x), containing x as a free variable can be used to determine a set. In other words, corresponding to every propositional function, P(x), there will exist a set whose members are exactly those things, x, that have property P. It is now generally, although not universally, agreed that such an axiom must either be abandoned or modified. Russell's own response to the paradox was his aptly named theory of types. Recognizing that self-reference lies at the heart of the paradox, Russell's basic idea is that we can

avoid commitment to R (the set of all sets that are not members of themselves) by arranging all sentences (or, equivalently, all propositional functions) into a hierarchy. The lowest level of this hierarchy will consist of sentences about individuals. The next lowest level will consist of sentences about sets of individuals. The next lowest level will consist of sentences about sets of sets of individuals, and so on. It is then possible to refer to all objects for which a given condition (or predicate) holds only if they are all at the same level or of the same "type." 51 Russells paradox 3 solutions Russell's own response to the paradox was his aptly named theory of types. Recognizing that self-reference lies at the heart of the paradox, Russell's basic idea is that we can avoid commitment to R (the set of all sets that are not members of themselves) by arranging all sentences (or, equivalently, all propositional functions) into a hierarchy. The lowest level of this hierarchy will consist of sentences about individuals. The next lowest level will consist of sentences about sets of individuals. The next lowest level will consist of sentences about sets of sets of individuals, and so on. It is then possible to refer to all objects for which a given condition (or predicate) holds only if they are all at the same level or of the same "type."

This solution to Russell's paradox is motivated in large part by the so-called vicious circle principle, a principle which, in effect, states that no propositional function can be defined prior to specifying the function's range. In other words, before a function can be defined, one first has to specify exactly those objects to which the function will apply. (For example, before defining the predicate "is a prime number," one first needs to define the range of objects that this predicate might be said to satisfy, namely the set, N, of natural numbers.) From this it follows that no function's range will ever be able to include any object defined in terms of the function itself. As a result, propositional functions (along with their corresponding propositions) will end up being arranged in a hierarchy of exactly the kind Russell proposes. 52 Russells paradox 3 solutions Although Russell first introduced his theory of types in his 1903 Principles of Mathematics, type theory found its mature expression five years later in his 1908 article, "Mathematical Logic as Based on the Theory of Types," and in the monumental work he co-authored with Alfred North Whitehead, Principia Mathematica (1910, 1912, 1913). Russell's type theory thus appears in two versions: the "simple theory" of 1903 and the "ramified theory" of 1908. Both versions have been criticized for being too ad hoc to eliminate the

paradox successfully. In addition, even if type theory is successful in eliminating Russell's paradox, it is likely to be ineffective at resolving other, unrelated paradoxes. Other responses to Russell's paradox have included those of David Hilbert and the formalists (whose basic idea was to allow the use of only finite, well-defined and constructible objects, together with rules of inference deemed to be absolutely certain), and of Luitzen Brouwer and the intuitionists (whose basic idea was that one cannot assert the existence of a mathematical object unless one can also indicate how to go about constructing it). Yet a fourth response was embodied in Ernst Zermelo's 1908 axiomatization of set theory. Zermelo's axioms were designed to resolve Russell's paradox by again restricting the Comprehension axiom in a manner not dissimilar to that proposed by Russell. ZF and ZFC (i.e., ZF supplemented by the Axiom of Choice), the two axiomatizations generally used today, are modifications of Zermelo's theory developed primarily by Abraham Fraenkel. 53

Recently Viewed Presentations

  • 2014 Changes - Louisiana Department of Revenue

    2014 Changes - Louisiana Department of Revenue

    Louisiana Department of Revenue. ... Bobbie Swafford at (225) 219-2062 or by email at . ... If you received a notice of tax due, mail your payment and the payment coupon to LDR in the reply envelope. Electronic payment options...
  • Corso di Laurea Specialistica in Metodologie chimiche ...

    Corso di Laurea Specialistica in Metodologie chimiche ...

    TEMPERATURA: da 340 a 360°C, 1°C/min CARRIER GAS (He): 1,0 ml/min. ANALISI DEI TRIACILGLICEROLI POP PLP+PPoO POS POO PLS PLO PLL+PoLO SOS+POA SOO OOO+SLS SLO OLO+SLL SLL OLL LLL LLnL POBe AOO GaOO+PLBe ALO OLGa ALL GaLL POLg+SOBe BeOO PLLg...
  • By Tommy Boss

    By Tommy Boss

    "To say that a work of art is good, but incomprehensible to the majority of men, is the same as saying of some kind of food that it is very good but that most people can't eat it."-Leo Tolstoy. The...
  • Medieval Castles - Community Unit School District 308

    Medieval Castles - Community Unit School District 308

    Ladders. Ladders were used by those attacking a castle to climb over the walls and fight the people living in the castle. Disadvantage - leaving the man climbing the ladder subject to attack by arrow, boiling water or oil, or...
  • Occupational Health

    Occupational Health

    Health hazards are things that can cause sickness or harm your health. Which are the routes of entry? Skin Eyes Mouth Nose Chemical hazards - examples: Lead Asbestos Silica Solvents Physical hazards - examples: Noise Temperature extremes Biological hazards -...
  • WIN XP Operating System

    WIN XP Operating System

    Exploring the Basics of Windows XP Exploring the Basics of Microsoft Windows XP * Exploring the Basics of Microsoft Windows XP * Manipulating a Window Exploring the Basics of Microsoft Windows XP * Moving a Window To drag an object...
  • Chemical BONDING Chemical Bond  A bond results from

    Chemical BONDING Chemical Bond A bond results from

    Draw Polyatomics Ammonium Sulfate Types of Covalent Bonds NON-Polar bonds Electrons shared evenly in the bond E-neg difference is zero Between identical atoms Diatomic molecules Types of Covalent Bonds Polar bond Electrons unevenly shared E-neg difference greater than zero but...
  • Multivariate Analysis  Many statistical techniques focus on just

    Multivariate Analysis Many statistical techniques focus on just

    The data was split into three employment sectors Teaching, government and private industry Each sector showed a positive relationship Employer type was confounded with degree level Simpson's Paradox In each of these examples, the bivariate analysis (cross-tabulation or correlation) gave...