Namespaces
Variants
Actions

Difference between revisions of "Characterization theorems for logics"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 2 formulas out of 2 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 2 formulas, 2 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
First-order logic (cf. also [[Logical calculus|Logical calculus]]) is well-suited for mathematics, e.g.:
 
First-order logic (cf. also [[Logical calculus|Logical calculus]]) is well-suited for mathematics, e.g.:
  
Line 17: Line 25:
 
Most of the results obtained can be found in [[#References|[a1]]]. Two characterization theorems obtained for other logics are:
 
Most of the results obtained can be found in [[#References|[a1]]]. Two characterization theorems obtained for other logics are:
  
a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120120/c1201201.png" /> is a maximal bounded logic with the Karp property [[#References|[a2]]];
+
a) $\mathcal{L} _ { \infty  \omega}$ is a maximal bounded logic with the Karp property [[#References|[a2]]];
  
b) for topological structures, the logic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c120/c120120/c1201202.png" /> of  "invariant sentences"  is a maximal logic satisfying the compactness theorem and the Löwenheim–Skolem theorem [[#References|[a4]]].
+
b) for topological structures, the logic $L _ { t }$ of  "invariant sentences"  is a maximal logic satisfying the compactness theorem and the Löwenheim–Skolem theorem [[#References|[a4]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Barwise,  S. Feferman,  "Model-theoretic logics" , Springer  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Barwise,  "Axioms for abstract model theory"  ''Ann. Math. Logic'' , '''7'''  (1974)  pp. 221–265</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  P. Lindström,  "On extensions of elementary logic"  ''Theoria'' , '''35'''  (1969)  pp. 1–11</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Ziegler,  "A language for topological structures which satisfies a Lindström-theorem"  ''Bull. Amer. Math. Soc.'' , '''82'''  (1976)  pp. 568–570</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  J. Barwise,  S. Feferman,  "Model-theoretic logics" , Springer  (1985)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  J. Barwise,  "Axioms for abstract model theory"  ''Ann. Math. Logic'' , '''7'''  (1974)  pp. 221–265</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  P. Lindström,  "On extensions of elementary logic"  ''Theoria'' , '''35'''  (1969)  pp. 1–11</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  M. Ziegler,  "A language for topological structures which satisfies a Lindström-theorem"  ''Bull. Amer. Math. Soc.'' , '''82'''  (1976)  pp. 568–570</td></tr></table>

Latest revision as of 16:59, 1 July 2020

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) $\mathcal{L} _ { \infty \omega}$ is a maximal bounded logic with the Karp property [a2];

b) for topological structures, the logic $L _ { t }$ 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. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Characterization_theorems_for_logics&oldid=18155
This article was adapted from an original article by Joerg Flum (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article