1.
ZF + Every set is the same size as a wellfounded set - Forster, Thomas
Let ZFB be ZF + every set is the same size as a wellfounded set. Then the following are true.
¶
Every sentence true in every (Rieger-Bernays) permutation model of a model of ZF is a theorem of ZFB. (i.e., ZFB is the theory of Rieger-Bernays permutation models of models of ZF)
¶
ZF and ZFAFA are both extensions of ZFB conservative for stratified formul{\ae}.
¶
{The class of models of ZFB is closed under creation of Rieger-Bernays permutation models.
2.
An application of graphical enumeration to PA* - Weiermann, Andreas
For $\al$ less than $ \eo$ let $N\al$ be the number of occurrences
of $\om$ in the Cantor normal form of $\al$. Further let $\lh n$
denote the binary length of a natural number $n$, let $\lhh n$ denote
the $h$-times iterated binary length of $n$ and let $\inv n$ be the
least $h$ such that $\lhh n \leq2$. We show that for any natural number
$h$ first order Peano arithmetic, $\PA$, does not prove the following
sentence: For all $ K$ there exists an $ M$ which bounds the lengths $n$
of all strictly descending sequences $\langle \al0,... ,\aln\rangle$
of ordinals less than $\eo$ which satisfy the...
3.
On the induction schema for decidable predicates - Beklemishev, Lev D.
We study the fragment of Peano arithmetic formalizing the induction
principle for the class of decidable predicates, $I\Delta1$. We show
that $I\Delta1$ is independent from the set of all true arithmetical
$\Pi2$-sentences. Moreover, we establish the connections between this
theory and some classes of oracle computable functions with
restrictions on the allowed number of queries. We also obtain some
conservation and independence results for parameter free and inference
rule forms of $\Delta1$-induction.
¶ An open problem formulated by J. Paris (see \cite{CloKra,HP}) is
whether $I\Delta1$ proves the corresponding least element principle
for decidable predicates, $L\Delta1$ (or, equivalently, the
$\Sigma1$-collection principle $B\Sigma1$). We reduce this question
to a purely computation-theoretic one.
4.
Definable sets in Boolean ordered o-minimal structures. II - Wencel, Roman
Let $(M,\leq,...)$ denote a Boolean ordered o-minimal
structure. We prove that a Boolean subalgebra of $M$ determined by
an algebraically closed subset contains no dense atoms. We show
that Boolean algebras with finitely many atoms do not admit proper
expansions with o-minimal theory. The proof involves decomposition
of any definable set into finitely many pairwise disjoint cells,
i.e., definable sets of an especially simple nature. This leads to
the conclusion that Boolean ordered structures with o-minimal
theories are essentially bidefinable with Boolean algebras with
finitely many atoms, expanded by naming constants. We also discuss
the problem of existence of proper o-minimal expansions of Boolean
algebras.
5.
On a problem of Cooper and Epstein - Ishmukhametov, Shamil
In Bounding minimal degrees by computably enumerable degrees
by A. Li and D. Yang, (this Journal, \cite{LY}),
the authors prove that
there exist non-computable computably enumerable degrees
c > a > z such that any minimal degree
m being below c
is also below a. We analyze the proof of their result and
show that the proof contains a mistake. Instead we give a proof
for the opposite result.
6.
Strong extension axioms and Shelahs zero-one law for choiceless polynomial time - Blass, Andreas; Gurevich, Yuri
This paper developed from Shelahs proof of a zero-one law for the
complexity class choiceless polynomial time, defined by Shelah and
the authors. We present a detailed proof of Shelah's result for
graphs, and describe the extent of its generalizability to other sorts
of structures. The extension axioms, which form the basis for earlier
zero-one laws (for first-order logic, fixed-point logic, and
finite-variable infinitary logic) are inadequate in the case of
choiceless polynomial time; they must be replaced by what we call the
strong extension axioms. We present an extensive discussion of these
axioms and their role both in the zero-one law and in general.
7.
The Church-Rosser property in dual combinatory logic - Bimbó, Katalin
Dual combinators emerge from the aim of assigning
formulas containing $\leftarrow$ as types to combinators. This
paper investigates formally some of the properties of combinatory
systems that include both combinators and dual combinators.
Although the addition of dual combinators to a combinatory system
does not affect the unique decomposition of terms, it turns out
that some terms might be redexes in two ways (with a combinator as
its head, and with a dual combinator as its head). We prove a
general theorem stating that no dual combinatory system
possesses the Church-Rosser property. Although the lack of
confluence might be problematic in some cases, it is not a problem
per se. In...
8.
Presburger sets and p-minimal fields - Cluckers, Raf
We prove a cell decomposition theorem for Presburger sets and
introduce a dimension theory for $Z$-groups with the Presburger
structure. Using the cell decomposition theorem we obtain a full
classification of Presburger sets up to definable bijection. We
also exhibit a tight connection between the definable sets in an
arbitrary p-minimal field and Presburger sets in its value group.
We give a negative result about expansions of Presburger
structures and prove uniform elimination of imaginaries for
Presburger structures within the Presburger language.
9.
Epistemic models of shallow depths and decision making in games: Horticulture - Kaneko, Mamoru; Suzuki, Nobu-Yuki
Kaneko-Suzuki developed epistemic logics of shallow depths with
multiple players for investigations of game theoretical problems. By
shallow depth, we mean that nested occurrences of belief operators of
players in formulae are restricted, typically to be of finite depths,
by a given epistemic structure. In this paper, we develop
various methods of surgical operations (cut and paste) of epistemic
world models. An example is a bouquet-making, i.e., tying several
models into a bouquet. Another example is to engraft a model to some
branches of another model. By these methods, we obtain various
meta-theorems on semantics and syntax on epistemic logics. To
illustrate possible uses of our meta-theorems, we present one...
10.
The Steel hierarchy of ordinal valued Borel mappings - Duparc, J.
Given well ordered countable sets of the form $\lamphi$, we
consider Borel mappings from $\lamphiom$ with countable image
inside the ordinals. The ordinals and $\lamphiom$ are
respectively equipped with the discrete topology and the product
of the discrete topology on $\lamphi$. The Steel well-ordering on
such mappings is defined by $\phi\minf\psi$ iff there exists a
continuous function $f$ such that $\phi(x)\leq\psi\circ f(x)$
holds for any $x\in\lamphiom$. It induces a hierarchy of mappings
which we give a complete description of. We provide, for each
ordinal $\alpha$, a mapping $\T{\alpha}$ whose rank is precisely
$\alpha$ in this hierarchy and we also compute the height of the
hierarchy restricted to mappings with image bounded...
11.
Q-pointness, P-pointness and feebleness of ideals - Matet, Pierre; Pawlikowski, Janusz
We study the degree of (weak) $Q$-pointness,
and that of (weak) $P$-pointness, of ideals on a regular infinite
cardinal.
13.
Inequivalent representations of geometric relation algebras - Givant, Steven
It is shown that the automorphism group of a relation algebra
$\mla P$ constructed from a projective geometry $P$ is isomorphic
to the collineation group of $P$. Also, the base automorphism
group of a representation of $\mla P$ over an affine geometry $D$
is isomorphic to the quotient of the collineation group of $D$ by
the dilatation subgroup. Consequently, the total number of
inequivalent representations of $\mla P$, for finite geometries
$P$, is the sum of the numbers
\[
\frac{|\aut P|}{|\aut {D}|\mathbin{/}|\dil{D}|},
\]
where $D$ ranges over a list of the non-isomorphic
affine geometries having $P$ as their geometry at infinity. This
formula is used to compute the number of inequivalent
representations of relation...
14.
Separably closed fields with Hasse derivations - Ziegler, Martin
In \cite{MessmerW1995} Messmer and Wood proved quantifier
elimination for separably closed fields of finite Ershov invariant
$e$ equipped with a (certain) \Hde. We propose a variant of their
theory, using a sequence of $e$ commuting \Hds. In contrast
to \cite{MessmerW1995} our \Hds are iterative.
15.
Definability with a predicate for a semi-linear set - Benedikt, Michael; Keisler, H. Jerome
We settle a number of questions
concerning definability in first order logic
with an extra predicate symbol ranging over semi-linear sets.
We give new results both on the positive and
negative side: we show that in first-order logic one cannot query
a semi-linear set as to whether or not it contains a line, or
whether or not it contains the line segment between two given
points. However, we show that some of these queries become
definable if one makes small restrictions on the semi-linear sets
considered.
16.
The theory of Liouville functions - Koiran, Pascal
A Liouville function is an analytic function $H: \C \rightarrow
\C$ with a Taylor series $\sumn=1\infty xn/an$ such the
ans form a very fast growing sequence of integers. In this
paper we exhibit the complete first-order theory of the complex
field expanded with H.
17.
Universal graphs at the successor of a singular cardinal - Damonja, Mirna; Shelah, Saharon
The paper is concerned with the existence of a universal graph at
the successor of a strong limit singular ? of cofinality
\aleph0. Starting from the assumption of the existence of a
supercompact cardinal, a model is built in which for some such
? there are ?++ graphs on ?+ that taken jointly
are universal for the graphs on ?+, while $2?+ \gg
?++$.
The paper also addresses the general problem of obtaining a
framework for consistency results at the successor of a singular
strong limit starting from the assumption that a supercompact
cardinal ? exists. The result on the existence of universal
graphs is obtained as a specific application of...
19.
Simulating polyadic modal logics by monadic ones - Goguadze, George; Piazza, Carla; Venema, Yde
We define an interpretation of modal languages with polyadic operators
in modal languages that use monadic operators (diamonds) only.
We also define a simulation operator which associates a logic $\simL$ in the
diamond language with each logic $\La$ in the language with polyadic modal
connectives.
We prove that this simulation operator transfers several useful properties
of modal logics, such as finite/recursive axiomatizability, frame
completeness and the finite model property, canonicity and first-order
definability.
20.
Constructive interpolation in hybrid logic - Blackburn, Patrick; Marx, Maarten
Craigs interpolation lemma (if $?\rightarrow?$ is valid, then
$?\rightarrow?$ and $?\rightarrow?$ are valid, for
? a formula constructed using only primitive symbols which
occur both in ? and ?) fails for many propositional and
first order modal logics. The interpolation property is often
regarded as a sign of well-matched syntax and semantics. Hybrid
logicians claim that modal logic is missing important syntactic
machinery, namely tools for referring to worlds, and that adding such
machinery solves many technical problems. The paper presents strong
evidence for this claim by defining interpolation algorithms for both
propositional and first order hybrid logic. These algorithms produce
interpolants for the hybrid logic of every elementary class of...
1.
