Recursos de colección
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 ℱ...
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...
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.
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...
Soskova, Mariya I.; Cooper, S. Barry
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.
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.
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 S_{2}^{1}
exists in which NP is not in the second level of the linear hierarchy;
and that a model of S_{2}^{1} 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...
Barmpalias, George; Lewis, Andrew E. M.; Soskova, Mariya
We say that A≤_{LR}B 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 GL_{2} the LR degree of
α bounds 2^{ℵ0} degrees (so that, in particular,
there exist LR degrees with uncountably many predecessors) and
we give sample results which demonstrate...
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 2^{2ℵ0}, the size of the lattice itself.
We also prove that it is consistent with ZFC that the lattice has chains
of size 2^{2ℵ0}, 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...
Neeman, Itay
A Σ^{2}_{1} 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 Σ^{2}_{1} indescribable just in case that
for every Σ^{2}_{1} truth 〈 Q,ψ〉 for λ, there
exists \bar{λ} < λ so that \bar{λ} is a
cardinal and 〈 Q∩ H_{\bar{λ}},ψ〉 is a Σ^{2}_{1}
truth for \bar{λ}. More generally, an interval of
cardinals [κ,λ] with κ≤λ is Σ^{2}_{1} indescribable if for every Σ^{2}_{1} 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 Σ^{2}_{1}...
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.
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...
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.
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.
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.
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.
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
Σ^{0}_{n} (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...
Friedman, Sy-David; Welch, Philip; Woodin, W. Hugh
Steel, J. R.