2024/07/09 by Chen, Ruiyuan, Ziba, Ilir
#03E15 #03G25 #08A40 #08A65 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2407.06719
We study the lattice of all Borel clones on 2 = \0,1\: classes of Borel functions f : 2n → 2, n ≤ ω, which are closed under composition and include all projections. This is a natural extension to countable arities of Post's 1941 classification of all clones of finitary Boolean functions. Every Borel clone restricts to a finitary clone, yielding a "projection" from the lattice of all Borel clones to Post's lattice. It is well-known that each finitary clone of affine mod 2 functions admits a unique extension to a Borel clone. We show that over each finitary clone containing either both \wedge, \vee, or the 2-out-of-3 median operation, there lie at least 2 but only finitely many Borel clones. Over the remaining clones in Post's lattice, we give only a partial classification of the Borel extensions, and present some evidence that the full structure may be quite complicated.