Rabinovich, Alexander
On Uniformization in the Full Binary Tree
Abstract
A function f uniformizes a relation R(X,Y) if R(X,f(X)) holds for every X in the domain of R. The uniformization problem for a logic L asks whether for every Ldefinable relation there is an Ldefinable function that uniformizes it. Gurevich and Shelah proved that no Monadic SecondOrder (MSO) definable function uniformizes relation "Y is a one element subset of X" in the full binary tree. In other words, there is no MSO definable choice function in the full binary tree.
The crosssection of a relation R(X,Y) at D is the set of all E such that R(D,E) holds. Hence, a function that uniformizes R chooses one element from every nonempty crosssection. The relation "Y is a one element subset of X" has finite and countable crosssections.
We prove that in the full binary tree the following theorems hold:
▶ Theorem (Finite crosssections) If every crosssection of an MSO definable relation is finite, then it has an MSO definable uniformizer.
▶ Theorem (Uncountable crosssection) There is an MSO definable relation R such that every MSO definable relation included in R and with the same domain as R has an uncountable crosssection.
BibTeX  Entry
@InProceedings{rabinovich:LIPIcs.MFCS.2022.77,
author = {Rabinovich, Alexander},
title = {{On Uniformization in the Full Binary Tree}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {77:177:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16875},
URN = {urn:nbn:de:0030drops168757},
doi = {10.4230/LIPIcs.MFCS.2022.77},
annote = {Keywords: Monadic SecondOrder Logic, Uniformization}
}
22.08.2022
Keywords: 

Monadic SecondOrder Logic, Uniformization 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 