Logblog: Richard Zach's Logic Blog

University of Calgary

UofC Navigation

Submitted by Richard Zach on Mon, 04/24/2006 - 3:20pm

The February issue of Synthese is a special issue on proof-theoretic semantics, edited by Reinhard Kahle and Peter Schröder-Heister. It's papers from a conference in Tübingen in 1999.

- Dag Prawitz, Meaning Approached Via Proofs
- Peter Schroeder-Heister, Validity Concepts in Proof-theoretic Semantics
- Patrizio Contu, The Justification of the Logical Laws Revisited
- Lars Hallnäs, On the Proof-theoretic Foundation of General Definition Theory
- William W. Tait, Proof-theoretic Semantics for Classical Mathematics
- Göran Sundholm, Semantic Values for Natural Deduction Derivations
- Kosta Dosen, Models of Deduction
- Reinhard Kahle, A Proof-theoretic View of Necessity
- Gabriele Usberti, Towards a Semantics Based on the Notion of Justification
- Grigori Mints, Notes on Constructive Negation
- Michael Rathjen, Theories and Ordinals in Proof Theory

Submitted by Richard Zach on Fri, 04/21/2006 - 8:48pm

Call for Papers:

Uncertainty: Reasoning about probability and vagueness

September 5 to 8, Prague

Uncertainty is a ubiquitous phenomenon in everyday life, but it is also a topic of fundamental significance to many scientific disciplines. Uncertainty taken here in a broad sense, has many facets - among them probability and vagueness, including possibility, confidence, fuzziness etc. These are captured by different theories which often seem to be conceptually and technically incompatible. Therefore there is no universally accepted theory covering all this area and there are many reasons why we shall neither expect nor want to have one. On the other hand there have been attempts to cross the borders - there are theories trying to bridge gaps between rival approaches and looking for their common background.

The aim of the conference is to provide a platform for an open discussion between proponents of the main theories of uncertainty and vagueness on the market. Special attention shall be paid to the comparison of theories, analyzing differences and similarities of the respective concepts of uncertainty. Of particular interest are logical aspects and formal models of reasoning about vague information.

The scope of interest contains, but is not limited to the following topics:

- reasoning under uncertainity
- theories of vagueness
- supervaluationism
- foundations of fuzzy logic
- concepts of probability
- possibility and trust
- epistemic and pragmatic aspects of uncertainty

The invited speakers of the colloquium: Patrick Greenough (St. Andrews), Rosanna Keefe (Sheffield), Peter Milne (Edinburgh), Richard Zach (Calgary).

The colloquium uses an abstract processing service kindly provided by Atlas Conferences Inc. If you are interested in presenting a paper, please submit an abstract at http://atlas-conferences.com/cgi-bin/abstract/submit/casu-01. Your submission will be confirmed automatically on the e-mail address you provide. The accepted abstracts will be available on-line after the final decision of the program committee. If you have any problems to submit an abstract, please contact us at colloquium@ flu.cas.cz.

The deadline for contributions is 6 June 2006, the notification of acceptance/rejection will be sent until 30 June 2006.

Programme committee: Didier Dubois, Christian Fermüller, Ondrej Majer, Peter Milne, Richard Zach.

The conference fee is EUR 150, it covers conference materials, coffee breaks and the banquet at Villa Lanna. Participants unable to pay the conference fee are encouraged to apply for a reduction. Those who wish to apply for the reduction should explicitly state this when submitting their abstract, which should be extended to 2-4 pages. The official language of the symposium is English.

The authors will be offered to submit the papers presented at the colloquium to a special issue of Studia Logica on vagueness and uncertainty (their publication will be subject to the journal's regular refereeing process). Details on the special issue will be distributed at a later point by its editors.

The workshop starts one day after the Studia Logica International Conference Towards Mathematical Philosophy in Torun; the participants can consider taking part in both conferences (the journey to Prague from Torun takes less than one day).

The Prague International Colloquium continues the series of annual international meetings on topics in logic, epistemology and analytic philosophy organized in Prague by the Department of Logic of the Institute

of Philosophy (see previous colloquia).

The official web page of the colloquium is http://www.flu.cas.cz/Logica/konf/col2006.html. All correspondence should be directed to colloquium@flu.cas.cz .

Ondrej Majer*, Libor B?hounek°, Petr Cintula°

Organising Committee

*Institute of Philosophy, °Institute of Computer Science,

Academy of Sciences of the Czech Republic

Submitted by Richard Zach on Fri, 04/21/2006 - 3:28am

Sad news: Torkel Franzén has died yesterday. I've known Torkel since my undergraduate days, when he was tirelessly setting people straight on logical and philosophical matters in the newsgroup sci.logic. He wrote two wonderful books, a technical book on incompleteness (Inexhaustibility: A Non-Exhaustive Treatment) and one on misconceptions and misuses of Gödel's Theorems. He will be missed.

Torkel Franzén, well known for his many Usenet posts, died of skeleton cancer at Wednesday, April 19, at the age of 56.Torkel Franzén worked as a university lecturer at the department of Computer Science and Electrical Engineering, at Luleå University of Technology, Sweden. He taught programming courses, mostly using Java and Prolog. He earned his PhD in 2004. His thesis (in philosophy) was titled "Provability and Truth". He also wrote books, such as "Gödel's Theorem. An Incomplete Guide to Its Use and Abuse", which appeared in 2005.

Gödel's Theorem was indeed one of his major interests. He wrote many Usenet posts on this and related subjects, but he did also write posts on many other subjects.

Torkel's too early death is a great loss for his family, colleagues,

and Usenet friends.Erland Gadde

Department of Mathematics

Luleå University of Technology

Sweden

See also Sol Feferman's post on FOM.

Submitted by Richard Zach on Mon, 04/17/2006 - 10:49pm

One of the corollaries that easily follow from Gödel's first incompleteness theorem for arithmetic is the incompleteness of second-order logic: there can be no proof system that generates all and only the validities of second-order logic. It follows from the incompleteness of arithmetic because for any sentences ? of first-order arithmetic, there is a sentence of second-order logic ?? which is valid iff ? is true in the standard model. So if second-order logic was recursively enumerable (r.e.) then true arithmetic (the sentences true in the standard model) would be r.e. Now you may ask (and students regularly do ask): but what if Gödel's theorem had been false? What if arithmetic were complete? Would second-order logic then be complete, too? This question is usually not answered in the usual textbooks (at least I wasn't able to find it covered in the ones I looked). Now a conditional with a necessarily false antecedent is true, so "if arithmetic were complete, second-order logic would still be incomplete" is trivially true. But there's of course a way to give a non-trivial answer: There is no Turing machine that churns out all the valid sentences of second-order logic, even if that machine has access to an oracle which answers "yes" or "no" according to whether any given sentence of arithmetic is true in the standard model. (The function of such an oracle, of course, cannot itself be performed by a Turing machine, since the set of Gödel numbers of true arithmetic sentences is undecidable, and not even r.e.) That this is so is most easily seen by thinking of computability in terms of definability.

A set *V* of numbers is ?^{0}_{1}-definable if there is a ?^{0}_{1} formula ?(*x*) of arithmetic (one existential quantifier, then only bounded quantifiers) with a free variable *x* so that ?(*n*) is true in the standard model iff *n* ? *V*. *V* is r.e. iff it is ?^{0}_{1}-definable. (In one direction: ?(*x*) says "there is a number *k* which codes a computation of a Turing machine started on input *l* ? *k* and with output *n*.") If *W* is a set of numbers, we say that *V* is ?^{0}_{1}(W)-definable if there is a formula ?(*x*, *Y*) with a second-order variable *Y* so that *n* ? *V* iff ?(*n*, *Y*) is true in the standard model when *Y* is interpreted as the set *W*. *V* is enumerable by a Turing machine with access to an oracle for *W* iff it is ?^{0}_{1}(W)-definable.

If we let *TA* be the set of Gödel numbers of the true sentences of arithmetic and *Val*^{2} the set of Gödel numbers of valid sentences of second-order logic, our question:

IsVal^{2}enumerable by a Turing machine with an oracle forTA?

can be restated as:

IsVal^{2}?^{0}_{1}(TA)-definable?

It isn't: the class {*TA*} is definable in arithmetic, that is, there is an arithmetical formula ?(*Y*) with a free second-order variable *Y* so that ?(*Y*) is true iff *Y* = *TA* (see Theorem 23.2 in Boolos, Burgess, Jeffrey, *Computability and Logic*, 4th ed.). So if *Val*^{2} were ?^{0}_{1}(*TA*)-definable by some formula ?(*n*, *Y*), it would then also be definable in second-order arithmetic by the formula ? Y(?(*Y*) ? ?(*n*, *Y*)). And if *Val*^{2} were definable in second-order arithmetic, then *TA*^{2}, the set of Gödel numbers of true sentences of *second*-order arithmetic would be definable in second-order arithmetic, since the Gödel number of a sentence ? of second-order arithmetical sentence is in *TA*^{2} iff the Gödel number of **P**^{II} ? ? is in *Val*^{2} (where **P**^{II} is the conjunction of the the second-order Peano axioms, as in Example 22.6 of BBJ). But by Tarski's Theorem, *TA*^{2} is not definable in second-order arithmetic (see Theorem 41C of Enderton's *A Mathematical Introduction to Logic*).

Submitted by Richard Zach on Sat, 04/15/2006 - 3:59pm

A whole bunch of conference announcements came in over the Proof Theory and FOM lists the other day:

Logic Colloquium. July 27-August 2, Nijmegen, Netherlands. Submission deadline: April 17.

Workshop on Hybrid Logics. August 11, Seattle (part of FLoC). Submission deadline: May 26.

Computer Science Logic. September 25-29, Szeged, Hungary. Submission deadline: abstracts April 24, full papers May 1.

Congress on Tools for Teaching Logic. September 26-30, Salamanca, Spain. Submission deadline: May 15.

Conference on Logic, Navya-Nyaya, and Pallications. January 3-7, 2007, Calcutta, India. Submission deadline: August 31.

Submitted by Richard Zach on Sun, 04/09/2006 - 12:05am

Amazon.de emailed me today, suggesting that I preorder Kurt Gödel: The Album. There's not that much info on the amazon.de page, nor on the Vieweg page, but it's the book to accompany the exhibition the editors (Karl Sigmund, John Dawson and Kurt Mühlberger) are putting on for the Gödel Centenary in Vienna.

Submitted by Richard Zach on Tue, 04/04/2006 - 6:31pm

Don't know how I missed this: Yarden Katz has a blog, CrunchyLogic.

Submitted by Richard Zach on Sun, 04/02/2006 - 1:03am

The new issue of the Notices of the American Mathematical Society is devoted to Kurt Gödel's life and work.

Submitted by Richard Zach on Sun, 03/26/2006 - 12:54pm

The 2006 RZ World tour just started at the "Truth and Proof" conference in Edinburgh. Thanks Jeff Ketland and Jean-Louis Hudry for putting this on and inviting me! So far we had some excellent talks by John Dawson on the history of the notion of truth and use of semantic methods in logic; by Hannes Leitgeb on his work on modal predicates; and by Phil Welch on games describing supervaluation fixpoints and Hannes' dependency stuff. Met some people I've been hoping to meet for a long time, including Jeff, John, Peter Smith, Stewart Shapiro, Phil Ebert, Aatu Koskensilta, and seeing some old friends again. Ok, no time to put in links, Stewart is speaking in a few minutes, and then Panu Raatikainen.

Submitted by Richard Zach on Fri, 03/17/2006 - 6:11pm

Long time no blog. Sorry, been busy planning my 2006 world tour. Dates will be announced shortly.

While you're waiting, there's a neat little piece of metamathematics that should be more widely known than it is. You all know that if T is a consistent theory satisfying the usual assumptions, then Con(T) is undecidable in T. So T + Con(T) is properly stronger than T, and itself consistent and satisfies the conditions of Gödel's theorems. Now a very interesting question is: what happens if you keep adding consistency statements to T, i.e., look at the union of T, T + Con(T), T + Con(T) + Con(T + Con(T)), etc.?

This question was first asked (and answered) by Turing in his 1938 Princeton dissertation. The answer is, if you do this ? + 1 many times, you get all true ?_{1}^{0} sentences of arithmetic (if you start with T = PA). It was subsequently cleared up by Feferman, and exteneded to progressions of theories where you add other undecidable sentences to T, such as the reflection principle (Prov(A) ? A). The tricky part is defining the provability predicate for theories in these progressions; you have to use Kleene's recursive ordinals to do this for transfinite ordinals.

If you haven't seen this, look it up in Torkel Franzén's book, or the original papers.

Alan M. Turing, 1939, ‘Systems of logic defined by ordinals’, *Proceedings of the London Mathematical Society, ser. 2*, 45:161-228

Solomon Feferman, 1962. Transfinite recursive progressions of axiomatic theories. *Journal of Symbolic Logic*, 27:259-316.

Submitted by Richard Zach on Wed, 02/15/2006 - 9:21pm

I linked to it before, but now the deadline is nigh:

Call for Participation

Young Scholars' Competition

The Kurt Gödel Centenary: Horizons of Truth organizers and sponsors invite young scholars in logic, mathematics, physics, philosophy, computer science and theology to submit project proposals for the young scholars' competition honoring Kurt Gödels hundredth birthday.

Web: http://www.logic.at/goedel2006/index.php?students

Project Proposal Description

Submitted project proposals should be strongly connected to the scientific achievements including recent applications and/or life of Kurt Gödel. The proposals can cover any of the following disciplines:

logic, mathematics, physics, computer science, theology or philosophy.Participation Criteria

In order to participate in this competition, you must be born on or after January 1, 1970.

Required documents

1. Project proposal

2. Curriculum vitae

3. List of bibliographic referencesImportant note: Submissions should contain a description of the future research project, its relation to the fields of research as mentioned above, and to Kurt Gödel's life or work, and possible applications. Including the list of references, and the CV it should not exceed six (6) pages in PDF format.

Prizes

Ten chosen projects will compete for three top prizes.

1st prize: 20 000 EUR

2nd and 3rd prize: 5000 EUR eachDeadlines

Submission deadline: Monday, 24. February 2006. 6 p.m. CET

Notifications: Monday, 15. March 2006.Submissions

For submission software and instructions, see:

http://www.logic.at/goedel2006/index.php?submissions

Submitted by Richard Zach on Sun, 02/12/2006 - 11:21pm

The Studia Logica special issue on cut-elimination, edited by Alex Leitsch, is out. A bunch of very interesting papers. I'm especially glad to see Alessandra Carbone publish in proof theory again! I'm a big fan.

(Self-promotion: the issue also contains the final version of Georg Moser and my epsilon calculus paper. And while I'm linking, and since I'm too ~~lazy~~ busy to update my webpage, also a link to my review of Potter's book Reason's Nearest Kin in the Notre Dame Journal.)

Submitted by Richard Zach on Sun, 02/12/2006 - 10:50pm

Via OPP: Thierry Coquand's entry on Type Theory in the Stanford Encyclopedia went online a few days ago.

Submitted by Richard Zach on Wed, 02/01/2006 - 8:19pm

Brian Weatherson's Online Papers in Philosophy blog of new philosophy papers has been taken over by Jonathan Ichikawa and is now located here. So update your bookmarks/RSS feeds.

Via OPP I see that Calgary's very own Rafa? Urbaniak's paper on Lesniewski in the AJL is now online.

Submitted by Richard Zach on Wed, 02/01/2006 - 3:29am

This looks like a superb opportunity for undergrads and beginning graduate students:

In 2006, the Department of Philosophy at Carnegie Mellon University will launch a three-week summer school in logic and formal epistemology for promising undergraduates in philosophy, mathematics, computer science, linguistics, and other sciences. The goals are to

- introduce promising students to cross-disciplinary fields of research at an early stage in their career; and
- forge lasting interdisciplinary links between the various disciplines.
The summer school will be held from Monday, June 12 to Friday, June 30, 2006. There will be morning and afternoon lectures and daily problem sessions, as well as planned outings and social events.

The summer school is free. That is, we will provide:

- full tuition
- dormitory accommodations on the Carnegie Mellon campus
So students need only pay for travel to Pittsburgh and living expenses while there. There are no grades, and the courses do not provide formal course credit.

This year's topics are:

Causal Statistical Inference

Monday, June 12 to Friday, June 16

Instructor: David DanksFoundations of Computability

Monday, June 19 to Friday, June 23

Instructor: Wilfried SiegPhilosophical Logic

Monday, June 26 to Friday, June 30

Instructor: Horacio Arlo-CostaThe summer school is open to undergraduates, as well as to students who will have just received their undergraduate degrees. Instructions for applying can be found on the summer school web page. Materials must be submitted to the Philosophy Department by March 15, 2006. Inquiries may be directed to Jeremy Avigad (avigad@cmu.edu).

Submitted by Richard Zach on Wed, 01/18/2006 - 6:04pm

Ok, two logic-related posts already today, so I guess I can afford to post something else as well. Ang Lee's Brokeback Mountain, as is pointed out in every other review, wasn't filmed in Wyoming but right around where I am. Brokeback Mountain itself is played in the move by the Three Sisters Range which can be seen from the Trans-Canada Highway at Canmore, about an hour's drive west of Calgary. (In the movie, Jack and Ennis "go fishing" on the other side of the range.) Anyway: here's a Brokeback Mountain webcam.

Submitted by Richard Zach on Wed, 01/18/2006 - 5:56pm

`Received from Arnold Beckmann:`

FUNDING OPPORTUNITIES TO ATTEND COMPUTABILITY IN EUROPE 2006

This is just to clarify the various opportunities offeredthrought the organisers of CiE 2006 for PhD students andresearchers from the Former Soviet Union to obtain funding toattend the conference.

The deadline for all the funding schemes has been fixed forMARCH 31, 2006

Full details of how to apply are available via the webpage:

http://www.cs.swan.ac.uk/cie06/give-page.php?14

ASL FUNDING:

CiE 2006 is an ASL sponsored meeting, so PhD students who havetaken advantage of the ASL very favourable membership terms (orintend to do so soon), will be able to apply direct to them for agrant to attend. See:

http://www.aslonline.org/studenttravelawards.html

EPSRC FUNDING FOR UK-BASED PhD STUDENTS:

CiE 2006 has obtained generous support from the UK Engineeringand Physical Sciences Research Council for UK-based PhD students.For these grants, application is direct to the conferenceorganisers at cie06@swansea.ac.uk - see the website for details.

LMS FUNDING FOR UK-BASED PhD STUDENTS, AND fSU RESEARCHERS:

The London Mathematical Society funding for students is similarto that from EPSRC. In addition, there is funding for researchersfrom the Former Soviet Union, including some support for travel,as well as for accommodation, registration, etc. Again -application is direct to the organisers.

PRESENTERS OF PAPERS AT CiE 2006:

It is important to note that in allocating funding, theorganisers will prioritise presenters of papers at CiE 2006. Thedeadline for submission for the LNCS Proceedings volume is:

THURSDAY FEBRUARY 9th, 2006

For details of the submission procedure, see:

http://www.cs.swan.ac.uk/cie06/give-page.php?12

Similarly, giving a talk at CiE 2006 will improve the chances ofgetting funding through the ASL scheme.

Submitted by Richard Zach on Wed, 01/18/2006 - 4:56pm

Foundational Issues in Logic: logical consequence and logical constants revisited

18-19 May 2006

Santiago de Compostela (Spain /España)

Santiago de Compostela (Spain /España)

Organized by Área de Lógica y Filosofía de la Ciencia de la U.S.C.

Supported by European Society for Analytic Philosophy Sociedad de Lógica, Metodología y Filosofía de la Ciencia en España Sociedad Española de Filosofía Analítica

Supported by European Society for Analytic Philosophy Sociedad de Lógica, Metodología y Filosofía de la Ciencia en España Sociedad Española de Filosofía Analítica

Scientific committee/ Comité científico:

Manuel García-Carpintero (Universidad de Barcelona), Mario Gómez Torrente (UNAM/ICREA), Ignacio Jané (Universidad de Barcelona), Stewart Shapiro (Ohio State University), Stephen Read (University of St. Andrews).

Organising committee/ Comité organizador:

Concepción Martínez (Universidad de Santiago de Compostela) [President / Presidente]

José M. Sagüillo (Universidad de Santiago de Compostela) [Secretary / Secretaria]

Mª Uxía Rivas Monroy (Universidad de Santiago de Compostela)

Javier Vilanova Árias (Universidad Complutense de Madrid)

Invited Speakers

Manuel García-Carpintero (Universidad de Barcelona)

Mario Gómez Torrente (UNAM, ICREA)

Ignacio Jané (University of Barcelona)

Grzegorz Malinowski (University of Lodz)

Stephen Read (University of St. Andrews)

Ricardo Santos (Universidade Nova de Lisboa)

Stewart Shapiro (Ohio St. University/University of St. Andrews)

Gila Sher (University of California, San Diego)

Discussants (To be determined)

This workshop is organized by the group Lekton of the Department of Logic and Moral Philosophy of University of Santiago de Compostela. It counts with the support of the European Society for Analytic Philosophy, the Spanish Society for Analytic Philosophy (SEFA) and of the Association of Logic, Methodology and Philosophy of Science in Spain (SLMFCE).

This conference aims at providing a forum for the presentation and discussion of current research on the much discussed issues of logical consequence and logical constanthood. For that purpose, some of the most relevant scholars on the issue have been invited.

CALL FOR PAPERS

We invite submissions for 35-40-minute presentations in English (with 20) additional minutes for discussion) on the topics of the workshop. Submitted abstracts will be blind refereed and selected on the basis of general quality and relevance to the special topic of the workshop. Submissions should take the form of a 4000-5000 word summary. Authors' names, postal address, affiliation, phone and fax number and e-mail address should be given separately. Please send your submission by e-mail in an attached file in pdf, RTF or Word format to Concepción Martínez Vidal: lflpcmav@usc.es; José Miguel Sagüillo: lflgsagu@usc.es, Mª Uxía Rivas Monroy: lfuxia@usc.es, or Javier Vilanova: vilanova@filos.ucm.es by ordinary mail to the following address:

Dpto. de Lógica y Filosofía Moral

Facultad de Filosofía

Campus Universitario Sur

15782 Santiago de Compostela

Deadline for contributions: January 30st 2006

Communication of acceptance: March 1st, 2006

Final version: April, 15th.

OFFICIAL LANGUAGE : English

The organization will cover the accommodation expenses of the authors

of accepted papers. We regret that we can not cover travel and other

expenses.

The structure of the workshop

Lectures will be followed by a 20-minutes discussion in charge of an invited discussant, and by a debate. The Workshop will have no parallel sessions. The meeting is a small format conference; we aim to provide ample space for discussion and informal interaction among participants. Apart from the invited speakers, the two (three at most) authors of the contributed papers selected by the Scientific Committee will present their work (35-40 minutes) on some of the issues proposed by the Organizing Committee. These presentations will be followed by 20-minutes debates.