# Craig's Theorem

# CRAIG'S THEOREM

In mathematical logic, Craig's Theorem—not to be confused with Craig's Interpolation Theorem—states that any recursively enumerable theory is recursively axiomatizable. Its epistemological interest lies in its possible use as a method of eliminating "theoretical content" from scientific theories.

## Proof of Craig's Theorem

Assume that *S* is a deductively closed set of sentences, the elements of which may be recursively enumerated thus *F* (0), *F* (1), …, *F* (*n* ), … where *F* is a recursive function from natural numbers to sentences (we assume that expressions, sentences, etc., have been Gödel-coded in some manner). The set of theorems of an axiomatic theory is automatically recursively enumerable. But in general a recursively enumerable set is not automatically recursive. An example of a recursively enumerable set that is non-recursive is the set of logical truths in a first-order language with a single dyadic predicate. This follows from Church's Theorem, which states that the general notion of first-order validity is undecidable. However, through a trick devised by Craig, we can define a recursive set Craig(*S* ) whose deductive closure is *S*. Let *A* be a sentence and *n* a natural number. Let *A ^{n}* be the (

*n*+1)-fold conjunction

*A*∧ … ∧

*A*. The sentence

*A*

^{n}is logically interdeducible with

*A*. Next consider sentences of the form

*F*(

*n*)

*. Define Craig(*

^{n}*S*) to be {

*F*(

*n*)

*:*

^{n}*n*∈

*N*}. The deductive closure of Craig(

*S*) must be

*S*, since each element of Craig(

*S*) is equivalent to an element of

*S*. Next we give an informal decision procedure for membership in Craig(

*S*). Given a sentence

*A*, to decide whether

*A*∈ Craig(

*S*), first check if

*A*has the form

*B*, for some sentence

^{n}*B*and number

*n*. Through unique readability this is checkable, and if

*A*is not of this form then

*A*∉ Craig(

*S*). So suppose that

*A*is of the form

*B*. We calculate

^{n}*F*(

*n*), and if

*B*is indeed

*F*(

*n*) then

*A*∈ Craig(

*S*). And otherwise

*A*∉ Craig(

*S*). The existence of a decision procedure for membership in Craig(

*S*) implies that Craig(

*S*) is recursive. The set Craig(

*S*) is therefore a recursive axiomatization of the theory

*S*.

### craigian elimination

The logical positivists held that, under a logical reconstruction, a scientific theory is an axiom system formulated in a language *L* (*O, T* ), in which extra-logical predicates and function symbols are classified as either *O* -terms, for observational properties, or *T* -terms, for theoretical properties. Statements in *L* (*O, T* ) can be classified as observational, theoretical, or mixed, depending upon the presence or absence of *O* -terms or *T* -terms. Deleting theoretical terms yields a sublanguage *L* (*O* ) whose sentences express observational or empirical claims about the world. Assume that the property of being an *L* (*O* )-sentence is recursive. Consider a recursively enumerable theory *S* in *L* (*O, T* ). The empirical content of *S* is the set of *L* (*O* )-theorems of *S*. This is a subtheory of *S* obtained by a restriction on a recursive property. So it is recursively enumerable too. According to Craig's Theorem there is a recursive set of *L* (*O* )-sentences whose deductive closure is the empirical content of *S*. According to these assumptions we can therefore recursively axiomatize the empirical content of any given scientific theory *S*, obtaining a recursive axiom system Craig(*S* ), known as the Craigian reaxiomatization of *S* 's empirical content.

## Philosophical Significance of Craigian Elimination

Instrumentalism or positivism about science involves a scepticism towards the non-observational content of a scientific theory. Lacking such content the Craigian reaxiomatization Craig(*S* ) provides an object of rational belief compatible with instrumentalist or positivist scruples. Note that this elimination method need not be based on an observation/theory distinction. With obvious modification it can be used as a way of eliminating, for example, the mathematical content from a scientific theory formulated using mathematical predicates and quantification over sets, functions, and so forth, or as a way of eliminating theoretical content from a psychological theory that refers to mental states, and so on. Craigian reaxiomatization offers a possible elimination strategy for a variety of instrumentalist positions.

## Criticisms of Craigian Elimination

Of the aforementioned there are two methodological criticisms. First, even if the original theory *S* is presented in a simple manner, the reaxiomatization Craig(*S* ) will be complex and thus will violate the canon of *simplicity* which we might impose on admissible theories. Second Craig(*S* ) is *parasitic* upon the original theory *S* and so does not really stand alone from the original theory. Indeed Craig(*S* ) is a bizarre theory, having infinitely many axioms of the form *A ^{n}*, where

*A*is an empirical consequence of

*S*. Hartry Field refers to Craigian reaxiomatization as "bizarre trickery" and complains that Craig(

*S*) is "obviously uninteresting, since [it] does nothing towards explaining the phenomenon in question in terms of a small number of basic principles" (Field 1980, p. 8). A third criticism is that Craigian elimination rests on a mistaken conception of scientific theories, namely a

*syntactic view*of theories. This criticism has been urged by Bas van Fraassen, who writes "empirical import cannot be isolated syntactically … the reduced theory [Craig(

*S*)] is not a description of the observable part of the world of

*S*; rather it is a hobbled and hamstrung version of

*S*'s description of everything" (van Fraassen 1976, pp. 87–88). A final criticism attacks the tenability of the observation/theory distinction required. A simple example of this is that although "red" seems a paradigmatic observational term, we can nonetheless speak of red blood cells, which are too small to be visible to the naked eye (see Putnam 1962).

With respect to certain assumptions discussed above concerning the notion of "empirical content," Craig's Theorem tells us that we can reaxiomatize the empirical content of a scientific theory, thereby eliminating apparent reference to unobservable objects and properties. However this elimination procedure has not found many adherents, and it seems safe to say that the significance of Craigian elimination is primarily pedagogical.

** See also ** Field, Hartry.

## Bibliography

Craig, William. "On Axiomatizability Within a System." *Journal of Symbolic Logic* 18 (1953): 30–32.

Field, Hartry. *Science without Numbers*. Princeton, NJ: Princeton University Press, 1980.

Putnam, Hilary "What Theories Are Not." In *Logic, Methodology and Philosophy of Science*, edited by Ernest Nagel, Patrick Suppes, and Alfred Tarski. Stanford University Press, 1962. Reprinted in Hilary Putnam *Mathematics, Matter and Method: Philosophical Papers*, Vol. 1, Cambridge University Press, 1979.

van Fraassen, B. C. "To Save the Phenomena. " *Journal of Philosophy* 73 (1976): 623–632 (page references to the reprint in David Papineau, ed. *Philosophy of Science*. New York: Oxford University Press, 1996).

*Jeffrey Ketland (2005)*

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**Craig's Theorem**