ECONOMICS & BUSINESS (Includes Business Ethics

Description

• mémoire
• leçon - matière potentielle : from asia
• cours magistral
• expression écrite - matière potentielle : agnes of harcourt
• exposé
• expression écrite

ECONOMICS & BUSINESS (Includes Business Ethics) Fishman, Robert M., and Messina, Anthony M., eds. • The Year of the Euro: The Cultural, Social, and Political Import of Europe's Common Currency, paper Ghilarducci, Teresa, ed. • What You Need to Know About the Economics of Growing Old* (*But Were Afraid to Ask), paper Murphy, Patrick E., ed. • Eighty Exemplary Ethics Statements, paper Williams, C.S.C., Oliver F., ed.

• honor of robert w. hanning
• leroy s.
• j. joyce
• oliver f.
• lawrence a.
• c.s.c.
• s. j.
• s.j.
• cloth
• paper
• catholic church

Sujets

• Mémoire
• Cours magistral
• Exposé
• Vaught
• Edward Schillebeeckx

Informations

• Publié par: ossu
• Nombre de lectures: 17
• Langue: English

Extrait

SERGEI N. ARTEMOV & LEV D. BEKLEMISHEV
PROVABILITY LOGIC
1 INTRODUCTION
[The idea of provability logic seems to originate in a short paper G odel,
]1933. K. G odel was motivated by the question of providing Brouwer’s
intuitionistic logic, as formalized by Heyting, with an adequate semantics.
According to Brouwer, intuitionistic truth means provability. Here is a
[summary from Constructivism in Mathematics (Troelstra and van Dalen,
]1988, p. 4):
“A statement is true if we have a proof of it, and false if we can
showthattheassumptionthatthereisaproofforthestatement
leads to a contradiction.”
An axiom system for intuitionistic logic was introduced by Heyting in 1930;
[itsfulldescriptionmaybefoundinfundamentalmonographs Kleene, 1952;
]Troelstra and van Dalen, 1988 . In 1931–34 A. Heyting and A.N. Kol-
mogorov made Brouwer’s definition of intuitionistic truth explicit, though
informal, by introducing what is now known as the Brouwer–Heyting–Kol-
[mogorov (BHK) semantics (Heyting, 1931; Heyting, 1934; Kolmogoroff,
]1932). BHK semantics suggests that a formula is called true if it has a
proof. Further, a proof of a compound statement is described in terms of
proofs of its components:
† a proof of A^B consists of a proof of A and a proof of B;
† a proof of A_B is given by presenting either a proof of A or a proof
of B;
† a proof of A ! B is a construction transforming proofs of A into
proofs of B;
† falsehood ? is a proposition which has no proof, :A is a shorthand
for A!?.
The BHK semantics is widely recognized as the intended semantics for
[ ]intuitionistic logic. In G odel, 1933 an attempt was made to formalize the
BHK semantics. K.G odelintroducedamodalcalculusofclassicalprovabil-
ity (essentially equivalent to the Lewis modal system S4) and defined the
intuitionistic propositional logic IPC in this logic. G odel’s provability cal-
culus is based on the classical propositional logic and has the modal axioms
and rules
2F!F,
D. Gabbay and F. Guenthner (eds.),
Handbook of Philosophical Logic, Volume 10, 1–??.
°c 2002, Kluwer Academic Publishers. Printed in the Netherlands.2 SERGEI N. ARTEMOV & LEV D. BEKLEMISHEV
2(F!G)!(2F!2G),
2F!22F,
‘F )‘2F (necessitation rule).
G odel considered a translation t(F) of an intuitionistic formula F into the
classicalmodallanguage: “boxeachsubformulaof F”apparentlyregarding
1such a translation to be a fair formalization of the Brouwer thesis
intuitionistic truth = provability:
G odel established that
IPC‘F ) S4‘t(F);
thusprovidingareadingof IPC-formulasasstatementsaboutclassicalprov-
ability. He conjectured that the converse (() also held and concluded
[ ]in 1938 (see G odel, 1995 , p. 100–101): Intuitionismus ist daraus ableit-
2 [ ]bar . The (() conjecture was proved in McKinsey and Tarski, 1948 . The
ultimate goal, however, of defining IPC via classical proofs had not been
achieved because S4 was left without an exact intended semantics of the
provability operator 2:
IPC,! S4,!::: ? :::,!CLASSICAL PROOFS:
Here, CLASSICAL PROOFS refers to systems based on a proof predicate
Proof(x;y) denoting “x is the code of a proof of the formula having a code
y”foraclassicalfirstordertheorycontainingPeanoarithmetic PA.G odelin
[ ]G odel,1933 identifiedaproblemthereandpointedoutthatanaturalread-
ing of2F as the formal provability predicate Provable(F)=9xProof(x;F)
did not work.
Let ? be the boolean constant false and 2F be Provable(F).
Then2?!? corresponds to the statement Con(PA) expressing
consistency of PA. An S4-theorem 2(2?!?) expresses the
assertionthatCon(PA)isprovableinPA,whichisfalseaccording
to the second G odel incompleteness theorem.
[ ]Thus, G odel,1933 showedthatS4wasaprovabilitycalculuswithoutanex-
act provability semantics, whereas the interpretation of 2F = Provable(F)
was an exact provability semantics for modality without axiom system
known. G odel’s paper left open two natural problems:
1. Find the modal logic of the formal provability predicate Provable(F).
1 [ ]This translation appeared earlier in a paper by I.E. Orlov Orlov, 1928, who applied
it to a system different from S4.
2Intuitionism is derivable from this.PROVABILITY LOGIC 3
2. Find an exact provability semantics of S4 and thereby of IPC.
It was already clear that solutions to 1 and 2 led to essentially different
models of Provability, each targeting its own set of applications. The two
parts of the present paper — “Part I, Logic of Provability” (Sections 2–10)
and “Part II, Logic of Proofs” (Sections 11–16) — roughly correspond to
the developments around these two questions. Here in the Introduction we
briefly review main achievements in both directions.
Logic of Provability
The first significant step towards a solution of Problem 1 was made by
[ ]M.H. L ob L ob, 1955 who formulated, on the basis of the previous work
[ ]by D. Hilbert and P. Bernays from 1939 (see Hilbert and Bernays, 1968 ),
3a number of natural conditions on the formal provability predicate (nowa-
daysknownasBernays–L obderivabilityconditions )andobservedthatthese
conditionsweresufficientfortheproofofG odel’ssecondincompletenessthe-
orem. Moreover,underthesameconditionshefoundanimportantstrength-
eningoftheG odeltheorem. Heprovedthatthefollowingisavalidprinciple
of the logic of the formal provability predicate:
2(2F !F)!2F:
This powerful principle, taken together with the axioms and rules of the
modal logic K4 turned out later to provide a complete axiomatization of
the logic of formal provability. This system currenly bears the name GL for
4G odel and L ob .
M.H.L ob’swork, followedbysignificantadvancesingeneralunderstand-
ing of formalization of metamathematics particularly in the hands of S. Fe-
[ ]ferman Feferman, 1960, inspired S. Kripke, G. Boolos, D. de Jongh and
others to look into the problem of exact axiomatization of the logic of prov-
ability. Independently, the same notion appeared in an algebraic context in
[ ]the work of R. Magari and his school in Italy (see Magari, 1975b). A dra-
[maticaccountoftheseearlydevelopmentscanbefoundin BoolosandSam-
]bin,1991. Asanimportantearlyresultonprovabilitylogicstandsoutathe-
orem by D. de Jongh, found independently by G. Sambin, who established
[that the system GL has the fixed point property (see Smorynski,´ 1977b;
Smorynski,´ 1985] and some details below).
3These conditions were essentially expressed by the last two axioms and the necessi-
tation rule of the above mentioned system S4, in other words, by the modal logic K4. So,
their validity must have been known to G odel.
4This logic was alternatively denoted by G, L, K4.W, PrL. Neither G odel nor L ob
formulated the logic explicitly, though undeniably they established the validity of the
underlying arithmetical principles. Presumably, it was T. Smiley in whose work on the
[ ]foundations of ethics Smiley, 1963 the axioms of GL appeared for the first time.4 SERGEI N. ARTEMOV & LEV D. BEKLEMISHEV
H.Friedmanformulatedtheproblemofdecidabilityoftheletterlessfrag-
[ ]ment of provability logic as his Problem 35 in Friedman, 1975a. This
question, which happened to be much easier than the general case, was
[immediately answered by a number of people including G. Boolos Boolos,
]1976,J.vanBenthem,C.BernardiandF.Montagna. Abreakthroughcame
in 1976 when R. Solovay published a solution of the general problem show-
ing that the system GL axiomatizes the provability logic for any sufficiently
[ ]strong and sound formal theory Solovay, 1976. He also showed that the
set of modal formulas expressing universally true principles of provability
was axiomatized by a decidable extension of GL, which is usually denoted
by S and is called the truth provability logic.
Solovay’s results and his novel methods opened a new stage in the devel-
opmentofprovabilitylogic,withseveralgroupsofresearchers,mostnotably
in the USA (R. Solovay, G. Boolos, C. Smorynski),´ the Netherlands (D. de
Jongh, A. Visser), Italy (R. Magari, F. Montagna, G. Sambin, L. Valen-
tini), andUSSR(S.ArtÄemovandhisstudents), startingtoworkintensively
[ ]in this area. Textbooks by G. Boolos Boolos, 1979b and C. Smorynski´
[ ]Smorynski,´ 1985, the first of which appeared very early, played an impor-
tant educational role.
The main thrust of the research effort went into the direction of gen-
eralizing Solovay’s results to more expressive languages. Here we briefly
mention some of the probems that received prominent attention. Most of
them (though not all) are covered in greater detail below and roughly cor-
respond to the sections in this paper.
First order provability logics. It was soon discovered that the first or-
der version of GL is not arithmetically complete. G. Boolos formulated in
his book the problem of axiomatizing the full first order provability logic.
Improtant partial results in this direction were obtained by F. Montagna
[ ]Montagna, 1987a. A final negative solution was given in the papers by S.
[ ] [ ]ArtÄemov Artemov, 1985a and V. Vardanyan Vardanyan, 1986. In par-
0ticular, V. Vardanyan showed that this logic is Π -complete, thus not effec-2
tively axiomatizable. Earlier S. ArtÄemov showed that the first order truth
provability logic is not even arithmetical. Independently but somewhat
later similar results were obtained by V.