Figure 68: Encyclopedia Britannica: Model theory (1968)

 

 

Macropaedia, vol. 11, 1083-1086

 

MODEL THEORY

 

Background and typical problems.

 

In model theory one studies the interpretations (models) of theories formalized in the framework of formal logic, especially in that of the first-order predicate calculus with equality; i. e., in elementary logic.

 

A first-order language is given by a collection S of symbols for relations, functions, and constants, which, in combination with the symbols of elementary logic, single out certain combinations of symbols as sentences. Thus, for example, in the case of the system N, the formation rules yield a language that is determined in accordance with a uniform procedure by the set (indicated by braces) of uninterpreted extralogical symbols:

S = {+, ^., 0, 1}.

A first-order theory is determined by a language and a set of selected sentences of the language - those sentences of the theory that are, in an arbitrary, generalized sense, the "true" ones (called the "distinguished elements" of the set). In the particular case of the system N, one theory T_a, is built up on the basis of the language and the set of theorems of N, and another theory T_b is determined by the true sentences of N according to the natural interpretation or meaning of its language. In general, the language of N and any set of sentences of the language can be used to make up a theory.

 

Satisfaction of a theory by a structure: finite and infinite models.

 

A realization of a language (for example, the one based on S) is a structure  identified by the five elements so arranged

 

 = A, + , ^., 0, 1>,

 

in which A is a nonempty set (called the domain of ), the last two terms are members of A, and the other two terms are functions correlating each member of the Cartesian product A x A (i. e., from the set of ordered pairs <a,b> such that a,b belong to A) with a member of A.

The structure  satisfies or is a model of the theory T_a (or T_b) if all of the distinguished sentences of T_a (or T_b) are true in ( (or satisfied by ). Thus, if  is the structure of the ordinary non-negative integers <ω, + , ., 0, 1>, in which w is the set of all such integers and +, ., 0, and 1 the elements for their generation, then it is not only a realization of the language based on S but also a model of both T_a and T_b.

Gödel's incompleteness theorem permits nonstandard models of T_a that contain more objects than w but in which all of the distinguished sentences of T_a (viz., the theorems of the system N) are true. Skolem's constructions (related to ultraproducts, see below) yield nonstandard models for both theory T_a and theory T_b.

 

The use of the relation of satisfaction, or being-a-model-of, between a structure and a theory (or a sentence) can be traced to the book Wissenschaftslehre (1837; "Theory of Knowledge") by Bernard Bolzano, a Czech theologian and mathematician, and, in a more concrete context, to the introduction of models of non-Euclidean geometries around that time.

In the mathematical treatment of logic, these concepts can be found in works of Ernst Schröder, a late-19th-century German mathematician, and in Löwenheim (in particular, in his paper of 1915).

The basic tools and results achieved in model theory - such as the Löwenheim-Skolem theorem, the completeness theorem of elementary logic, and Skolem's construction of nonstandard models of arithmetic - were developed during the period from 1915 to 1933. A more general and abstract study of model theory began after 1950, in the work of Tarski and others.

 

One group of new developments may be classified as refinements and extensions of the Löwenheim-Skolem theorem. These developments employ the concept of a "cardinal number," which - for a finite set - is simply the number at which one stops in counting its elements. For infinite sets, however, the elements must be matched from set to set instead of being counted, and the "sizes" of these sets must thus be designated by transfinite numbers.

A rather direct generalization can be drawn that says that, if a theory has any infinite model, then, for any infinite cardinal number, it has a model of that cardinality. It follows that no theory with any infinite model can be categorical or such that any two models of the theory are isomorphic (i. e., matchable in one-to-one correspondence) because models of different cardinalities can obviously not be so matched.

A natural question is whether a theory can be categorical in certain infinite cardinalities; i. e., whether there are cardinal numbers such that any two models of the theory of the same cardinality are isomorphic. According to a central discovery made in 1963 by Michael Morley, a U.S. mathematician, if a theory is categorical in any uncountable cardinality (i. e., any cardinality higher than the countable), then it is categorical in every uncountable cardinality.

On the other hand, examples are known for all four combinations of countable and uncountable cardinalities: specifically, there are theories that are categorical

(1) in every infinite cardinality;

(2) in the countable cardinality but in no uncountable cardinality;

(3) in every uncountable cardinality but not in the countable; and

(4) in no infinite cardinality.

 

In another direction, there are "two-cardinal" problems that arise from the possibilities of changing, from one model to another, not only the cardinality of the domain of the first model but also the cardinality of some chosen property (such as being a prime number). Various answers to these questions have been found, including proofs of independence (based 0n the ordinary axioms employed in set theory) and proofs of conditional theorems made on the basis of certain familiar hypotheses of set theory.

 

Elementary logic.

 

An area that is perhaps of more philosophical interest is that of the nature of elementary logic itself. On the one hand, the completeness discoveries seem to show in some sense that elementary logic is what the logician naturally wishes to have. On the other hand, he is still inclined to ask whether there might be some principle of uniqueness according to which elementary logic is the only solution that satisfies certain natural requirements on what a logic should be.

The recent development of model theory has led to a more general outlook that enabled Per Lindström, a Swedish logician, to prove, in 1969, a general theorem to the effect that, roughly speaking, within a broad class of possible logics, elementary logic is the only one that satisfies the requirements of axiomatizability of the Löwenheim-Skolem thorem. Although Lindström's theorem does not settle satisfactorily whether or not elementary logic is the right logic, it does seem to suggest that mathematical findings can help the logician to clarify his concepts of logic and of logical truth.

 

A particularly useful tool for obtaining new models from the given models of a theory is the construction of a special combination called the "ultraproduct" of a family of structures - in particular, the ultrapower when the structures are all copies of the same structure (just as the product of a₁, . . . , a_n is the same as the power aⁿ, if a_i = a for each i).

The intuitive idea in this method is to establish that a sentence is true in the ultraproduct if and only if it is true in "almost all" of the given structures (i. e., "almost everywhere" - an idea that was present in a different form in Skolem's construction of a nonstandard model of arithmetic in 1933). It follows that if the given structures are models of a theory, then their ultraproduct is such a model also, because every sentence in the theory is true everywhere (which is a special case of "almost everywhere" in the technical sense employed).

Ultraproducts have been applied, for example, to provide a foundation for what is known as "nonstandard analysis" that yields an unambiguous interpretation of the classical concept of infinitesimals-the division into units as small as one pleases. They have also been applied by two mathematicians, James Ax and S. B. Kochen, to problems in the field of algebra (on p-adic fields).

 

Nonelementary logic and Future developments.

 

There are also studies that develop the model theory of nonelementary logic: such as second-order logic and infinitary logics.

Second-order logic contains, in addition to variables that range over individual objects, a second kind of variable ranging over sets of objects so that the model  of a second-order sentence or theory also involves, beyond the basic domain, a larger set (called its "power set") that encompasses all of the subsets of the domain.

Infinitary logics may include functions or relations with infinitely many arguments, infinitely long conjunctions and disjunctions, or infinite strings of quantifiers. From studies on infinitary logics, William Hanf, an American logician, was able to define certain cardinals, some of which have been studied in connection with the lange cardinals in set theory.

In yet another direction, logicians are developing model theories for modal logics-those dealing with such modalities as necessity and possibility-and for the intuitionistic logic.

 

There is a large gap between the general theory of models and the construction of interesting particular models such as those employed in the proofs of the independence (and consistency) of special axioms and hypotheses in set theory. It is natural to look for further developments of model theory that will yield more systematic methods for constructing models of axioms with interesting particular properties, especially in deciding whether certain given sentences are derivable from the axioms. Relative to the present state of knowledge, such goals appear fairly remote. The gap is not unlike that between the abstract theory of computers and the basic properties of actual computers.

 

...

 

BIBLIOGRAPHY

 

Original sources:

JEAN VAN HEIJENOORT (ed.), From Frege to Gödel (1967);

PAUL BENACERRAF and HILLARY PUTNAM (eds.), Philosophy of Mathematics (1964);

MARTIN DAVIS (ed.), The Undecidable (1965);

DAVID HILBERT, Gesammelte Abhandlungen, vol. 3 (1935, reprinted 1965);

LUDWIG WITTGENSTEIN, Tractatus logico-philosophicus (1922);

THORALF SKOLEM, Selected Works in Logic (1970);

GERHARD GENTZEN, The Collected Papers (1969);

KURT GODEL, "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes," Dialectica, 12:280-287 (1958);

A. S. KAHR, EDWARD F. MOORE, and HAO WANG, "Entscheidungsproblem Reduced to the AEA Case," Proc. Natn. Acad. Sci. U.S.A., 48:365-377 (1962);

MICHAEL MORLEY, "On Theories Categorical in Uncountable Powers," ibid., 49:213-216 (1963);

JAMES Ax and SIMON KOCHEN, "Diophantine Problems over Local Fields," pt. 1-2, Am. J. Math., 87:605-648 (1965), and pt. 3, Ann. Math., 83:437-456 (1966);

PER LINDSTROM, "On Extension of Elementary Logic," Theoria, 35:1-11 (1969);

and J. V. MATIJASEVICZ, "Enumerable Sets Are Diophantine," Soviet Math. Doklady, 11:354-358 (1970).

 

Expositions:

DAVID HILBERT, Grundlagen der Geometrie (1899; Eng. trans., Foundations of Geometry, 1902);

ALFRED NORTH WHITEHEAD and BERTRAND RUSSELL, Principia Mathematica (1910-13; 2nd ed., 1925-27);

DAVID HILBERT and WILHELM ACKERMANN, Grundzüge der theoretischen Logik (1928; 5th ed., 1967);

DAVID HILBERT and PAUL BERNAYS, Grundlagen der Mathematik, 2 vol. (1934-39; 2nd cd., 196870);

WILLARD V. QUINE, Mathematical Logic (1941; rev. ed., 1951);

RUDOLF CARNAP, Introduction to Semantics (1942);

STEPHEN C. KLEENE, Introduction to Metamathematics (1952);

ALFRED TARSKI, Undecidable Theories (1953);

ALONZO CHURCH, Introduction to Mathematical Logic, vol. 1 (1956);

ERNEST NAGEL and JAMES R. NEWMAN, Gödel's Proof (1958);

KURT SCHUETTE, Beweistheorie (1960) and Vollständige Systeme modaler und intuitionistischer Logik (1968);

HAO WANG, A Survey of Mathematical Logic (1962);

MICHAEL MORLEY, Partitions and Models," Proc. Summer School in Logic (1968).

 

If a serious study of the field is contemplated, most of the central results can be found in the following textbooks:

PAUL J. COHEN, Set Theory and the Continuum Hypothesis (1966);

JOSEPH B. SHOENFIELD, Mathematical Logic (1967);

J. L. BELL and A .B. SLOMSON, Models and Ultraproducts: An Introduction (1969).

 

Hao Wang