Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistinguishing Number of Countable Homogeneous Relational Structures
332
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The general theory developed by Ben Yaacov for metric structures provides Fraisse limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.
We show that Morleys theorem on the number of countable models of a countable first-order theory becomes an undecidable statement when extended to second-order logic. More generally, we calculate the number of equivalence classes of $sigma$-projective equivalence relations in several models of set theory. Our methods include random and Cohen forcing, Woodin cardinals and Inner Model Theory.
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.
Let $mathrm{G}$ be a subgroup of the symmetric group $mathfrak S(U)$ of all permutations of a countable set $U$. Let $overline{mathrm{G}}$ be the topological closure of $mathrm{G}$ in the function topology on $U^U$. We initiate the study of the poset $overline{mathrm{G}}[U]:={f[U]mid fin overline{mathrm{G}}}$ of images of the functions in $overline{mathrm{G}}$, being ordered under inclusion. This set $overline{mathrm{G}}[U]$ of subsets of the set $U$ will be called the emph{poset of copies for} the group $mathrm{G}$. A denomination being justified by the fact that for every subgroup $mathrm{G}$ of the symmetric group $mathfrak S(U)$ there exists a homogeneous relational structure $R$ on $U$ such that $overline G$ is the set of embeddings of the homogeneous structure $R$ into itself and $overline{mathrm{G}}[U]$ is the set of copies of $R$ in $R$ and that the set of bijections $overline Gcap mathfrak S(U)$ of $U$ to $U$ forms the group of automorphisms of $mathrm{R}$.
The Hanf number for a set $S$ of sentences in $L_{omega_1,omega}$ (or some other logic) is the least infinite cardinal $kappa$ such that for all $varphiin S$, if $varphi$ has models in all infinite cardinalities less than $kappa$, then it has models of all infinite cardinalities. S-D. Friedman asked what is the Hanf number for Scott sentences of computable structures. We show that the value is $beth_{omega_1^{CK}}$. The same argument proves that $beth_{omega_1^{CK}}$ is the Hanf number for Scott sentences of hyperarithmetical structures.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
