Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn undecidable extension of Morleys theorem on the number of countable models
182
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Sahlqvist formulas are a syntactically specified class of modal formulas proposed by Hendrik Sahlqvist in 1975. They are important because of their first-order definability and canonicity, and hence axiomatize complete modal logics. The first-order properties definable by Sahlqvist formulas were syntactically characterized by Marcus Kracht in 1993. The present paper extends Krachts theorem to the class of `generalized Sahlqvist formulas introduced by Goranko and Vakarelov and describes an appropriate generalization of Kracht formulas.
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.
All known structural extensions of the substructural logic $mathsf{FL_e}$, Full Lambek calculus with exchange/commutativity, (corresponding to subvarieties of commutative residuated lattices axiomatized by ${vee, cdot, 1}$-equations) have decidable theoremhood; in particular all the ones defined by knotted axioms enjoy strong decidability properties (such as the finite embeddability property). We provide infinitely many such extensions that have undecidable theoremhood, by encoding machines with undecidable halting problem. An even bigger class of extensions is shown to have undecidable deducibility problem (the corresponding varieties of residuated lattices have undecidable word problem); actually with very few exceptions, such as the knotted axioms and the other prespinal axioms, we prove that undecidability is ubiquitous. Known undecidability results for non-commutative extensions use an encoding that fails in the presence of commutativity, so and-branching counter machines are employed. Even these machines provide encodings that fail to capture proper extensions of commutativity, therefore we introduce a new variant that works on an exponential scale. The correctness of the encoding is established by employing the theory of residuated frames.
In this paper, we will give an extension of Moks theorem on the generalized Frankel conjecture under the condition of the orthogonal bisectional curvature.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
