Advanced search
1 file | 318.65 KB

Some natural zero one laws for ordinals below ε0

Author
Organization
Project
PTLC
Abstract
We are going to prove that every ordinal α with ε_0 > α ≥ ω^ω satisfies a natural zero one law in the following sense. For α < ε_0 let Nα be the number of occurences of ω in the Cantor normal form of α. (Nα is then the number of edges in the unordered tree which can canonically be associated with α.) We prove that for any α with ω ω  ≤ α < ε_0 and any sentence ϕ in the language of linear orders the asymptotic density of ϕ along α is an element of  {0,1}. We further show that for any such sentence ϕ the asymptotic density along ε_0 exists although this limit is in general in between 0 and 1. We also investigate corresponding asymptotic densities for ordinals below ω^ω .
Keywords
zero one law, proof-theoretic ordinal, random tree, limit law, random ordinal

Downloads

  • CiE2012WeiermannWoods.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 318.65 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Weiermann, Andreas, and Alan R Woods. 2012. “Some Natural Zero One Laws for Ordinals Below Ε0.” In Lecture Notes in Computer Science, ed. S Barry Cooper, Anuj Dawar, and Benedikt Löwe, 7318:723–732. Berlin, Germany: Springer.
APA
Weiermann, A., & Woods, A. R. (2012). Some natural zero one laws for ordinals below ε0. In S. B. Cooper, A. Dawar, & B. Löwe (Eds.), Lecture Notes in Computer Science (Vol. 7318, pp. 723–732). Presented at the Turing Centenary Conference ; 8th Conference on Computability in Europe (CiE 2012), Berlin, Germany: Springer.
Vancouver
1.
Weiermann A, Woods AR. Some natural zero one laws for ordinals below ε0. In: Cooper SB, Dawar A, Löwe B, editors. Lecture Notes in Computer Science. Berlin, Germany: Springer; 2012. p. 723–32.
MLA
Weiermann, Andreas, and Alan R Woods. “Some Natural Zero One Laws for Ordinals Below Ε0.” Lecture Notes in Computer Science. Ed. S Barry Cooper, Anuj Dawar, & Benedikt Löwe. Vol. 7318. Berlin, Germany: Springer, 2012. 723–732. Print.
@inproceedings{2140893,
  abstract     = {We are going to prove that every ordinal \ensuremath{\alpha} with \ensuremath{\epsilon}\_0\,{\textrangle}\,\ensuremath{\alpha}\,\ensuremath{\geq}\,\ensuremath{\omega}\^{ }\ensuremath{\omega} satisfies a natural zero one law in the following sense. For \ensuremath{\alpha}\,{\textlangle}\,\ensuremath{\epsilon}\_0 let N\ensuremath{\alpha} be the number of occurences of \ensuremath{\omega} in the Cantor normal form of \ensuremath{\alpha}. (N\ensuremath{\alpha} is then the number of edges in the unordered tree which can canonically be associated with \ensuremath{\alpha}.) We prove that for any \ensuremath{\alpha} with \ensuremath{\omega} \ensuremath{\omega} \,\ensuremath{\leq}\,\ensuremath{\alpha}\,{\textlangle}\,\ensuremath{\epsilon}\_0 and any sentence \unmatched{03d5} in the language of linear orders the asymptotic density of \unmatched{03d5} along \ensuremath{\alpha} is an element of \,\{0,1\}. We further show that for any such sentence \unmatched{03d5} the asymptotic density along \ensuremath{\epsilon}\_0 exists although this limit is in general in between 0 and 1. We also investigate corresponding asymptotic densities for ordinals below \ensuremath{\omega}\^{ }\ensuremath{\omega} .},
  author       = {Weiermann, Andreas and Woods, Alan R},
  booktitle    = {Lecture Notes in Computer Science},
  editor       = {Cooper, S Barry  and Dawar, Anuj and L{\"o}we, Benedikt},
  isbn         = {9783642308697},
  issn         = {0302-9743},
  keyword      = {zero one law,proof-theoretic ordinal,random tree,limit law,random ordinal},
  language     = {eng},
  location     = {Cambridge, UK},
  pages        = {723--732},
  publisher    = {Springer},
  title        = {Some natural zero one laws for ordinals below \ensuremath{\epsilon}0},
  url          = {http://dx.doi.org/10.1007/978-3-642-30870-3\_73},
  volume       = {7318},
  year         = {2012},
}

Altmetric
View in Altmetric
Web of Science
Times cited: