Logblog: Richard Zach's Logic Blog

University of Calgary

UofC Navigation

Submitted by Richard Zach on Fri, 09/05/2008 - 5:27pm

Last year in May, Berkeley held a conference in honor of Bill Craig, who will turn 90 this coming November. Bill is probably best known for the Craig Interpolation Theorem and the theorem that every recursively enumerable theory is recursively axiomatizable. Just in time, the Festschrift arising from that conference has appeared online. It's a special issue of Synthese, edited by Paolo Mancosu. The table of contents is below; Paolo's introduction contains a nice outline of Bill's life and work.

- Paolo Mancosu, Introduction
- William Craig, Elimination problems in logic: a brief history
- William Craig, The road to two theorems of logic
- Solomon Feferman, Harmonious logic: Craig’s interpolation theorem and its descendants
- William Demopoulos, Some remarks on the bearing of model theory on the theory of theories
- Michael Friedman, Wissenschaftslogik: The role of logic in the philosophy of science
- Jouko Väänänen, The Craig Interpolation Theorem in abstract model theory
- Giovanna D’Agostino, Interpolation in non-classical logics
- Gerard R. Renardel de Lavalette, Interpolation in computing science: the semantics of modularization
- Johan Benthem, The many faces of interpolation

Submitted by Richard Zach on Fri, 09/05/2008 - 3:05pm

Henri Cartan, last surviving member of the original Bourbakistes, died on August 13. He'll be remembered not just for his mathematical work, but also for his political engagement for human rights and European federalism. Obits:

Daily Telegraph

Die Zeit

Le Figaro

Le Monde

New York Times

Washington Post

(HT: Giuseppina Ronzitti)

Submitted by Richard Zach on Fri, 09/05/2008 - 2:52pm

The CiE series of conferences now has an associated association. At 0 EUR, membership is pretty cheap! By the way, next year's CiE in Heidelberg will be a blast for the logic-y side of computation. Jeremy Avigad has agreed to be one of the invited speakers, Pavel Pudlák will give a tutorial, and there will be a session on philosophical and mathematical aspects of hypercomputation organized by Phil Welch and James Ladyman. Deadline for paper submission is January 20, 2009.

After four very successful conferences in Amsterdam in 2005, Swansea in 2006, Siena in 2007 and Athens in 2008, our community has officially formed the associationComputability in Europeat the Annual General Meeting at this year's Computability in Europe conference in Athens. The object of the Association is to promote the development, particularly in Europe, of computability-related science, ranging over mathematics, computer science, and applications in various natural and engineering sciences such as physics and biology. This also includes the promotion of the study of philosophy and history of computing as it relates to questions of computability. A draft constitution of the Association can be found at

http://www.amsta.leeds.ac.uk/~pmt6sbc/CiE.const.draft.pdf

We invite every researcher interested in the object of the Association to become a member. The initial membership fee is set at zero, and lasts until 30 June 2010.

To apply for membership of the Association, please complete and submit the form at

http://www.cs.swan.ac.uk/acie/

Any enquiries concerning association CiE membership should be sent to the Membership Secretary, Arnold Beckmann, at a.beckmann@swansea.ac.uk.

Submitted by Richard Zach on Sat, 08/30/2008 - 4:39pm

Another exciting new blog, by Chris Pincock: Honest Toil.

Submitted by Richard Zach on Sat, 08/30/2008 - 4:31pm

My former student Rafa? Urbaniak has a new blog, Entia et Nomina.

Submitted by Richard Zach on Fri, 08/08/2008 - 5:53am

Submitted by Richard Zach on Thu, 07/17/2008 - 9:57am

Mark van Atten's excellent entry on the history of intuitionistic logic for the Stanford Encyclopedia is out. And last week in Jena, my Carnap Project colleague Steve Awodey got an awesome stamp commemorating the centennial (last year) of Brouwer's thesis (not from me, so don't ask):

Submitted by Richard Zach on Thu, 07/03/2008 - 11:01am

Krister Segerberg will be visiting the Philosophy Department at the University of Calgary during the 2008/09 academic year as Killam Visiting Scholar. He'll be teaching two courses, an intro to modal logic course in the Fall and an advanced course in the Winter term. There will also be a little two day workshop, most likely in January, with him, Aldo Antonelli, and Nuel Belnap.

Submitted by Richard Zach on Thu, 07/03/2008 - 9:44am

My department is advertising for a junor position in logic. Please apply or tell me if you know of any promising candidates. If you need more information, you can contact Ali Kazmi (contact details below) or me, of course. We also have a recruitment page. Salient details missing from the ad: teaching load is 2-2, instruction is in English.

The Department of Philosophy at the University of Calgary invites applications for a tenure?track position at the rank of Assistant Professor beginning July 1, 2009. A PhD or equivalent is required. The Department is seeking candidates who are able to teach a range of courses in logic, from elementary formal logic to the advanced levels, including the meta?theory of first?order logic, undecidability, incompleteness, and non?classical logics. The area of specialization for this position is Logic or a related field of study.Teaching duties include undergraduate and graduate instruction as well as graduate supervision. Complete dossiers, including a curriculum vitae, at least three confidential letters of reference, post?graduate transcripts, a recent sample of writing, and evidence of teaching effectiveness may be sent to:

Merlette Schnell

Department of Philosophy

University of Calgary

2500 University Drive NW

Calgary, Alberta T2N 1N4

Canada

schnell@ucalgary.caThe Selection Committee will begin to assess applications after NOVEMBER 21, 2008.

Applications will be accepted until the position is filled. All qualified candidates are encouraged to apply; however, Canadian citizens and permanent residents of Canada will be given priority. The University of Calgary respects, appreciates, and encourages diversity. Specific inquiries about this position may be directed to:

Ali Kazmi, Head

Department of Philosophy

University of Calgary

(403) 220?5535

akazmi@ucalgary.ca

Submitted by Richard Zach on Sun, 06/29/2008 - 12:34pm

Hannes Leitgeb has edited an interesting special issue of Studia Logica on "Psychologism in Logic?". From the introduction:

There is no doubt that Frege’s and Husserl’s famous attack on Psychologism in logic had a significant influence on the emergence of logic as a separate discipline. Now that this battle can be safely regarded won, it is time to reconsider psychologism from a modern point of view. Logic has taken a cognitive turn in the meantime: formal representations of agents are used as parts of logical models, cognitive concepts are treated as logical constants in much the same way as the negation sign or the quantifiers, the logic of commonsense reasoning has become the joint interest of theoretical computer scientists and psychologists, and naturalistic accounts of logic and mathematics aim to reduce the gap between the apriori and the empirical. Does this necessitate a reassessment of psychologism in logic? That is the question to be addressed by this special issue.

Submitted by Richard Zach on Wed, 06/25/2008 - 7:06am

NYU Philosophy is hosting a conference on the philosophy of mathematics, ~~October~~ April 10-12, ~~2008~~ 2009. The speakers are John Burgess, Haim Gaifman, Joel Hamkins, Kai Hauser, Peter Koellner, Stewart Shapiro, Stephen Simpson, Bill Tait, Neil Tennant, and Hugh Woodin.

Submitted by Richard Zach on Wed, 06/25/2008 - 7:02am

Submitted by Richard Zach on Tue, 06/24/2008 - 6:45pm

Pictures and videos from the Gödel Centenary Fellowship are online here.

Submitted by Richard Zach on Tue, 06/24/2008 - 6:45pm

Pictures and videos from the Gödel Centenary Fellowship celebration are online here.

Submitted by Richard Zach on Fri, 06/13/2008 - 12:38am

There's a very interesting issue of Erkenntnis just out. It's the proceedings of PhiPMSAP 1. PhiMSAP is the Network on Philosophy of Mathematics: Sociological Aspects and Mathematical Practice of the DFG, run mostly by Benedikt Löwe and Thomas Müller, the third workshop of which I just had the pleasure of attending. Contents of the issue:

Experimental Mathematics by Alan Baker

Visualizations in Mathematics Kajsa Bråting and Johanna Pejlare

A Mathematician Reflects on the Useful and Reliable Illusion of Reality in Mathematics by Keith Devlin

The Role of Axioms in Mathematics by Kenny Easwaran

What can the Philosophy of Mathematics Learn from the History of Mathematics? by Brendan Larvor

On Abstraction and the Importance of Asking the Right Research Questions: Could Jordan have Proved the Jordan-Hölder Theorem? by Dirk Schlimm

Pi on Earth, or Mathematics in the Real World by Bart Van Kerkhove and Jean Paul Van Bendegem

Submitted by Richard Zach on Wed, 06/11/2008 - 11:19am

The first issue of the Review of Symbolic Logic will be out soon (Cambridge UP page here). The Review, like the Journal and Bulletin of Symbolic Logic will be mailed to all members of the Association for Symbolic Logic. So if you're not a member (and you probably should be, if you're reading this!), join now! (Only 76$ per year--38$ for students-- for three of the most important journals in logic, plus all the other benefits of membership)

Table of contents:

A Cut-Free Simple Sequent Calculus for Modal Logic S5

FRANCESCA POGGIOLESI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

How Applied Mathematics Became Pure

PENELOPE MADDY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

The Closing of the Mind: How the Particular Quantifier Became Existentially Loaded Behind Our Backs

GRAHAM PRIEST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Recognizing Strong Random Reals

DANIEL OSHERSON AND SCOTT WEINSTEIN. . . . . . . . . . . . . . . . 56

Truth-Functionality

BENJAMIN SCHNIEDER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Probabilistic Conditionals are Almost Monotonic

MATTHEW P. JOHNSON AND ROHIT PARIKH . . . . . . . . . . . . . . . . 73

On Adopting Kripke Semantics in Set Theory

LUCA INCURVATI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

The Iterative Conception of Set

THOMAS FORSTER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

A Decision Procedure for Probability Calculus with Applications

BRANDEN FITELSON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Ultimate Truth vis-à-vis Stable Truth

P.D. WELCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

Submitted by Richard Zach on Mon, 06/09/2008 - 9:09am

Last week, Brian Leiter posted about possibly re-drawing the dividing lines between the specialty areas ranked in the Philosophical Gourmet Report

In a comment, Cian asks:

Philosophical Logic and Mathematical Logic. While there is a fair amount of divergence between the two rankings, I also see, for example, that NYU gets ranked at 4.5 in mathematical logic even though as far as I can see, almost everything the relevant people have written about logic is more naturally classified as philosophical logic than as mathematical logic. Is that a sign that the borderline between these two areas is too wide and fuzzy for the distinction to be worth making by the PGR?

If one thinks of mathematical logic as "formal logic motivated by mathematical concerns"---roughly, this is the conception according to which mathematical logic consists of model theory, set theory, recursion theory, and proof theory--then it is indeed puzzling why NYU gets ranked at the top of group 2 in the mathematical logic ranking, in addition to the top in the philosophical logic ranking. But one might also think of mathematical logic the way it's defined in the AMS Mathematics Subject Classification (03). Now how do we take "philosophical logic"? But if we take the now-standard (at least in North America) definition of "philosophical logic", then it's that part of formal logic that paradigmatically includes: "various versions of modal, temporal, epistemic, and deontic logic; constructive logics; relevance and other sub-classical logics; many-valued logics; logics of conditionals; quantum logic; decision theory, inductive logic, logics of belief change, and formal epistemology; defeasible and nonmonotonic logics; formal philosophy of language; vagueness; and theories of truth and validity" (from editorial description of the Journal of Philosophical Logic). Almost all of that is included in MSC 03Bxx! Clearly, for the purpose of the PGR at least, it would be better to define "mathematical logic" as "formal logic, but not philosophical logic".

I don't know if the evaluators for the PGR "mathematical logic" and "philosophical logic" categories get instructions on the intended scope of the category. It probably also makes a big difference--bigger than in other specialty areas--if faculty with appointments in the mathematics (or computer science) departments get included in the PGR faculty lists. As the note at the bottom of the ranking says, "much work in mathematical logic goes on in Mathematics and Computer Science departments."

Then there's also the confusion between the definition of "philosophical logic" as "formal logic motivated by philosophy" and the older (British) use of "philosophical logic" to mean "philosophy motivated by logic" (and including philosophical study of notions such as reference, necessity, truth, analyticity, etc.) Maybe a better term for that is "philosophy of logic". Leiter's proposed restructuring would have a category "philosophy of language & logic" (but no philosophical logic category).

I don't think that "philosophical logic" and "mathematical logic" should be combined in the PGR ranking. But as it currently stands--with the scope of these categories so unclear--the rankings aren't particularly informative. I'm not sure what would be more informative, but getting clarity on the definitions would be one step. Maybe it wouldn't be such a bad idea to include "philosophy of logic" in the "philosophy of language" category, and reserve "philosophical logic" for the formal work you find in the JPL or the Review of Symbolic Logic. Maybe it wouldn't even be a bad idea to merge mathematical logic into the philosophy of mathematics category. What do others think?

Submitted by Richard Zach on Mon, 06/02/2008 - 5:41pm

What more do we know about a theorem if we have a proof (by restricted means) than merely that it is true? That's an old question of Kreisel's that motivated his "unwinding program": extract additional information from proofs of theorems in constructive theories, such as bounds on y in theorems of the form ?x?y A(x, y).

Ulrich Kohlenbach has worked on problems like this more than anyone else, and his book Applied Proof Theory: Proof Interpretations and Their Use in Mathematics is now out from Springer.

Ulrich Kohlenbach presents an applied form of proof theory that has led in recent years to new results in number theory, approximation theory, nonlinear analysis, geodesic geometry and ergodic theory (among others). This applied approach is based on logical transformations (so-called proof interpretations) and concerns the extraction of effective data (such as bounds) from prima facie ineffective proofs as well as new qualitative results such as independence of solutions from certain parameters, generalizations of proofs by elimination of premises.The book first develops the necessary logical machinery emphasizing novel forms of Goedel's famous functional (Dialectica) interpretation. It then establishes general logical metatheorems that connect these techniques with concrete mathematics. Finally, two extended case studies (one in approximation theory and one in fixed point theory) show in detail how this machinery can be applied to concrete proofs in different areas of mathematics.

1 Introduction

2 Unwinding proofs (‘Proof Mining’)

2.1 Introductory remark

2.2 Informal treatment of ineffective proofs

2.3 Herbrand’s theorem and the no-counterexample interpretation

2.4 Exercises, historical comments and suggested further reading3 Intuitionistic and classical arithmetic in all finite types

3.1 Intuitionistic and classical predicate logic

3.2 Intuitionistic (‘Heyting’) arithmetic HA and Peano arithmetic PA

3.3 Extensional intuitionistic (‘Heyting’) and classical (‘Peano’)

arithmetic in all finite types

3.4 Fragments of (W)E-HA^? and (W)E-PA^?

3.5 Fragments corresponding to the Grzegorczyk hierarchy

3.6 Models of E-PA^?

3.7 Exercises, historical comments and suggested further reading4 RepresentationofPolish metric spaces

4.1 Representation of real numbers

4.2 Representation of complete separable metric (‘Polish’) spaces

4.3 Special representation of compact metric spaces

4.4 Fragments, exercises, historical comments and suggested further

reading5 Modified realizability

5.1 The soundness and program extraction theorems

5.2 Remarks on fragments of E-HA^?

5.3 Exercises, historical comments and suggested further reading6 Majorizability and the fan rule

6.1 A syntactic treatment of majorization and the fan rule

6.2 Exercises, historical comments and suggested further reading7 Semi-intuitionistic systems and monotone modified realizability

7.1 The soundness and bound extraction theorems

7.2 Fragments, exercises, historical comments and suggested further

reading8 Gödel’s functional (‘Dialectica’) interpretation

8.1 Introduction

8.2 The soundness and program extraction theorems

8.3 Fragments, exercises, historical comments and suggested further

reading9 Semi-intuitionistic systems and monotone functional interpretation

9.1 The soundness and bound extraction theorems

9.2 Applications of monotone functional interpretation

9.3 Examples of axioms ? : Weak König’s lemmaWKL

9.4 WKL as a universal sentence ?

9.5 Fragments, exercises, historical comments and suggested further

reading10 Systems based on classical logic and functional interpretation

10.1 The negative translation

10.2 Combination of negative translation and functional interpretation

10.3 Application: Uniform weak König’s lemma UWKL

10.4 Elimination of extensionality

10.5 Fragments of (W)E-PA^?

10.6 The computational strength of full extensionality

10.7 Exercises, historical comments and suggested further reading11 Functional interpretation of full classical analysis

11.1 Functional interpretation of full comprehension

11.2 Functional interpretation of dependent choice

11.3 Functional interpretation of arithmetical comprehension

11.4 Functional interpretation of (IPP) by finite bar recursion

11.5 Models of bar recursion

11.6 Exercises, historical comments and suggested further reading12 A non-standard principle of uniform boundedness

12.1 The ?^0_1 -boundedness principle

12.2 Applications of ?^0_1 -boundedness

12.3 Remarks on the fragments E-G_nA^?

12.4 Exercises, historical comments and suggested further reading13 Elimination of monotone Skolem functions

13.1 Skolem functions of type degree 1 in fragments of finite type

arithmetic

13.2 Elimination of Skolem functions for monotone formulas

13.3 The principle of convergence for bounded monotone sequences

of real numbers (PCM)

13.4 ?^0_1 -CA and ?^0_1 -AC

13.5 The Bolzano-Weierstraß property for bounded sequences in R^d

13.6 Exercises, historical comments and suggested further reading14 The Friedman A-translation

14.1 The A-translation

14.2 Historical comments and suggested further reading15 Applications to analysis: general metatheorems I

15.1 A general metatheorem for Polish spaces

15.2 Applications to uniqueness proofs

15.3 Applications to monotone convergence theorems

15.4 Applications to proofs of contractivity

15.5 Remarks on fragments of T^?

15.6 Historical comments and suggested further reading16 Case study I: Uniqueness proofs in approximation theory

16.1 Uniqueness proofs in best approximation theory

16.2 Best Chebycheff approximation I

16.3 Best Chebycheff approximation II

16.4 Best L_1-approximation

16.5 Exercises, historical comments and suggested further reading17 Applications to analysis: general metatheorems II

17.1 Introduction

17.2 Main results in the metric and hyperbolic case

17.3 The case of normed spaces

17.4 Proofs of theorems 17.35, 17.52 and 17.69

17.5 Further variations

17.6 Treatment of several metric or normed spaces X_1 . . . , X_n

simultaneously

17.7 A generalized uniform boundedness principle ?-UB^X

17.8 Applications of ?-UB^X

17.9 Fragments of A^? [. . .]

17.10 Exercises, historical comments and suggested further reading18 Case study II: Applications to the fixed point theory of nonexpansive

mappings

18.1 General facts

18.2 Applications of the metatheorems from chapter 17

18.3 Logical analysis of the proof of the Borwein-Reich-Shafrir

theorem

18.4 Asymptotically nonexpansive mappings

18.5 Applications of proof mining in ergodic theory

18.6 Exercises, historical comments and suggested further reading19 Final comments

Submitted by Richard Zach on Mon, 05/19/2008 - 10:07am

From my colleague up north, Rob Wilson:

The What Sorts of People blog is now up and running: check it out. This is the blog for the What Sorts of People Should There Be? network, a collaborative blog with regular contributions from around 10 team members. Short, recent posts are available on double-amputee Oscar Pistorius's bid to compete Olympically, and on a so-recent-it's-still-forthcoming piece by Steve Pinker in The New Republic on the concept of dignity and its use in a recent President's Council on Bioethics report. Biella Coleman, who was a Killam Postdoc at Alberta last year and now teaches at NYU, has just posted a tempered rant on the blog on medical genetics and eugenics.

Submitted by Richard Zach on Sat, 05/17/2008 - 11:44am

Rob Loftis has a roundup of open access introductory logic textbooks. And Hans von Ditmarsch has a list of logic course software.

- Halbach & Visser: Self-reference in arithmetic
- Storify'd Michael Beaney's Vinna Circle Lecture on Susan Stebbing
- More on Shatunovsky, Kagan, and Yanovskaya
- Some Lesser Known (to me) Russian/Soviet Logicians
- Graduate Programs in Philosophical Logic
- One person's modus ponens...
- Adolf Lindenbaum
- Kennedy's Interpreting Gödel Out Now