Mostrando recursos 1 - 20 de 11.498

  1. Cardinal invariants and the collapse of the continuum by Sacks forcing

    Repický, Miroslav
    We study cardinal invariants of systems of meager hereditary families of subsets of ω connected with the collapse of the continuum by Sacks forcing ?? and we obtain a cardinal invariant ??ω such that ?? collapses the continuum to ??ω and ??≤??ω≤??. Applying the Baumgartner-Dordal theorem on preservation of eventually narrow sequences we obtain the consistency of ??=??ω*0 and ≼*1 on the set (ωω)Fin of finite-to-one functions which are Tukey equivalent to the eventual dominance relation of functions such that if ℱ⊆(ωω)Fin is ≼*1-unbounded, well-ordered by ≼*1, and not ≼*0-dominating, then there is a nonmeager p-ideal. The existence of such a system ℱ...

  2. Transfer and a supremum principle for ERNA

    Impens, Chris; Sanders, Sam
    Elementary Recursive Nonstandard Analysis, in short ERNA, is a constructive system of nonstandard analysis proposed around 1995 by Patrick Suppes and Richard Sommer, who also proved its consistency inside PRA. It is based on an earlier system developed by Rolando Chuaqui and Patrick Suppes, of which Michal Rössler and Emil Jeřábek have recently proposed a weakened version. We add a Π1-transfer principle to ERNA and prove the consistency of the extended theory inside PRA. In this extension of ERNA a Σ1-supremum principle ‘up-to-infinitesimals’, and some well-known calculus results for sequences are deduced. Finally, we prove that transfer is ‘too strong’ for finitism by reconsidering Rössler...

  3. The PCF conjecture and large cardinals

    Pereira, Luís
    We prove that a combinatorial consequence of the negation of the PCF conjecture for intervals, involving free subsets relative to set mappings, is not implied by even the strongest known large cardinal axiom.

  4. Generic complexity of undecidable problems

    Myasnikov, Alexei G.; Rybalov, Alexander N.
    In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic...

  5. How enumeration reducibility yields extended Harrington non-splitting

    Soskova, Mariya I.; Cooper, S. Barry

  6. Changing the heights of automorphism towers by forcing with Souslin trees over L

    Fuchs, Gunter; Hamkins, Joel David
    We prove that there are groups in the constructible universe whose automorphism towers are highly malleable by forcing. This is a consequence of the fact that, under a suitable diamond hypothesis, there are sufficiently many highly rigid non-isomorphic Souslin trees whose isomorphism relation can be precisely controlled by forcing.

  7. Complex tilings

    Durand, Bruno; Levin, Leonid A.; Shen, Alexander
    We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with ??(n) Kolmogorov complexity of its (n×n)-squares. We construct tile sets for which this bound is tight: all (n×n)-squares in all tilings have complexity Ω(n). This adds a quantitative angle to classical results on non-recursivity of tilings—that we also develop in terms of Turing degrees of unsolvability.

  8. The polynomial and linear hierarchies in models where the weak pigeonhole principle fails

    Kołodziejczyk, Leszek Aleksander; Thapen, Neil
    We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. ¶ Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak pigeonhole principle fails in a certain way, and then work with this failure to obtain our results. ¶ As a corollary of one of the proofs, we...

  9. Randomness, lowness and degrees

    Barmpalias, George; Lewis, Andrew E. M.; Soskova, Mariya
    We say that A≤LRB if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ, oracle B can also find patterns on γ. In other words, B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever α is not GL2 the LR degree of α bounds 20 degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate...

  10. On the structure of the Medvedev lattice

    Terwijn, Sebastiaan A.
    We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size 220, the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size 220, and in fact that these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a...

  11. Hierarchies of forcing axioms II

    Neeman, Itay
    A Σ21 truth for λ is a pair 〈 Q,ψ〉 so that Q ⊆ Hλ, ψ is a first order formula with one free variable, and there exists B ⊆ Hλ+ such that (Hλ+;∈,B)⊨ψ[Q]. A cardinal λ is Σ21 indescribable just in case that for every Σ21 truth 〈 Q,ψ〉 for λ, there exists \bar{λ} < λ so that \bar{λ} is a cardinal and 〈 Q∩ H\bar{λ},ψ〉 is a Σ21 truth for \bar{λ}. More generally, an interval of cardinals [κ,λ] with κ≤λ is Σ21 indescribable if for every Σ21 truth 〈 Q,ψ〉 for λ, there exists \bar{κ}≤\bar{λ}<κ, \bar{Q}⊆ H\bar{λ}, and π: H\bar{λ}→ Hλ so that \bar{λ} is a cardinal, 〈 \bar{Q},ψ〉 is a Σ21...

  12. Internal consistency and global co-stationarity of the ground model

    Dobrinen, Natasha; Friedman, Sy-David
    Global co-stationarity of the ground model from an ℵ2-c.c. forcing which adds a new subset of ℵ1 is internally consistent relative to an ω1-Erdős hyperstrong cardinal and a sufficiently large measurable above.

  13. Some pathological examples of precipitous ideals

    Gitik, Moti
    We construct a model with an indecisive precipitous ideal and a model with a precipitous ideal with a non precipitous normal ideal below it. Such kind of examples were previously given by M. Foreman [2] and R. Laver [4] respectively. The present examples differ in two ways: first- they use only a measurable cardinal and second- the ideals are over a cardinal. Also a precipitous ideal without a normal ideal below it is constructed. It is shown in addition that if there is a precipitous ideal over a cardinal κ such that [start-list] *after the forcing with its positive sets the cardinality of κ remains above ℵ1 *there is no a normal...

  14. Coding complete theories in Galois groups

    Gray, James
    In this paper, I will give a new characterisation of the spaces of complete theories of pseudo-finite fields and of algebraically closed fields with a generic automorphism (ACFA) in terms of the Vietoris topology on absolute Galois groups of prime fields.

  15. Special groups whose isometry relation is a finite union of cosets

    Astier, Vincent
    0-stable ℵ0-categorical linked quaternionic mappings are studied and are shown to correspond (in some sense) to special groups which are ℵ0-stable, ℵ0-categorical, satisfy AP(3) and have finite 2-symbol length. They are also related to special groups whose isometry relation is a finite union of cosets, which are then considered on their own, as well as their links with pseudofinite, profinite and weakly normal special groups.

  16. On metric types that are definable in an o-minimal structure

    Valette, Guillaume
    In this paper we study the metric spaces that are definable in a polynomially bounded o-minimal structure. We prove that the family of metric spaces definable in a given polynomially bounded o-minimal structure is characterized by the valuation field Λ of the structure. In the last section we prove that the cardinality of this family is that of Λ. In particular these two results answer a conjecture given in [SS] about the countability of the metric types of analytic germs. The proof is a mixture of geometry and model theory.

  17. Finite state automata and monadic definability of singular cardinals

    Neeman, Itay
    We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals.

  18. Reals n-generic relative to some perfect tree

    Anderson, Bernard A.
    We say that a real X is n-generic relative to a perfect tree T if X is a path through T and for all Σ0n (T) sets S, there exists a number k such that either X|k ∈ S or for all σ ∈ T extending X|k we have σ ∉ S. A real X is n-generic relative to some perfect tree if there exists such a T. We first show that for every number n all but countably many reals are n-generic relative to some perfect tree. Second, we show that proving this statement requires ZFC- + “∃ infinitely many iterates of the power...

  19. On the consistency strength of the inner model hypothesis

    Friedman, Sy-David; Welch, Philip; Woodin, W. Hugh

  20. Scales in K(ℝ) at the end of a weak gap

    Steel, J. R.

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.