Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHereditarily rigid relations
118
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An $h$-ary relation $r$ on a finite set $A$ is said to be emph{hereditarily rigid} if the unary partial functions on $A$ that preserve $r$ are the subfunctions of the identity map or of constant maps. A family of relations ${mathcal F}$ is said to be emph{hereditarily strongly rigid} if the partial functions on $A$ that preserve every $r in {mathcal F}$ are the subfunctions of projections or constant functions. In this paper we show that hereditarily rigid relations exist and we give a lower bound on their arities. We also prove that no finite hereditarily strongly rigid families of relations exist and we also construct an infinite hereditarily strongly rigid family of relations.
rate research
Read More
We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over $mathbb Z$ or ${mathbb Z}_m$ and allow an interpretation as counting the number of relations satisfying a property expressible in Monadic Second Order Logic (MSOL). C. Blatter and E. Specker (1981) showed that if such a function $f$ counts the number of binary relations satisfying a property expressible in MSOL then $f$ satisfies for every $m in mathbb{N}$ a linear recurrence relation over $mathbb{Z}_m$. In this paper we give a complete characterization in terms of definability in MSOL of the combinatorial functions which satisfy a linear recurrence relation over $mathbb{Z}$, and discuss various extensions and limitations of the Specker-Blatter theorem.
We establish that if it is consistent that there is a supercompact cardinal, then it is consistent that every locally compact, hereditarily normal space which does not include a perfect pre-image of omega_1 is hereditarily paracompact.
Let $k$ be a field of characteristic zero containing all roots of unity and $K=k((t))$. We build a ring morphism from the Grothendieck group of semi-algebraic sets over $K$ to the Grothendieck group of motives of rigid analytic varieties over $K$. It extend the morphism sending the class of an algebraic variety over $K$ to its cohomological motive with compact support. We show that it fits inside a commutative diagram involving Hrushovski and Kazhdans motivic integration and Ayoubs equivalence between motives of rigid analytic varieties over $K$ and quasi-unipotent motives over $k$ ; we also show that it satisfies a form of duality. This allows us to answer a question by Ayoub, Ivorra and Sebag about the analytic Milnor fiber.
We study the class of analytic binary relations on Polish spaces, compared with the notions of continuous reducibility or injective continuous reducibility. In particular, we characterize when a locally countable Borel relation is $Sigma$ 0 $xi$ (or $Pi$ 0 $xi$), when $xi$ $ge$ 3, by providing a concrete finite antichain basis. We give a similar characterization for arbitrary relations when $xi$ = 1. When $xi$ = 2, we provide a concrete antichain of size continuum made of locally countable Borel relations minimal among non-$Sigma$ 0 2 (or non-$Pi$ 0 2) relations. The proof of this last result allows us to strengthen a result due to Baumgartner in topological Ramsey theory on the space of rational numbers. We prove that positive results hold when $xi$ = 2 in the acyclic case. We give a general positive result in the non-necessarily locally countable case, with another suitable acyclicity assumption. We provide a concrete finite antichain basis for the class of uncountable analytic relations. Finally, we deduce from our positive results some antichain basis for graphs, of small cardinality (most of the time 1 or 2).
In this paper, we use a categorical and functorial set up to model the syntax and inference of logics of algebraic signature, extending previous works on algebraisation of logics. The main feature of this work is that structurality, or invariance under substitution of variables, are modelled by functoriality in this paper, resulting in a much clearer framework for algebraisation. It also provides a very nice conceptual understanding of various existing results already established in the literatures, and derives several new results as well.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
