Skip to Main content Skip to Navigation
Journal articles

Choice functions and well-orderings over the infinite binary tree

Abstract : We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded order on the infinite binary tree by showing that every infinite binary tree with a well-founded order has an undecidable MSO-theory.
Document type :
Journal articles
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00733452
Contributor : Arnaud Carayol <>
Submitted on : Tuesday, March 5, 2013 - 10:54:34 PM
Last modification on : Monday, June 8, 2020 - 9:48:02 AM
Long-term archiving on: : Thursday, June 6, 2013 - 3:55:39 AM

File

CEJM-CLNW10.pdf
Files produced by the author(s)

Identifiers

Citation

Arnaud Carayol, Christof Loeding, Damian Niwinski, Igor Walukiewicz. Choice functions and well-orderings over the infinite binary tree. Central European Journal of Mathematics, Springer Verlag, 2010, 8 (6), pp.662-682. ⟨10.2478/s11533-010-0046-z⟩. ⟨hal-00733452⟩

Share

Metrics

Record views

902

Files downloads

398