Mostrando recursos 1 - 20 de 11.931

  1. Low level nondefinability results: Domination and recursive enumeration

    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.

  2. The theory of tracial von Neumann algebras does not have a model companion

    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.

  3. Invariance properties of almost disjoint families

    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.

  4. Diagonally non-computable functions and bi-immunity

    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.

  5. New examples of small Polish structures

    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.

  6. Comparisons of polychromatic and monochromatic Ramsey theory

    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...

  7. Failure of interpolation in constant domain intuitionistic logic

    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.

  8. A limit law of almost $l$-partite graphs

    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...

  9. Measures induced by units

    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...

  10. Principles weaker than BD-N

    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.

  11. Higher-order illative combinatory 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.

  12. Rainbow Ramsey Theorem for triples is strictly weaker than the Arithmetical Comprehension Axiom

    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.

  13. Killing the $GCH$ everywhere with a single real

    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.

  14. Namba forcing and no good scale

    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.

  15. Infinite sets that satisfy the principle of omniscience in any variety of constructive mathematics

    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...

  16. On the prewellorderings associated with the directed systems of mice

    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]).

  17. $K$ without the measurable

    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.

  18. Forcing closed unbounded subsets of $\aleph_{\omega_{1}+1}$

    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.

  19. Corrigendum to: “Relation algebra reducts of cylindric algebras and complete representations”

    Hirsch, R.

  20. Isomorphism of computable structures and {V}aught's {C}onjecture

    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}$.

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.