### Top 6 Arxiv Papers Today in Logic

##### #1. Degrees of Randomized Computability
###### Rupert Hölzl, Christopher P. Porter
In this survey we discuss work of Levin and V'yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V'yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal{A}$ and $\mathcal{B}$, $\mathcal{A}$ is less than $\mathcal{B}$ in this ordering if $\mathcal{A}\setminus\mathcal{B}$ is negligible. The degree structure associated with this ordering, the $\textit{Levin-V'yugin degrees}$ (or $\textit{LV-degrees}$), can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin-V'yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between...
more | pdf | html
None.
###### Tweets
mathLOb: Rupert Hölzl, Christopher P. Porter : Degrees of Randomized Computability https://t.co/hOXg9xirdu https://t.co/EnsOybgwB5
arxiv_cslo: Degrees of Randomized Computability https://t.co/m5YXkE9H29
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #2. Constructing Wadge classes
###### Raphaël Carroy, Andrea Medini, Sandra Müller
We show that, assuming the Axiom of Determinacy, every non-selfdual Wadge class can be constructed by starting with those of level $\omega_1$ (that is, the ones that are closed under Borel preimages) and iteratively applying the operations of expansion and separated differences. The proof is essentially due to Louveau, and it yields at the same time a new proof of a theorem of Van Wesep (namely, that every non-selfdual Wadge class can be expressed as the result of a Hausdorff operation applied to the open sets). The exposition is self-contained, except for facts from classical descriptive set theory.
more | pdf | html
None.
###### Tweets
logicians: “Constructing Wadge classes”, R. Carroy, A. Medini, S. Müller. #math #logic https://t.co/TcuQ93xlrC
mathLOb: Raphaël Carroy, Andrea Medini, Sandra Müller : Constructing Wadge classes https://t.co/wwea2P8aV6 https://t.co/PodqBdAfb2
BenediktLoewe: RT @mathLOb: Raphaël Carroy, Andrea Medini, Sandra Müller : Constructing Wadge classes https://t.co/wwea2P8aV6 https://t.co/PodqBdAfb2
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #3. Bounded homomorphisms and finitely generated fiber products of lattices
###### William DeMeo, Peter Mayr, Nik Ruskuc
We investigate when fiber products of lattices are finitely generated and obtain a new characterization of bounded lattice homomorphisms onto finitely presented lattices and onto lattices satisfying Whitman's condition. Specifically, for lattice epimorphisms $g\colon A\to D$, $h\colon B\to D$, where $A$, $B$ are finitely generated and $D$ is finitely presented or satisfies Whitman's condition, we show the following: If $g$ and $h$ are bounded, then their fiber product (pullback) $C=\{(a,b)\in A\times B : g(a)=h(b)\}$ is finitely generated. While the converse is not true in general, it does hold when $A$ and $B$ are free. As a consequence we obtain an exponential time algorithm to decide whether a finitely presented lattice or a finitely generated sublattice satisfying Whitman's condition is bounded. This generalizes an unpublished result of Freese and Nation.
more | pdf | html
None.
###### Tweets
mathLOb: William DeMeo, Peter Mayr, Nik Ruskuc : Bounded homomorphisms and finitely generated fiber products of lattices https://t.co/SE949fWjbY https://t.co/6h2DB2Br1h
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 7255
Unqiue Words: 1359

##### #4. A simplified ordinal analysis of first-order reflection
###### Toshiyasu Arai
In this note we give a simplified ordinal analysis of first-order reflection. An ordinal notation system $OT$ is introduced based on $\psi$-functions. Provable $\Sigma_{1}$-sentences on $L_{\omega_{1}^{CK}}$ are bounded through cut-elimination on operator controlled derivations.
more | pdf | html
None.
###### Tweets
mathLOb: Toshiyasu Arai : A simplified ordinal analysis of first-order reflection https://t.co/OnJat1rh5v https://t.co/9ggaSEhxSx
berenbeim: RT @mathLOb: Toshiyasu Arai : A simplified ordinal analysis of first-order reflection https://t.co/OnJat1rh5v https://t.co/9ggaSEhxSx
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #5. A Canonical Model Proof of Strong Completeness for BQL
###### Ben Middleton
I prove using a canonical model construction that a simple extension of Visser's natural deduction system for Basic Propositional Logic is both sound and strongly complete with respect to Basic First-Order Logic (BQL). I utilize the canonical model construction to show that BQL satisfies both the Disjunction Property and the Existence Property.
more | pdf | html
None.
###### Tweets
mathLOb: Ben Middleton : A Canonical Model Proof of Strong Completeness for BQL https://t.co/sntny5sWT4 https://t.co/o3Rk4b9M8j
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5920
Unqiue Words: 885

##### #6. Abstract categorial grammars with island constraints and effective decidability
###### Sergey Slavnov
A well-known approach to treating syntactic island constraints in the setting of Lambek grammars consists in adding specific bracket modalities to the logic. We adapt this approach to abstract categorial grammars (ACG). Thus we define bracketed (implicational) linear logic, bracketed lambda-calculus, and, eventually, bracketed ACG based on bracketed $\lambda$-calculus. This allows us modeling at least simplest island constraints, typically, in the context of relativization. Next we identify specific safely bracketed ACG which, just like ordinary (bracket-free) second order ACG generate effectively decidable languages, but are sufficiently flexible to model some higher order phenomena like relativization and correctly deal with syntactic islands, at least in simple toy examples.
more | pdf | html
None.
###### Tweets
mathLOb: Sergey Slavnov : Abstract categorial grammars with island constraints and effective decidability https://t.co/ThpUfYbi9K https://t.co/BGt4pR8qRy
arxiv_cscl: Abstract categorial grammars with island constraints and effective decidability https://t.co/zYPXqzFPNU
arxiv_cscl: Abstract categorial grammars with island constraints and effective decidability https://t.co/zYPXqzFPNU
berenbeim: RT @mathLOb: Sergey Slavnov : Abstract categorial grammars with island constraints and effective decidability https://t.co/ThpUfYbi9K https…
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 9827
Unqiue Words: 1913

###### About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 160,428 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 160,428 papers.