Theory (logic)

In mathematical logic , a theory ( first-order predicate logic ) is a set of statements about a signature .

definition

A set of statements is called deductively closed if all statements are made ${\displaystyle T}$ ${\displaystyle \phi }$

${\displaystyle T\vdash \phi }$

it already follows that

${\displaystyle \phi \in T.}$

If there is a language, then a theory is a deductively closed set of statements about this language. ${\displaystyle L}$

(Note: the definitions are not uniform in the literature. In some cases, it is also not required that a theory be deductively closed.)

A set of statements is a set of axioms for a theory if the deductive conclusion of those statements is the theory.

If there is a structure, it is a theory, since this set is deductively closed. ${\displaystyle M}$ ${\displaystyle \mathrm {Th} (M)=\{\phi |M\Vdash \phi \}}$

properties

General

• The power of a theory is its power as a set, or at least countable.
• A theory is consistent when it doesn't contain every sentence. (This is equivalent to not including a sentence of the form " ".) ${\displaystyle \phi \wedge \neg \phi }$
• The theory is complete when it contains either it or its negation for each proposition.
• The theory is finitely axiomatizable if it is the deductive conclusion of a finite set of statements.

Model theory

• A theory is model-complete if the fact that one model is in the other means that it is also fundamentally in the other.
• A theory has quantifier elimination if it is the deductive closure of a set of formulas that were formed without quantifiers.
• A theory is categorical in a cardinal number if it has only one model of power apart from isomorphism . ${\displaystyle \kappa }$ ${\displaystyle \kappa }$
• A complete theory is called small or narrow if it is countable for all . ( is the set of all complete types in variables.) ${\displaystyle T}$ ${\displaystyle n\ S_{n}(T)}$ ${\displaystyle S_{n}(T)}$ ${\displaystyle n}$

sentences

Important sentences about theories are:

The Gödel completeness theorem :

• Every consistent theory has a model.

The Löwenheim-Skolem :

• If a theory has a model in an infinite cardinal number, it also has one in every cardinal number greater than or equal to its power.

The set of Morley :

• If a countable theory is categorical in an uncountable cardinal number, then in every one.

Examples

The theory of natural numbers

The theory of natural numbers is formulated using language , the axioms formalize the following statements: ${\displaystyle (0,S,\cdot ,+)}$

• Zero is not a value of the (successor function) S.
• The successor function is injective
• For everyone is ${\displaystyle n}$ ${\displaystyle n+0=n}$
• For everyone is ${\displaystyle n}$ ${\displaystyle n+1=Sn}$
• For everyone is ${\displaystyle n}$ ${\displaystyle n+(Sm)=S(n+m)}$
• For everyone is ${\displaystyle n}$ ${\displaystyle n\cdot 0=0}$
• For everyone is ${\displaystyle n}$ ${\displaystyle n\cdot Sm=(n\cdot m)+n}$

In addition, the induction formula with an axiom is for each formula : ${\displaystyle \phi }$ ${\displaystyle \phi }$

• ${\displaystyle \phi (0,{\vec {y}})\land \forall x(\phi (x,{\vec {y}})\rightarrow \phi (x+1,{\vec {y}}))\rightarrow \forall x\phi (x,{\vec {y}})}$

( stands for ) ${\displaystyle {\vec {y}}}$ ${\displaystyle y_{1},...,y_{k}}$

The theory of natural numbers is incomplete. There is no consistent recursively enumerable expansion of the natural numbers. This is the statement of the incompleteness theorem .

The theory of dense linear order with no endpoints

The theory of the dense linear order without end points is the theory of the rational numbers with the order relation "<". The axioms are in detail:

1. ${\displaystyle (x<y)\vee (x=y)\vee (y<x)}$ (Trichotomy)
2. ${\displaystyle (x<y)\rightarrow \neg (y<x)}$ (Asymmetry)
3. ${\displaystyle (x<y)\wedge (y<z)\rightarrow (x<z)}$ (Transitivity)
4. ${\displaystyle \exists y,z:(x<y,z<x)}$ (Openness)
5. ${\displaystyle x<y\rightarrow \exists z(x<z\wedge z<y)}$ (Tightness)

It has the following properties, among others

• It is finitely axiomatizable, but has no finite models.
• It is complete and model-complete .
• All countable models are isomorphic (for proof ), in uncountable cardinal numbers there are non-isomorphic models. In the language of model theory this means: It is - categorical , but not categorical in uncountable cardinal numbers: If an uncountable cardinal number, then this theory has non-isomorphic models of power . ${\displaystyle \omega }$ ${\displaystyle \kappa }$ ${\displaystyle 2^{\kappa }}$ ${\displaystyle \kappa }$
• It is the (uniquely determined) model companion of the theory of the linear order.
• With the rational numbers it has a prime model . (This is a model that can be fundamentally embedded in any other model.)
• Every model is atomic .
• It has quantifier elimination .
• It is not stable .

The theory of algebraically closed bodies (in the characteristic p or 0)

• The theory of algebraically closed bodies without specifying the characteristic is model-complete, but not complete.
• For the theory of algebraically closed bodies with an indication of the characteristic, the following applies:

• It is complete.
• She has a prime model.
• It is -categorical, but not categorical in an uncountable cardinal number. ${\displaystyle \omega }$
• It has quantifier elimination.

Individual evidence

1. ↑ Chang, Chen C., Keisler, H. Jerome: Model Theory. Amsterdam [u. a.], North-Holland, 1998, p. 12

literature

• H.-D. Ebbinghaus, J. Flum, W. Thomas: Introduction to Mathematical Logic , Spectrum Academic Publishing House, ISBN 3-8274-0130-5
• Wilfrid Hodges : Model theory. Cambridge University Press, 1993, ISBN 0-521-30442-3 .
• Chang, Chen C., Keisler, H. Jerome: Model Theory. Amsterdam [u. a.], North-Holland, 1998.
• Prestel, Alexander: Introduction to Mathematical Logic and Model Theory. Vieweg, Braunschweig 1986. (Vieweg course; 60: advanced course in mathematics). ISBN 3-528-07260-1 . 286 pp.
• Philipp Rothmaler: Introduction to Model Theory. Spektrum Akademischer Verlag, 1995, ISBN 978-3-86025-461-5 .