Mathematical Logic Seminar Abstracts Spring 2009

Solomon Feferman (Stanford)
Introduction to Systems of Notation for Predicative Ordinals (And Beyond): Completeness and Effectiveness Properties

As background for the talks April 28 and May 5 on the work of Beklemishev relating systems of notation for predicative ordinals to provability algebras, I will go over material from my paper “Systems of predicative analysis, II: Representations of ordinals”, J. Symbolic Logic 33 (1968) 193–220, that is also available at http://math.stanford.edu/~feferman/papers.html, item #9.

Peter Koellner (Harvard)
Intrinsic Justifications and Reflection Principles

Gödel initiated the program of finding and justifying axioms that effect a significant reduction in incompleteness and he drew a fundamental distinction between intrinsic and extrinsic justifications. Reflection principles are the most promising candidates for new axioms that are intrinsically justified. Taking as our starting point Tait's work on general reflection principles, we will discuss a series of limitative results concerning this approach. These results collectively show that general reflection principles are either weak (in that they are consistent relative to the Erdős cardinal κ(ω)) or inconsistent. The philosophical significance of these results is discussed.

Grigori Mints (Stanford)
Review of L. Beklemishev's “Reflection schemata and provability algebras in formal arithmetic”

Proof-theoretic ordinals are used to measure the consistency strength of formal theories and growth rate of computable functions. Defining suitable ordinals for strong theories is one of the most important outstanding problems of proof theory and foundations. It is not even clear what is suitable “material” for such definitions. One of the popular candidates is consistency statements.

We outline the problem and describe a solution for the ordinal ε₀ (cosistency stength of the first order arithmetic) given by L. Beklemishev.

Reference

Beklemishev, L. D. (2005): “Reflection principles and provability algebras in formal arithmetic&rdquo. Uspehi Matematicheskih Nauk 60(2), pp. 3–78. (In Russian. English translation: Russian Mathematical Surveys 60(2) (2005), pp. 197–268.) Paper Preprint (in English): Logic Group Preprint Series 236, May 2005.

Thomas Icard (Stanford)
Review of L. Beklemishev's “Veblen hierarchy in the context of provability algebras”

In the previous seminar on May 5, we had a presentation of Beklemishev's solution to the problem of providing a canonical ordinal notation system up to ε₀, the consistency strength of first-order arithmetic. A natural question is how this can be extended beyond ε₀ to larger ordinals measuring the strength of, e.g., fragments of second order arithmetic. I shall present Beklemishev's own proposal for how to extend the system up to the ordinal Γ₀, the consistency strength predicative analysis.

Reference

Beklemishev, L.D. (2005): “Veblen hierarchy in the context of provability algebras”. In: P. Hájek, L. Valdés-Villanueva, D. Westerståhl (eds.), Logic, Methodology and Philosophy of Science, Proceedings of the Twelfth International Congress. Kings College Publications, 2005, pp. 65–78.

Johan van Benthem (Stanford, Amsterdam)
The Information in Logic: Dynamic Epistemic Logic Meets Intuitionism

The notion of information is implicit in many logical systems, but it takes a (de-)constructive effort to make it explicit, especially as notions of information appropriate to logic are diverse, and not all charted. We start with dynamic epistemic logic of observation-based semantic information, and first show how it needs protocol extensions to deal with 'procedural information'. In addition, it needs syntactic access structure for inferential update, and acts of 'promotion' giving conscious access to implicit knowledge. Next, we discuss a major alternative in this light: intuitionistic logic as a theory of implicit information, 'epistemically loading' meanings of logical constants. The latter system merges three kinds of information: factual, procedural, and inferential, in a mix that is tantalizingly different from that of dynamic epistemic logic. Finally, we discuss some other dimensions: 'loading' versus addition, and the role of (constructive) proof interpretations.

This talk connects several ideas in the DEL literature, but takes them in a perhaps surprising direction: the heartrland of constructivism.

References

J. van Benthem, 2008, “Merging Observation and Access in Dynamic Epistemic Logic”, Studies in Logic, 1(1), 1–16.
J. van Benthem, 2008, “The Information in Intuitionistic Logic”, Synthese 167(2), 251–270.
J. van Benthem & M. Martinez, 2008, “The Stories of Logic and Information”, in P. Adriaans & J. van Benthem (eds.), Handbook of the Philosophy of Information, Elsevier, Amsterdam.
J. van Benthem, J. Gerbrandy, T. Hoshi & E. Pacuit, 2009, “Merging Frameworks for Interaction&rdqo;, Journal of Philosophical Logic on-line, January 16, 2009.
T. Hoshi, 2009, Epistemic Dynamics and Protocol Information, Ph. D. Dissertation, Department of Philosophy, Stanford University.
F. Velazquez, 2008, “Dynamic Logic of Inference and Update”, ILLC Amsterdam, to appear in Knowledge, Rationality, and Action.

Grigori Mints (Stanford)
A Simple Epsilon Substitution Method for ID₁

The epsilon substitution method was introduced by Hilbert as a basic tool of his consistency program. Its extension to the impredicative case of ID₁ was outlined in my paper (2000) and carried out by T. Arai. Unfortunately his formulation and termination proof are very complicated. In this talk a much simpler formulation and termination proof are presented. The simplification is based on simple recursion-theoretic considerations.