Some natural zero one laws for ordinals below ε0
 Author
 Andreas Weiermann (UGent) and Alan R Woods
 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, prooftheoretic ordinal, random tree, limit law, random ordinal
Downloads

CiE2012WeiermannWoods.pdf
 full text
 
 open access
 
 
 318.65 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU2140893
 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 = {03029743}, keyword = {zero one law,prooftheoretic ordinal,random tree,limit law,random ordinal}, language = {eng}, location = {Cambridge, UK}, pages = {723732}, publisher = {Springer}, title = {Some natural zero one laws for ordinals below \ensuremath{\epsilon}0}, url = {http://dx.doi.org/10.1007/9783642308703\_73}, volume = {7318}, year = {2012}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: