## Thursday, 31 March 2011

### Syntax, arithmetic, etc.

As Michael Jackson put it, "ABC, 123, baby, you and me girl":

## Wednesday, 30 March 2011

### Two conferences for M-PHIers

And one month left to submit. Think about it.

-------

Formal epistemology meets experimental philosophy

First Pittsburgh-Tilburg Workshop

Tilburg University, Thursday 29 - Friday 30 September 2011

Over the years, the methodological toolbox of philosophers of science has widened considerably. Today, formal and experimental methods importantly complement more traditional methods such as conceptual analysis and case studies. So far, however, there has not been much interaction between the corresponding communities. Formal work is all too often conducted in an a priori fashion, drawing on intuitions to substantiate various assumptions and to test their consequences. Experimental work, on the other hand, is often limited to testing various assumptions and intuitions, and often does not identify or create new phenomena that can subsequently be integrated into a formal framework. The working assumption of this workshop is that philosophy of science can gain a lot from combining formal and experimental studies. By doing so, philosophy of science will become increasingly scientific as a crucial aspect of the scientific endeavor lies in the combination of formal theories and experimental insights.
This workshop aims to explore the relation between formal and experimental approaches to the philosophy of science. We invite meta-theoretical papers, but especially papers that fruitfully combine both methods to problems from the philosophy of science. This first Pittsburgh-Tilburg workshop will pay special attention to the philosophy of the social sciences, but a focus on other subfields of philosophy of science is also welcome.

Call for papers: We invite submissions of both a short abstract (max. 100 words) and an extended abstract (1000-1500 words) through our automatic submission system by 1 May 2011. Decisions will be made by 15 May 2011.

(Go here for more.)

-------

Progic 2011

The Progic conference series is intended to promote interactions between probability and logic. The fifth installment of the series will be held at Columbia University in New York on September 10th and 11th of 2011. While several of the earlier Progic meetings included a special focus, Progic 2011 will honor Haim Gaifman's contributions to the intersection of probability and logic. Progic 2011 will consist of 11 talks, 6 invited and 5 contributed. The following distinguished speakers have been confirmed:

• Horacio Arló -Costa (Carnegie Mellon)
• Haim Gaifman (Columbia)
• Rohit Parikh (CUNY)
• Jeff Paris (Manchester)
• Dana Scott (Carnegie Mellon)
Call for Papers: The five contributed papers will be selected from among the submissions that we receive. Submissions may be on any topic that is relevant to the interaction between probability and logic. Preference will be given to papers that make contact with at least one of the relevant themes in Haim Gaifman's work. All submissions should be sent to progicconference2011@gmail.com by May 1 of 2011. Decision notices will be sent by June 1 of 2011.

(Go here for more.)

Don't miss it!

## Sunday, 27 March 2011

### Should probabilities be countably additive?

After being shown live streaming by the Rotman Institute of Philosophy (as promptly announced at Choice & Inference), Colin Howson's talk Should probabilities be countably additive? at the University of Western Ontario is now freely available.

## Thursday, 24 March 2011

### Carnapian explication idea of the century

Because it "has opened the floodgates to the use of formal methods in philosophy". Jon Williamson says so in a recent article from The Philosophers' Magazine. (And, hey, he relies on the Munich Center for Mathematical Philosophy as supporting evidence :-)

## Tuesday, 22 March 2011

### Philosophy, mathematics, and war

As for philosophy, have a look here. For mathematics, below.

## Sunday, 20 March 2011

### On Adding a Validity Predicate to PA

This note was occasioned by reading JC Beall & Julien Murzi's manuscript, "Two Flavors of Curry's Paradox" concerning the possibility of reconstructing a Curry-style paradox within a theory of validity.

Under certain circumstances, the theory is consistent, as it can be interpreted inside Peano arithmetic, $PA$. Suppose we begin with $PA$ in its usual first order language $\mathcal{L}$ with $=, 0, S, +$ and $\times$. Suppose that $\vdash$ stands for ordinary first-order deducibility. "$P$ is a derivation of $B$ from $A$" means "$P$ is a finite sequence $(P_0, ..., P_n)$ where $P_n$ is $B$, and each $P_i$ is either a logical axiom, or is $A$, or is obtained from previous formulas by Modus Ponens". The relation "$P$ is a derivation of $B$ from $A$" is decidable. So, it can be strongly represented in $PA$ by a recursive formula, $\mathbf{Proof}(x, y, z)$, in such a way that:
• (i) If $P$ is a derivation of $B$ from $A$ then $PA \vdash \mathbf{Proof}(\ulcorner P \urcorner, \ulcorner A \urcorner, \ulcorner B \urcorner)$.
and
• (ii) If $P$ is not a derivation of $B$ from $A$ then $PA \vdash \neg \mathbf{Proof}(\ulcorner P \urcorner, \ulcorner A \urcorner, \ulcorner B \urcorner)$.
Write $\mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner)$ to mean: "there is a derivation of $B$ from $A$".
Then (i) guarantees that we have a version of (V-Intro):
• (V-Intro) $\text{If } A \vdash B, \text{ then } PA \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner)$.
[This doesn't say that $PA$ itself is closed under this introduction rule. If that were so, we would have a version of Montague's Paradox.]

Next, as $PA$ is sound, if $PA \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner)$, then $\mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner)$ is true --- that is, $A \vdash B$. So, we have a version of (V-Elim):
• (V-Elim) $\text{If } PA \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner), \text{ then } A \vdash B$.
Finally, the difficult part. A property of $PA$ is that, for every $\mathcal{L}$-sentence $A$:

(iii) $PA \vdash A \rightarrow \mathbf{Con}(A)$.

where $\mathbf{Con}(A)$ means: "there is no derivation of $0 = 1$ from $A$".

[Update, 6 April: This is a non-trivial result about $PA$. (See Hajek/Pudlak, 1993, Metamathematics of First-Order Arithmetic, p. 108.) It is intimately related to the fact that $PA$ is reflexive - $PA$ proves the consistency of any of its finitely axiomatized subtheories. The proof of (iii) in Hajek/Pudlak uses partial truth definitions, first to show that $I\Sigma_k$ proves the consistency of all true $\Pi_{k+1}$-sentences.]

So,

(iv) $PA \vdash \neg(A \rightarrow B) \rightarrow \mathbf{Con}(\neg(A \rightarrow B))$.

So,

(v) $PA \vdash \neg \mathbf{Con}(\neg(A \rightarrow B)) \rightarrow (A \rightarrow B)$.

The validity of the inference in logic from $A$ to $B$ can be expressed by saying that the sentence $\neg (A \rightarrow B)$ is not consistent. This in fact can be proved in $PA$ itself,

(vi) $PA \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner) \leftrightarrow \neg \mathbf{Con}(\neg (A \rightarrow B))$.

So, we get a version of the scheme (V-Out):
• (V-Out) $PA \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner) \rightarrow (A \rightarrow B)$.
[Relatedly, $PA$ proves the local reflection scheme for logic: if $\mathbf{Prov}_{\emptyset}(x)$ means "$x$ is a theorem of logic", then $PA$ proves all instances of $\mathbf{Prov}_{\emptyset}(\ulcorner A \urcorner) \rightarrow A$.]

So, $PA$ itself is a consistent theory that already contains a theory of validity with versions of (V-Intro), (V-Elim) and (V-Out).

The example discussed in Beall & Murzi concerns a validity-Curry sentence, a sentence $C$ which says "I am inconsistent". In the case of $PA$, choose $C$ such that,

(vii) $PA \vdash C \leftrightarrow \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$.

where $\bot$ is some contradiction (e.g., $0 \neq 0$). Using property (V-Out), we get:

(viii) $PA \vdash C \rightarrow (C \rightarrow \bot)$.

[Note: this is where we are about to use something like "contraction", as $C \rightarrow (C \rightarrow \bot)$ is equivalent in classical logic to $C \rightarrow \bot$.]

Thus,

(ix) $PA \vdash \neg C$.

So, since $PA$ is sound, $C$ is not true. This tells us that $\mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$ is not true. In other words, $C$ is consistent. In particular, it is not the case that $\bot$ is derivable in logic from $C$. This is why we cannot apply (V-Intro). Rather, $\bot$ is derivable in $PA$ itself from $C$, and $PA$ is stronger than logic. From (vii) and (ix), $PA \vdash \neg \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$. So:

(x) $PA \vdash \mathbf{Con}(C)$.

Beall & Murzi (ms) give a derivation of a contradiction from a sentence like $C$, but their derivation uses a different version of (V-Intro). Suppose $V$ is a theory of validity (including arithmetic) such that:
• $V$ permits diagonalization.
• $V$ proves each instance of the scheme (V-Out).
• $V$ has the following form of the (V-Intro) rule:
• (V-Intro)* $\text{If } V, A \vdash B, \text{ then } V \vdash \mathbf{Val}(\ulcorner A \urcorner, \ulcorner B \urcorner)$.
Then, following Beall & Murzi's derivation, $V$ is inconsistent:
1. $V \vdash C \leftrightarrow \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$.
2. $V \vdash \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner) \rightarrow (C \rightarrow \bot)$.
3. $V, C \vdash \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$.
4. $V, C \vdash C \rightarrow \bot$.
5. $V, C \vdash \bot$.
6. $V \vdash \mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$.
7. $V \vdash C$.
8. $V \vdash \bot$.
The crucial step that might be considered problematic is (6), which invokes the strong introduction rule (V-Intro)* to infer $\mathbf{Val}(\ulcorner C \urcorner, \ulcorner \bot \urcorner)$ from a derivation of $\bot$ from $C$ in the theory $V$ itself. But the derivation of $\bot$ from $C$ inside $V$ surely doesn't imply that the inference of $C$ to $\bot$ is logically valid.

Abstracting from the interpretation of $\mathbf{Val}$, this seems to me to be closely related to a version of Montague's Paradox: a theory which contains an "absolute knowability" predicate satisfying an (Intro) rule and an (Out) scheme.

[Update 1, 16 April: LaTeX-ified.]

[Update 2, 24 April: Since the issue of logical derivability is crucial here, I've changed occurrences of $0=1$ (which is normally used in discussion of consistency for systems of arithmetic) to $\bot$, which stands for a genuine contradiction, say $0 \neq 0$.]

Recently, I have been (re)reading Fitelson and Hawthorne's extensive and thorough discussion of "The Wason task(s) and the paradox of confirmation", which revived a puzzling little thought that I have. Wason's selection task is widely known, I guess. You have four cards as follows:

Each card has a letter on one side and a number on the other. A hypothesis is at issue, i.e., H = "for any card, if there's a vowel on one side, then there's an even number on the other side". Your task is to say which of the cards you need to turn over in order to find out whether H is true or false. (I want to be very careful here with the wording - I'm closely following Johnson-Laird & Wason, 1977, via Humberstone, 1994). [Edit: By the way - I forgot to say! - people strongly tend to choose the E- and the 4-card. The point is if this makes logical sense.]

Two cases have to be clearly distinguished: either (i) the domain of H is restricted to the four cards initially presented, or (ii) a larger deck is involved, from which those four cards have been sampled. If (ii) is allowed for, then very interesting issues arise (most famously tackled by Oaksford and Chater, 1994). However, Wason had (i) in mind, and everyone seems to agree that in that case the correct answer is: turn over the E- and the 7-card. Why?

From Wason on, the standard answer has been more or less the same: because only by turning the E- and the 7-card you could possibly falsify H. (Wason's experimental idea was apparently inspired by his knowledge of Popper.) But the logical point seems stronger than that: if the domain is restricted, then H is logically equivalent to "there's an even number behind E and a consonant behind 7". Logically equivalent - period. Not just such that it would otherwise be falsified. The proof is easy, and it provides ultimate motivation for why the selection of E and 7 is indeed compelling (recall how the question is spelled out: which cards are needed to find out whether H is true or false). Yet I have consistently found variants of the "Popperian" argument, and never seen an overt statement of that plain logical equivalence. I'd be happy to know if anyone alse ever has.

Refs
Humberstone, L. (1994), "Hempel meets Wason", Erkenntnis, 41 (1994), pp. 391–402.
Johnson-Laird, P.N. & Wason, P.C. (1977), "A theoretical analysis of insight into a reasoning task", in P.N. Johnson-Laird & P.C. Wason (eds.), Thinking: Readings in Cognitive Science, Cambridge University Press, Cambridge, pp. 143-157.
Oaksford, M. & Chater N. (1994), "A rational analysis of the selection task as optimal data selection", Psychological Review, 101 (1994), pp. 608–631.

## Friday, 18 March 2011

### The Completeness of PA with the $\omega$-rule

Although it's a well-known fact that the theory obtained by "closing $PA$ under the $\omega$-rule" is complete, I cannot find an immediately available online source, so here is a proof. (Something like this is in a proof theory textbook, like Takeuti, but almost all my books are a thousand miles away.)

The language $L_A$ is the first-order language of arithmetic with $=, 0, S, +$ and $\times$. Assume a Hilbert-style linear deductive system, with Modus Ponens; By "$\phi$ is an axiom of $PA$" I mean "either $\phi$ is a logical axiom or $\phi$ is one of usual axioms for $S, +$ and $\times$, or $\phi$ is an instance of induction". But we shall allow infinitely long derivations, indexed by ordinals. We define the system $PA^{\omega}$ as follows: a (possibly infinite) sequence $(\theta_0, ..., \theta_{\alpha})$ of formulas is an derivation in $\omega$-logic from $PA$ iff, for each $\beta \leq \alpha$:
(i) either $\theta_{\beta}$ is an axiom of $PA$;
(ii) or there are $\gamma, \delta < \beta$, such that $\theta_{\delta}$ has the form $\theta_{\gamma} \rightarrow \theta_{\beta}$;
(iii) or $\theta_{\beta}$ has the form $\forall x \psi(x)$ for some formula $\psi(x)$ with exactly $x$ free, and there is an injection $f : \omega \rightarrow \beta$ such that $\theta_{f(n)} = \psi(n)$, for all $n \in \omega$.
Here $\alpha, \beta, \gamma$ and $\delta$ are ordinals; derivations may be infinite; the second condition (ii) expresses a single application of Modus Ponens; the third condition (iii) expresses a single application of the $\omega$-rule - roughly, the derivation has a subsequence which is an $\omega$-sequence of the form $\psi(0), \psi(1), ...$, and the "conclusion" formula has the form $\forall x \psi(x)$.

Say that $\phi$ is a theorem of $PA$ in $\omega$-logic just when there is an $\omega$-derivation of the form $(\dots, \phi)$ from $PA$. Let $PA^{\omega}$ be the set of theorems of $PA$ in $\omega$-logic. We aim to prove that: $PA^{\omega}$ is the same as true arithmetic; that is,
Theorem. $PA^{\omega} = Th(\mathbb{N})$.
Lemma 1. If, for all $n \in \omega, \phi(n) \in PA^{\omega}$, then $\forall x \phi(x) \in PA^{\omega}$. (I.e., $PA^{\omega}$ is closed under the $\omega$-rule.)
[Proof: Assume that, for all $n \in \omega, \phi(n) \in PA^{\omega}$. So, for each $\phi(n)$, there is an $\omega$-derivation; next, take all these $\omega$-derivations (of $\phi(0), \phi(1)$, etc.) and paste them together; place the formula $\forall x \phi(x)$ at the end. This is an $\omega$-derivation of $\forall x \phi(x)$. So, $\forall x \phi(x) \in PA^{\omega}$.]

Lemma 2. If $\phi \in PA^{\omega}$, then $\mathbb{N} \models \phi$. (I.e., $PA^{\omega}$ is sound.)
[Proof: Each axiom of $PA$ is true in $\mathbb{N}$. Modus ponens is sound for $\mathbb{N}$. The $\omega$-rule is sound for $\mathbb{N}$. Hence, in any given $\omega$-derivation from $PA$, every formula is true in $\mathbb{N}$. So, all $\omega$-theorems of $PA$ are true in $\mathbb{N}$.]

Lemma 3. For all sentences $\phi$, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$. (I.e., $PA^{\omega}$ is complete.)
[Proof. This is by induction on the complexity of $\phi$. $PA$ is itself negation-complete for atomic sentences. If $\phi$ is of the form $\neg \theta$ and either $\theta \in PA^{\omega}$ or $\neg \theta \in PA^{\omega}$, then either $\neg \neg \theta \in PA^{\omega}$ or $\neg \theta \in PA^{\omega}$; and so, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$. And similarly with conjunctions.
For quantified formulas, suppose $\phi$ has the form $\forall x \psi$. As induction hypothesis, suppose that, for all $n \in \omega$, either $\psi(n) \in PA^{\omega}$ or $\neg \psi(n) \in PA^{\omega}$. Consider two cases.
Case 1. Suppose that, for all $n \in \omega$, $\psi(n) \in PA^{\omega}$. Then, $\forall x \psi \in PA^{\omega}$, by lemma 1. So, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$, as required.
Case 2. Suppose that, for some $n \in \omega$, $\psi(n) \notin PA^{\omega}$. So, by induction hypothesis, $\neg \psi(n) \in PA^{\omega}$. So, $\exists x \neg \psi \in PA^{\omega}$. So, $\neg \phi \in PA^{\omega}$. So, either $\phi \in PA^{\omega}$ or $\neg \phi \in PA^{\omega}$, as required.]

Lemmas 2 and 3 say that $PA^{\omega}$ is sound and complete. Hence, all of its models are elementarily equivalent. Since $\mathbb{N}$ is a model of $PA^{\omega}$, all of its models are elementarily equivalent to $\mathbb{N}$. So, $PA^{\omega} = Th(\mathbb{N})$. In fact, the only properties of $PA$ we actually needed to use are that its axioms are true in $\mathbb{N}$ and that it is negation-complete for atomic sentences. These properties both hold for Robinson arithmetic $Q$. So, we get that $Q^{\omega} = Th(\mathbb{N})$.

## Wednesday, 16 March 2011

### Breakthrough in number theory

2011 started with the announcement of an outstanding achievement in number theory: the discovery of a finite, algebraic formula for partition numbers. The real technical stuff is daunting, but below is a remarkable, partly informal and historical talk by the senior figure of the research team, Ken Ono. And maybe someone in the philosophy of mathematics could find inspiration for an engaging case-study?

(I owe the pointer to Walking Randomly.)

## Monday, 14 March 2011

### Events at MCMP 2011

Events at MCMP that have already been planned for 2011 are listed here.
The Thursday seminars dedicated to mathematical philosophy are listed here.
The Wednesday seminars dedicated to logic & philosophy of science are listed here.
Upcoming workshops are listed here.

## Sunday, 13 March 2011

### Set Theory and Higher-Order Logic at Birkbeck

Summer School on Set Theory and Higher-Order Logic:
Foundational Issues and Mathematical Developments

London, August 1-6, 2011
http://www.bbk.ac.uk/philosophy/our-research/ppp/summer-school

This is an interdisciplinary summer school, consisting of four days of mini-courses (August 1-4) and a subsequent two-day conference (August 5-6), all hosted at the Institute of Philosophy in London. The goal of this summer school is to provide a forum in which set theorists and philosophers of mathematics -- as well as students of these disciplines -- can interact and discuss recent results and debates at the intersection of set-theory and higher-order logic. Topics to be represented at the summer school include but are not limited to: the semantics for higher-order logics, Omega-Logic, groundedness, set-theoretic geology, interpretability and incompleteness, predicativity, and formal theories of truth.

The mini-course speakers include: Joan Bagaria (Barcelona), Fernando Ferreira (Lisbon), ‪Luca Incurvati‬ (Cambridge), Joel Hamkins (CUNY), Leon Horsten (Bristol), Hannes Leitgeb (Munich), Jouko Väänänen (Helsinki), Phillip Welch (Bristol), and Albert Visser (Utrecht). In addition to a large subset of the mini-course speakers, the conference speakers include: Donald A. Martin (UCLA) and Gabriel Uzquiano (Oxford).

This summer school is made possible through generous support provided by: the Plurals, Predicates, and Paradox Project (European Research Council), the Ideals of Proof Project (L’Agence nationale de la recherche), the Munich Center for Mathematical Philosophy (Alexander von Humboldt Stiftung), and the New Frontiers of Infinity Project (European Science Foundation).

This support also makes it possible to offer ten 200 GBP student stipends to help defray costs for students. The stipends will be allocated on the basis of merit and need. To apply, please send a brief CV, along with any information about need, to Sean Walsh (email below) prior to May 1, 2011.

Organized by: Michael Detlefsen (ANR and Notre Dame), Hannes Leitgeb (Munich Center for Mathematical Philosophy), and Øystein Linnebo (Birkbeck).

## Friday, 11 March 2011

### The Reasoner

The March issue is out.

## Wednesday, 9 March 2011

### Kuhn vs. Kripke on the NYT

After Wittgenstein's poker, we now have Kuhn's ashtray.

It continues here and here, and two more episodes should be forthcoming.

(I owe the pointer to Child's Play.)

Edit: The fourth and fifth parts are here and here.