1.
Immunity and Hyperimmunity for Sets of Minimal Indices - Stephan, Frank; Teutsch, Jason
We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that
minimal index sets are immune, and we show that they are also immune against high levels of the
arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect
to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not
simply a refinement of arithmetic complexity. Of particular note here are the fact that there
are three minimal index sets located in ?3 ?
?3 with distinct levels of immunity and that certain immunity properties
depend on the choice of underlying acceptable numbering. We show that minimal...
2.
Mass Problems and Intuitionism - Simpson, Stephen G.
Let $\mathcal{P}_w$ be the lattice of Muchnik degrees of nonempty $\Pi^0_1$ subsets of $2^\omega$ . The lattice $\mathcal{P}$ has been studied extensively in previous publications. In this note we prove that the
lattice $\mathcal{P}$ is not Brouwerian.
3.
A Note on the Logic of Eventual Permanence for Linear Time - French, Rohan
In a paper from the 1980s, Byrd claims that the logic of "eventual permanence" for linear
time is KD5. In this note we take up Byrd's novel argument for this and, treating the
problem as one concerning translational embeddings, show that rather than KD5 the
correct logic of "eventual permanence" is KD45
4.
An Undecidable Property of Recurrent Double Sequences - Prunescu, Mihai
For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$ .
¶ The problem if such recurrent double sequences are ultimately zero is undecidable, even if we
restrict it to the class of commutative finite algebras.
5.
Fitch's Argument and Typing Knowledge - Paseau, Alexander
Fitch's argument purports to show that if all truths are knowable then all truths are known.
The argument exploits the fact that the knowledge predicate or operator is untyped and may thus
apply to sentences containing itself. This article outlines a response to Fitch's argument
based on the idea that knowledge is typed. The first part of the article outlines the
philosophical motivation for the view, comparing it to the motivation behind typing truth. The
second, formal part presents a logic in which knowledge is typed and demonstrates that it
allows nonlogical truths to be knowable yet unknown.
6.
Tennenbaum's Theorem and Unary Functions - Yaegasi, Sakae
It is well known that in any nonstandard model of $\mathsf{PA}$ (Peano arithmetic) neither addition nor multiplication is recursive. In this paper we
focus on the recursiveness of unary functions and find several pairs of unary functions which
cannot be both recursive in the same nonstandard model of $\mathsf{PA}$ (e.g., $\{2x,2x+1\}$ , $\{x^2,2x^2\}$ , and $\{2^x,3^x\}$ ). Furthermore, we prove that for any computable injection $f(x)$ , there is a nonstandard model of $\mathsf{PA}$ in which $f(x)$ is recursive.
7.
Functors of Lindenbaum-Tarski, Schematic Interpretations, and Adjoint Cylinders between
Sentential Logics - Vidal, J. Climent; Tur, J. Soliveres
We prove, by using the concept of schematic interpretation, that the natural embedding from
the category ISL, of intuitionistic sentential pretheories and i-congruence classes of
morphisms, to the category CSL, of classical sentential pretheories and c-congruence
classes of morphisms, has a left adjoint, which is related to the double negation
interpretation of Gödel-Gentzen, and a right adjoint, which is related to the Law of
Excluded Middle. Moreover, we prove that from the left to the right adjoint there is a
pointwise epimorphic natural transformation and that since the two endofunctors at CSL,
obtained by adequately composing the aforementioned functors, are naturally isomorphic to the
identity functor for CSL,...
8.
Approximate Similarities and Poincaré Paradox - Gerla, Giangiacomo
De Cock and Kerre, in considering Poincaré paradox, observed that the intuitive
notion of "approximate similarity" cannot be adequately represented by the fuzzy equivalence
relations. In this note we argue that the deduction apparatus of fuzzy logic gives adequate
tools with which to face the question. Indeed, a first-order theory is proposed whose fuzzy
models are plausible candidates for the notion of approximate similarity. A connection between
these structures and the point-free metric spaces is also established.
9.
Automorphisms of Countable Short Recursively Saturated Models of PA - Shochat, Erez
A model of Peano Arithmetic is short recursively saturated if it
realizes all its bounded finitely realized recursive types. Short
recursively saturated models of
$\PA$ are exactly the elementary
initial segments of recursively saturated models of
$\PA$ . In this
paper, we survey and prove results on short recursively saturated
models of
$\PA$ and their automorphisms. In particular, we
investigate a certain subgroup of the automorphism group of such
models. This subgroup, denoted
$G|_{M(a)}$ , contains all the
automorphisms of a countable short recursively saturated model of
which can be extended
to an automorphism of the countable recursively saturated elementary end extension of
the model.
10.
Intuitionistic Logic according to Dijkstra's Calculus of Equational Deduction - Bohórquez V., Jaime
Dijkstra and Scholten have proposed a formalization of
classical predicate logic on a novel deductive system as an
alternative to Hilbert's style of proof and Gentzen's
deductive systems. In this context we call it CED
(Calculus of Equational Deduction). This deductive
method promotes logical equivalence over implication and shows
that there are easy ways to prove predicate formulas without
the introduction of hypotheses or metamathematical tools such
as the deduction theorem. Moreover, syntactic considerations
(in Dijkstra's words, "letting the symbols do the work") have
led to the "calculational style," an impressive array of
techniques for elegant proof constructions. In this paper, we
formalize intuitionistic predicate logic according to
CED with similar success. In...
11.
A Note on Logics of Ignorance and Borders - Steinsvold, Christopher
We present and show topological completeness for LB, the logic
of the topological border. LB is also a logic of epistemic
ignorance. Also, we present and show completeness for LUT, the
logic of unknown truths. A simple topological completeness proof
for S4 is also presented using a T1 space
12.
Models Omitting Given Complete Types - Tsuboi, Akito
We consider a problem of constructing a model that omits given complete types.
We present two results. The first one is related to the Lopez-Escobar
theorem and the second one is a version of Morley's omitting
types theorem.
13.
Weakening of Intuitionistic Negation for Many-valued Paraconsistent da Costa System - Majki?, Zoran
In this paper we propose substructural propositional logic obtained
by da Costa weakening of the intuitionistic negation. We show that
the positive fragment of the da Costa system is distributive lattice
logic, and we apply a kind of da Costa weakening of negation, by
preserving, differently from da Costa, its fundamental properties:
antitonicity, inversion, and additivity for distributive lattices.
The other stronger paraconsistent logic with constructive negation
is obtained by adding an axiom for multiplicative property of weak
negation. After that, we define Kripke-style semantics based on
possible worlds and derive from it many-valued semantics based on
truth-functional valuations for these two paraconsistent logics.
Finally, we demonstrate that this model-theoretic inference...
14.
The Sum of
Irreducible Fractions with Consecutive Denominators Is Never an
Integer in PA- - Pambuccian, Victor
Two results of elementary number theory, going back to Kürschák and Nagell, stating that the sums
$\sum_{i=1}^k \frac{m_i}{n+i}$ (with
$k\geq 1$ ,
$(m_i, n+i)=1$ ,
$m_i\lessthan n+i$ ) and
$\sum_{i=0}^k \frac{1}{m+in}$ (with
$n, m, k$
positive integers) are never integers, are shown to hold in
$\mathrm{PA}^{-}$ , a very weak arithmetic, whose axiom system has no
induction axiom.
15.
Proof Mining in Topological Dynamics - Gerhardy, Philipp
A famous theorem by van der Waerden states the following: Given any
finite coloring of the integers, one color contains arbitrarily
long arithmetic progressions. Equivalently, for every q,k, there is
an N = N(q,k) such that for every q-coloring of an interval of
length N one color contains a progression of length k. An
obvious question is what is the growth rate of N = N(q,k). Some
proofs, like van der Waerden's combinatorial argument, answer this
question directly, while the topological proof by Furstenberg and
Weiss does not. We present an analysis of (Girard's variant of)
Furstenberg and Weiss's proof based on monotone functional
interpretation, both yielding bounds and providing...
17.
On Partial and Paraconsistent Logics - Muskens, Reinhard
In this paper we consider the theory of predicate
logics in which the principle of bivalence or the principle of
noncontradiction or both fail. Such logics are partial or
paraconsistent or both. We consider sequent calculi for these logics
and prove model existence. For $ \bf L_4$ , the most general logic
under consideration, we also prove a version of the Craig-Lyndon
Interpolation Theorem. The paper shows that many techniques used
for classical predicate logic generalize to partial and
paraconsistent logics once the right setup is chosen. Our logic
$ \bf L_4$ has a semantics that also underlies Belnap's logic and is related
to the logic of bilattices. $ \bf...
1.
