Ghent University Academic Bibliography

Advanced

Some natural zero one laws for ordinals below ε0

Andreas Weiermann UGent and Alan R Woods (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:
author
organization
alternative title
Some natural zero one laws for ordinals below epsilon 0
year
type
conference
publication status
published
subject
keyword
zero one law, proof-theoretic ordinal, 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
9783642308697
9783642308703
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
2015-06-17 10:05:07
@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},
}

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.