Recursos de colección
White, Graham
We start with Fodor's critique of cognitive science in
"The mind doesn't work that way: The scope
and limits of computational psychology": he argues that much mental activity
cannot be handled by the current methods of cognitive science
because it is nonmonotonic and, therefore, is global in nature,
is not context-free, and is thus not capable of being
formalized by a Turing-like mental architecture. We look at
the use of nonmonotonic logic in the artificial intelligence
community, particularly with the discussion of the so-called
frame problem. The mainstream approach to the frame problem
is, we argue, probably susceptible to Fodor's critique; however,
there is an alternative approach, due to McCain and...
Lipparini, Paolo
We use Shelah's theory of possible cofinalities in order to
solve some problems about ultrafilters. Theorem: Suppose that $\lambda$
is a singular cardinal, $\lambda ' \lessthan \lambda$ , and the ultrafilter $D$
is
$\kappa$
-decomposable for all regular cardinals $\kappa$
with $\lambda '\lessthan \kappa \lessthan \lambda$ . Then $D$
is either
$\lambda$ -decomposable or $\lambda ^+$ -decomposable.
Corollary: If $\lambda$
is a singular cardinal, then
an ultrafilter is ( $\lambda$ , $\lambda$ )-regular
if and only if it is either $\operator{cf} \lambda$ -decomposable
or $\lambda^+$ -decomposable.
We also give applications to topological spaces and to abstract logics.
Kowalski, Tomasz
Humberstone asks whether every theorem of BCI
provably implies $\phi\to\phi$
for some formula $\phi$ .
Meyer conjectures that the axiom $\mathbf{B}$
does not imply any such
"self-implication." We prove a slightly stronger result, thereby
confirming Meyer's conjecture.
Ellison, Ben; Fleischmann, Jonathan; McGinn, Dan; Ruitenburg, Wim
From classical, Fraïissé-homogeneous, ( $\leq \omega$ )-categorical
theories over finite relational languages, we construct intuitionistic
theories that are complete, prove negations of classical tautologies,
and admit quantifier elimination.
We also determine the intuitionistic universal fragments of these theories.
de Bruin, Boudewijn
We develop a logical system that captures two different
interpretations of what extensive games model, and we apply this to a
long-standing debate in game theory between those who defend the
claim that common knowledge of rationality leads to backward
induction or subgame perfect (Nash) equilibria and those who reject
this claim. We show that a defense of the claim à la Aumann
(1995) rests on a conception of extensive game playing as a one-shot
event in combination with a principle of rationality that is
incompatible with it, while a rejection of the claim à la
Reny (1988) assumes a temporally extended, many-moment
interpretation of extensive games in combination with...
Cantwell, John
It is argued that the "inner" negation $\mathord{\sim}$ familiar from 3-valued logic can be interpreted as a form of
"conditional" negation: $\mathord{\sim}$ is read ' $A$ is false if it has a truth value'. It
is argued that this reading squares well with a particular 3-valued
interpretation of a conditional that in the literature has been seen
as a serious candidate for capturing the truth conditions of the
natural language indicative conditional (e.g., "If Jim went to the
party he had a good time"). It is shown that the logic induced by
the semantics shares many familiar properties with classical
negation, but is orthogonal to both intuitionistic and...
Alfeld, Christopher P.
A $\Pi^0_1$ class can be defined as the set of infinite paths through a
computable tree. For classes $P$ and $Q$ , say that $P$ is Medvedev reducible to $Q$ , $P \leq_M Q$ , if there is a computably continuous functional mapping $Q$ into $P$ . Let $\mathcal{L}_M$ be the lattice of degrees formed by $\Pi^0_1$ subclasses of $2^\omega$ under the Medvedev reducibility. In "Non-branching degrees in
the Medvedev lattice of $\Pi \sp{0}\sb{1} classes," I provided a characterization of
nonbranching/branching and a classification of the nonbranching
degrees. In this paper, I present a similar classification of the
branching degrees. In particular, $P$ is separable...
Bridges, Douglas S.
The anti-Specker property, a constructive version of sequential compactness,
is used to prove constructively that a pointwise continuous, order-dense
preference relation on a compact metric space is uniformly sequentially
continuous. It is then shown that Ishihara's principle BD-ℕ implies that a
uniformly sequentially continuous, order-dense preference relation on a
separable metric space is uniformly continuous. Converses of these two
theorems are also proved.
Carter, Nathan C.
It is known that the set of intermediate propositional logics
that can prove their own completeness theorems is exactly those
which prove every instance of the principle of testability,
¬ϕ ∨ ¬¬ϕ. Such logics are called
reflexive. This paper classifies reflexive intermediate logics in
the first-order case: a first-order logic is reflexive if and only
if it proves every instance of the principle of double negation
shift and the metatheory created from it proves every instance of
the principle of testability.
Lokhorst, Gert-Jan C.
We present axiomatizations of the deontic fragment of Anderson's
relevant deontic logic (the logic of obligation and related
concepts) and the eubouliatic fragment of Anderson's eubouliatic
logic (the logic of prudence, safety, risk, and related concepts).
Bellè, D.; Parlamento, F.
Let HF be the collection of the hereditarily finite
well-founded sets and let the primitive language of set theory be
the first-order language which contains binary symbols for
equality and membership only. As announced in a previous paper by
the authors, "Truth in V for
∃^{*}∀∀-sentences is decidable," truth in
HF for ∃^{*}∀∀-sentences of the primitive
language is decidable. The paper provides the proof of that
claim.
Hinnion, Roland; Libert, Thierry
We state the consistency problem of extensional partial set
theory and prove two complementary results toward a definitive
solution. The proof of one of our results makes use of an
extension of the topological construction that was originally
applied in the paraconsistent case.
Binns, Stephen; Kjos-Hanssen, Bjørn; Lerman, Manuel; Schmerl, James H.; Solomon, Reed
We divide the class of infinite computable trees into three
types. For the first and second types, 0' computes a nontrivial
self-embedding while for the third type 0'' computes a nontrivial
self-embedding. These results are optimal and we obtain partial
results concerning the complexity of nontrivial self-embeddings of
infinite computable trees considered up to isomorphism. We show
that every infinite computable tree must have either an infinite
computable chain or an infinite Π^{0}_{1}
antichain. This result is optimal and has connections to the
program of reverse mathematics.
Marcone, Alberto
We study the reverse mathematics of interval orders. We establish
the logical strength of the implications among various definitions
of the notion of interval order. We also consider the strength of
different versions of the characterization theorem for interval
orders: a partial order is an interval order if and only if it does
not contain 2 \oplus 2. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order
if and only if it contains neither 2 \oplus 2 nor 3 \oplus 1.
Sureson, Claude
The archetypal Rumely domain is the ring \widetildeZ of algebraic integers. Its constructible Boolean algebra is atomless. We study
here the opposite situation: Rumely domains whose constructible Boolean
algebra is atomic. Recursive models (which are rings of algebraic
numbers) are proposed; effective model-completeness and decidability of the corresponding theory are proved.
Joosten, Joost J.
A fast consistency prover is a consistent polytime axiomatized theory that has short proofs of the finite consistency statements of any other polytime axiomatized theory. Krajíček and Pudlák have proved that the existence of an optimal propositional proof system is equivalent to the existence of a fast consistency prover. It is an easy observation that NP = coNP implies the existence of a fast consistency prover. The reverse implication is an open question. In this paper we define the notion of an unlikely fast consistency prover and prove that its existence is equivalent to
NP = coNP. Next it is proved...
Ivanov, A.; Majcher, K.
The age of a structure M is the set of all isomorphism types of finite substructures of M. We study ages of generic expansions of
ω-stable ω-categorical structures.
Kummer, Martin; Schaefer, Marcus
An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.
Hirschfeldt, Denis; Miller, Russell; Podzorov, Sergei
We give a straightforward computable-model-theoretic definition of a
property of \Delta^0_2 sets called order-computability. We then
prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.
Scowcroft, Philip
This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.