Proof-Theoretic Modal PA-Completeness II: The Syntactic Countermodel

This paper is the second part of the syntactic demonstration of the Arithmetical Completeness of the modal system G, the first part of which is presented in [9]. Given a sequent S so that ⊢_GL-LIN S, ⊬_G S, and given its characteristic formula H = char(S), which expresses the non G-provability of S, we construct a canonical proof-tree T of ~ H in GL-LIN, the height of which is the distance d(S, G) of S from G. T is the syntactic countermodel of S with respect to Gand is a tool of general interest in Provability Logic, that allows some classification in the set of the arithmetical interpretations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Proof-Theoretic Modal PA-Completeness I: A System-Sequent Metric

This paper is the first of a series of three articles that present the syntactic proof of the PA-completeness of the modal system G, by introducing suitable proof-theoretic objects, which also have an independent interest. We start from the syntactic PA-completeness of modal system GL-LIN, previously obtained in [7], [8], and so we assume to be working on modal sequents S which are GL-LIN-theorems. If S is not a G-theorem we define here a notion of syntactic metric d(S, G): we calculate a canonical characteristic fomula H of S (char(S)) so that _G H (S) and _GL-LIN H, and the complexity of H gives the distance d(S, G) of S from G. Then, in order to produce the whole completeness proof as an induction on this d(S, G), we introduce the tree-interpretation of a modal sequent Q into PA, that sends the letters of Q into PA-formulas describing the properties of a GL-LIN-proof P of Q: It is also a d(*, G)-metric linked interpretation, since it will be applied to a proof-tree T of H with H = char(S) and ( H) = d(S, G).     

Cut Elimination for GLS Using the Terminability of its Regress Process

The system GLS, which is a modal sequent calculus system for the provability logic GL, was introduced by G. Sambin and S. Valentini in Journal of Philosophical Logic, 11(3), 311–342, (1982), and in 12(4), 471–476, (1983), the second author presented a syntactic cut-elimination proof for GLS. In this paper, we will use regress trees (which are related to search trees) in order to present a simpler and more intuitive syntactic cut derivability proof for GLS₁, which is a (more connectively and inferentially economical) variant of GLS without the cut rule.     

A Routley-Meyer affixing style semantics for logics containing Aristotle's Thesis

We provide a semantics for relevant logics with addition of Aristotle's Thesis, ∼(A→∼A) and also Boethius,(A→B)→∼(A→∼B). We adopt the Routley-Meyer affixing style of semantics but include in the model structures a regulatory structure for all interpretations of formulae, with a view to obtaining a lessad hoc semantics than those previously given for such logics. Soundness and completeness are proved, and in the completeness proof, a new corollary to the Priming Lemma is introduced (c.f.Relevant Logics and their Rivals I, Ridgeview, 1982).     

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.     

A measure for the distance between an interval hypothesis and the truth

The problem of distance from the truth, and more generally distance between hypotheses, is considered here with respect to the case of quantitative hypotheses concerning the value of a given scientific quantity.Our main goal consists in the explication of the concept of distance D(I, ) between an interval hypothesis I and a point hypothesis . In particular, we attempt to give an axiomatic foundation of this notion on the basis of a small number of adequacy conditions.Moreover, the distance function introduced here is employed for the reformulation of the approach to scientific inference — developed by Hintikka, Levi and other scholars — labelled cognitive decision theory. In this connection, we supply a concrete illustration of the rules for inductive acceptance of interval hypotheses that can be obtained on the basis of D(I, ).Lastly, our approach is compared with other proposals made in literature about verisimilitude and distance from the truth.I am grateful for the possibility of spending a period of some months at the Department of Philosophy of University of Gröningen. I profited there a lot from the supervision by Dr. Theo Kuipers. I am also grateful to Prof. Ilkka Niiniluoto who gave rise to my interest in this kind of research during a period spent at Department of Philosophy of University of Helsinki, and who made a number of useful suggestions in the final stage of this paper. Moreover, I would like to thank Dr. Carlo Buttasi for suggesting a better formulation of the proof of (T.24).     

Virtual Modality

Model-theoretic 1-types overa given first-order theory T may be construed as natural metalogical miniatures of G. W. Leibniz' ``complete individual notions', ``substances' or ``substantial forms'. This analogy prompts this essay's modal semantics for an essentiallyundecidable first-order theory T, in which one quantifies over such ``substances' in a boolean universe V(C), where C is the completion of the Lindenbaum-algebra of T.More precisely, one can define recursively a set-theoretic translate of formulae _N of formulae of a normal modal theory T_m based on T, such that the counterpart `<sub>i</sub>' of a the modal variable `x_i' of L(T_m) in this translation-scheme ranges over elements of V(C) that are 1-types of T with value 1 (sometimes called `definite' C-valued 1-types of T).The article's basic completeness-result (2.13) then establishes that varphi; is a theorem of T<sub>m</sub> iff [[ <sub>N</sub> () is aconsequenceof <sub>N</sub> (T<sub>m</sub>) for each extension N of T which is a subtheory of the canonical generic theory (ultrafilter) u]] = 1 – or equivalently, that T<sub>m</sub> is consistent iff[[there is anextension N of T such that N is a subtheory of the canonical generic theory u, and <sub>N</sub>() for all in T<sub>m</sub>]] > 0.The proof of thiscompleteness-result also shows that an N which provides a countermodel for a modally unprovable – or equivalently, a closed set in the Stone space St(T) in the sense of V(C) – is intertranslatable with an `accessibility'-relation of a closely related Kripke-semantics whose `worlds' are generic extensions of an initial universe V via C.This interrelation providesa fairly precise rationale for the semantics' recourse to C-valued structures, and exhibits a sense in which the boolean-valued context is sharp.     

Constructing a covariance matrix that yields a specified minimizer and a specified minimum discrepancy function value

A method is presented for constructing a covariance matrix Σ*₀ that is the sum of a matrix Σ(γ₀) that satisfies a specified model and a perturbation matrix,E, such that Σ*₀=Σ(γ0) +E. The perturbation matrix is chosen in such a manner that a class of discrepancy functionsF(Σ*₀, Σ(γ₀)), which includes normal theory maximum likelihood as a special case, has the prespecified parameter value γ₀ as minimizer and a prespecified minimum δ A matrix constructed in this way seems particularly valuable for Monte Carlo experiments as the covariance matrix for a population in which the model does not hold exactly. This may be a more realistic conceptualization in many instances. An example is presented in which this procedure is employed to generate a covariance matrix among nonnormal, ordered categorical variables which is then used to study the performance of a factor analysis estimator. We are grateful to Alexander Shapiro for suggesting the proof of the solution in section 2.     

A comment on Birnbaum's three-parameter logistic model in the latent trait theory

Birnbaum's three-parameter logistic model for the multiple-choice item in the latent trait theory is considered with respect to the item response information function and the unique maximum condition. It is clarified that with models of knowledge or random guessing nature, which include the three-parameter logistic model, the unique maximum condition is not satisfied for the correct answer, and the item response information function is negative for the interval (− ∞,θ _g ). It is suggested that we should useθ _g as a criterion in selecting optimal items for a specified group of examinees, so that we can practically avoid the possibility of non-unique maxima of the likelihood function on the response pattern given by an examinee in the group. The work described in this paper was partially done while the author was at University of New Brunswick, Canada, in 1968–1970, supported by NRC Grant APA-345 from National Research Council of Canada.     

Lower bounds for the reliability of the total score on a test composed of non-homogeneous items: II: A search procedure to locate the greatest lower bound

Finding the greatest lower bound for the reliability of the total score on a test comprisingn non-homogenous items with dispersion matrix Σ _x is equivalent to maximizing the trace of a diagonal matrix Σ _E with elements θ _I , subject to Σ _E and Σ _T =Σ _x − Σ _E being non-negative definite. The casesn=2 andn=3 are solved explicity. A computer search in the space of the θ _i is developed for the general case. When Guttman's λ₄ (maximum split-half coefficient alpha) is not the g.l.b., the maximizing set of θ _i makes the rank of Σ _T less thann − 1. Numerical examples of various bounds are given. Present affiliation of the first author: St. Hild's College of Education, Durham City, England.     

Computerized assessment of syntactic complexity in Alzheimer’s disease: a case study of Iris Murdoch’s writing

Currently, the majority of investigations of linguistic manifestations of neurodegenerative disorders such as Alzheimer’s disease are conducted based on manual linguistic analysis. Grammatical complexity is one of the language use characteristics sensitive to the effects of Alzheimer’s disease and is difficult to operationalize and measure using manual approaches. In the current study, we demonstrate the application of computational linguistic methods to automate the analysis of grammatical complexity. We implemented the Computerized Linguistic Analysis System (CLAS) based on the Stanford syntactic parser (Klein and Manning, Pattern Recognition, 38(9), 1407–1419, 2005) for longitudinal analysis of changes in syntactic complexity in language affected by neurodegenerative disorders. We manually validated CLAS scoring and used it to analyze writings of Iris Murdoch, a renowned Irish author diagnosed with Alzheimer’s disease. We found clear patterns of decline in grammatical complexity consistent with previous analyses of Murdoch’s writing conducted by Garrard, Maloney, Hodges, and Patterson (Brain, 128(250–260, 2005). CLAS is a fully automated system that may be used to derive objective and reproducible measures of syntactic complexity in language production and can be particularly useful in longitudinal studies with large volumes of language samples.     

Ensuring Positiveness of the Scaled Difference Chi-square Test Statistic

A scaled difference test statistic [(T)\tilde]_d\tilde{T}{}_{d} that can be computed from standard software of structural equation models (SEM) by hand calculations was proposed in Satorra and Bentler (Psychometrika 66:507–514, 2001). The statistic [(T)\tilde]_d\tilde{T}_{d} is asymptotically equivalent to the scaled difference test statistic [`(T)]<sub>d</sub>\bar{T}_{d} introduced in Satorra (Innovations in Multivariate Statistical Analysis: A Festschrift for Heinz Neudecker, pp. 233–247, 2000), which requires more involved computations beyond standard output of SEM software. The test statistic [(T)\tilde]<sub>d</sub>\tilde{T}_{d} has been widely used in practice, but in some applications it is negative due to negativity of its associated scaling correction. Using the implicit function theorem, this note develops an improved scaling correction leading to a new scaled difference statistic [`(T)]_d\bar{T}_{d} that avoids negative chi-square values.     

Effective Cut-elimination for a Fragment of Modal mu-calculus

A non-effective cut-elimination proof for modal mu-calculus has been given by G. J?ger, M. Kretz and T. Studer. Later an effective proof has been given for a subsystem M ₁ with non-iterated fixpoints and positive endsequents. Using a new device we give an effective cut-elimination proof for M ₁ without restriction to positive sequents.     

Sequent Calculi and Decision Procedures for Weak Modal Systems

We investigate sequent calculi for the weak modal (propositional) system reduced to the equivalence rule and extensions of it up to the full Kripke system containing monotonicity, conjunction and necessitation rules. The calculi have cut elimination and we concentrate on the inversion of rules to give in each case an effective procedure which for every sequent either furnishes a proof or a finite countermodel of it. Applications to the cardinality of countermodels, the inversion of rules and the derivability of Löb rules are given.     

Phonological Bases for L2 Morphological Learning

Two experiments examined the hypothesis that L1 phonological awareness plays a role in children’s ability to extract morphological patterns of English as L2 from the auditory input. In Experiment 1, 84 Chinese-speaking third graders were tested on whether they extracted the alternation pattern between the base and the derived form (e.g., inflate – inflation) from multiple exposures. Experiment 2 further assessed children’s ability to use morphological cues for syntactic categorization through exposures to novel morphologically varying forms (e.g., lutate vs. lutant) presented in the corresponding sentential positions (noun vs. verb). The third-grade EFL learners revealed emergent sensitivity to the morphological cues in the input but failed in fully processing intraword variations. The learners with poorer L1 PA were likely to encounter difficulties in identifying morphological alternation rules and in discovering the syntactic properties of L2 morphology. In addition to L1 PA, L2 vocabulary knowledge also contributed significantly to L2 morphological learning.     

Undecidability and intuitionistic incompleteness

Let S be a deductive system such that S-derivability (s) is arithmetic and sound with respect to structures of class K. From simple conditions on K and s, it follows constructively that the K-completeness of s implies MP(S), a form of Markov's Principle. If s is undecidable then MP(S) is independent of first-order Heyting arithmetic. Also, if s is undecidable and the S proof relation is decidable, then MP(S) is independent of second-order Heyting arithmetic, HAS. Lastly, when s is many-one complete, MP(S) implies the usual Markov's Principle MP.An immediate corollary is that the Tarski, Beth and Kripke weak completeness theorems for the negative fragment of intuitionistic predicate logic are unobtainable in HAS. Second, each of these: weak completeness for classical predicate logic, weak completeness for the negative fragment of intuitionistic predicate logic and strong completeness for sentential logic implics MP. Beth and Kripke completeness for intuitionistic predicate or sentential logic also entail MP.These results give extensions of the theorem of Gödel and Kreisel (in [4]) that completeness for pure intuitionistic predicate logic requires MP. The assumptions of Gödel and Kreisel's original proof included the Axiom of Dependent Choice and Herbrand's Theorem, no use of which is explicit in the present article.     

A note on the equivalence of the graded response model and the sequential model

This paper concerns items that consist of several item steps to be responded to sequentially. The item scoreX is defined as the number of correct responses until the first failure. Samejima's graded response model states that each steph=1,...,m is characterized by a parameterb _h , and, for a subject with ability, Pr(Xh; )=F(–b _h ). Tutz's general sequential model associates with each step a parameterdh, and it states that Pr(Xh;)= _r ^=1h G(–d _r ). Tutz's (1991, 1997) conjectures that the models are equivalent if and only ifF(x)=G(x) is an extreme value distribution. This paper presents a proof for this conjecture.     

The Class of Extensions of Nelson's Paraconsistent Logic

The article is devoted to the systematic study of the lattice εN4_⊥ consisting of logics extending N4_⊥. The logic N4_⊥ is obtained from paraconsistent Nelson logic N4 by adding the new constant ⊥ and axioms ⊥ → p, p → ∼ ⊥. We study interrelations between εN4_⊥ and the lattice of superintuitionistic logics. Distinguish in εN4_⊥ basic subclasses of explosive logics, normal logics, logics of general form and study how they are relate. The author acknowledges support by the Alexander von Humboldt-Stiftung and by Counsil for Grants under RF President, project NSh - 2112.2003.1.     

Selective Revision

We introduce a constructive model of selective belief revision in which it is possible to accept only a part of the input information. A selective revision operator ο is defined by the equality K ο α = K * f(α), where * is an AGM revision operator and f a function, typically with the property ⊢ α → f(α). Axiomatic characterizations are provided for three variants of selective revision. This revised version was published online in June 2006 with corrections to the Cover Date.