Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-01-23T11:32:35.509Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Equimorphism Types of Linear Orderings

Published online by Cambridge University Press:  15 January 2014

Antonio Montalbán
Antonio Montalbán*
Affiliation:
Department of Mathematics, University of Chicago, Chicago, IL, USAE-mail: antonio@math.uchicago.eduURL: www.math.uchicago.edu/~antonio
Get access Rights & Permissions [Opens in a new window]

Extract

§1. Introduction. A linear ordering (also known as total ordering) embeds into another linear ordering if it is isomorphic to a subset of it. Two linear orderings are said to be equimorphic if they can be embedded in each other. This is an equivalence relation, and we call the equivalence classes equimorphism types. We analyze the structure of equimorphism types of linear orderings, which is partially ordered by the embeddability relation. Our analysis is mainly fromthe viewpoints of Computability Theory and Reverse Mathematics. But we also obtain results, as the definition of equimorphism invariants for linear orderings, which provide a better understanding of the shape of this structure in general.

This study of linear orderings started by analyzing the proof-theoretic strength of a theorem due to Jullien [Jul69]. As is often the case in Reverse Mathematics, to solve this problem it was necessary to develop a deeper understanding of the objects involved. This led to a variety of results on the structure of linear orderings and the embeddability relation on them. These results can be divided into three groups.

Type
Communications
Information
Bulletin of Symbolic Logic , Volume 13 , Issue 1 , March 2007 , pp. 71 - 99
Copyright
Copyright © Association for Symbolic Logic 2007

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

[Ash86] Ash, C. J., Stability of recursive structures in arithmetical degrees, Annals of Pure and Applied Logic, vol. 32 (1986), no. 2, pp. 113–135.Google Scholar
[AK00] Ash, C. J. and Knight, J., Computable structures and the hyperarithmetical hierarchy, Elsevier Science, 2000.Google Scholar
[BS75] Barwise, Jon and Schlipf, John, On recursively saturated models of arithmetic, Model theory and algebra (A memorial tribute to Abraham Robinson), Lecture Notes in Mathematics, vol. 498, Springer, Berlin, 1975, pp. 42–55.CrossRefGoogle Scholar
[Bau73] Baumgartner, James E., All ℵ1-dense sets of reals can be isomorphic, Fundamenta Mathematicae, vol. 79 (1973), no. 2, pp. 101–106.Google Scholar
[BP82] Bonnet, R. and Pouzet, M., Linear extensions of ordered sets, Ordered sets (Banff, Alta., 1981), NATO Advanced Study Institute. Series C: Mathematical and Physical Sciences, vol. 83, Reidel, Dordrecht, 1982, pp. 125–170.Google Scholar
[BP69] Bonnet, Robert and Pouzet, Maurice, Extension et stratification d'ensembles dispersés, Comptes Rendus Mathématique. Académie des Sciences. Paris Séries A–B, vol. 268 (1969), pp. A1512–A1515.Google Scholar
[CJS01] Cholak, Peter A., Jockusch, Carl G., and Slaman, Theodore A., Onthe strength of Ramsey's theorem for pairs, The Journal of Symbolic Logic, vol. 66 (2001), no. 1, pp. 1–55.Google Scholar
[Clo90] Clote, P., The metamathematics of Fraïssé's order type conjecture, Recursion theory week (Oberwolfach, 1989), Lecture Notes in Mathematics, vol. 1432, Springer, Berlin, 1990, pp. 41–56.Google Scholar
[dJP77] de Jongh, D. H. J. and Parikh, Rohit, Well-partial orderings and hierarchies, Indagationes Mathematicae, vol. 39 (1977), no. 3, pp. 195–207.Google Scholar
[Dow98] Downey, R.G., Computability theory and linear orderings, Handbook of recursive mathematics, vol. 2, Studies in Logic and the Foundations of Mathematics, vol. 139, North-Holland, Amsterdam, 1998, pp. 823–976.Google Scholar
[DR00] Downey, Rod and Remmel, J. B., Questions in computable algebra and combinatorics, Computability theory and its applications (Boulder, CO, 1999), Contemporary Mathematics, vol. 257, American Mathematical Society, Providence, RI, 2000, pp. 95–125.Google Scholar
[DHLS03] Downey, Rodney G., Hirschfeldt, Denis R., Lempp, Steffen, and Solomon, Reed, Computability-theoretic and proof-theoretic aspects of partial and linear orderings, Israel Journal of Mathematics, vol. 138 (2003), pp. 271–352.CrossRefGoogle Scholar
[EH63] Erdös, P. and Hajnal, A., On a classification of denumerable order types and an application to the partition calculus, Fundamenta Mathematicae, vol. 51 (1962/1963), pp. 117–129.CrossRefGoogle Scholar
[Fei67] Feiner, Lawrence, Orderings and Boolean algebras not isomorphic to recursive ones, Ph.D. thesis, MIT, Cambridge, MA, 1967.Google Scholar
[Fei70] Feiner, Lawrence, Hierarchies of Boolean algebras, The Journal of Symbolic Logic, vol. 35 (1970), pp. 365–374.Google Scholar
[Fra48] Fraïssé, Roland, Sur la comparaison des types d'ordres, Comptes Rendus Mathématique. Académie des Sciences. Paris, vol. 226 (1948), pp. 1330–1331.Google Scholar
[Fra00] Fraïssé, Roland, Theory of relations, revised ed., North Holland, 2000.Google Scholar
[Fri67] Friedman, Harvey, Subsystems of set theory and analysis, Ph.D. thesis, Massachusetts Institute of Technology, 1967.Google Scholar
[Fri75] Friedman, Harvey, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), vol. 1, Canadian Mathematics Congress, Montreal, Quebec, 1975, pp. 235–242.Google Scholar
[GM] Greenberg, Noam and Montalbán, Antonio, Ranked structures and arithmetic transfinite recursion, submitted for publication.Google Scholar
[Har68] Harrison, J., Recursive pseudo-well-orderings, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
[Hau08] Hausdorff, F., Grundzüge einer Theorie der Geordnete Mengen, Mathematische Annalen, vol. 65 (1908), pp. 435–505.Google Scholar
[JS91] Jockusch, Carl G. Jr., and Soare, Robert I., Degrees of orderings not isomorphic to recursive linear orderings, Annals of Pure and Applied Logic, vol. 52 (1991), no. 1–2, pp. 39–64, International Symposium on Mathematical Logic and its Applications (Nagoya, 1988).Google Scholar
[Jul69] Jullien, Pierre, Contribution à l'étude des types d'ordre dispersés, Ph.D. thesis, Marseille, 1969.Google Scholar
[Kle55] Kleene, S. C., Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.Google Scholar
[Kle59] Kleene, S. C., Quantification of number-theoretic functions, Compositio Mathematica, vol. 14 (1959), pp. 23–40.Google Scholar
[Kre62] Kreisel, G., The axiom of choice and the class of hyperarithmetic functions, Indagationes Mathematicae, vol. 24 (1962), pp. 307–319.Google Scholar
[Kru60] Kruskal, J. B., Well-quasi-ordering, the Tree Theorem, and Vazsonyi's conjecture, Transactions of the American Mathematical Society, vol. 95 (1960), pp. 210–225.Google Scholar
[Kun80] Kunen, Kenneth, Set theory, an introduction to independence proofs, Studies in Logic and the Foundations of Mathematics, vol. 102, North-Holland Publishing Company, Amsterdam, New York, Oxford, 1980.Google Scholar
[Lav71] Laver, Richard, On Fräissé's order type conjecture, Annals of Mathematics. Second Series, vol. 93 (1971), pp. 89–111.CrossRefGoogle Scholar
[Lav73] Laver, Richard, An order type decomposition theorem, Annals of Mathematics. Second Series, vol. 98 (1973), pp. 96–119.CrossRefGoogle Scholar
[Ler81] Lerman, Manuel, On recursive linear orderings, Logic Year 1979–80 (Proceedings of the Seminars and Conference on Mathematical Logic, University of Connecticut, Storrs, Connecticut, 1979/80), Lecture Notes in Mathematics, vol. 859, Springer, Berlin, 1981, pp. 132–142.CrossRefGoogle Scholar
[Mar05] Marcone, Alberto, Wqo and bqo theory in subsystems of second order arithmetic, Reverse mathematics 2001, Lecture Notes in Logic, Association for Symbolic Logic, 2005.Google Scholar
[Mil04] Mileti, Joseph R., Partition theorems and computability theory, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2004.Google Scholar
[Mon05a] Montalbán, Antonio, Beyond the arithmetic, Ph.D. thesis, Cornell University, Ithaca, New York, 2005.Google Scholar
[Mon05b] Montalbán, Antonio, Up to equimorphism, hyperarithmetic is recursive, The Journal of Symbolic Logic, vol. 70 (2005), no. 2, pp. 360–378.Google Scholar
[Mon06] Montalbán, Antonio, Equivalence between Fraïssé's conjecture and Jullien's theorem, Annals of Pure and Applied Logic, (2006), to appear.Google Scholar
[Mona] Montalbán, Antonio, Computable linearizations of well-partial-orderings, in preparation.Google Scholar
[Monb] Montalbán, Antonio, Equimorphism invariants for scattered linear orderings, Submitted for publication.Google Scholar
[Monc] Montalbán, Antonio, Indecomposable linear orderings and hyperarithmetic analysis, Submitted for publication.Google Scholar
[Mooa] Moore, Justin T., ω1 and ω* 1 may be the only minimal uncountable order types, in preparation.Google Scholar
[Moob] Moore, Justin T., On linear orders which do not contain real of Aronszajn suborders, in preparation.Google Scholar
[NW68] Nash-Williams, C. St. J. A., On better-quasi-ordering transfinite sequences, Proceedings of the Cambridge Philosophical Society, vol. 64 (1968), pp. 273–290.Google Scholar
[RW93] Rathjen, Michael and Weiermann, Andreas, Proof-theoretic investigations on Kruskal's theorem, Annals of Pure and Applied Logic, vol. 60 (1993), no. 1, pp. 49–88.CrossRefGoogle Scholar
[Ros82] Rosenstein, Joseph G., Linear orderings, Academic Press, New York, London, 1982.Google Scholar
[Ros84] Rosenstein, Joseph G., Recursive linear orderings, Orders: description and roles (l'Arbresle, 1982), North-Holland Mathetics Studies, vol. 99, North-Holland, Amsterdam, 1984, pp. 465–475.Google Scholar
[Sac90] Sacks, Gerald E., Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990.CrossRefGoogle Scholar
[Sho93] Shore, Richard A., On the strength of Fraïssé's conjecture, Logical methods (Ithaca, NY, 1992), Progress in Computer Science and Applied Logic, vol. 12, Birkhäuser Boston, Boston, MA, 1993, pp. 782–813.Google Scholar
[Sho06] Shore, Richard A., Invariants, Boolean algebras and ACA+ , Transactions of the American Mathematical Society, vol. 358 (2006), pp. 989–1014.CrossRefGoogle Scholar
[Sim85] Simpson, Stephen G., Nonprovability of certain combinatorial properties of finite trees, Harvey Friedman's research on the foundations of mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, North-Holland, Amsterdam, 1985, pp. 87–117.Google Scholar
[Sim99] Simpson, Stephen G., Subsystems of second order arithmetic, Springer, 1999.Google Scholar
[Soa87] Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, A study of computable functions and computably generated sets.Google Scholar
[Spe55] Spector, Clifford, Recursive well-orderings, The Journal of Symbolic Logic, vol. 20 (1955), pp. 151–163.CrossRefGoogle Scholar
[Ste78] Steel, John R., Forcing with tagged trees, Annals of Mathematical Logic, vol. 15 (1978), no. 1, pp. 55–74.CrossRefGoogle Scholar
[Szp30] Szpilrajn, Edward, Sur l'extension de l'ordre partiel, Fundamenta Mathematicae, vol. 16 (1930), pp. 386–389.CrossRefGoogle Scholar
[Van77] VanWesep, Robert Alan, Subsystems of second-order arithmetic, and descriptive set theory under the axiom of determinateness, Ph.D. thesis, University of California, Berkeley, 1977.Google Scholar
[Yu] Yu, Liang, Some notes on ranked structures, Unpublished notes.Google Scholar