Sunday, June 21, 2015

﻿

 Lógica Matemáticas Astronomía y Astrofísica Física Química Ciencias de la Vida Ciencias de la Tierra y Espacio Ciencias Agrarias Ciencias Médicas Ciencias Tecnológicas Antropología Demografía Ciencias Económicas Geografía Historia Ciencias Jurídicas y Derecho Lingüística Pedagogía Ciencia Política Psicología Artes y Letras Sociología Ética Filosofía

## Recursos de colección

Project Euclid (Hosted at Cornell University Library) (181,109 recursos)

Journal of Symbolic Logic

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