No Arabic abstract
We study the extension of the Kechris-Solecki-Todorcevic dichotomy on analytic graphs to dimensions higher than 2. We prove that the extension is possible in any dimension, finite or infinite. The original proof works in the case of the finite dimension. We first prove that the natural extension does not work in the case of the infinite dimension, for the notion of continuous homomorphism used in the original theorem. Then we solve the problem in the case of the infinite dimension. Finally, we prove that the natural extension works in the case of the infinite dimension, but for the notion of Baire-measurable homomorphism.
We study the analytic digraphs of uncountable Borel chromatic number on Polish spaces, and compare them with the notion of injective Borel homomorphism. We provide some minimal digraphs incomparable with G 0. We also prove the existence of antichains of size continuum, and that there is no finite basis. 2010 Mathematics Subject Classification. 03E15, 54H05
We develop general machinery to cast the class of potential canonical Scott sentences of an infinitary sentence $Phi$ as a class of structures in a related language. From this, we show that $Phi$ has a Borel complete expansion if and only if $S_infty$ divides $Aut(M)$ for some countable model $Mmodels Phi$. Using this, we prove that for theories $T_h$ asserting that ${E_n}$ is a countable family of cross cutting equivalence relations with $h(n)$ classes, if $h(n)$ is uniformly bounded then $T_h$ is not Borel complete, providing a converse to Theorem~2.1 of cite{LU}.
We prove that, for any natural number n $ge$ 1, we can find a finite alphabet $Sigma$ and a finitary language L over $Sigma$ accepted by a one-counter automaton, such that the $omega$-power L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L} is $Pi$ 0 n-complete. We prove a similar result for the class $Sigma$ 0 n .
In this paper we are interested in finding and evaluating cardinal characteristics of the continuum that appear in large-scale topology, usually as the smallest weights of coarse structures that belong to certain classes (indiscrete, inseparated, large) of finitary or locally finite coarse structures on $omega$. Besides well-known cardinals $mathfrak b,mathfrak d,mathfrak c$ we shall encounter two new cardinals $mathsf Delta$ and $mathsf Sigma$, defined as the smallest weight of a finitary coarse structure on $omega$ which contains no discrete subspaces and no asymptotically separated sets, respectively. We prove that $max{mathfrak b,mathfrak s,mathrm{cov}(mathcal N)}lemathsf Deltalemathsf Sigmalemathrm{non}(mathcal M)$, but we do not know if the cardinals $mathsf Delta,mathsf Sigma,mathrm{non}(mathcal M)$ can be distinguished in suitable models of ZFC.
We give a completely constructive solution to Tarskis circle squaring problem. More generally, we prove a Borel version of an equidecomposition theorem due to Laczkovich. If $k geq 1$ and $A, B subseteq mathbb{R}^k$ are bounded Borel sets with the same positive Lebesgue measure whose boundaries have upper Minkowski dimension less than $k$, then $A$ and $B$ are equidecomposable by translations using Borel pieces. This answers a question of Wagon. Our proof uses ideas from the study of flows in graphs, and a recent result of Gao, Jackson, Krohne, and Seward on special types of witnesses to the hyperfiniteness of free Borel actions of $mathbb{Z}^d$.