Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputable structures in generic extensions
178
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we investigate connections between structures present in every generic extension of the universe $V$ and computability theory. We introduce the notion of {em generic Muchnik reducibility} that can be used to to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of {em generic presentability}, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making $omega_2$ countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentble by a forcing notion that does not make $omega_2$ countable has a copy in the ground model. We also show that any countable structure $mathcal{A}$ that is generically presentable by a forcing notion not collapsing $omega_1$ has a countable copy in $V$, as does any structure $mathcal{B}$ generically Muchnik reducible to a structure $mathcal{A}$ of cardinality $aleph_1$. The former positive result yields a new proof of Harringtons result that counterexamples to Vaughts conjecture have models of power $aleph_1$ with Scott rank arbitrarily high below $omega_2$. Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.
rate research
Read More
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.
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.
We compare three notions of genericity of separable metric structures. Our analysis provides a general model theoretic technique of showing that structures are generic in descriptive set theoretic (topological) sense and in measure theoretic sense. In particular, it gives a new perspective on Vershiks theorems on genericity and randomness of Urysohns space among separable metric spaces.
We investigate computable metrizability of Polish spaces up to homeomorphism. In this paper we focus on Stone spaces. We use Stone duality to construct the first known example of a computable topological Polish space not homeomorphic to any computably metrized space. In fact, in our proof we construct a right-c.e. metrized Stone space which is not homeomorphic to any computably metrized space. Then we introduce a new notion of effective categoricity for effectively compact spaces and prove that effectively categorical Stone spaces are exactly the duals of computably categorical Boolean algebras. Finally, we prove that, for a Stone space $X$, the Banach space $C(X;mathbb{R})$ has a computable presentation if, and only if, $X$ is homeomorphic to a computably metrized space. This gives an unexpected positive partial answer to a question recently posed by McNicholl.
A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal degrees. One class of particular interest in the study of negligibility is the class of diagonally non-computable (DNC) functions, proven by Kucera to be non-negligible in a strong sense: every Martin-Lof random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-Lof random real. In this paper, we show that such the set of such DNC functions is in fact non-negligible. More precisely, we prove that for every sufficiently fast-growing computable~$h$, every 2-random real computes an $h$-bounded DNC function which computes no Martin-Lof random real. Further, we show that the same holds for the set of reals which compute a DNC function but no bounded DNC function. The proofs of these results use a combination of a technique due to Kautz (which, following a metaphor of Shen, we like to call a `fireworks argument) and bushy tree forcing, which is the canonical forcing notion used in the study of DNC functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
