Namespaces
Variants
Actions

Characterization theorems for logics

From Encyclopedia of Mathematics
Jump to: navigation, search

First-order logic (cf. also Logical calculus) is well-suited for mathematics, e.g.:

1) There is a sound and complete proof calculus (completeness theorem). The decidability of many theories has been proven using the completeness theorem. (Cf. also Completeness (in logic); Sound rule.)

2) There is a system of first-order logical axioms for set theory (e.g., ZFC) that serves as a basis for mathematics.

3) There is a balance between syntax and semantics, e.g., implicitly definable concepts are explicitly definable (Beth's theorem; cf. also Beth definability theorem).

4) Semantic results such as the compactness theorem and the Löwenheim–Skolem theorem are valuable model-theoretic tools and lead to an enrichment of mathematical methods. Mainly in the period from 1950 to 1970, much effort was spent in finding languages which strengthen first-order logic but are still simple enough to yield general principles which are useful in investigating and classifying models. In particular, taking into account the situation for first-order logic, many logicians attempted to find logics satisfying analogues of the theorems mentioned above. However, results due to P. Lindström [a3] limit this search. Or, to state it more positively, Lindström proved the following characterization theorems for first-order logic:

First-order logic is a maximal logic with respect to expressive power satisfying the compactness theorem and the Löwenheim–Skolem theorem.

First-order logic is a maximal logic satisfying the completeness theorem and the Löwenheim–Skolem theorem.

These results were the starting point for investigations trying to order the diversity of extensions of first-order logic, for a systematic study of the relationship between different model-theoretic properties of logics, and for a search for further characterizations theorems for first-order and other logics.

Most of the results obtained can be found in [a1]. Two characterization theorems obtained for other logics are:

a) is a maximal bounded logic with the Karp property [a2];

b) for topological structures, the logic of "invariant sentences" is a maximal logic satisfying the compactness theorem and the Löwenheim–Skolem theorem [a4].

References

[a1] J. Barwise, S. Feferman, "Model-theoretic logics" , Springer (1985)
[a2] J. Barwise, "Axioms for abstract model theory" Ann. Math. Logic , 7 (1974) pp. 221–265
[a3] P. Lindström, "On extensions of elementary logic" Theoria , 35 (1969) pp. 1–11
[a4] M. Ziegler, "A language for topological structures which satisfies a Lindström-theorem" Bull. Amer. Math. Soc. , 82 (1976) pp. 568–570
How to Cite This Entry:
Characterization theorems for logics. Joerg Flum (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Characterization_theorems_for_logics&oldid=18155
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098