### Some natural zero one laws for ordinals below ε0

(2012) Lecture Notes in Computer Science. 7318. p.723-732- 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 ω^ω .

Please use this url to cite or link to this publication:
http://hdl.handle.net/1854/LU-2140893

- author
- Andreas Weiermann UGent and Alan R Woods
- organization
- alternative title
- Some natural zero one laws for ordinals below epsilon 0
- year
- 2012
- type
- conference
- publication status
- published
- subject
- keyword
- proof-theoretic ordinal, zero one law, random tree, limit law, random ordinal
- in
- Lecture Notes in Computer Science
- Lect. Notes Comput. Sci.
- editor
- S Barry Cooper, Anuj Dawar and Benedikt Löwe
- volume
- 7318
- issue title
- How the world computes
- pages
- 723 - 732
- publisher
- Springer
- place of publication
- Berlin, Germany
- conference name
- Turing Centenary Conference ; 8th Conference on Computability in Europe (CiE 2012)
- conference location
- Cambridge, UK
- conference start
- 2012-06-18
- conference end
- 2012-12-23
- Web of Science type
- Conference Paper
- Web of Science id
- 12789195
- ISSN
- 0302-9743
- ISBN
- 9783642308703
- 9783642308697
- DOI
- 10.1007/978-3-642-30870-3_73
- project
- PTLC
- language
- English
- UGent publication?
- yes
- classification
- C1
- copyright statement
*I have transferred the copyright for this publication to the publisher*- VABB id
- c:vabb:339812
- VABB type
- VABB-5
- id
- 2140893
- handle
- http://hdl.handle.net/1854/LU-2140893
- date created
- 2012-06-12 16:07:07
- date last changed
- 2012-08-07 13:23:50

@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 = {9783642308703}, issn = {0302-9743}, keyword = {proof-theoretic ordinal,zero one law,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}, }

- 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.