Craig’s Theorem and the Empirical
Underdetermination Thesis Reassessed

The present paper proposes to revive the twenty-year old debate on the question of whether Craig’s theorem poses a challenge to the empirical underdetermination thesis. It will be demonstrated that Quine’s account of this issue in his paper "Empirically Equivalent Systems of the World" (1975) is mathematically flawed and that Quine makes too strong a concession to the Craigian challenge. It will further be pointed out that Craig’s theorem would threaten the empirical underdetermination thesis only if the set of all relevant observation conditionals could be shown to be recursively enumerable — a condition which Quine seems to overlook —, and it will be argued that, at least within the framework of Quine’s philosophy, it is doubtful whether this condition is satisfiable.

Such is Quine’s empirical underdetermination thesis. Although the question of whether this thesis is plausible is still far from settled — even two decades after the philosophical debate on this subject was most heated —, philosophers seem to have reached a (limited) consensus on one particular aspect of this question: William Craig’s theorem (1953, 1956) concerning the replacement of auxiliary expressions is seen as a challenge, if only a theoretical one, to the empirical underdetermination thesis. Jane English (1973) forcefully argues for this view, and Quine himself concedes that, although "[Craig’s] result does not belie under-determination", "it does challenge the interest of under-determination" (Quine, 1975, p. 313).

In the present paper, I will argue that a reassessment of this view is overdue, and that, at least within the framework of Quine’s philosophy, Quine’s thesis can be defended against Quine’s own concession. In particular, I will show that Quine’s concession is grounded in a mathematically flawed use of Craig’s theorem. I will then argue that, within the framework of Quine’s philosophy, it is highly doubtful whether the conditions under which Craig’s result would pose a challenge to the empirical underdetermination thesis are satisfiable.

Using the traditional syntactic approach to scientific theories, we define a theory to be a deductively closed set of sentences of a formal language. Given a theory T, a theory formulation of T is a (usually finite) subset S of T, often interpreted as the set of basic axioms, such that the deductive closure of S is the whole of T. How are theory and observations related? Typically, observation sentences of the form "The liquid in this vessel is blue!" are not directly entailed by a theory (i.e. contained in the set T), because, first, they lack the generality characteristic of a theory and, second, their truth-value — unlike the truth-value of a typical theoretical sentence — is dependent upon the occasion of utterance. Quine portrays the link between a theory and such sentences as a two-step relation. As a first step, observation sentences are pegged to specific spatio-temporal co-ordinates so as to make their truth-value independent of the occasion of utterance. But as theories typically make little reference to particulars, pegged observation sentences are still insufficiently general to be directly entailed by a theory. Rather, theories imply particulars via other particulars, that is to say, via boundary conditions. But, instead of saying that the conjunction of a theory and a set of boundary conditions implies certain pegged observation sentences, we may simply say — and this is the second step of the two-step relation — that the theory implies appropriate observation conditionals, where an observation conditional is a conditional sentence whose antecedent is a conjunction of pegged observation sentences and whose consequent is a pegged observation sentence (Quine, 1975).

In this terminology, two theories are defined to be empirically equivalent if they entail the same body of observation conditionals. Now the empirical underdetermination thesis requires that there exist rival theories which are empirically equivalent, but logically incompatible. However, if the empirical underdetermination thesis is to be an interesting and nontrivial claim, it must actually require more than that. It must, firstly, rule out the possibility that two purportedly irreconcilable rival theories simply turn out to be divergent extensions of a single theory, which itself is not subject to empirical underdetermination. And it must, secondly, rule out the possibility that two such rival theories turn out to be notational variants of each other, where one is, for example, the result of interchanging the terms ‘electron’ and ‘neutron’ throughout the other. To accommodate the first point, the underdetermination thesis must require not just that there are some pairs of suitable rival theories, but that, for any theory, a suitable rival exists. To accommodate the second point, we introduce a general method of constructing new notational variants of a theory by defining a reconstrual of predicates to be a function whose domain is the set of predicates of the relevant language and whose converse domain is the set of open sentences of the language such that each n-place predicate is mapped to a sentence with n free variables. Now the empirical underdetermination thesis can be stated thus: given any scientific theory, there exists a rival theory which is empirically equivalent to the given theory and which cannot be rendered logically compatible with it by means of a reconstrual of predicates⁽²⁾ (Quine, 1975).

At first sight, we may find this claim puzzling. Surely, we may ask, if our ‘irreconcilable’ rival theories are empirically equivalent, they must have a considerable number of sentences in common, in particular all the observation conditionals which each of the theories implies. So, given a set of rival theories, can we not simply take their intersection as a new theory⁽³⁾ which is both empirically equivalent to each of the given theories and immune to empirical underdetermination? Indeed, if the set of desired observation conditionals to be entailed by a theory is finite, we can easily define the theory to be the deductive closure of the conjunction of these observation conditionals; such a theory is obviously unique and unaffected by empirical underdetermination. Similarly, if the set of observation conditionals is infinite, but exhibits so much structure that its deductive closure can be expressed as the deductive closure of a finite theory formulation, it is also possible to construct a tightly fitting theory. In its most general form, the empirical underdetermination thesis is therefore wrong.

However, given the complexity of the world, we may expect that, in many cases, (the deductive closure of) the set of all relevant observation conditionals is not axiomatizable in terms of a conceptually neat, let alone finite, theory formulation. Rather, any conceptually manageable (in particular, finite) theory formulation may well entail (the deductive closure of) the desired observation conditionals as well as some other (non-observational) sentences. And this is precisely why we can envisage that the problem of empirical underdetermination may crop up.

These considerations are certainly plausible. But are they incontrovertible? At this point we should turn our attention to Craig’s theorem, since, as we have indicated in the introduction, this result is often viewed as providing a method of constructing a conceptually manageable (at least, theoretically), though not usually finite, theory formulation which entails exclusively (the deductive closure of) the desired set of observation conditionals.

Some technical preliminaries are due. A set S is said to be recursively enumerable if it can be written as a sequence S = {s₁, s₂, s₃, …} which can be generated by means of an effective mechanism (i.e. by means of an appropriate Turing machine). A set S is said to be recursive (or decidable) if there exists an effective mechanism which can determine in a finite number of steps whether or not any given entity is a member of S. A set of sentences of a formal language is said to be recursively axiomatizable if it is the deductive closure of a recursive set of axioms. It is important to note that there are sets which are countably infinite (i.e. ‘enumerable’), but not recursively enumerable⁽⁴⁾, and that there are sets which are recursively enumerable, but not recursive⁽⁵⁾.

The basic insight underlying Craig’s theorem is the following: every theory which can be expressed as the deductive closure of a recursively enumerable set of axioms is recursively axiomatizable. Let us briefly go through the proof of this proposition. Suppose that T is the deductive closure of the recursively enumerable set of sentences S = {s₁, s₂, s₃, …}. We shall construct a recursive set of axioms for T. Define S' to be the set {s₁, (s_2 Ù  s₂), ((s_{3 Ù} s₃) Ù s₃), …} such that, for each s_i in S, S' contains a self-conjunction of s_i of length i. The question of whether or not a given sentence f is a member of S' is mechanically decidable in a finite number of steps. Given f , the unique readability of sentences of our formal language implies that there exist a unique sentence y and a unique number n (possibly y = f and n = 1) such that f is a self-conjunction of y of length n. We then consider the n^th element of the sequence {s₁, s₂, s₃, …}, which is, by assumption, mechanically accessible in a finite number of steps, and we compare y with s_n. If these two sentences are identical, we conclude that f is a member of S', and if they are distinct, we conclude that it isn’t. So S' is a recursive set. Furthermore, S and S' are clearly logically equivalent, and hence they have the same deductive closure, namely T. Thus S' is a recursive set of axioms for T as required.

Now Craig’s theorem concerning the replacement of auxiliary expressions is actually a special case of the result we have just proved.

Let T be a theory expressed in a formal language L, where T has a recursive theory formulation, and let P be the set of all predicate symbols of the language L. Consider any recursive subset P* of P, interpreted, for instance, as the subset of all ‘essential’ (as opposed to ‘auxiliary’) predicates of L. Let L* denote that part of the language L which contains all the sentences that can be expressed in the restricted vocabulary contained in P*. Craig’s theorem states that the restriction of T to L* — i.e. the set of all those sentences of T in which only predicates in P* (e.g. ‘essential’ ones) occur — is recursively axiomatizable.

This follows immediately from the basic insight we have just proved; to apply this insight, it is sufficient to show that the restriction of T to L* is recursively enumerable; its recursive axiomatizability will then follow. We first note that the set of all sentences of T is recursively enumerable: using the standard method of Gödel-numbering, we can effectively generate all well-formed strings of symbols of L, and, since T has a recursive theory formulation, it is possible to determine in a finite number of steps whether or not a given string of symbols of L constitutes a deduction of a sentence of T from the theory formulation of T. By selecting the last line of each such proof, our mechanical enumeration of all proofs of sentences of T can easily be converted into a mechanical enumeration of all sentences of T. But as P* is a recursive subset of P, there exists a mechanical procedure for deciding in a finite number of steps whether or not a given sentence of T belongs to the restriction of T to L*: the procedure simply needs to check whether all predicate symbols that occur in the given sentence are contained in P*. Using this decision procedure, our effective procedure for enumerating all sentences of T can be transformed into an effective procedure for enumerating all sentences of the restriction of T to L*. The recursive axiomatizability of the restriction of T to L* now follows from its recursive enumerability, as indicated above.

Let us return to our original question. We have seen that the empirical underdetermination thesis is parasitic upon the claim that, given a sufficiently complex set of observation conditionals, (i) the deductive closure of this set is not axiomatizable in terms of a conceptually neat theory formulation, and (ii) any conceptually manageable theory formulation will entail (the deductive closure of) the given set of observation conditionals as well as some other (non-observational) sentences. In what way could Craig’s theorem pose a challenge to this claim?

Let us quote Quine in detail:

Obviously, the basic idea is to invoke Craig’s theorem to establish the existence of a recursive (but possibly infinite) set of sentences which is logically equivalent to the desired set of observation conditionals and which can be used as a tightly fitting theory formulation for the deductive closure of our set of observation conditionals.

However, Quine’s argument is logically flawed. Although Quine is of course especially concerned with sets of observation conditionals, he insists that, for "any desired class of consequences" (my italics) of a theory formulation, we can specify a second class of sentences which is decidable and whose elements are logically equivalent to the elements of the given class. Let us examine this rather general claim first. In the next section, we shall then turn to Quine’s more specific claim regarding the application of Craig’s result to classes of observation conditionals.

The see whether the former claim is tenable, let us choose any finite theory formulation which has an infinite set of consequences, say T, and let us construct a particular subset of T, for which we will subsequently try to specify the corresponding ‘Craig class’ as explained by Quine. As before, we note that T is a recursively enumerable set. So T can be expressed as a mechanically producible sequence {t₁, t₂, t₃, …}. Let M be any subset of the natural numbers which is not recursively enumerable⁽⁶⁾. Define S := {t_n : n Î  M}. If S were recursively enumerable, we could use our enumeration mechanisms for S and for T to construct an enumeration mechanism for M. But there exists no such enumeration mechanism for M; and, in consequence, S cannot be recursively enumerable.

Using the method proposed by Quine, we shall define S' to be the ‘Craig class’ corresponding to S. Quine’s claim is that S' is decidable. We may already be puzzled here. Why? Given any sentence f of T and assuming that the Gödel number of its proof is n, define y to be a self-conjunction of f of length n, and use Quine’s suggested decision procedure to determine whether or not y is a member of S'. As Quine demands, we "count its internal repetitions" — the answer is n —, we "decode the proof, if any" — the result is a proof of f —, and we "see whether it is a proof of the repeated part of the given sentence" — the answer is ‘yes’! And this answer follows irrespective of whether or not the original sentence f is contained in S and also irrespective of whether or not the sentence y is contained in S'. Something must have gone wrong.

And indeed, we shall now see that Quine’s claim that S' is decidable gives rise to a contradiction. So let us begin with the assumption that "membership in [S'] admits of a mechanical decision procedure". Given an effective mechanism for generating the sequence of all well-formed formulae of our formal language, we can go through this sequence of well-formed formulae, one by one, mechanically testing whether or not each of the enumerated formulae is contained in S'. In this manner, we can mechanically enumerate all members of S'. But, of course, each element of S' is simply a certain self-conjunction of a corresponding element of S. So we can easily transform our mechanical enumeration procedure for S' into a mechanical enumeration procedure for S. This implies that S is recursively enumerable, a contradiction!

So what has gone wrong? Recalling our exposition of Craig’s theorem, we can easily see that Quine’s claim is simply too strong. Instead of starting off with "any desired class of consequences" (my italics) of a given theory formulation, he should have started off with a recursively enumerable set of consequences. The required "visibly equivalent" ‘Craig class’ could then be constructed in the manner explained in our proof of the insight preceding Craig’s theorem.

Bearing these observations in mind, we should now turn to Quine’s more specific point, namely that Craig’s result, applied to the class of all desired observation conditionals, may "challenge the interest of under-determination".

Clearly — and as Jane English (1973) argues conclusively —, if the set of all relevant observation conditionals could somehow be shown to be recursively enumerable, we would immediately be in a position to infer that the deductive closure of that set was recursively axiomatizable. In this case, there would indeed exist a tightly fitting theory formulation which could be regarded as ‘conceptually manageable’ so long as our notion of ‘conceptual manageability’ were to admit not only finite theory formulations, but also recursive ones. In particular, there would be no room for empirical underdetermination. For the present purposes, let us concede all this and focus upon the observation that the claim that Craig’s theorem challenges the empirical underdetermination thesis hinges crucially upon the recursive enumerability of the set of observation conditionals. In the remaining part of this paper, I will argue that, at least within the framework of Quine’s philosophy, the question of whether the relevant set of observation conditionals is recursively enumerable is likely to receive a negative answer.

Essentially, there are two strategies through which one might hope to establish the recursive enumerability of this set. One strategy would be to try to construct an explicit enumeration mechanism directly, and the other strategy would be to invoke a suitable subdivision of our language into ‘theoretical’ and ‘observational’ terms, in the manner of Craig’s theorem. We shall discuss each strategy in turn.

Presumably, an effective mechanism for enumerating all observation conditionals would have to be a combination of an effective mechanism for enumerating all sentences of our theory, which, as we know, exists, and a mechanical procedure for determining in a finite number of steps whether or not each such sentence is an observation conditional. The task of designing the latter procedure is tantamount to the task of designing a mechanical procedure for determining in a finite number of steps whether or not a given sentence is an observation sentence; for, the relation between observation sentences and observation conditionals (via pegged observation sentences) seems sufficiently systematic to be tractable by a mechanical procedure. But can this new task be performed?

Quine defines observation sentences in terms of a behavioural criterion: an observation sentence is an occasion sentence — i.e. a sentence whose truth-value depends upon the occasion of utterance — on which all competent speakers of the relevant language "give the same verdict when given the same concurrent stimulation" (Quine, 1969, p. 87) ⁽⁷⁾. This definition not only relies on contingent facts about the behaviour of the relevant group of competent speakers, but it is, in particular, ‘community-specific’ in the sense that the question of what occasion sentences are regarded as observation sentences may depend upon the community of witnesses that is taken to be relevant, and upon the witnesses’ background conceptual frameworks. Given all this and the fact that the cognitive and behavioural sciences are still in their infancy, the sheer idea of designing a mechanical procedure for determining in a finite number of steps whether or not a given sentence is an observation sentence according to the stated behavioural criterion appears to be highly implausible.

As a result, the second strategy, namely the search for a suitable subdivision of our language into ‘theoretical’ and ‘observational’ terms, may seem to be a more promising way of establishing the recursive enumerability of the set of all relevant observation conditionals. If we could capture the observational part of a theory by devising such a linguistic subdivision, the premises of Craig’s theorem would be met, and (the deductive closure of) the set of observation conditionals would be axiomatizable in a tightly fitting way.

Jane English, for instance, recognises the difficulties involved in the task of devising the required linguistic subdivision, but holds that "[i]f … science is recursively axiomatized, the problem of saying which of the system’s terms are observational is tractable" (1973, p. 454). Whether or not there are philosophical views according to which the present strategy would be regarded as promising, I will here point out that, from a Quinean perspective, it won’t. First and foremost, a Quinean would strongly resist the idea of drawing a principled distinction between ‘theoretical’ and ‘observational’ terms. As Quine is more than ready to argue, the smallest individually significant units of language are statements or sentences rather than terms (1953, section 5; and 1960). Observationality, for Quine, is a property of sentences or statements, but not of individual terms: the same term can occur in a broad range of fundamentally different sentences, observational and non-observational ones, and no sense can be made of claims about the alleged ‘observational’ or ‘theoretical’ nature of a term on its own.

But even if, contrary to Quine’s position, a principled distinction between ‘theoretical’ and ‘observational’ terms could be drawn, it would remain highly unclear whether we would be in a better position to utilise Craig’s theorem to challenge the empirical underdetermination thesis. Let me explain. It is well known that a restriction of the vocabulary of our language is not a particularly accurate or successful method of pinpointing sentences with an observational content. The fact that all the predicate symbols occurring in a given sentence are ‘observational’ predicate symbols does not guarantee that the sentence itself is an ‘observational’ sentence. As van Fraassen argues, "[t]he empirical import of a theory cannot be isolated in this syntactical fashion, by drawing a distinction among theorems in terms of vocabulary. If that could be done, T/E [i.e. the restriction of a theory to that part of our language in which there are only ‘observational’ predicate symbols] would say exactly what T says about what is observable and what it is like, and nothing more. But any unobservable entity will differ from the observable ones in the way it systematically lacks observable characteristics. As long as we do not abjure negation, therefore, we shall be able to state in the observational vocabulary (however conceived) that there are unobservable entities, and, to some extent, what they are like. The quantum theory, Copenhagen version, implies that there are things which sometimes have a position in space, and sometimes have not. This consequence I have just stated without using a single theoretical term. Newton’s theory implies that there is something (to wit, Absolute Space) which neither has a position nor occupies a volume. Such consequences are by no stretch of the imagination about … the observable world" (van Fraassen, 1980, pp. 54-55).

So even on an optimistic view on whether the empirical import of a theory can be captured by means of a suitable restriction of its vocabulary, we would have to acknowledge that the set of all relevant observation conditionals was only a proper subset of the set of all sentences of the theory expressible in the restricted vocabulary. In consequence, even a suitably constructed Craig reduction would not constitute a perfectly tightly fitting theory, for it would entail all sentences of the theory expressible in the restricted vocabulary and not just the genuinely observational ones; again, there would be logical space for empirical underdetermination.

The following objection could be raised: is it not conceivable that, although the set of all relevant observation conditionals is indeed a proper subset of the set of all sentences of the theory expressible in the restricted vocabulary, the former set logically determines the latter, in the sense that, once truth-values are assigned to all observation conditionals, this will immediately imply an assignment of truth-values to all sentences expressible in the restricted vocabulary (or, in other words, once we know what sentences are contained in the former set, we have no degrees of freedom in choosing what sentences are to be included in the latter one)?

However, van Fraassen’s above cited argument provides a straightforward counterexample to this objection. As we know, the totality of genuine observation conditionals of Newtonian mechanics is logically compatible both with the statement that there exists such a thing as absolute space and with the statement that there doesn’t exist such a thing. But as demonstrated by van Fraassen, such statements can be expressed solely in terms of the ‘observational’ vocabulary. Hence we see that the set of genuine observation conditionals of Newton’s theory by no means logically determines the set of all those sentences of the theory that are expressible in the ‘observational’ vocabulary. The objection must therefore be rejected.

We conclude that, from a Quinean viewpoint, it is doubtful whether the conditions under which Craig’s theorem would pose a challenge to the empirical underdetermination thesis can be satisfied. Neither the idea of directly designing an effective mechanism for enumerating all observation conditionals, nor the idea of devising a suitable subdivision of the terms of the relevant language into ‘theoretical’ and ‘observational’ ones are particularly promising strategies for establishing, as required, that the set of all observation conditionals entailed by a theory is recursively enumerable.

From the perspective of Quine’s philosophy, I have argued for a revision of the view that Craig’s theorem poses a (theoretical) challenge to the empirical underdetermination thesis. I have shown that Quine’s concession to the Craigian argument can probably be traced back to the fact that Quine invokes Craig’s theorem in a mathematically flawed way. Indeed, once the requirement that the set of all observation conditionals be recursively enumerable is recognised, Quine’s empirical underdetermination thesis can be defended against the Craigian challenge. This is not to say, however, that the thesis is correct. There may (or may not) be independent reasons why the empirical underdetermination thesis is untenable.

Christian List
University of Oxford
Nuffield College
Oxford OX1 1NF, U.K.
christian.list@nuffield.oxford.ac.uk

References

Notes

1. I wish to express my gratitude to Simon Saunders and to an anonymous referee for comments and suggestions, to Daniel Harbour for many fruitful discussions, and to the Scatcherd European Scholarship Foundation of Oxford University as well as to the (British) Economic and Social Research Council for financial support.
2. To be precise, we shall say that two theories can be rendered logically compatible by means of a reconstrual of predicates if there exists a reconstrual of predicates under which one of the two theories is mapped onto a (not necessarily proper) subset of the other.
3. Since each of the given theories is deductively closed, so is their intersection.
4. Consider, for instance, the set of all non-theorems of first-order Peano-arithmetic.
5. Consider, for instance, the set of all theorems of a first-order system of the predicate calculus.
6. In note (4), I have cited the set of all non-theorems of first-order Peano-arithmetic as an example of a set that is countably infinite, but not recursively enumerable. Call this set A. We can use A to generate the required set M as follows. A is clearly a subset of the recursively enumerable set of all well-formed formulae of an appropriate first-order language. Call the latter set B. Then B can be expressed as the sequence {b₁, b₂, b₃, …}. Now define M = {n Î  N : b_n Î  A}. If M were recursively enumerable, we could easily combine our enumeration mechanism for M with that for B so as to construct an enumeration mechanism for A. But this would imply the recursive enumerability of A, a contradiction! Hence M is a subset of the natural numbers which is not recursively enumerable.
7. As Davidson (1990) argues, Quine vacillates between two different criteria for defining observation sentences. The definition I state here makes use of the proximal criterion, Quine’s ‘official’ one, according to Davidson. Under the distal criterion, the subclause "when given the same concurrent stimulation" would have to be replaced with the subclause "when presented with the same intersubjectively shared situation". Whilst the two accounts have rather distinct philosophical consequences in many respects, the important point to note in the present context is that both definitions are essentially behavioural.