Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA separation result for countable unions of Borel rectangles
101
0
0.0
(
0
)
Authors
Dominique Lecomte
Ask ChatGPT about the research
No Arabic abstract
We provide dichotomy results characterizing when two disjoint analytic binary relations can be separated by a countable union of ${bfSigma}^0_1 !times! {bfSigma}^0_xi$ sets, or by a ${bfPi}^0_1 !times! {bfPi}^0_xi$ set.
rate research
Read More
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 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$.
We investigate the statement the order topology of every countable complete linear order is compact in the framework of reverse mathematics, and we find that the statements strength depends on the precise formulation of compactness. If we require that open covers must be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{WKL}_0$ over $mathsf{RCA}_0$. If open covers need not be uniformly expressible as unions of basic open sets, then the compactness of complete linear orders is equivalent to $mathsf{ACA}_0$ over $mathsf{RCA}_0$. This answers a question of Franc{c}ois Dorais.
We define a collection of topological Ramsey spaces consisting of equivalence relations on $omega$ with the property that the minimal representatives of the equivalence classes alternate according to a fixed partition of $omega$. To prove the associated pigeonhole principles, we make use of the left-variable Hales-Jewett theorem and its extension to an infinite alphabet. We also show how to transfer the corresponding infinite-dimensional Ramsey results to equivalence relations on countable limit ordinals (up to a necessary restriction on the set of minimal representatives of the equivalence classes) in order to obtain a dual Ramsey theorem for such ordinals.
The distinguishing number of a graph $G$ is the smallest positive integer $r$ such that $G$ has a labeling of its vertices with $r$ labels for which there is no non-trivial automorphism of $G$ preserving these labels. Albertson and Collins computed the distinguishing number for various finite graphs, and Imrich, Klavv{z}ar and Trofimov computed the distinguishing number of some infinite graphs, showing in particular that the Random Graph has distinguishing number 2. We compute the distinguishing number of various other finite and countable homogeneous structures, including undirected and directed graphs, and posets. We show that this number is in most cases two or infinite, and besides a few exceptions conjecture that this is so for all primitive homogeneous countable structures.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
