Theory (mathematical logic)

This article is about theories in a formal language, as studied in mathematical logic. For other uses, see Theory (disambiguation).

In mathematical logic, a theory is a set of sentences in a formal language. For example, a first-order theory is a set of first-order sentences. Many authors require that the theory be closed under logical consequence.

Theories in general

The construction of a theory begins by specifying a definite non-empty set of statements. Let's call this set ${\mathcal {E}}$. These initial statements are often called the primitive elements or elementary statements of the theory. We so designate these initial statements, so as to distinguish them from other statements which we may derive from them.

A theory then, is the conceptual set of these elementary statements. Let ${\mathcal {T}}$ be such a theory. The elementary statements which belong to ${\mathcal {T}}$ which are true are called the elementary theorems of ${\mathcal {T}}$. In this way, a theory is a way of designating a subset of ${\mathcal {E}}$ which consists entirely of true statements.

This general way of designating a theory stipulates that the truth of its elementary statements are not known without reference to ${\mathcal {T}}$. It also makes it possible to evaluate two different theories with the same elementary statements. In this way statements such as "He is a terrible person." cannot be judged to be true or false without reference to some interpretation of who "He" is and for that matter what a "terrible person" is under this theory.

Subtheories and extensions

We can define a theory ${\mathcal {T}}$₁ as being a subtheory of another ${\mathcal {T}}$ or as being an extension or supertheory of another using the notation of set theory.

${\mathcal {T}}$₁ $\subseteq {\mathcal {T}}$, and likewise ${\mathcal {T}}\supseteq {\mathcal {T}}$₁

If every elementary theorem of ${\mathcal {T}}$₁ is also one of ${\mathcal {T}}$

Consistent theories

Main article: Consistency

Under the general definition given above of a theory involving ${\mathcal {E}}$ and ${\mathcal {T}}$, a consistent theory is one which does not exhaust the whole of ${\mathcal {E}}$.

In theories based in predicate calculus the elementary statements are of the form $\vdash$P, where P is a some formula and '$\vdash$' designates the predicate of assertability. Such a theory would be called inconsistent if both a formula and its negation were assertable.

Deductive theories

A theory is said to be a deductive theory if ${\mathcal {T}}$ is an inductive class. That is, that its content is based on some formal deductive system and that some of its elementary statements are taken as axioms. In a deductive theory, any sentence which is a logical consequence of one or more of the axioms is also a sentence of that theory.

Examples

One way to specify a theory is to define a set of axioms in a particular language. The theory can be taken to include just those axioms, or their logical or provable consequences, as desired. Theories obtained this way include ZFC and Peano arithmetic.

A second way to specify a theory is to begin with a structure and then let the theory be the set of formulas that are satisfied by the structure. This is one method for producing complete theories, described below. Examples of theories of this sort include the sets of true sentences in the structures (N, +, ×, 0, 1, =) and (R, +, ×, 0, 1, =), where N is the set of natural numbers and R is the set of real numbers. The first of these, called the theory of true arithmetic, cannot be written as the set of logical consequences of any enumerable set of axioms. The theory of (R, +, ×, 0, 1, =) was shown by Tarski to be decidable; it is the theory of real closed fields.

Consistency and completeness

A syntactically consistent theory is a theory from which not every sentence in the underlying language can be proved (with respect to some deductive system which is usually clear from context). In a deductive system (such as first-order logic) that satisfies the principle of explosion, this is equivalent to requiring that there is no sentence φ such that both φ and its negation can be proved from the theory.

A satisfiable theory is a theory that has a model. This means there is a structure M that satisfies every sentence in the theory. Any satisfiable theory is syntactically consistent, because the structure satisfying the theory will satisfy exactly one of φ and the negation of φ, for each sentence φ.

A consistent theory is sometimes defined to be a syntactically consistent theory, and sometimes defined to be a satisfiable theory. For first-order logic, the most important case, it follows from the completeness theorem that the two meanings coincide. In other logics, such as second-order logic, there are syntactically consistent theories that are not satisfiable, such as ω-inconsistent theories.

A complete consistent theory (or just a complete theory) is a consistent theory T such that for every sentence φ in its language, either φ is provable from T or T $\cup$ {φ} is inconsistent. For theories closed under logical consequence, this means that for every sentence φ, either φ or its negation is contained in the theory. An incomplete theory is a consistent theory that is not complete.

See also ω-consistent theory for a stronger notion of consistency.

Interpretation of a theory

Main article: Formal interpretation

An interpretation of a theory is the relationship between a theory and some contensive subject matter when there is a many-to-one correspondence between certain elementary statements of the theory, and certain contensive statements related to the subject matter. If every elementary statement in the theory has a contensive correspondent it is called a full interpretation, otherwise it is called a partial interpretation.

In other common terminology, theories may be associated with a structure. The complete theory of a structure A, is the set of all first-order sentences over the signature of A which are satisfied by A. It is denoted by Th(A). More generally, the theory of K, a class of σ-structures, is the set of all first-order σ-sentences that are satisfied by all structures in K, and is denoted by Th(K). Clearly Th(A) = Th({A}). These notions can also be defined with respect to other logics.

For a σ-structure A, there are several associated theories in a larger signature σ' that extends σ by adding one new constant symbol for each element of the domain of A. (If the new constant symbols are identified with the elements of A which they represent, σ' can be taken to be σ $\cup$ A.) The cardinality of σ' is thus the larger of the cardinality of σ and the cardinality of A.

The diagram of A consists of all atomic or negated atomic σ'-sentences that are satisfied by A and is denoted by diag_A. The positive diagram of A is the set of all atomic σ'-sentences which A satisfies. It is denoted by diag⁺_A. The elementary diagram of A is the set eldiag_A of all first-order σ'-sentences that are satisfied by A or, equivalently, the complete (first-order) theory of the natural expansion of A to the signature σ'.

See also

• Axiomatic system
• List of first-order theories

References

• Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 0-521-58713-1.