The Pentus Theorem for Lambek Calculus with Simple Nonlogical Axioms

The Lambek calculus introduced in Lambek [6] is a strengthening of the type reduction calculus of Ajdukiewicz [1]. We study Associative Lambek Calculus L in Gentzen style axiomatization enriched with a finite set Γ of nonlogical axioms, denoted by L(Γ).It is known that finite axiomatic extensions of Associative Lambek Calculus generate all recursively enumerable languages (see Buszkowski [2]). Then we confine nonlogical axioms to sequents of the form p → q, where p and q are atomic types. For calculus L(Γ) we prove interpolation lemma (modifying the Roorda proof for L [10]) and the binary reduction lemma (using the Pentus method [9] with modification from [3]). In consequence we obtain the weak equivalence of the Context-Free Grammars and grammars based on L(Γ).     

The countable homogeneous universal model of B 2

We give a detailed account of the Algebraically Closed and Existentially Closed members of the second Lee class B ₂ of distributive p-algebras, culminating in an explicit construction of the countable homogeneous universal model of B ₂. The axioms of Schmid [7], [8] for the AC and EC members of B ₂ are reduced to what we prove to be an irredundant set of axioms. The central tools used in this study are the strong duality of Clark and Davey [3] for B ₂ and the method of Clark [2] for constructing AC and EC algebras using a strong duality. Applied to B ₂, this method transfers the entire discussion into an equivalent dual category X ₂ of Boolean spaces which carry a pair of tightly interacting orderings. The doubly ordered spaces of X ₂ prove to be much more readily constructed and analyzed than the corresponding algebras in B ₂.     

The simple substitution property of Gödel's intermediate propositional logics S n 's

The simple substitution property provides a systematic and easy method for proving a theorem from the additional axioms of intermediate prepositional logics. There have been known only four intermediate logics that have the additional axioms with the property. In this paper, we reformulate the many valued logics S' _n defined in Gödel [3] and prove the simple substitution property for them. In our former paper [9], we proved that the sets of axioms composed of one prepositional variable do not have the property except two of them. Here we provide another proof for this theorem.     

Color measurement and color theory: I. Representation theorem for Grassmann structures

For trichromatic color measurement, the empirically based structure consists of the set of colored lights, with its operations of additive mixture and scalar multiplication, and the binary relation of metameric matching. The representing numerical structure is a vector space. The important axioms are Grassmann's laws. The vector representation is constructed in a canonical or coordinate-free manner, mainly using Grassmann's additivity law. Trichromacy is used only to fix the dimensionality.Color theories attempt to get a more unique homomorphism by enriching the basic empirical structure with new empirical relations, subject to new axioms. Examples of such enriching relations include: discriminability or dissimilarity ordering of color pairs; dichromatic matching relations; and unidimensional matching relations, or codes. Representation theorems for the latter two examples are based on Grassmann-type laws also. The relationship between a Grassmann structure and its unidimensional Grassmann codes is modeled by the relationship between a vector space and its dual space of linear functionals. Dual spaces are used to clarify theorems relating to the three-pigment hypothesis and to reduction dichromacy.     

Coherent choice functions under uncertainty

We discuss several features of coherent choice functions—where the admissible options in a decision problem are exactly those that maximize expected utility for some probability/utility pair in fixed set S of probability/utility pairs. In this paper we consider, primarily, normal form decision problems under uncertainty—where only the probability component of S is indeterminate and utility for two privileged outcomes is determinate. Coherent choice distinguishes between each pair of sets of probabilities regardless the “shape” or “connectedness” of the sets of probabilities. We axiomatize the theory of choice functions and show these axioms are necessary for coherence. The axioms are sufficient for coherence using a set of probability/almost-state-independent utility pairs. We give sufficient conditions when a choice function satisfying our axioms is represented by a set of probability/state-independent utility pairs with a common utility.     

Non-Commutative Topology and Quantales

The relationship between q-spaces (c.f. [9]) and quantum spaces (c.f. [5]) is studied, proving that both models coincide in the case of Spec A, the spectrum of a non-commutative C*-algebra A. It is shown that a sober T ₁ quantum space is a classical topological space. This difficulty is circumvented through a new definition of point in a quantale. With this new definition, it is proved that Lid A has enough points. A notion of orthogonality in quantum spaces is introduced, which permits us to express the usual topological properties of separation. The notion of stalks of sheaves over quantales is introduced, and some results in categorial model theory are obtained.     

Projection of a medium

Learning spaces, partial cubes, and preference orderings are just a few of the many structures that can be captured by a ‘medium,’ a set of transformations on a possibly infinite set of states, constrained by four strong axioms. In this paper, we introduce a method for summarizing an arbitrary medium by gathering its states into equivalence classes and treating each equivalence class as a state in a new structure. When the new structure is also a medium, it can be characterized as a projection of the original medium. We show that any subset of tokens from an arbitrary medium generates a projection, and that each state in the projection determines a submedium.     

Partial monotonicity and a new version of the Ramsey test

We introduce two new belief revision axioms: partial monotonicity and consequence correctness. We show that partial monotonicity is consistent with but independent of the full set of axioms for a Gärdenfors belief revision sytem. In contrast to the Gärdenfors inconsistency results for certain monotonicity principles, we use partial monotonicity to inform a consistent formalization of the Ramsey test within a belief revision system extended by a conditional operator. We take this to be a technical dissolution of the well-known Gärdenfors dilemma.In addition, we present the consequential correctness axiom as a new measure of minimal revision in terms of the deductive core of a proposition whose support we wish to excise. We survey several syntactic and semantic belief revision systems and evaluate them according to both the Gärdenfors axioms and our new axioms. Furthermore, our algebraic characterization of semantic revision systems provides a useful technical device for analysis and comparison, which we illustrate with several new proofs.Finally, we have a new inconsistency result, which is dual to the Gärdenfors inconsistency results. Any elementary belief revision system that is consequentially correct must violate the Gärdenfors axiom of strong boundedness (K^*8), which we characterize as yet another monotonicity condition.This work was supported by the McDonnell Douglas Independent Research and Development program.     

A quantum theoretical explanation for probability judgment errors

A quantum probability model is introduced and used to explain human probability judgment errors including the conjunction and disjunction fallacies, averaging effects, unpacking effects, and order effects on inference. On the one hand, quantum theory is similar to other categorization and memory models of cognition in that it relies on vector spaces defined by features and similarities between vectors to determine probability judgments. On the other hand, quantum probability theory is a generalization of Bayesian probability theory because it is based on a set of (von Neumann) axioms that relax some of the classic (Kolmogorov) axioms. The quantum model is compared and contrasted with other competing explanations for these judgment errors, including the anchoring and adjustment model for probability judgments. In the quantum model, a new fundamental concept in cognition is advanced--the compatibility versus incompatibility of questions and the effect this can have on the sequential order of judgments. We conclude that quantum information-processing principles provide a viable and promising new way to understand human judgment and reasoning.     

Big toy models

We pursue a model-oriented rather than axiomatic approach to the foundations of Quantum Mechanics, with the idea that new models can often suggest new axioms. This approach has often been fruitful in Logic and Theoretical Computer Science. Rather than seeking to construct a simplified toy model, we aim for a ??big toy model??, in which both quantum and classical systems can be faithfully represented??as well as, possibly, more exotic kinds of systems. To this end, we show how Chu spaces can be used to represent physical systems of various kinds. In particular, we show how quantum systems can be represented as Chu spaces over the unit interval in such a way that the Chu morphisms correspond exactly to the physically meaningful symmetries of the systems??the unitaries and antiunitaries. In this way we obtain a full and faithful functor from the groupoid of Hilbert spaces and their symmetries to Chu spaces. We also consider whether it is possible to use a finite value set rather than the unit interval; we show that three values suffice, while the two standard possibilistic reductions to two values both fail to preserve fullness.     

Note on two necessary and sufficient axioms for a well-graded knowledge space

We introduce two pedagogically sound axioms for a knowledge structure modeling a student’s learning: outer fringe coherence and learning smoothness. We show that the knowledge structures satisfying these two axioms are equivalent to well-graded knowledge spaces.     

Relational semantics for full linear logic

Relational semantics, given by Kripke frames, play an essential role in the study of modal and intuitionistic logic. In [4] it is shown that the theory of relational semantics is also available in the more general setting of substructural logic, at least in an algebraic guise. Building on these ideas, in [5] a type of frames is described which generalise Kripke frames and provide semantics for substructural logics in a purely relational form.In this paper we study full linear logic from an algebraic point of view. The main additional hurdle is the exponential. We analyse this operation algebraically and use canonical extensions to obtain relational semantics. Thus, we extend the work in [4], [5] and use their approach to obtain relational semantics for full linear logic. Hereby we illustrate the strength of using canonical extension to retrieve relational semantics: it allows a modular and uniform treatment of additional operations and axioms.Traditionally, so-called phase semantics are used as models for (provability in) linear logic [8]. These have the drawback that, contrary to our approach, they do not allow a modular treatment of additional axioms. However, the two approaches are related, as we will explain.     

A characterization of ‘min’ as a procedure for exploiting valued preference relations and related results

This paper is concerned with procedures which transform valued preference relations on a set of alternatives into crisp relations. We present a simple characterization of a procedure that ranks alternatives in decreasing order of their minimal performance. This is done by means of three axioms that are shown to be independent. Among other results, we characterize in a very similar manner a procedure called ‘leximin’ and investigate two families of procedures whose intersection is the ‘min’ procedure.     

Categorizing Smells: A Localist Approach

Humans are poorer at identifying smells and communicating about them, compared to other sensory domains. They also cannot easily organize odor sensations in a general conceptual space, where geometric distance could represent how similar or different all odors are. These two generalities are more or less accepted by psychologists, and they are often seen as connected: If there is no conceptual space for odors, then olfactory identification should indeed be poor. We propose here an important revision to this conclusion: We believe that the claim that there is no odor space is true only if by odor space, one means a conceptual space representing all possible odor sensations, in the paradigmatic sense used for instance for color. However, in a less paradigmatic sense, local conceptual spaces representing a given subset of odors do exist. Thus the absence of a global odor space does not warrant the conclusion that there is no olfactory conceptual map at all. Here we show how a localist account provides a new interpretation of experts and cross-cultural categorization studies: Rather than being exceptions to the poor olfactory identification and communication usually seen elsewhere, experts and cross-cultural categorization are here taken to corroborate the existence of local conceptual spaces.     

The shortest possible length of the longest implicational axiom

A four-valued matrix is presented which validates all theorems of the implicational fragment, IF, of the classical sentential calculus in which at most two distinct sentence letters occur. The Wajsberg/Diamond-McKinsley Theorem for IF follows as a corollary: every complete set of axioms (with substitution and detachment as rules) must include at least one containing occurrences of three or more distinct sentence letters.Additionally, the matrix validates all IF theses built from nine or fewer occurrences of connectives and letters. So the classic result of Jaskovski for the full sentential calculus —that every complete axiom set must contain either two axioms of length at least nine or else one of length at least eleven—can be improved in the implicational case: every complete axiom set for IF must contain at least one axiom eleven or more characters long.Both results are best possible, and both apply as well to most subsystems of IF, e.g., the implicational fragments of the standard relevance logics, modal logics, the relatives of implicational intutionism, and logics in the ukasiewicz family.Earlier proofs of these results, utilizing a five-valued matrix built from the product matrix of C2 with itself via the method of [8], were obtained in 1988 while the author was a Visiting Research Fellow at the Automated Reasoning Project, Research School of Social Sciences, Australian National University, and were presented in [9]. The author owes thanks to the RSSS for creating the Project, and to the members of the Project generally for the stimulating atmosphere they created in turn, but especially to Robert K. Meyer for making the visit possible, and for many discussions over the years.     

关于Erdos-Moser定理的研究

本文主要研究Erdos-Moser定理。在简单介绍了反推数学的一些基础知识后,首先研究了Erdos-Moser定理的证明论强度：存在一个可计算的二元二染色函数使得任何无穷∑20集合都不是该函数的传递集,同时存在一个可计算的二元二染色函数使得每一个该函数的无穷传递集都是超免疫的。其次,我们进一步考虑了稳定性Erdos—Moser定理,证明了在二阶算术子系统RCA0下稳定性Erdos-Moser定理是不可证的并且对每一个可计算的稳定性二色二阶函数,我们构造了一个Ф’可计算的无穷传递集。     

Elementary school children’s attentional biases in physical and numerical space

Numbers are conceptualized spatially along a horizontal mental line. This view is supported by mounting evidence from healthy adults and patients with unilateral spatial neglect. Little is known about children's representation of numbers with respect to space. This study investigated elementary school children's directional biases in physical and numerical space to better understand the relation between space and number. We also examined the nature of spatial organization in numerical space. In two separate tasks, children (n = 57) were asked to bisect a physical line and verbally estimate the midpoint of number pairs. In general, results indicated leftward biases in both tasks, but the degree of deviation did not correlate between the tasks. In the number bisection task, leftward bias (underestimating the midpoint) increased as a function of numerical magnitude and interval between number pairs. In contrast, a rightward deviation was found for smaller number pairs. These findings suggest that different underlying spatial attentional mechanisms might be directed in physical and numerical space in young school children, which would be integrated in adulthood.     

A conjunction in closure spaces

This paper is closely related to investigations of abstract properties of basic logical notions expressible in terms of closure spaces as they were begun by A. Tarski (see [6]). We shall prove many properties of ω-conjunctive closure spaces (X is ω-conjunctive provided that for every two elements of X their conjunction in X exists). For example we prove the following theorems:

1. For every closed and proper subset of an ω-conjunctive closure space its interior is empty (i.e. it is a boundary set).
2. If X is an ω-conjunctive closure space which satisfies the ω-compactness theorem and \(\hat P\) [X] is a meet-distributive semilattice (see [3]), then the lattice of all closed subsets in X is a Heyting lattice.
3. A closure space is linear iff it is an ω-conjunctive and topological space.
4. Every continuous function preserves all conjunctions.

     

Second-Order Quantifier Elimination in Higher-Order Contexts with Applications to the Semantical Analysis of Conditionals

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we first generalize the result of Nonnengart and Szałas [17] by allowing second-order variables to appear within higher-order contexts. Then we focus on a semantical analysis of conditionals, using the introduced technique and Gabbay’s semantics provided in [10] and substantially using a third-order accessibility relation. The analysis is done via finding correspondences between axioms involving conditionals and properties of the underlying third-order relation. Presented by Wojciech Buszkowski     

Analysis of multinomial models under inequality constraints: Applications to measurement theory

Multinomial random variables are used across many disciplines to model categorical outcomes. Under this framework, investigators often use a likelihood ratio test to determine goodness-of-fit. If the permissible parameter space of such models is defined by inequality constraints, then the maximum likelihood estimator may lie on the boundary of the parameter space. Under this condition, the asymptotic distribution of the likelihood ratio test is no longer a simple χ² distribution. This article summarizes recent developments in the constrained inference literature as they pertain to the testing of multinomial random variables, and extends existing results by considering the case of jointly independent mutinomial random variables of varying categorical size. This article provides an application of this methodology to axiomatic measurement theory as a means of evaluating properly operationalized measurement axioms. This article generalizes Iverson and Falmagne’s [Iverson, G. J. & Falmagne, J. C. (1985). Statistical issues in measurement. Mathematical Social Sciences, 10, 131-153] seminal work on the empirical evaluation of measurement axioms and provides a classical counterpart to Myung, Karabatsos, and Iverson’s [Myung, J. I., Karabatsos, G. & Iverson, G. J. (2005). A Bayesian approach to testing decision making axioms. Journal of Mathematical Psychology, 49, 205-225] Bayesian methodology on the same topic.