Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIndependently Axiomatizable L_{omega_1,omega} Theories
107
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In partial answer to a question posed by Arnie Miller (http://www.math.wisc.edu/~miller/res/problem.pdf) and X. Caicedo, we obtain sufficient conditions for an L_{omega_1,omega} theory to have an independent axiomatization. As a consequence we obtain two corollaries: The first, assuming Vaughts Conjecture, every L_{omega_1,omega} theory in a countable language has an independent axiomatization. The second, this time outright in ZFC, every intersection of a family of Borel sets can be formed as the intersection of a family of independent Borel sets.
rate research
Read More
We use set-theoretic tools to make a model-theoretic contribution. In particular, we construct a emph{single} $mathcal{L}_{omega_1,omega}$-sentence $psi$ that codes Kurepa trees to prove the consistency of the following: (1) The spectrum of $psi$ is consistently equal to $[aleph_0,aleph_{omega_1}]$ and also consistently equal to $[aleph_0,2^{aleph_1})$, where $2^{aleph_1}$ is weakly inaccessible. (2) The amalgamation spectrum of $psi$ is consistently equal to $[aleph_1,aleph_{omega_1}]$ and $[aleph_1,2^{aleph_1})$, where again $2^{aleph_1}$ is weakly inaccessible. This is the first example of an $mathcal{L}_{omega_1,omega}$-sentence whose spectrum and amalgamation spectrum are consistently both right-open and right-closed. It also provides a positive answer to a question in [18]. (3) Consistently, $psi$ has maximal models in finite, countable, and uncountable many cardinalities. This complements the examples given in [1] and [2] of sentences with maximal models in countably many cardinalities. (4) $2^{aleph_0}<aleph_{omega_1}<2^{aleph_1}$ and there exists an $mathcal{L}_{omega_1,omega}$-sentence with models in $aleph_{omega_1}$, but no models in $2^{aleph_1}$. This relates to a conjecture by Shelah that if $aleph_{omega_1}<2^{aleph_0}$, then any $mathcal{L}_{omega_1,omega}$-sentence with a model of size $aleph_{omega_1}$ also has a model of size $2^{aleph_0}$. Our result proves that $2^{aleph_0}$ can not be replaced by $2^{aleph_1}$, even if $2^{aleph_0}<aleph_{omega_1}$.
Fix 2<n<omega. Let L_n denote first order logic restricted to the first n variables. CA_n denotes the class of cylindric algebras of dimension n and for m>n, Nr_nCA_m(subseteq CA_n) denotes the class of n-neat reducts of CA_ms. The existence of certain finite relation algebras and finite CA_ns lacking relativized complete representations is shown to imply that the omitting types theorem (OTT) fails for L_n with respect to clique guarded semantics (which is an equivalent formalism of its packed fragments), and for the multi-dimensional modal logic S5^n. Several such relation and cylindric algebras are explicitly exhibited using rainbow constructions and Monk-like algebras. Certain CA_n constructed to show non-atom canonicity of the variety SNr_nCA_{n+3} are used to show that Vaughts theorem (VT) for L_{omega, omega}, looked upon as a special case of OTT for L_{omega, omega}, fails almost everywhere (a notion to be defined below) when restricted to L_n. That VT fails everywhere for L_n, which is stronger than failing almost everywhere as the name suggests, is reduced to the existence, for each n<m<omega, of a finite relation algebra R_m having a so-called m-1 strong blur, but R_m has no m-dimensional relational basis. VT for other modal fragments and expansions of L_n, like its guarded fragments, n-products of uni-modal logics like K^n, and first order definable expansions, is approached. It is shown that any multi-modal canonical logic L, such that $K^nsubseteq Lsubseteq S5^n$, L cannot be axiomatized by canonical equations. In particular, L is not Sahlqvist. Elementary generation and di-completeness for L_n and its clique guarded fragments are proved. Positive omitting types theorems are proved for L_n with respect to standard semantics.
We obtain a computable structure of Scott rank omega_1^{CK} (call this ock), and give a general coding procedure that transforms any hyperarithmetical structure A into a computable structure A such that the rank of A is ock, ock+1, or < ock iff the same is true of A.
We study the computational complexity of deciding whether a given set of term equalities and inequalities has a solution in an $omega$-categorical algebra $mathfrak{A}$. There are $omega$-categorical groups where this problem is undecidable. We show that if $mathfrak{A}$ is an $omega$-categorical semilattice or an abelian group, then the problem is in P or NP-hard. The hard cases are precisely those where Pol$(mathfrak{A}, eq)$ has a uniformly continuous minor-preserving map to the clone of projections on a two-element set. The results provide information about algebras $mathfrak{A}$ such that Pol$(mathfrak{A}, eq)$ does not satisfy this condition, and they are of independent interest in universal algebra. In our proofs we rely on the Barto-Pinsker theorem about the existence of pseudo-Siggers polymorphisms. To the best of our knowledge, this is the first time that the pseudo-Siggers identity has been used to prove a complexity dichotomy.
We prove that $omega$-regular languages accepted by Buchi or Muller automata satisfy an effective automata-theoretic version of the Baire property. Then we use this result to obtain a new effective property of rational functions over infinite words which are realized by finite state Buchi transducers: for each such function $F: Sigma^omega rightarrow Gamma^omega$, one can construct a deterministic Buchi automaton $mathcal{A}$ accepting a dense ${bf Pi}^0_2$-subset of $Sigma^omega$ such that the restriction of $F$ to $L(mathcal{A})$ is continuous.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
