How to eliminate self-reference: a précis

We provide a systematic recipe for eliminating self-reference from a simple language in which semantic paradoxes (whether purely logical or empirical) can be expressed. We start from a non-quantificational language L which contains a truth predicate and sentence names, and we associate to each sentence F of L an infinite series of translations h ₀(F), h ₁(F), ..., stated in a quantificational language L ^*. Under certain conditions, we show that none of the translations is self-referential, but that any one of them perfectly mirrors the semantic behavior of the original. The result, which can be seen as a generalization of recent work by Yablo (1993, Analysis, 53, 251–252; 2004, Self-reference, CSLI) and Cook (2004, Journal of Symbolic Logic, 69(3), 767–774), shows that under certain conditions self-reference is not essential to any of the semantic phenomena that can be obtained in a simple language.     

Valuation Semantics for First-Order Logics of Evidence and Truth

This paper introduces the logic QLET_F, a quantified extension of the logic of evidence and truth LET_F, together with a corresponding sound and complete first-order non-deterministic valuation semantics. LET_F is a paraconsistent and paracomplete sentential logic that extends the logic of first-degree entailment (FDE) with a classicality operator ∘ and a non-classicality operator ∙, dual to each other: while ∘A entails that A behaves classically, ∙A follows from A’s violating some classically valid inferences. The semantics of QLET_F combines structures that interpret negated predicates in terms of anti-extensions with first-order non-deterministic valuations, and completeness is obtained through a generalization of Henkin’s method. By providing sound and complete semantics for first-order extensions of FDE, K3, and LP, we show how these tools, which we call here the method of anti-extensions + valuations, can be naturally applied to a number of non-classical logics.

     

All Proper Normal Extensions of S5-square have the Polynomial Size Model Property

We show that every proper normal extension of the bi-modal system S5 ² has the poly-size model property. In fact, to every proper normal extension L of S5 ² corresponds a natural number b(L) - the bound of L. For every L, there exists a polynomial P(·) of degree b(L) + 1 such that every L-consistent formula is satisfiable on an L-frame whose universe is bounded by P(||), where || denotes the number of subformulas of . It is shown that this bound is optimal.     

The Elimination of Self-Reference: Generalized Yablo-Series and the Theory of Truth

Although it was traditionally thought that self-reference is a crucial ingredient of semantic paradoxes, Yablo (1993, 2004) showed that this was not so by displaying an infinite series of sentences none of which is self-referential but which, taken together, are paradoxical. Yablo’s paradox consists of a countable series of linearly ordered sentences s(0), s(1), s(2),... , where each s(i) says: For each k > i, s(k) is false (or equivalently: For no k > i is s(k) true). We generalize Yablo’s results along two dimensions. First, we study the behavior of generalized Yablo-series in which each sentence s(i) has the form: For Q k > i, s(k) is true, where Q is a generalized quantifier (e.g., no, every, infinitely many, etc). We show that under broad conditions all the sentences in the series must have the same truth value, and we derive a characterization of those values of Q for which the series is paradoxical. Second, we show that in the Strong Kleene trivalent logic Yablo’s results are a special case of a more general fact: under certain conditions, any semantic phenomenon that involves self-reference can be emulated without self-reference. Various translation procedures that eliminate self-reference from a non-quantificational language are defined and characterized. An Appendix sketches an extension to quantificational languages, as well as a new argument that Yablo’s paradox and the translations we offer do not involve self-reference.     

The Undecidability of Iterated Modal Relativization

In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 ¹₁–complete. Two of these fragments do not include transitive closure. We also show that the question of whether a sentence in these fragments has a finite (tree) model is fi0 ⁰₁–complete. These results go via reduction to problems concerning domino systems.     

Martin's Axiom,Omitting Types,and Complete Representations in Algebraic Logic

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin's axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey's omitting types theorem fails for L _n, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. L _n has been recently (and quite extensively) studied as a many-dimensional modal logic.     

Processing doubly quantified sentences: Evidence from eye movements

We investigated the processing of doubly quantified sentences, such asKelly showed a photo to every critic, that are ambiguous as to whether the indefinite (a photo) specifies single or multiple referents. Ambiguity resolution requires the computation of relative quantifier scope: Whether a or every takes wide scope, thereby determining how many entities or events are to be represented. In an eye-tracking experiment, we manipulated quantifier order and whether continuations were singular or plural, for constructions with the direct or the indirect object occurring first. We obtained effects consistent with the on-line processing of relative scope at the doubly quantified phrase and considered two possible explanations for a preference for singular continuations to the quantified sentence. We conclude that relative quantifier scope is computed on line during reading but may not be a prerequisite for the resolution of definite anaphors, unless required by secondary tasks.     

Vortex dynamics in La1.86Sr0. 14CuO4 studied by magnetoresistivity

Abstract

Vortex dynamics in La_1.86Sr_0.14CuO₄ have been studied by the measurement of ρ_c ^//i (T, H), where ρ_c ^//i is the c-axis resistivity for H//i (i = c or a-b). We argue that, at temperatures higher than the irreversibility temperature T _irr, the usual vortex picture breaks down owing to the thermal motion of vortices, resulting in a T- and T _in-dependent anisotropic parameter γ. After taking into account the dependence of γ on T and T _irr, we show that at each given temperature we can rescale the ρ_c ^//a-b (T, H) data onto the corresponding ρ_c ^//c (T, H) curves. This scaling property clearly indicates that the Lorentz-force-free mechanism is responsible for ρ_c ^//a-b (T, H). Furthermore, we also show that the measured ρ_c ^//a-b (T, H) data can be explained in terms of the recently developed extended Josephson coupling model which is verified by rescaling ρ_c ^//a-b (T) data for various fields onto a single curve.     

Intermediate logics with the same disjunctionless fragment as intuitionistic logic

Given an intermediate prepositional logic L, denote by L ^–d its disjuctionless fragment. We introduce an infinite sequence {J _n}_n1 of propositional formulas, and prove:(1)For any L: L ^–d =I ^–d (I=intuitionistic logic) if and only if J _n L for every n 1.Since it turns out that L{J _{n} n}1 = Ø for any L having the disjunction property, we obtain as a corollary that L ^–d = I ^–d for every L with d.p. (cf. open problem 7.19 of [5]). Algebraic semantic is used in the proof of the if part of (1). In the last section of the paper we provide a characterization in Kripke's semantic for the logics J _n =I+ +J _n (n 1).     

A group-theoretical invariant for elementary equivalence and its role in representations of elementary classes

There is a natural map which assigns to every modelU of typeτ, (U ε St^τ) a groupG (U) in such a way that elementarily equivalent models are mapped into isomorphic groups.G(U) is a subset of a collection whose members are called Fraisse arrows (they are decreasing sequences of sets of partial isomorphisms) and which arise in connection with the Fraisse characterization of elementary equivalence. LetEC _λ ^U be defined as {U εStr ^τ: ℬ ≡U and |ℬ|=λ; thenEG _λ ^U can be faithfully (i.e. 1-1) represented onto G(U) ×π ^*, whereπ ^*, is a collection of partitions over λ∪λ²∪....     

Pure Extensions, Proof Rules, and Hybrid Axiomatics

In this paper we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic.A preliminary version of this paper was presented at the fifth conference on Advances in Modal Logic (AiML 2004) in Manchester. We would like to thank Maarten Marx for his comments on an early draft and Agnieszka Kisielewska for help with the proof reading.Special Issue Ways of Worlds II. On Possible Worlds and Related Notions Edited by Vincent F. Hendricks and Stig Andur Pedersen     

Satisfying Predicates: Kleene's Proof of the Hilbert–Bernays Theorem

The Hilbert–Bernays Theorem establishes that for any satisfiable first-order quantificational schema S, one can write out linguistic expressions that are guaranteed to yield a true sentence of elementary arithmetic when they are substituted for the predicate letters in S. The theorem implies that if L is a consistent, fully interpreted language rich enough to express elementary arithmetic, then a schema S is valid if and only if every sentence of L that can be obtained by substituting predicates of L for predicate letters in S is true. The theorem therefore licenses us to define validity substitutionally in languages rich enough to express arithmetic. The heart of the theorem is an arithmetization of Gödel's completeness proof for first-order predicate logic. Hilbert and Bernays were the first to prove that there is such an arithmetization. Kleene established a strengthened version of it, and Kreisel, Mostowski, and Putnam refined Kleene's result. Despite the later refinements, Kleene's presentation of the arithmetization is still regarded as the standard one. It is highly compressed, however, and very difficult to read. My goals in this paper are expository: to present the basics of Kleene's arithmetization in a less compressed, more easily readable form, in a setting that highlights its relevance to issues in the philosophy of logic, especially to Quine's substitutional definition of logical truth, and to formulate the Hilbert–Bernays Theorem in a way that incorporates Kreisel's, Mostowski's, and Putnam's refinements of Kleene's result.     

Quantifiers and Congruence Closure

We prove some results about the limitations of the expressive power of quantifiers on finite structures. We define the concept of a bounded quantifier and prove that every relativizing quantifier which is bounded is already first-order definable (Theorem 3.8). We weaken the concept of congruence closed (see [6]) to weakly congruence closed by restricting to congruence relations where all classes have the same size. Adapting the concept of a thin quantifier (Caicedo [1]) to the framework of finite structures, we define the concept of a meager quantifier. We show that no proper extension of first-order logic by means of meager quantifiers is weakly congruence closed (Theorem 4.9). We prove the failure of the full congruence closure property for logics which extend first-order logic by means of meager quantifiers, arbitrary monadic quantifiers, and the Härtig quantifier (Theorem 6.1).     

Semantic representations as procedures for verification

Doubly quantified sentences can be ambiguous (Every man knows some woman) or unambiguous (Every man knows every woman). For active and passive sentences of these types, we elicited from subjects three types of judgments designed to reflect which quantifier they assigned wide scope in interpreting the sentence. There was a strong tendency for the three measures to agree, and for these agreements to fall on the surface structure subject of the sentence, independent of sentence type. The data are interpreted as showing a tendency for the first quantifier to include the second within its scope; thus for both ambiguous and unambiguous sentence types active sentences tend to be interpreted differently from their passive transforms. A semantic theory adequate to capture this phenomenon must assign sentences semantic representations specifying not only truth-conditions but also procedures for verification.     

A syntactical approach to modality

Conclusion The systems T _N and T _M show that necessity can be consistently construed as a predicate of syntactical objects, if the expressive/deductive power of the system is deliberately engineered to reflect the power of the original object language operator. The system T _N relies on salient limitations on the expressive power of the language L _N through the construction of a quotational hierarchy, while the system T _Mrelies on limiting the scope of the modal axioms schemas to the sublanguage L _infM ⁺, which corresponds exactly with the restrictive hierarchy of L _N. The fact that L _infM ⁺ is identical to the image of the metalinguistic mapping C ⁺ from the normal operator system into L _M reveals that iterated operator modality is implicitly hierarchical, and that inconsistency is produced by applying the principles of the modal logic to formulas which have no natural analogues in the operator development. Thus the contradiction discovered by Montague can be diagnosed as the result of instantiating the axiom schemas with modally ungrounded formulas, and thereby adding radically new modal axioms to the predicate system.The predicate treatment of necessity differs significantly from that of the operator in that the cumulative models for the predicate system are strictly first-order. Possible worlds are not used as model-theoretic primitives, but rather alternate models are appealed to in order to specify the extension of N, which is semantically construed as a first-order predicate. In this manner, the intensional aspects of modality are built into the mode of specifying the particular set of objects which the denotation function assigns to N, rather than in the specification of the basic truth conditions for modal formulas. Intensional phenomena are thereby localised to the special requirements for determining the extension of a particular predicate, and this does not constitute a structural modification of the first-order models, but rather limits the relevant class of models to those which possess an appropriate denotation function.     

Methodological appraisals, advice, and historiographical models

In the paper I examine (Section I) the best defense for the claim that methodologies shouldnot function heuristically (thesis-LW) as it appears in John Worrall. I then evaluate (Section II) his proposal of a criterion^* M which is offered as a criterion for evaluating competing methodologies such as falsificationism, conventionalism, methodology of research programmes. etc. Finally, I consider (Section III) the consequences of arguments presented earlier (Section I and II) as they bear on the problem of selecting a historiographical model.I argue, among other things, (I) that thesis-LW is defended on some very dubious assumptions; (II) that Worrall's criterion^* M falters under three clear cases two of which at least^*M should accomodate, and that part of^* M's failure can be linked to its being hooked to thesis-LW. By arguments analogous to the ones which serve^* M, I show thatcontra John Worrall and John Watkins, thesis-LW is testable; finally, (III) if we accept arguments for thesis-LW and^* M we are left with a skeptical conclusion with respect to the choice of a historiographical model which Worrall by parity of reasoning should accept, but does not.     

A First Order Nonmonotonic Extension of Constructive Logic

Certain extensions of Nelson's constructive logic N with strong negation have recently become important in arti.cial intelligence and nonmonotonic reasoning, since they yield a logical foundation for answer set programming (ASP). In this paper we look at some extensions of Nelson's .rst-order logic as a basis for de.ning nonmonotonic inference relations that underlie the answer set programming semantics. The extensions we consider are those based on 2-element, here-and-there Kripke frames. In particular, we prove completeness for .rst-order here-and-there logics, and their minimal strong negation extensions, for both constant and varying domains. We choose the constant domain version, which we denote by QN^c₅, as a basis for de.ning a .rst-order nonmonotonic extension called equilibrium logic. We establish several metatheoretic properties of QN^c₅, including Skolem forms and Herbrand theorems and Interpolation, and show that the .rst-oder version of equilibrium logic can be used as a foundation for answer set inference.     

A 2-categorial Generalization of the Concept of Institution

After defining, for each many-sorted signature Σ = (S, Σ), the category Ter(Σ), of generalized terms for Σ (which is the dual of the Kleisli category for \mathbb T_S{\mathbb {T}_{\bf \Sigma}}, the monad in Set ^S determined by the adjunction T_S \dashv G_S{{\bf T}_{\bf \Sigma} \dashv {\rm G}_{\bf \Sigma}} from Set ^S to Alg(Σ), the category of Σ-algebras), we assign, to a signature morphism d from Σ to Λ, the functor d_à{{\bf d}_\diamond} from Ter(Σ) to Ter(Λ). Once defined the mappings that assign, respectively, to a many-sorted signature the corresponding category of generalized terms and to a signature morphism the functor between the associated categories of generalized terms, we state that both mappings are actually the components of a pseudo-functor Ter from Sig to the 2-category Cat. Next we prove that there is a functor Tr^Σ, of realization of generalized terms as term operations, from Alg(Σ) × Ter(Σ) to Set, that simultaneously formalizes the procedure of realization of generalized terms and its naturalness (by taking into account the variation of the algebras through the homomorphisms between them). We remark that from this fact we will get the invariance of the relation of satisfaction under signature change. Moreover, we prove that, for each signature morphism d from Σ to Λ, there exists a natural isomorphism θ ^d from the functor Tr^L °(Id ×d_à){{{\rm Tr}^{\bf {\bf \Lambda}} \circ ({\rm Id} \times {\bf d}_\diamond)}} to the functor Tr^S °(d^* ×Id){{\rm Tr}^{\bf \Sigma} \circ ({\bf d}^* \times {\rm Id})}, both from the category Alg(Λ) × Ter(Σ) to the category Set, where d* is the value at d of the arrow mapping of a contravariant functor Alg from Sig to Cat, that shows the invariant character of the procedure of realization of generalized terms under signature change. Finally, we construct the many-sorted term institution by combining adequately the above components (and, in a derived way, the many-sorted specification institution), but for a strict generalization of the standard notion of institution.     

The pseudodiagnosticity trap: Should participants consider alternative hypotheses?

The pseudodiagnosticity task has been used as an example of the tendency on the part of participants to incorrectly assess Bayesian constraints in assessing data, and as a failure to consider alternative hypotheses in a probabilistic inference task. In the task, participants are given one value, the anchor value, corresponding to P(D1|H) and may choose one other value, either P(D1|¬!H), P(D2|H), or P(D2|not;!H). Most participants select P(D2|H), or P(D2|¬!H) which have been considered inappropriate (and called pseudodiagnostic) because only P(D1|¬!H) allows use of Bayes' theorem. We present a new analysis based on probability intervals and show that selection of either P(D2|H), or P(D2|¬!H) is in fact pseudodiagnostic, whereas choice of P(D1|¬!H) is diagnostic. Our analysis shows that choice of the pseudodiagnostic values actually increases uncertainty regarding the posterior probability of H, supporting the original interpretation of the experimental findings on the pseudodiagnosticity task. The argument illuminates the general proposition that evolutionarily adaptive heuristics for Bayesian inference can be misled in some task situations.     

A linear conservative extension of Zermelo-Fraenkel set theory

In this paper, we develop the system LZF of set theory with the unrestricted comprehension in full linear logic and show that LZF is a conservative extension of ZF^– i.e., the Zermelo-Fraenkel set theory without the axiom of regularity. We formulate LZF as a sequent calculus with abstraction terms and prove the partial cut-elimination theorem for it. The cut-elimination result ensures the subterm property for those formulas which contain only terms corresponding to sets in ZF^–. This implies that LZF is a conservative extension of ZF^– and therefore the former is consistent relative to the latter. Hiroakira Ono