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 (also called a formal theory) is a set of sentences in a formal language. Usually a deductive system is understood from context. An element of a theory T is then called an axiom of the theory, and any sentence that follows from the axioms () is called a theorem of the theory. Every axiom is also a theorem. A firstorder theory is a set of firstorder sentences.
Contents
Theories expressed in formal language generally
When defining theories for foundational purposes, additional care must be taken and normal settheoretic language may not be appropriate.
The construction of a theory begins by specifying a definite nonempty conceptual class , the elements of which are called statements. These initial statements are often called the primitive elements or elementary statements of the theory, to distinguish them from other statements which may be derived from them.
A theory is a conceptual class consisting of certain of these elementary statements. The elementary statements which belong to are called the elementary theorems of and said to be true. In this way, a theory is a way of designating a subset of which consists entirely of true statements.
This general way of designating a theory stipulates that the truth of any of its elementary statements is not known without reference to . Thus the same elementary statement may be true with respect to one theory, and not true with respect to another. This is as in ordinary language, where 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. ^{[1]}
Subtheories and extensions
A theory S is a subtheory of a theory T if S is a subset of T. If T is a subset of S then S is an extension or supertheory of T
Deductive theories
A theory is said to be a deductive theory if 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.^{[1]}
Consistency and completeness
Main articles: Consistency and CompletenessA 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 firstorder 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 firstorder logic, the most important case, it follows from the completeness theorem that the two meanings coincide. In other logics, such as secondorder 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 {φ} 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: Interpretation (logic)An interpretation of a theory is the relationship between a theory and some contensive subject matter when there is a manytoone 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.^{[2]}
Theories associated with a structure
Each structure has several associated theories. The complete theory of a structure A is the set of all firstorder 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 firstorder σ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 each σ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 σ 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 firstorder σ'sentences that are satisfied by A or, equivalently, the complete (firstorder) theory of the natural expansion of A to the signature σ'.
Firstorder theories
Further information: List of firstorder theoriesA firstorder theory is a set of sentences in a firstorder formal language .
Derivation in a first order theory
Main article: First order logic#Deductive systemsThere are many formal derivation ("proof") systems for firstorder logic.
Syntactic consequence in a first order theory
A formula A is a syntactic consequence of a firstorder theory if there is a derivation of A using only formulas in as nonlogical axioms. Such a formula A is also called a theorem of . The notation "" indicates A is a theorem of
Interpretation of a first order theory
Main article: Structure (mathematical logic)An interpretation of a firstorder theory provides a semantics for the formulas of the theory. An interpretation is said to satisfy a formula if the formula is true according to the interpretation. A model of a first order theory is an interpretation in which every formula of is satisfied.
First order theories with identity
Main article: First order logic#Equality and its axiomsA first order theory is a firstorder theory with identity if includes the identity relation symbol "=" and the reflexivity and substitution axiom schemes for this symbol.
 Compactness theorem
 Consistent set
 Deduction theorem
 Enumeration theorem
 Lindenbaum's lemma
 LowenheimSkolem theorem
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.
See also
References
 Hodges, Wilfrid (1997). A shorter model theory. Cambridge University Press. ISBN 0521587131.
Categories: Model theory
 Formal theories
 Concepts
 Logical syntax
Wikimedia Foundation. 2010.
Look at other dictionaries:
Mathematical logic — (also known as symbolic logic) is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic.[1] The field includes both the mathematical study of logic and the… … Wikipedia
Structure (mathematical logic) — In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it. Universal algebra studies structures that generalize the algebraic structures such as… … Wikipedia
Independence (mathematical logic) — In mathematical logic, a sentence sigma; is called independent of a given first order theory T if T neither proves nor refutes sigma;; that is, it is impossible to prove sigma; from T , and it is also impossible to prove from T that sigma; is… … Wikipedia
Absoluteness (mathematical logic) — In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures (also called models). Theorems about absoluteness typically show that each of a large syntactic class of formulas is… … Wikipedia
Judgment (mathematical logic) — In mathematical logic, a judgment can be for example an assertion about occurrence of a free variable in an expression of the object language, or about provability of a proposition (either as a tautology or from a given context); but judgments… … Wikipedia
Literal (mathematical logic) — In mathematical logic, a literal is an atomic formula (atom) or its negation. The definition mostly appears in proof theory (of classical logic), e.g. in conjunctive normal form and the method of resolution. Literals can be divided into two types … Wikipedia
List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic … Wikipedia
Timeline of mathematical logic — A timeline of mathematical logic 19th century * 1847 George Boole formalizes symbolic logic in The Mathematical Analysis of Logic , defining what is now called Boolean algebra. * 1874 Georg Cantor shows that the set of all real numbers is… … Wikipedia
Department of Mathematical Logic (Bulgarian Academy of Sciences) — The Department of Mathematical Logic at the Bulgarian Academy of Sciences was created by the Institute of Mathematics and Informatics in implementation of Government Decree N0. 236 of November 3, 1959. Its first chairman was Boyan Petkanchin… … Wikipedia
Theory (disambiguation) — Theory may refer to:;Concepts * Theory, a logical explanation for a given set of facts * Theory (mathematics) a branch of mathematics which covers a single subject (e.g. Number theory) * Theory (mathematical logic), the set of statements… … Wikipedia