An infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice are found related to directed cycles and finite choice.
Abstract
We can associate a compactness principle $\mathcal K_{\mathcal{D}}$ to the Constraint Satisfaction Problem (CSP) with constraint library $\mathcal{D}$. These principles were studied by Kat\'ay, T\'oth, and Vidny\'anszky and by Rorabaugh, Tardif, and Wehlau. We expand their work comparing the strength of $K_{\mathcal{D}}$ for varying structures $\mathcal{D}$. We characterize the structures whose compactness principles are provable from ZF; these turn out to be the width-1 structures. We compare some important compactness principles, namely those of $2\text{SAT}$, $3\text{LIN}2$, and $K_2$, settling a question of Kat\'ay, T\'oth, and Vidny\'anszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.
We introduce a novel extension of reflection calculus, $\mathsf{RC_{BI}}$, to analyze a family of extensions of $\mathsf{ACA}_0$ generated by uniform $\omega$-model and syntactic reflection principles, together with several other related operators. The union of these theories coincides with the theory of Bar Induction...
We continue the study of compactness phenomena between the set-theoretic universe and $\mathrm{HOD}$ initiated by Goldberg--Poveda \cite{GolPov}. We focus on compactness phenomena around the power-set functions of $V$ and $\mathrm{HOD}$. We prove: (1) A singular strong limit cardinal with uncountable cofinality cannot...
Tom Benhamou, James Cummings, Yair Hayut et al.· 0 citations
We define a class of classes of complete first-order theories, denoted by $\mathfrak{D}_{n\text{-var}}$, using positive consistency-inconsistency configurations and generalized indiscernibles. It contains the classes of stable, simple, NIP, NTP$_1$, NTP$_2$, NATP, NCTP, NBTP, NWP, NGP, and NPM$^{(k)}$ theories. For any...
In this work we investigate a relative notion of protomodularity. We say that a finitely complete category $\mathsf{C}$ satisfies the \defn{$\mathscr{M}$-version of protomodularity} when the change-of-base functors (concerning the fibration of points) are conservative with respect to a class of morphisms $\mathscr{M}$...
We study definability in fixed-point logic with counting (FPC) for a class of constraint satisfaction problems (CSPs) that simultaneously generalises finite-domain CSPs and temporal CSPs. The templates for the CSPs are first-order expansions of the structure $([k] \times {\mathbb Q};<_1,\dots,<_k,\sim)$ where $<_i \, :...
Consider a constraint satisfaction problem $\mathbf{C}$ on finitely many independent random variables with dependency graph $G$. Let $p_a$ be the violation probability of a constraint $a\in \mathbf{C}$ and $N_G^2 (a)$ the set of constraints at distance one or two from $a$ in $G$. Suppose that, there exists $x\in (0,1)^...
Vishesh Jain, Clayton Mizgerd, H. Pham· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
