Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2025-01-03T10:25:02.949Z Has data issue: false hasContentIssue false
  • English
  • Français

Some useful preservation theorems

Published online by Cambridge University Press:  12 March 2014

Kevin J. Compton
Kevin J. Compton*
Affiliation:
Wesleyan University, Middletown, Connecticut 06457
Get access Rights & Permissions [Opens in a new window]

Extract

The study of preservation theorems for first order logic was the focus of much research by model theorists in the 1960's. These theorems, which came to form the foundation for classical model theory, characterize first order sentences and theories that are preserved under operations such as the taking of unions or submodels (see Chang and Keisler [5] for a discussion of preservation theorems for first order logic). In current model theoretic research, logics richer than first order logic and applications of logic to other parts of mathematics have assumed the central position. In the former area, preservation theorems are not so important; in the latter, especially in applications to algebra, many of the techniques developed for proving these theorems have been useful.

In this paper I prove several preservation theorems for first order logic which I discovered while investigating the asymptotic growth of classes of finite combinatorial structures. The significance of these theorems lies in their applications to problems in finite combinatorics. Since the applications require combinatorial and analytical techniques that are not pertinent to logical questions discussed here, I shall present them in another paper [7].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 48 , Issue 2 , June 1983 , pp. 427 - 440
Copyright
Copyright © Association for Symbolic Logic 1983

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

[1]Andrews, G.F., The theory of partitions, Addison-Wesley, Reading, Mass., 1976.Google Scholar
[2]Barwise, J. and Schlipf, J., An introduction to recursively saturated and resplendent models, this Journal, vol. 41 (1976), pp. 531–576.Google Scholar
[3]Bender, B.A., Asymptotic methods in enumeration, SIAM Review, vol. 16 (1974), pp. 485–515.CrossRefGoogle Scholar
[4]de Bruijn, N.G., Asymptotic methods in analysis, North-Holland, Amsterdam, 1958.Google Scholar
[5]Chang, C.C. and Keisler, H.J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[6]Compton, K.J., Applications of logic to finite combinatorics, Ph. D. thesis, University of Wisconsin, 1980.Google Scholar
[7]Compton, K.J., A logical approach to asymptotic combinatorics (to appear).Google Scholar
[8]Goncharov, V., Sur la distribution des cycles dans les permutations, Comptes Rendus (Doklady) de l'Academie des Sciences de l'URSS, vol. 35 (1942), pp. 267–269.Google Scholar
[9]Harary, F. and Palmer, E.M., Graphical enumeration, Academic Press, New York, 1973.Google Scholar
[10]Katz, L., The problem of indecomposability of random mapping funtions, Annals of Mathematical Statistics, vol. 26 (1955), pp. 512–517.CrossRefGoogle Scholar
[11]Keisler, H.J., Unions of relational systems, Proceedings of the American Mathematical Society, vol. 15 (1964), pp. 540–545.CrossRefGoogle Scholar
[12]Kleitman, D.J. and Rothschild, B.I., Asymptotic enumeration of partial orders on a finite set, Transactions of the American Mathematical Society, vol. 205 (1975), pp. 205–223.CrossRefGoogle Scholar
[13]Knuth, D.E., The art of computer programming, Vol. 1, Addison-Wesley, Reading, Mass., 1968.Google Scholar
[14]Metropolis, N. and Ulam, S., A property of randomness in an arithmetical function, American Mathematical Monthly, vol. 61 (1954), pp. 392–397.Google Scholar
[15]Shepp, L.A. and Lloyd, S.P., Ordered cycle lengths in random permutations, Transactions of the American Mathematical Society, vol. 121 (1966), pp. 340–357.CrossRefGoogle Scholar