Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-19T02:58:15.961Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability and ℵ0-categoricity of theories of partially ordered sets

Published online by Cambridge University Press:  12 March 2014

James H. Schmerl
James H. Schmerl*
Affiliation:
University of Connecticut, Storrs, Connecticut 06268
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper is primarily concerned with ℵ0-categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ0-categoricity. Among the latter are the following.

Corollary 3.3. For every countable ℵ0-categoricalthere is a linear order of A such that (, <) is ℵ0-categorical.

Corollary 6.7. Every ℵ0-categorical theory of a partially ordered set of finite width has a decidable theory.

Theorem 7.7. Every ℵ0-categorical theory of reticles has a decidable theory.

There is a section dealing just with decidability of partially ordered sets, the main result of this section being

Theorem 8.2. If (P, <) is a finite partially ordered set and KP is the class of partially ordered sets which do not embed (P, <), then Th(KP) is decidable iff KP contains only reticles.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 45 , Issue 3 , September 1980 , pp. 585 - 611
Copyright
Copyright © Association for Symbolic Logic 1980

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

REFERENCES

[1]Ash, C. J., Undecidable ℵ0-categorical theories, Notices of the American Mathematical Society, vol. 18 (1971), p. 423.Google Scholar
[2]Bacsich, P., The strong amalgamation property, Colloquium Mathtmaticum, vol. 33 (1975), pp. 13–23.CrossRefGoogle Scholar
[3]Baker, K. A., Fishburn, P. C. and Roberts, F. S., Partial orders of dimension 2, Networks, vol. 2 (1971), pp. 11–28.CrossRefGoogle Scholar
[4]Crossley, J. and Nerode, A., Combinatorial functors, Ergebnisse Mathematische Grenzgebiete, Band 81, Springer, New York, 1974.Google Scholar
[5]Dilworth, R. P., A decomposition theorem for partially ordered sets, Annals of Mathematics, vol. 51 (1950), pp. 161–166.CrossRefGoogle Scholar
[6]Dushnik, B. and Miller, E. W., Partially ordered sets, American Journal of Mathematics, vol. 63 (1941), pp. 600–610.CrossRefGoogle Scholar
[7]Ehrenfeucht, A., There are continuum ℵ0-categorical theories, Bulletin de l'Académie Polonaise des Sciences. Séries des Sciences Mathématiques, Astronomiques et Physiques, vol. 20 (1972), pp. 425–427.Google Scholar
[8]Eklof, P., Algebraic closure operators and strong amalgamation bases, Algebra Universalis, vol. 4 (1974), pp. 89–98.CrossRefGoogle Scholar
[9]Engeler, E., A characterization of theories with isomorphic denumerable models, Notices of the American Mathematical Society, vol. 6 (1959), p. 161.Google Scholar
[10]Fraïssé, R., Sur certaines relations qui généralisent l'ordre des nombres rationnels, Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B, vol. 237 (1953), pp. 540–542.Google Scholar
[11]Glassmire, W. Jr., There are 2ℵ0 countably categorical theories, Bulletin de l'Académie Polonaise des Sciences. Séries des Sciences Mathématiques, Astronomiques et Physiques, vol. 19 (1971), pp. 185–190.Google Scholar
[12]Grzegorczyk, A., Logical uniformity by decomposition and categoricity in ℵ0, Bulletin de l'Académie Polonaise des Sciences. Séries des Sciences Mathématiques, Astronomiques et Physiques, vol. 16 (1968), pp. 687–692.Google Scholar
[13]Henson, C. W., Countable homogeneous relational structures and ℵ0-categorical theories, this Journal, vol. 37 (1972), pp. 494–500.Google Scholar
[14]Herrmann, E., On Lindenbaum functions of ℵ0-categorical theories of finite similarity types, Bulletin de l'Académie Polonaise des Sciences. Séries des Sciences Mathématiques, Astronomiques et Physiques, vol. 24 (1976), pp. 17–21.Google Scholar
[15]Manaster, A. and Rosenstein, J., Two-dimensional partial orderings and recursion theory (preprint).Google Scholar
[16]Peretyatkin, M. G., On complete theories with a finite number of denumerable models, Algebra i Logika, vol. 12 (1973), pp. 550–576.Google Scholar
[17]Plotkin, J., Generic embeddings, Ph.D. thesis, Cornell University, 1968.Google Scholar
[18]Rabin, M. O., A simple method for undecidability proofs and some applications, Logic, Methodology and Philosophy of Science, Proceedings of the 1964 International Congress, North-Holland, Amsterdam, 1965, pp. 58–68.Google Scholar
[19]Rabin, M. O., Decidability of second-order theories and automata on finite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[20]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[21]Rosenstein, J.G., ℵ0-categoricity of linear orderings, Fundamenta Mathematicae, vol. 44 (1969), pp. 1–5.CrossRefGoogle Scholar
[22]Ryll-Nardzewski, C., On the categoricity in power ≤ ℵ0, Bulletin de l'Académie Polonaise des Sciences. Séries des Sciences Mathématiques, Astronomiques et Physiques, vol. 7 (1959), pp. 545–548.Google Scholar
[23]Schmerl, J.H., The decidability of some ℵ0-categorical theories, Colloquium Mathematicum, vol. 36 (1976), pp. 165–169.CrossRefGoogle Scholar
[24]Schmerl, J.H., On ℵ0-categoricity and the theory of trees, Fundamenta Mathematicae, vol. 94 (1977), pp. 121–128.CrossRefGoogle Scholar
[25]Schmerl, J.H., A decidable ℵ0-categorical theory with a non-recursive Ryll-Nardzewski function, Fundamenta Mathematicae, vol. 98 (1978), pp. 121–125.CrossRefGoogle Scholar
[26]Schmerl, J.H., ℵ0-categoricity of partially ordered sets of width 2, Proceedings of the American Mathematical Society, vol. 63 (1977), pp. 299–305.Google Scholar
[27]Svenonius, L., ℵ0-categoricity in first-order predicate calculus, Theoria (Lund), vol. 25 (1959), pp. 82–94.CrossRefGoogle Scholar
[28]Venning, M.C., Type structure of aleph-zero categorical theories, Ph.D. thesis, Cornell University, 1976.Google Scholar