Recursos de colección
Project Euclid (Hosted at Cornell University Library) (185.988 recursos)
Journal of Symbolic Logic
Journal of Symbolic Logic
Cai, Mingzhong; Shore, Richard A.
We study low level nondefinability in the Turing degrees. We prove a variety
of results, including, for example, that being array nonrecursive is not
definable by a $\Sigma_{1}$ or $\Pi_{1}$ formula in the language $(\leq
,\REA)$ where $\REA$ stands for the ``r.e.\ in and
above'' predicate. In contrast, this property is definable
by a $\Pi_{2}$ formula in this language. We also show that the $\Sigma_{1}$-theory of $(\mathcal{D},\leq ,\REA)$ is decidable.
Goldbring, Isaac; Hart, Bradd; Sinclair, Thomas
In this note, we show that the theory of tracial von Neumann algebras does not have a model companion. This will follow from the fact that the theory of any locally universal, McDuff II$_1$ factor does not have quantifier elimination. We also show how a positive solution to the Connes Embedding Problem implies that there can be no model-complete theory of II$_1$ factors.
Arciga-Alejandre, M.; Hrušák, M.; Martinez-Ranero, C.
We answer a question of Garcia-Ferreira and Hrušák by consistently constructing a MAD family maximal in the Katětov order. We also answer several questions of Garcia-Ferreira.
Jockusch, Jr., Carl G.; Lewis, Andrew E. M.
We prove that every diagonally noncomputable function computes a set
$A$ which is bi-immune, meaning that neither $A$ nor its complement
has an infinite computably enumerable subset.
Dobrowolski, Jan
We answer some questions from [4] by giving suitable examples of small Polish structures. First, we present a class of small Polish group structures without generic elements. Next, we construct a first example of a small non-zero-dimensional Polish $G$-group.
Palumbo, Justin
We compare the strength of polychromatic and monochromatic Ramsey theory
in several set-theoretic domains. We show that the rainbow Ramsey theorem
does not follow from ZF, nor does the rainbow Ramsey theorem imply Ramsey's
theorem over ZF. Extending the classical result of Erdős and Rado we
show that the axiom of choice precludes the natural infinite exponent
partition relations for polychromatic Ramsey theory. We introduce rainbow
Ramsey ultrafilters, a polychromatic analogue of the usual Ramsey ultrafilters.
We investigate the relationship of rainbow Ramsey ultrafilters with various
special classes of ultrafilters, showing for example that every rainbow
Ramsey ultrafilter is nowhere dense but rainbow Ramsey ultrafilters need not
be rapid. This...
Mints, Grigori; Olkhovikov, Grigory; Urquhart, Alasdair
This paper shows that the interpolation theorem fails in the
intuitionistic logic of constant domains. This result refutes two
previously published claims that the interpolation property holds.
Koponen, Vera
For integers $l \geq 1$, $d \geq 0$ we study (undirected) graphs with vertices
$1, \ldots, n$ such that the vertices
can be partitioned into $l$ parts such that every vertex has at most
$d$ neighbours in its own part.
The set of all such graphs is denoted $\mathbf{P}_n(l,d)$.
We prove a labelled first-order limit law, i.e., for every first-order sentence
$\varphi$, the proportion of graphs in $\mathbf{P}_n(l,d)$ that satisfy $\varphi$ converges
as $n \to \infty$.
By combining this result with a result of
Hundack, Prömel and Steger [12] we also prove that if
$1 \leq s_1 \leq \ldots \leq s_l$ are integers, then $\mathbf{Forb}(\mathcal{K}_{1, s_1, \ldots, s_l})$
has a labelled...
Panti, Giovanni; Ravotti, Davide
The half-open real unit interval $(0,1]$ is closed under the ordinary multiplication and its residuum. The corresponding infinite-valued propositional logic has as its equivalent algebraic semantics the equational class of cancellative hoops. Fixing a strong unit in a cancellative hoop—equivalently, in the enveloping lattice-ordered abelian group—amounts to fixing a gauge scale for falsity.
In this paper we show that any strong unit in a finitely presented cancellative hoop $H$ induces naturally (i.e., in a representation-independent way) an automorphism-invariant
positive normalized linear functional on $H$. Since $H$ is representable as a uniformly dense set of continuous functions on its maximal spectrum, such functionals—in...
Lubarsky, Robert S.; Diener, Hannes
BD-N is a weak principle of constructive analysis. Several
interesting principles implied by BD-N have already been
identified, namely the closure of the anti-Specker spaces under
product, the Riemann Permutation Theorem, and the Cauchyness of
all partially Cauchy sequences. Here these are shown to be
strictly weaker than BD-N, yet not provable in set theory alone
under constructive logic.
Czajka, łukasz
We show a model construction for a system of higher-order illative
combinatory logic $\mathcal{I}_\omega$, thus establishing its strong
consistency. We also use a variant of this construction to provide a
complete embedding of first-order intuitionistic predicate logic
with second-order propositional quantifiers into the system $\mathcal{I}_0$
of Barendregt, Bunder and Dekkers, which gives a partial answer to a
question posed by these authors.
Wang, Wei
We prove that $\operatorname{RCA}_0 + \operatorname{RRT}^3_2 \nvdash \operatorname{ACA}_0$ where $\operatorname{RRT}^3_2$ is the
Rainbow Ramsey Theorem for $2$-bounded colorings of triples. This reverse
mathematical result is based on a cone avoidance theorem, that every
$2$-bounded coloring of pairs admits a cone-avoiding infinite rainbow,
regardless of the complexity of the given coloring. We also apply the proof
of the cone avoidance theorem to the question whether
$\operatorname{RCA}_0 + \operatorname{RRT}^4_2 \vdash \operatorname{ACA}_0$ and obtain some partial answer.
Friedman, Sy-David; Golshani, Mohammad
Shelah—Woodin [10] investigate the possibility of
violating instances of GCH through the addition of a single
real. In particular they show that it is possible to obtain a
failure of CH by adding a single real to a model of GCH,
preserving cofinalities. In this article we strengthen their
result by showing that it is possible to violate GCH at all
infinite cardinals by adding a single real to a model of GCH.
Our assumption is the existence of an $H(\kappa^{+3})$-strong
cardinal; by work of Gitik and Mitchell [6] it
is known that more than an $H(\kappa^{++})$-strong cardinal is
required.
Krueger, John
We develop a version of
Namba forcing which is useful for constructing models with
no good scale on $\aleph_\omega$.
A model is produced in which $\Box_{\aleph_n}$ holds for all finite
$n \ge 1$, but there is no good scale on $\aleph_\omega$; this
strengthens a theorem of
Cummings, Foreman, and Magidor [3]
on the non-compactness of square.
Escardó, Martín
We show that there are plenty of infinite sets that satisfy the
omniscience principle, in a minimalistic setting for constructive
mathematics that is compatible with classical mathematics. A first
example of an omniscient set is the one-point compactification
of the natural numbers, also known as the generic
convergent sequence. We relate this to Grilliot's and Ishihara's
Tricks. We generalize this example to many infinite subsets of
the Cantor space. These subsets turn out to be ordinals in a
constructive sense, with respect to the lexicographic order,
satisfying both a well-foundedness condition with respect to
decidable subsets, and transfinite induction restricted to decidable
predicates. The use of simple types allows us to...
Sargsyan, Grigor
Working under $AD$, we investigate the length of prewellorderings given by the iterates of $\mathcal{M}_{2k+1}$,
which is the minimal proper class mouse with $2k+1$ many Woodin cardinals. In particular, we answer some questions from [4] (the discussion of the questions appears in the last section of [2]).
Jensen, Ronald; Steel, John
We show in ZFC that if there is no proper class inner
model with a Woodin cardinal, then there is an absolutely definable
core model that is close to $V$ in various ways.
Stanley, M. C.
Using square sequences, a stationary subset
$S_T$ of $\aleph_{\omega_{1}+1}$ is constructed from a tree $T$ of height $\omega_1$, uniformly in $T$.
Under suitable hypotheses, adding a closed unbounded subset to $S_T$ requires
adding a cofinal branch to $T$ or collapsing at least one of $\omega_1$,
$\aleph_{\omega_{1}}$, and $\aleph_{\omega_1+1}$.
An application is that in ZFC there is no parameter free
definition of the family of subsets of $\aleph_{\omega_1+1}$ that have a
closed unbounded subset in some $\omega_1$, $\aleph_{\omega_{1}}$, and $\aleph_{\omega_1+1}$
preserving outer model.
Hirsch, R.
Becker, Howard
The following question is open: Does there exist a hyperarithmetic class of computable structures with exactly one non-hyperarithmetic isomorphism-type? Given any oracle $a \in 2^\omega$, we can ask the same question relativized to $a$. A negative answer for every $a$ implies Vaught's Conjecture for $L_{\omega_1 \omega}$.