Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T10:34:21.278Z Has data issue: false hasContentIssue false
  • English
  • Français

THE WADGE ORDER ON THE SCOTT DOMAIN IS NOT A WELL-QUASI-ORDER

Published online by Cambridge University Press:  29 August 2019

JACQUES DUPARC  and
LOUIS VUILLEUMIER
JACQUES DUPARC
Affiliation:
DEPARTMENT OF OPERATIONS (DO) UNIVERSITY OF LAUSANNE (UNIL) QUARTIER UNIL-CHAMBERONNE, BÂTIMENT ANTHROPOLE 1015 LAUSANNE, SWITZERLAND E-mail: [email protected]
LOUIS VUILLEUMIER
Affiliation:
DEPARTMENT OF OPERATIONS (DO) UNIVERSITY OF LAUSANNE (UNIL) QUARTIER UNIL-CHAMBERONNE, BÂTIMENT ANTHROPOLE 1015 LAUSANNE, SWITZERLAND and RESEARCH INSTITUTE ON THE FOUNDATIONS OF COMPUTER SCIENCE (IRIF) PARIS DIDEROT UNIVERSITY (PARIS 7), SORBONNE PARIS CITÉ 8 PLACE AURÉLIE NEMOURS, BÂTIMENT SOPHIE GERMAIN 75205 PARIS CEDEX 13, FRANCE E-mail: [email protected]: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets $\mathbb{P}_{emb} $ equipped with the order induced by homomorphisms is embedded into the Wadge order on the $\Delta _2^0 $-degrees of the Scott domain. We then show that $\mathbb{P}_{emb} $ admits both infinite strictly decreasing chains and infinite antichains with respect to this notion of comparison, which therefore transfers to the Wadge order on the $\Delta _2^0 $-degrees of the Scott domain.

Keywords

03B7003D3003E1554H0568Q15descriptive set theoryquasi-Polish spaceScott domainWadge reducibilitywell-quasi-order
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 1 , March 2020 , pp. 300 - 324
Copyright
Copyright © The Association for Symbolic Logic 2019 

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

Andretta, A., The SLO principle and the Wadge hierarchy, Foundations of the Formal Sciences V (Bold, S., Löwe, B., Räsch, T., and van Benthem, J., editors), Studies in Logic, vol. 11, College Publications, London, 2007, pp. 1–38.Google Scholar
Andretta, A. and Louveau, A., Wadge degrees and pointclasses. Introduction to Part III, Wadge Degrees and Projective Ordinals. The Cabal Seminar. Volume II (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. 3–23.Google Scholar
Becher, V. and Grigorieff, S., Wadge hardness in Scott spaces and its effectivization. Mathematical Structures in Computer Science, vol. 25 (2015), no. 7, pp. 1520–1545.CrossRefGoogle Scholar
De Brecht, M., Quasi-Polish spaces. Annals of Pure and Applied Logic, vol. 164 (2013), no. 3, pp. 356–381.CrossRefGoogle Scholar
Duparc, J., Wadge hierarchy and Veblen hierarchy. I. Borel sets of finite rank, this Journal, vol. 66 (2001), no. 1, pp. 56–86.Google Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., and Scott, D. S., Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications, vol. 93, Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
Goubault-Larrecq, J., Non-Hausdorff Topology and Domain Theory, New Mathematical Monographs, vol. 22, Cambridge University Press, Cambridge, 2013.CrossRefGoogle Scholar
Hodges, W., Model Theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993.CrossRefGoogle Scholar
Ikegami, D., Schlicht, P., and Tanaka, H., Borel subsets of the real line and continuous reducibility. Fundamenta Mathematicae, vol. 244 (2019), no. 3, pp. 209–241.CrossRefGoogle Scholar
Kechris, A. S., Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.CrossRefGoogle Scholar
Kihara, T. and Montalbán, A., On the structure of the Wadge degrees of bqo-valued Borel functions. Transactions of the American Mathematical Society, vol. 371 (2019), no. 11, pp. 7885–7923.CrossRefGoogle Scholar
Lehtonen, E., Labeled posets are universal. European Journal of Combinatorics, vol. 29 (2008), no. 2, pp. 493–506.CrossRefGoogle Scholar
Louveau, A., Some results in the Wadge hierarchy of Borel sets, Wadge Degrees and Projective Ordinals. The Cabal Seminar. Volume II (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. 47–73.Google Scholar
Louveau, A. and Saint-Raymond, J., The strength of Borel Wadge determinacy, Wadge Degrees and Projective Ordinals. The Cabal Seminar. Volume II (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. 74–101.Google Scholar
Motto Ros, L., Schlicht, P., and Selivanov, V. L., Wadge-like reducibilities on arbitrary quasi-Polish spaces. Mathematical Structures in Computer Science, vol. 25 (2015), no. 8, pp. 1705–1754.CrossRefGoogle Scholar
Pequignot, Y., A Wadge hierarchy for second countable spaces. Archive for Mathematical Logic, vol. 54 (2015), no. 5–6, pp. 659–683.CrossRefGoogle Scholar
Schlicht, P., Continuous reducibility and dimension of metric spaces. Archive for Mathematical Logic, vol. 57 (2018), no. 3–4, pp. 329–359.CrossRefGoogle Scholar
Scott, D. S., Data types as lattices. SIAM Journal on Computing, vol. 5 (1976), no. 3, pp. 522–587. Semantics and correctness of programs.CrossRefGoogle Scholar
Selivanov, V. L., Hierarchies in ϕ-spaces and applications. Mathematical Logic Quarterly, vol. 51 (2005), no. 1, pp. 45–61.CrossRefGoogle Scholar
Selivanov, V. L., Towards a descriptive set theory for domain-like structures. Theoretical Computer Science, vol. 365 (2006), no. 3, pp. 258–282.CrossRefGoogle Scholar
Selivanov, V. L., Extending Wadge theory to k-partitions, Unveiling Dynamics and Complexity (Kari, J., Manea, F., and Petre, I., editors), Lecture Notes in Computer Science, vol. 10307, Springer, Cham, 2017, pp. 387–399.CrossRefGoogle Scholar
Selivanov, V. L., Towards a descriptive theory of ${\text{cb}}_0 $-spaces. Mathematical Structures in Computer Science, vol. 27 (2017), no. 8, pp. 1553–1580.CrossRefGoogle Scholar
Van Wesep, R., Wadge degrees and descriptive set theory, Wadge Degrees and Projective Ordinals. The Cabal Seminar. Volume II (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. 24–42.Google Scholar
Wadge, W. W., Reducibility and determinateness on the Baire space, Ph.D. thesis, University of California, Berkeley, 1984.Google Scholar
Wadge, W. W., Early investigations of the degrees of Borel sets, Wadge Degrees and Projective Ordinals. The Cabal Seminar. Volume II (Kechris, A. S., Löwe, B., and Steel, J. R., editors), Lecture Notes in Logic, vol. 37, Association for Symbolic Logic, La Jolla, CA; Cambridge University Press, Cambridge, 2012, pp. 166–195.Google Scholar
Weihrauch, K., Computable Analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000.CrossRefGoogle Scholar
Zhukov, A. V., Some notes on the universality of three-orders on finite labeled posets, Logic, Computation, Hierarchies (Brattka, V., Diener, H., and Spreen, D., editors), Ontos Mathematical Logic, vol. 4, De Gruyter, Berlin, 2014, pp. 393–409.Google Scholar