Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Virtual Large Cardinal Hierarchy
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We continue the study of the virtual large cardinal hierarchy, initiated in Gitman and Schindler (2018), by analysing virtu
rate research
Read More
In [5], Hjorth proved that for every countable ordinal $alpha$, there exists a complete $mathcal{L}_{omega_1,omega}$-sentence $phi_alpha$ that has models of all cardinalities less than or equal to $aleph_alpha$, but no models of cardinality $aleph_{alpha+1}$. Unfortunately, his solution does not yield a single $mathcal{L}_{omega_1,omega}$-sentence $phi_alpha$, but a set of $mathcal{L}_{omega_1,omega}$-sentences, one of which is guaranteed to work. It was conjectured in [9] that it is independent of the axioms of ZFC which of these sentences has the desired property. In the present paper, we prove that this conjecture is true. More specifically, we isolate a diagonalization principle for functions from $omega_1$ to $omega_1$ which is a consequence of the Bounded Proper Forcing Axiom (BPFA) and then we use this principle to prove that Hjorths solution to characterizing $aleph_2$ in models of BPFA is different than in models of CH. In addition, we show that large cardinals are not needed to obtain this independence result by proving that our diagonalization principle can be forced over models of CH.
A function f from reals to reals (f:R->R) is almost continuous (in the sense of Stallings) iff every open set in the plane which contains the graph of f contains the graph of a continuous function. Natkaniec showed that for any family F of continuum many real functions there exists g:R->R such that f+g is almost continuous for every f in F. Let AA be the smallest cardinality of a family F of real functions for which there is no g:R->R with the property that f+g is almost continuous for every f in F. Thus Natkaniec showed that AA is strictly greater than the continuum. He asked if anything more could be said. We show that the cofinality of AA is greater than the continuum, c. Moreover, we show that it is pretty much all that can be said about AA in ZFC, by showing that AA can be equal to any regular cardinal between c^+ and 2^c (with 2^c arbitrarily large). We also show that AA = AD where AD is defined similarly to AA but for the class of Darboux functions. This solves another problem of Maliszewski and Natkaniec.
Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility $leq_c$. This gives rise to a rich degree-structure. In this paper, we lift the study of $c$-degrees to the $Delta^0_2$ case. In doing so, we rely on the Ershov hierarchy. For any notation $a$ for a non-zero computable ordinal, we prove several algebraic properties of the degree-structure induced by $leq_c$ on the $Sigma^{-1}_{a}smallsetminus Pi^{-1}_a$ equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of $c$-degrees.
A numbering of a countable family $S$ is a surjective map from the set of natural numbers $omega$ onto $S$. A numbering $ u$ is reducible to a numbering $mu$ if there is an effective procedure which given a $ u$-index of an object from $S$, computes a $mu$-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. The paper studies Rogers semilattices for families $S subset P(omega)$ belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers $m eq n$, any non-trivial Rogers semilattice of a $Pi^1_m$-computable family cannot be isomorphic to a Rogers semilattice of a $Pi^1_n$-computable family. One of the key ingredients of the proof is an application of the result by Downey and Knight on degree spectra of linear orders.
Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies $Delta^0_2$ sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice $L$ (e.g., the real interval $[0; 1]_mathbb{R}$). In this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. In particular, we focus on the fuzzy $n$-c.e. sets which form the finite levels of this hierarchy. Intuitively, a fuzzy set is $n$-c.e. if its membership function can be approximated by changing monotonicity at most $n-1$ times. We prove that the Fuzzy Ershov Hierarchy does not collapse; that, in analogy with the classical case, each fuzzy $n$-c.e. set can be represented as a Boolean combination of fuzzy c.e. sets; but that, contrary to the classical case, the Fuzzy Ershov Hierarchy does not exhaust the class of all $Delta^0_2$ fuzzy sets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
