Accretive and monotone operator theory are central branches of nonlinear functional analysis and constitute the abstract study of certain set-valued mappings between function spaces. This paper deals with the computational properties of these accretive and (generalized) monotone set-valued operators. In particular, we develop (and extend) for this field the theoretical framework of proof mining, a program in mathematical logic that seeks to extract computational information from prima facie “non-computational” proofs from the mainstream literature. To this end, (...) we establish logical metatheorems that guarantee and quantify the computational content of theorems pertaining to accretive and (generalized) monotone set-valued operators. On the one hand, our results unify a number of recent case studies, while they also provide characterizations of central analytical notions in terms of proof theoretic ones on the other, which provides a crucial perspective on needed quantitative assumptions in future applications of proof mining to these branches. (shrink)

We generalize, by a progressive procedure, the notions of conjunction and disjunction of two conditional events to the case of n conditional events. In our coherence-based approach, conjunctions and disjunctions are suitable conditional random quantities. We define the notion of negation, by verifying De Morgan’s Laws. We also show that conjunction and disjunction satisfy the associative and commutative properties, and a monotonicity property. Then, we give some results on coherence of prevision assessments for some families of compounded conditionals; in particular (...) we examine the Fréchet-Hoeffding bounds. Moreover, we study the reverse probabilistic inference from the conjunction Cn+1 of n + 1 conditional events to the family {Cn,En+1|Hn+1}. We consider the relation with the notion of quasi-conjunction and we examine in detail the coherence of the prevision assessments related with the conjunction of three conditional events. Based on conjunction, we also give a characterization of p-consistency and of p-entailment, with applications to several inference rules in probabilistic nonmonotonic reasoning. Finally, we examine some non p-valid inference rules; then, we illustrate by an example two methods which allow to suitably modify non p-valid inference rules in order to get inferences which are p-valid. (shrink)

This article studies the monotonicity behavior of plural determinersthat quantify over collections. Following previous work, we describe thecollective interpretation of determiners such as all, some andmost using generalized quantifiers of a higher type that areobtained systematically by applying a type shifting operator to thestandard meanings of determiners in Generalized Quantifier Theory. Twoprocesses of counting and existential quantification thatappear with plural quantifiers are unified into a single determinerfitting operator, which, unlike previous proposals, both capturesexistential quantification with plural determiners and (...) respects theirmonotonicity properties. However, some previously unnoticed factsindicate that monotonicity of plural determiners is not always preservedwhen they apply to collective predicates. We show that the proposedoperator describes this behavior correctly, and characterize themonotonicity of the collective determiners it derives. It is proved thatdeterminer fitting always preserves monotonicity properties ofdeterminers in their second argument, but monotonicity in the firstargument of a determiner is preserved if and only if it is monotonic inthe same direction in the second argument. We argue that this asymmetryfollows from the conservativity of generalized quantifiers innatural language. (shrink)

The aim of the present paper is to analyse compactness properties of nonmonotonic inference operations within the framework of model theory. For this purpose the concepts of a deductive frame and its semantical counterpart, a semantical frame are introduced. Compactness properties play a fundamental in the study of non-monotonic inference, and in the paper several new versions of compactness are studied.

This paper continues investigations of the monotone fixed point principle in the context of Feferman's explicit mathematics begun in [14]. Explicit mathematics is a versatile formal framework for representing Bishop-style constructive mathematics and generalized recursion theory. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new (...) axiom not merely postulates the existence of a least solution, but, by adjoining a new constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. Let T 0 + UMID denote this extension of explicit mathematics. [14] gave lower bounds for the strength of two subtheories of T 0 + UMID in relating them to fragments of second order arithmetic based on Π 1 2 comprehension. [14] showed that T $_0 \upharpoonright$ + UMID and T $_0 \upharpoonright$ + IND N + UMID have at least the strength of (Π 1 2 - CA) $\upharpoonright$ and (Π 1 2 - CA), respectively. Here we are concerned with the exact reversals. Let UMID N be the monotone fixed-point principle for subclassifications of the natural numbers. Among other results, it is shown that T $_0 \upharpoonright$ + UMID N and T $_0 \upharpoonright$ + IND N + UMID N have the same strength as (Π 1 2 - CA) $\upharpoonright$ and (Π 1 2 - CA), respectively. The results are achieved by constructing set-theoretic models for the aforementioned systems of explicit mathematics in certain extensions of Kripke-Platek set theory and subsequently relating these set theories to subsystems of second arithmetic. (shrink)

Symmetric generalized Galois logics (i.e., symmetric gGl s) are distributive gGl s that include weak distributivity laws between some operations such as fusion and fission. Motivations for considering distribution between such operations include the provability of cut for binary consequence relations, abstract algebraic considerations and modeling linguistic phenomena in categorial grammars. We represent symmetric gGl s by models on topological relational structures. On the other hand, topological relational structures are realized by structures of symmetric gGl s. We generalize the (...) weak distributivity laws between fusion and fission to interactions of certain monotone operations within distributive super gGl s. We are able to prove appropriate generalizations of the previously obtained theorems—including a functorial duality result connecting classes of gGl s and classes of structures for them. (shrink)

The context for this paper is Feferman's theory of explicit mathematics, a formal framework serving many purposes. It is suitable for representing Bishop-style constructive mathematics as well as generalized recursion, including direct expression of structural concepts which admit self-application. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, (...) the new axiom not merely postulates the existence of a least solution, but, by adjoining a new functional constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation. The upshot of the paper is that the latter extension of explicit mathematics (when based on classical logic) embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on Π 1 2 comprehension. (shrink)

We introduce a new class of real-valued monotones in preordered spaces, injective monotones. We show that the class of preorders for which they exist lies in between the class of preorders with strict monotones and preorders with countable multi-utilities, improving upon the known classification of preordered spaces through real-valued monotones. We extend several well-known results for strict monotones (Richter–Peleg functions) to injective monotones, we provide a construction of injective monotones from countable multi-utilities, and relate injective monotones to classic results concerning (...) Debreu denseness and order separability. Along the way, we connect our results to Shannon entropy and the uncertainty preorder, obtaining new insights into how they are related. In particular, we show how injective monotones can be used to generalize some appealing properties of Jaynes’ maximum entropy principle, which is considered a basis for statistical inference and serves as a justification for many regularization techniques that appear throughout machine learning and decision theory. (shrink)

Classical modal logics, based on the neighborhood semantics of Scott and Montague, provide a generalization of the familiar normal systems based on Kripke semantics. This paper defines AGM revision operators on several first-order monotonic modal correspondents, where each first-order correspondence language is defined by Marc Pauly’s version of the van Benthem characterization theorem for monotone modal logic. A revision problem expressed in a monotone modal system is translated into first-order logic, the revision is performed, and the new (...) belief set is translated back to the original modal system. An example is provided for the logic of Risky Knowledge that uses modal AGM contraction to construct counter-factual evidence sets in order to investigate robustness of a probability assignment given some evidence set. A proof of correctness is given. (shrink)

The feasible interpolation theorem for semantic derivations from [J. Krajíček, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62 457–486] allows to derive from some short semantic derivations of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol computing the Karchmer–Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] from (...) [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer–Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Krajíček [Interpolation by a game, Math. Logic Quart. 44 450–458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity. In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle, that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to cutting planes CP, to small width resolution over CP of Krajíček [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63 1582–1596] ) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79 496–525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. (shrink)

We develop some parts of the theory of compact operators from the point of view of computable analysis. While computable compact operators on Hilbert spaces are easy to understand, it turns out that these operators on Banach spaces are harder to handle. Classically, the theory of compact operators on Banach spaces is developed with the help of the non-constructive tool of sequential compactness. We demonstrate that a substantial amount of this theory can be developed computably on (...) Banach spaces with computable Schauder bases that are well-behaved. The conditions imposed on the bases are such that they generalize the Hilbert space case. In particular, we prove that the space of compact operators on Banach spaces with monotone, computably shrinking, and computable bases is a computable Banach space itself and operations such as composition with bounded linear operators from left are computable. Moreover, we provide a computable version of the Theorem of Schauder on adjoints in this framework and we discuss a non-uniform result on composition with bounded linear operators from right. (shrink)

We study positive bilinear forms on a Hilbert space which are not necessarily bounded nor induced by some positive operator. We show when different families of bilinear forms can be described as a generalized effect algebra. In addition, we present families which are or are not monotone downwards (Dedekind upwards) σ-complete generalized effect algebras.

A. Tarski [21] proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering dofeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations (...) is inspired by the results of [11] on finitary nonmonotonic operations, but this paper is self-contained. (shrink)

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ????(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ????(A) can be finite or infinite. We state some general results on ????(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.

Empirical evidence from both utility and psychophysical experiments suggests that people respond quite differently—perhaps discontinuously—to stimulus pairs when one consequence or signal is set to `zero.' Such stimuli are called unitary. The author's earlier theories assumed otherwise. In particular, the key property of segregation relating gambles and joint receipts (or presentations) involves unitary stimuli. Also, the representation of unitary stimuli was assumed to be separable (i.e., multiplicative). The theories developed here do not invoke separability. Four general cases based on two (...) distinctions are explored. The first distinction is between commutative joint receipts, which are relevant to utility, and the non-commutative ones, which are relevant to psychophysics. The second distinction concerns how stimuli of the form (x, C; y) and the operation of joint receipt are linked: by segregation, which mixes stimuli and unitary ones, and by distributivity, which does not involve any unitary stimuli. A class of representations more general than rank-dependent utility (RDU) is found in which monotonic functions of increments U(x)-U(y), where U is an order preseving representation of gambles, and joint receipt play a role. This form and its natural generalization to gambles with n > 2 consequences, which is also axiomatized, appear to encompass models of configural weights and decision affect. When joint receipts are not commutative, somewhat similar representations of stimuli arise, and joint receipts are shown to have a conjoint additive representation and in some cases a constant bias independent of signal intensity is predicted. (shrink)

A. Tarski [22] proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations (...) is inspired by the results of [12] on nonmonotonic inference relations, and relies on some of the definitions found there. (shrink)

We examine recursive monotonic functions on the Lindenbaum algebra of EA. We prove that no such function sends every consistent φ to a sentence with deductive strength strictly between φ and (φ∧Con(φ)). We generalize this result to iterates of consistency into the effective transfinite. We then prove that for any recursive monotonic function f, if there is an iterate of Con that bounds f everywhere, then f must be somewhere equal to an iterate of Con.

There are several areas in logic where the monotonicity of the consequence relation fails to hold. Roughly these are the traditional non-monotonic systems arising in Artificial Intelligence (such as defeasible logics, circumscription, defaults, ete), numerical non-monotonic systems (probabilistic systems, fuzzy logics, belief functions), resource logics (also called substructural logics such as relevance logic, linear logic, Lambek calculus), and the logic of theory change (also called belief revision, see Alchourron, Gärdenfors, Makinson [2224]). We are seeking a common axiomatic and semantical approach (...) to the notion of consequence whieh can be specialised to any of the above areas. This paper introduces the notions of structured consequence relation, shift operators and structural connectives, and shows an intrinsic connection between the above areas. (shrink)

This paper presents a uniform semantic treatment of nonmonotonic inference operations that allow for inferences from infinite sets of premises. The semantics is formulated in terms of selection functions and is a generalization of the preferential semantics of Shoham (1987), (1988), Kraus, Lehman, and Magidor (1990) and Makinson (1989), (1993). A selection function picks out from a given set of possible states (worlds, situations, models) a subset consisting of those states that are, in some sense, the most preferred ones. A (...) proposition α is a nonmonotonic consequence of a set of propositions Γ iff α holds in all the most preferred Γ-states. In the literature on revealed preference theory, there are a number of well-known theorems concerning the representability of selection functions, satisfying certain properties, in terms of underlying preference relations. Such theorems are utilized here to give corresponding representation theorems for nonmonotonic inference operations. At the end of the paper, the connection between nonmonotonic inference and belief revision, in the sense of Alchourrón, Gärdenfors, and Makinson, is explored. In this connection, infinitary belief revision operations that allow for the revision of a theory with a possibly infinite set of propositions are introduced and characterized axiomatically. (shrink)

We present results from numerical studies of supervised learning operations in recurrent networks considered as graphs, leading from a given set of input conditions to predetermined outputs. Graphs that have optimized their output for particular inputs with respect to predetermined outputs are asymptotically stable and can be characterized by attractors which form a representation space for an associative multiplicative structure of input operations. As the mapping from a series of inputs onto a series of such attractors generally depends on the (...) sequence of inputs, this structure is generally noncommutative. Moreover, the size of the set of attractors, indicating the complexity of learning, is found to behave non-monotonically as learning proceeds. A tentative relation between this complexity and the notion of pragmatic information is indicated. (shrink)

The purpose of this note is to make quite clear the relationship between two variants of the general notion of a preferential model for nonmonotonic inference: the models of Kraus, Lehmann and Magidor (KLM models) and those of Makinson (MAK models).On the one hand, we introduce the notion of the core of a KLM model, which suffices to fully determine the associated nonmonotonic inference relation. On the other hand, we slightly amplify MAK models with a monotonic consequence operation as additional (...) ingredient. (shrink)

As we’ve seen in the last chapter, there is good linguistic reason to categorize negations (and negative operators in general) by which De Morgan laws they support. The weakest negative operators (merely downward monotonic) support only two De Morgan laws;1 medium-strength negative operators support a third;2 and strong negative operators support all four. As we’ve also seen, techniques familiar from modal logic are of great use in giving unifying theories of negative operators. In particular, Dunn’s (...) (1990) distributoid theory allows us to generate relational semantics for many negations. However, the requirements of distributoid theory are a bit too strict for use in modeling the weakest negations. For a relational semantics to work, an operator must either distribute or antidistribute over either conjunction or disjunction; but the merely downward monotonic operators do not. Thus, a unifying semantics cannot be had in distributoid theory. In the (more familiar) study of positive modalities, there is a parallel result. Normal necessities distribute over conjunction, and normal possibilities over disjunction. When these distributions break down, a relational semantics is no longer appropriate. Here, there is a somewhat familiar solution: neighborhood semantics. In this chapter, I’ll adapt neighborhood semantics to the less familiar case of negative modalities, showing how it can be used to give a single semantic framework appropriate to all the pertinent sorts of negative operators. (shrink)

Let E be a separable Banach space with separable dual. We show that the operation of subdifferentiation and the inverse operation are Borel from the convex functions on E into the monotone operators on E for the Effros–Borel structures.We also prove that the set of derivatives of differentiable convex functions is coanalytic non-Borel, by using the already known fact that the set of differentiable convex functions is itself coanalytic non-Borel, as proved in Bossard et al. 142).At last, we (...) give a new proof of this latter fact, for reflexive E's, by giving a coanalytic rank on those sets and constructing functions of “high ranks”. This approach, based on an ordinal rank which follows from a construction of trees, is quite different — not so general but actually more constructive — from the previous results of this kind, in Bossard et al. 142) and Godefroy et al. , based on reductions of arbitrary coanalytic or difference of analytic sets to the studied sets. (shrink)

This paper makes the non-monotonicity of a wide range of moral reasoning the basis of a case for particularism. Non-monotonicity threatens practical decision with an overwhelming informational complexity to which a form of ethical generalism seems the best response. It is argued that this impression is wholly misleading: the fact of non-monotonicity is best accommodated by the defence of four related theses in any theory of justification. First, the explanation of and defence of a default/challenge model of justification. Secondly, the (...) development of a theory of epistemic status and an explanation of those unearned entitlements that accrue to such status. Thirdly, an explanation of the basis of epistemic virtues. Finally, an account must be given of the executive capacity of rational decision itself as a ‘contentless ability’. This overall set of views can accommodate a limited role for generalizations about categories of evidence, but not such as to rescue a principled generalism. In particular, the version of particularism defended here explains why one ought not to accept the principled holism that has proved to be a problem for Dancy’s form of particularism. Ethics certainly involves hedged principles. However, principles cannot be self-hedging: there cannot be a that’s it operator in a principle as Richard Holton has claimed that there can be. Practical reasoning is concluded by the categorical detachment of the action-as-conclusion itself. (shrink)

A nucleus is an operation on the collection of truth values which, like double negation in intuitionistic logic, is monotone, inflationary, idempotent and commutes with conjunction. Any nucleus determines a proof-theoretic translation of intuitionistic logic into itself by applying it to atomic formulas, disjunctions and existentially quantified subformulas, as in the Gödel–Gentzen negative translation. Here we show that there exists a similar translation of intuitionistic logic into itself which is more in the spirit of Kuroda’s negative translation. The key (...) is to apply the nucleus not only to the entire formula and universally quantified subformulas, but to conclusions of implications as well. (shrink)

We discuss nonmonotonic reasoning in terms of consequence relations and corresponding operators. Based on the matrix consequence that gives the monotonic case, we define a restricted matrix consequence that illustrates the nonmonotonic case. The latter is a generalization of the relation of logical friendliness introduced by D. Makinson. We prove that any restricted single matrix consequence, although it may be nonmonotonic, is always weakly monotonic and, in the case of a finite matrix, the restricted matrix consequence is very strongly (...) finitary. Further, by modifying the definition of logical friendliness relation formulated specifically in a proof-theoretic manner, we show a possibility of obtaining other reflexive nonmonotonic consequence relations, for which a limited result towards finitariness is proved. This leads to numerous questions about nonmonotonic consequence relations in the segment between the monotonic consequence relation based on intuitionistic propositional logic and logical friendliness. (shrink)

We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts declared “persistent by default”. The focus of the paper is on the relation between this approach and the update semantics recently proposed by Katsuno and Mendelzon. Our contribution in this regard is twofold:We prove a representation theorem for KM semantics in terms of a restricted subfamily of the (...) operators defined by our construction.We show how the KM semantics can be generalized by relaxing our construction in a number of ways, each justified in certain intuitive circumstances and each corresponding to one specific postulate. It follows that there are reasonable update operators outside the KM family.Our approach is not dependent for its plausibility on this connection with KM semantics. Rather, it provides a relatively rich and flexible framework in which the frame and ramification problems can be solved in a systematic way by reasoning about default persistence of facts. (shrink)

We propose a new perspective on logics of computation by combining instantial neighborhood logic INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document} with bisimulation safe operations adapted from PDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PDL}$$\end{document}. INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document} is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a (...) logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve invariance for instantial neighborhood bisimulations, the appropriate bisimulation concept for INL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {INL}$$\end{document}. We also prove that our extended logic IPDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {IPDL}$$\end{document} is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for IPDL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {IPDL}$$\end{document}, and establish its finite model property and decidability. (shrink)

We propose a new perspective on logics of computation by combining instantial neighborhood logic \ with bisimulation safe operations adapted from \. \ is a recent modal logic, based on an extended neighborhood semantics which permits quantification over individual neighborhoods plus their contents. This system has a natural interpretation as a logic of computation in open systems. Motivated by this interpretation, we show that a number of familiar program constructors can be adapted to instantial neighborhood semantics to preserve invariance for (...) instantial neighborhood bisimulations, the appropriate bisimulation concept for \. We also prove that our extended logic \ is a conservative extension of dual-free game logic, and its semantics generalizes the monotone neighborhood semantics of game logic. Finally, we provide a sound and complete system of axioms for \, and establish its finite model property and decidability. (shrink)

Statman and Orevkov independently proved that cut-elimination is of nonelementary complexity. Although their worst-case sequences are mathematically different the syntax of the corresponding cut formulas is of striking similarity. This leads to the main question of this paper: to what extent is it possible to restrict the syntax of formulas and — at the same time—keep their power as cut formulas in a proof? We give a detailed analysis of this problem for negation normal form , prenex normal form and (...) monotone formulas. We show that proof reduction to NNF is quadratic, while PNF behaves differently: although there exists a quadratic transformation into a proof in PNF too, additional cuts are needed; the elimination of these cuts requires nonelementary expense in general. By restricting the logical operators to {,,,}, we obtain the type of monotone formulas. We prove that the elimination of monotone cuts can be of nonelementary complexity . On the other hand, we define a large class of problems where cut-elimination of monotone cuts is only exponential and show that this bound is tight. This implies that the elimination of monotone cuts in equational theories is at most exponential. Particularly, there are no short proofs of Statman's sequence with monotone cuts. (shrink)

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if (...) the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)

Since it is desirable to be able to talk about rational agents forming attitudes toward their concrete agency, we suggest an introduction of doxastic, volitional, and intentional modalities into the multi-agent logic of deliberatively seeing to it that, dstit logic. These modalities are borrowed from the well-known BDI (belief-desire-intention) logic. We change the semantics of the belief and desire operators from a relational one to a monotonic neighbourhood semantic in order to handle ascriptions of conflicting but not inconsistent beliefs (...) and desires as being satisfiable. The proposed bdi-stit logic is defined with respect to branching time frames, and it is shown that this logic is a generalization of a bdi logic based on branching time possible worlds frames (but without temporal operators) and dstit logic. The new bdi-stit logic generalizes bdi and dstit logic in the sense that for any model of bdi or dstit logic, there is an equivalent bdi-stit model. (shrink)

A systematic approach to the algebraic and Kripke semantics for logics with restricted structural rules, notably for logics on an underlying non-distributive lattice, is developed. We provide a new topological representation theorem for general lattices, using the filter space X. Our representation involves a galois connection on subsets of X, hence a closure operator $\Gamma$, and the image of the representation map is characterized as the collection of $\Gamma$-stable, compact-open subsets of the filter space . The original lattice ${\cal L}$ (...) is thus imbedded in the complete lattice of stable sets. The representation is shown to be functorial and is extended to a Stone-type duality. ;In the presence of additional operators, the extension problem is addressed in terms of what we call adjoint completions of normal operators. An operator f on a lattice L is normal if f: $L\sp{} \times \cdots \times L\sp{} \to L\sp{}$ is a monotone map, where each $L\sp{}$, $i \in n$ + 1, is either L or $L\sp{op}$ and f sends finite joins of $L\sp{}$ to joins in $L\sp{}$. Every familiar operator, such as $\circ$ , + , $\gets, \to, \neg, \square$ O is normal. By a uniform argument we show that normal operators $f\sb{i}$ on L extend to operators $F\sb{i}$ on $\Gamma X$ that distribute over arbitrary joins or meets and that \sb{i\in I})$ is a universal such extension. ;We also raise and resolve the question of representability of operators on stable sets by relations. We give an extensive number of examples of representation of specific operators and provide explicit constructions of canonical Kripke frames, based on our extension arguments, for a number of logical systems, notably for Intuitionistic and Classical Linear Logics, or Non-commutative Linear Logic and of fragments thereof. (shrink)

This paper is an attempt to bring together two separated areas of research: classical mathematics and metamathematics on the one side, non-monotonic reasoning on the other. This is done by simulating nonmonotonic logic through antitonic theory extensions. In the first half, the specific extension procedure proposed here is motivated informally, partly in comparison with some well-known non-monotonic formalisms. Operators V and, more generally, U are obtained which have some plausibility when viewed as giving nonmonotonic theory extensions. In the second (...) half, these operators are treated from a mathematical and metamathematical point of view. Here an important role is played by U -closed theories and U -fixed points. The last section contains results on V-closed theories which are specific for V. (shrink)

This paper introduces some of the main components of a novel type theoretical semantics for quantifi- cation with plural noun phrases. This theory, unlike previous ones, sticks to the standard generalized quantifier treatment of singular noun phrases and uses only one lifting operator per semantic category (predicate, quantifier and determiner) for quantification with plurals. Following Bennett (1974), plural individuals are treated as functions of type ¢¡ . Plural nouns and other plural predicates accordingly denote £ ¢¡¥¤¦¡ functions. Such predicates (...) do not match the standard £ ¢¡¥¤ £§£ ¢¡¨¤©¡¥¤ type of determiners. Following Partee and Rooth (1983), type mismatches are resolved using type shifting operators. These operators derive collectivity with plurals, keeping the analysis of singular noun phrases, where no type mismatch arises, as in Barwise and Cooper (1981). A single type shifting operator for determiners combines into one reading the existential shift and the counting (neutral) shift of Scha (1981) and Van der Does (1993). This operator combines the conservativity principle of generalized quantifier theory with Szabolcsi’s (1997) existential quantification over witness sets. The unified lift prevents unmotivated ambiguity as well as the monotonicity ill of existential lifts pointed out by Van Benthem.. (shrink)

In this article, we revisit the classic comparison between Bertrand and Cournot competition in the presence of a cartel of firms that faces outsiders acting individually. This competition setting enables to deal with both non-cooperative and cooperative oligopoly games. We concentrate on industries consisting of symmetrically differentiated products where firms operate at a constant and identical marginal cost. First, while the standard Bertrand–Cournot rankings still hold for Nash equilibrium prices, we show that the results may be altered for Nash equilibrium (...) quantities and profits. Second, we define cooperative Bertrand and Cournot oligopoly games with transferable utility on the basis of their non-cooperative foundation. We establish that the core of a cooperative Cournot oligopoly game is strictly included in the core of a cooperative Bertrand oligopoly game when the number of firms is lower or equal to 25. Moreover, we focus on the aggregate-monotonic core, a subset of the core, that has the advantage to select point solutions satisfying both core selection and aggregate monotonicity properties. We succeed in comparing the aggregate-monotonic cores between Bertrand and Cournot competition regardless of the number of firms. Finally, we study a class of three-firm oligopolies with asymmetric costs in which the core inclusion property mentioned above still holds. We also provide numerical examples to illustrate the difficulty to generalize this result to an arbitrary number of firms because of negative equilibrium quantities. (shrink)

Aravind Joshi famously hypothesized that natural language syntax was characterized (in part) by mildly context-sensitive generative power. Subsequent work in mathematical linguistics over the past three decades has revealed surprising convergences among a wide variety of grammatical formalisms, all of which can be said to be mildly context-sensitive. But this convergence is not absolute. Not all mildly context-sensitive formalisms can generate exactly the same stringsets (i.e. they are not all weakly equivalent), and even when two formalisms can both generate a (...) certain stringset, there might be differences in the structural descriptions they use to do so. It has generally been difficult to find cases where such differences in structural descriptions can be pinpointed in a way that allows linguistic considerations to be brought to bear on choices between formalisms, but in this paper we present one such case. The empirical pattern of interest involves wh-movement dependencies in languages that do not enforce the wh-island constraint. This pattern draws attention to two related dimensions of variation among formalisms: whether structures grow monotonically from one end to another, and whether structure-building operations are conditioned by only a finite amount of derivational state. From this perspective, we show that one class of formalisms generates the crucial empirical pattern using structures that align with mainstream syntactic analysis, and another class can only generate that same string pattern in a linguistically unnatural way. This is particularly interesting given that (i) the structurally-inadequate formalisms are strictly more powerful than the structurally-adequate ones from the perspective of weak generative capacity, and (ii) the formalism based on derivational operations that appear on the surface to align most closely with the mechanisms adopted in contemporary work in syntactic theory (merge and move) are the formalisms that fail to align with the analyses proposed in that work when the phenomenon is considered in full generality. (shrink)

We introduce the notion of complexity, first at an intuitive level and then in relatively more concrete terms, explaining the various characteristic features of complex systems with examples. There exists a vast literature on complexity, and our exposition is intended to be an elementary introduction, meant for a broad audience. -/- Briefly, a complex system is one whose description involves a hierarchy of levels, where each level is made of a large number of components interacting among themselves. The time evolution (...) of such a system is of a complex nature, depending on the interactions among subsystems in the next level below the one under consideration and, at the same time, conditioned by the level above, where the latter sets the context for the evolution. Generally speaking, the interactions among the constituents of the various levels lead to a dynamics characterized by numerous characteristic scales, each level having its own set of scales. What is more, a level commonly exhibits ‘emergent properties’ that cannot be derived from considerations relating to its component systems taken in isolation or to those in a different contextual setting. In the dynamic evolution of some particular level, there occurs a self-organized emergence of a higher level and the process is repeated at still higher levels. -/- The interaction and self-organization of the components of a complex system follow the principle commonly expressed by saying that the ‘whole is different from the sum of the parts’. In the case of systems whose behavior can be expressed mathematically in terms of differential equations this means that the interactions are nonlinear in nature. -/- While all of the above features are not universally exhibited by complex systems, these are nevertheless indicative of a broad commonness relative to which individual systems can be described and analyzed. There exist measures of complexity which, once again, are not of universal applicability, being more heuristic than exact. The present state of knowledge and understanding of complex systems is itself an emerging one. Still, a large number of results on various systems can be related to their complex character, making complexity an immensely fertile concept in the study of natural, biological, and social phenomena. -/- All this puts a very definite limitation on the complete description of a complex system as a whole since such a system can be precisely described only contextually, relative to some particular level, where emergent properties rule out an exact description of more than one levels within a common framework. -/- We discuss the implications of these observations in the context of our conception of the so-called noumenal reality that has a mind-independent existence and is perceived by us in the form of the phenomenal reality. The latter is derived from the former by means of our perceptions and interpretations, and our efforts at sorting out and making sense of the bewildering complexity of reality takes the form of incessant processes of inference that lead to theories. Strictly speaking, theories apply to models that are constructed as idealized versions of parts of reality, within which inferences and abstractions can be carried out meaningfully, enabling us to construct the theories. -/- There exists a correspondence between the phenomenal and the noumenal realities in terms of events and their correlations, where these are experienced as the complex behavior of systems or entities of various descriptions. The infinite diversity of behavior of systems in the phenomenal world are explained within specified contexts by theories. The latter are constructs generated in our ceaseless attempts at interpreting the world, and the question arises as to whether these are reflections of `laws of nature' residing in the noumenal world. This is a fundamental concern of scientific realism, within the fold of which there exists a trend towards the assumption that theories express truths about the noumenal reality. We examine this assumption (referred to as a ‘point of view’ in the present essay) closely and indicate that an alternative point of view is also consistent within the broad framework of scientific realism. This is the view that theories are domain-specific and contextual, and that these are arrived at by independent processes of inference and abstractions in the various domains of experience. Theories in contiguous domains of experience dovetail and interpenetrate with one another, and bear the responsibility of correctly explaining our observations within these domains. -/- With accumulating experience, theories get revised and the network of our theories of the world acquires a complex structure, exhibiting a complex evolution. There exists a tendency within the fold of scientific realism of interpreting this complex evolution in rather simple terms, where one assumes (this, again, is a point of view) that theories tend more and more closely to truths about Nature and, what is more, progress towards an all-embracing ‘ultimate theory’ -- a foundational one in respect of all our inquiries into nature. We examine this point of view closely and outline the alternative view -- one broadly consistent with scientific realism -- that there is no ‘ultimate’ law of nature, that theories do not correspond to truths inherent in reality, and that successive revisions in theory do not lead monotonically to some ultimate truth. Instead, the theories generated in succession are incommensurate with each other, testifying to the fact that a theory gives us a perspective view of some part of reality, arrived at contextually. Instead of resembling a monotonically converging series successive theories are analogous to asymptotic series. -/- Before we summarize all the above considerations, we briefly address the issue of the complexity of the {\it human mind} -- one as pervasive as the complexity of Nature at large. The complexity of the mind is related to the complexity of the underlying neuronal organization in the brain, which operates within a larger biological context, its activities being modulated by other physiological systems, notably the one involving a host of chemical messengers. The mind, with no materiality of its own, is nevertheless emergent from the activity of interacting neuronal assemblies in the brain. As in the case of reality at large, there can be no ultimate theory of the mind, from which one can explain and predict the entire spectrum of human behavior, which is an infinitely rich and diverse one. (shrink)

We present an approach to database update as a form of non monotonic temporal reasoning, the main idea of which is the (circumscriptive) minimization of changes with respect to a set of facts declared persistent by default. The focus of the paper is on the relation between this approach and the update semantics recently proposed by Katsuno and Mendelzon. Our contribution in this regard is twofold: • We prove a representation theorem for KM semantics in terms of a restricted subfamily (...) of the operators defined by our construction. • We show how the KM semantics can be generalized by relaxing our construction in a number of ways, each justified in certain intuitive circumstances and each corresponding to one specific postulate. It follows that there are reasonable update operators outside the KM family. • Our approach is not dependent for its plausibility on this connection with KM semantics. Rather, it provides a relatively rich and flexible framework in which the frame and ramification problems can be solved in a systematic way by reasoning about default persistence of facts. (shrink)

This paper concerns periodic solutions of a class of equations that model gene regulatory networks. Unlike the vast majority of previous studies, it is not assumed that all decay rates are identical. To handle this more general situation, we rely on monotonicity properties of these systems. Under an alternative assumption, it is shown that a classical fixed point theorem for monotone, concave operators can be applied to these systems. The required assumption is expressed in geometrical terms as an (...) alignment condition on so-called focal points . As an application, we show the existence and uniqueness of a stable periodic orbit for negative feedback loop systems in dimension 3 or more, and of a unique stable equilibrium point in dimension 2. This extends a theorem of Snoussi, which showed the existence of these orbits only. (shrink)

Slagging-off is an important preprocessing operation of steel-making to improve the purity of iron. Current manual-operated slag removal schemes are inefficient and labor-intensive. Automatic slagging-off is desirable but challenging as the reliable recognition of iron and slag is difficult. This work focuses on realizing an efficient and accurate recognition algorithm of iron and slag, which is conducive to realize automatic slagging-off operation. Motivated by the recent success of deep learning techniques in smart manufacturing, we introduce deep learning methods to this (...) field for the first time. The monotonous gray value of industry images, poor image quality, and nonrigid feature of iron and slag challenge the existing fully convolutional networks. To this end, we propose a novel spatial and feature graph convolutional network module. SFGCN module can be easily inserted in FCNs to improve the reasoning ability of global contextual information, which is helpful to enhance the segmentation accuracy of small objects and isolated areas. To verify the validity of the SFGCN module, we create an industrial dataset and conduct extensive experiments. Finally, the results show that our SFGCN module brings a consistent performance boost for a wide range of FCNs. Moreover, by adopting a lightweight network as backbone, our method achieves real-time iron and slag segmentation. In the future work, we will dedicate our efforts to the weakly supervised learning for quick annotation of big data stream to improve the generalization ability of current models. (shrink)

Dung’s (1995) argumentation framework takes as input two abstract entities: a set of arguments and a binary relation encoding attacks between these arguments. It returns acceptable sets of arguments, called extensions, w.r.t. a given semantics. While the abstract nature of this setting is seen as a great advantage, it induces a big gap with the application that it is used to. This raises some questions about the compatibility of the setting with a logical formalism (i.e., whether it is possible to (...) instantiate it properly from a logical knowledge base), and about the significance of the various semantics in the application context. In this paper we tackle the above questions. We first propose to fill in the previous gap by extending Dung’s (1995) framework. The idea is to consider all the ingredients involved in an argumentation process. We start with the notion of an abstract monotonic logic which consists of a language (defining the formulas) and a consequence operator. We show how to build, in a systematic way, arguments from a knowledge base formalised in such a logic. We then recall some basic postulates that any instantiation should satisfy. We study how to choose an attack relation so that the instantiation satisfies the postulates. We show that symmetric attack relations are generally not suitable. However, we identify at least one ‘appropriate’ attack relation. Next, we investigate under stable, semi-stable, preferred, grounded and ideal semantics the outputs of logic-based instantiations that satisfy the postulates. For each semantics, we delimit the number of extensions an argumentation system may have, characterise the extensions in terms of subsets of the knowledge base, and finally characterise the set of conclusions that are drawn from the knowledge base. The study reveals that stable, semi-stable and preferred semantics either lead to counter-intuitive results or provide no added value w.r.t. naive semantics. Besides, naive semantics either leads to arbitrary results or generalises the coherence-based approach initially developed by Rescher and Manor (1970). Ideal and grounded semantics either coincide and generalise the free consequence relation developed by Benferhat, Dubois, and Prade (1997), or return arbitrary results. Consequently, Dung’s (1995) framework seems problematic when applied over deductive logical formalisms. (shrink)

This paper revisits intervention effects in Mandarin Chinese why-questions. I present a novel empirical generalization, in which it is shown that the ability for quantifiers to induce intervention hinges upon their monotonicity and their ability to be interpreted as topics. I then propose a semantic account of intervention that correlates topicality with the monotone properties of intervening operators. A crucial assumption in this account is that why-questions in Chinese are idiosyncratic, in that the Chinese equivalent of why directly (...) merges at a high scope position that stays above a propositional argument. Combining the semantic idiosyncrasies of why-questions with the theory of topicality, I conclude that a wide range of intervention phenomena can be explained in terms of interpretation failure. (shrink)

We study the existence of a group of individuals which has some decisive power for social choice correspondences that satisfy a monotonicity property which we call modified monotonicity. And we examine the relation between modified monotonicity and strategy-proofness of social choice correspondences according to the definition by Duggan and Schwartz (2000). We will show mainly the following two results. (1) Modified monotonicity implies the existence of an oligarchy. An oligarchy is a group of individuals such that it has some decisive (...) power (semi-decisiveness), and at least one of the most preferred alternatives of every its member is always chosen by any social choice correspondence. (2) Strategy-proofness of social choice correspondences is equivalent to modified monotonicity. (shrink)

We investigate two formalizations of Optimality Theory, a successful paradigm in linguistics.We first give an order-theoretic counterpart for the data and processinvolved in candidate evaluation.Basically, we represent each constraint as a function that assigns every candidate a degree of violation.As for the second formalization, we define (after Samek-Lodovici and Prince) constraints as operations that select the best candidates out of a set of candidates.We prove that these two formalizations are equivalent (accordingly, there is no loss of generality with using violation (...) marks and dispensing with them is only apparent).Importantly, we show that the second formalization is equivalent with a class of operations over sets of formulas in a given logical language.As a result, we prove that Optimality Theory can be characterized by certain cumulative logics.So, applying Optimality Theory is shown to be reasoning by the rules of cumulative logics. (shrink)

In this paper we apply the idea of Revision Rules, originally developed within the framework of the theory of truth and later extended to a general mode of definition, to the analysis of the arithmetical hierarchy. This is also intended as an example of how ideas and tools from philosophical logic can provide a different perspective on mathematically more “respectable” entities. Revision Rules were first introduced by A. Gupta and N. Belnap as tools in the theory of truth, and they (...) have been further developed to provide the foundations for a general theory of (possibly circular) definitions. Revision Rules are non-monotonic inductive operators that are iterated into the transfinite beginning with some given “bootstrapper” or “initial guess.” Since their iteration need not give rise to an increasing sequence, Revision Rules require a particular kind of operation of “passage to the limit,” which is a variation on the idea of the inferior limit of a sequence. We then define a sequence of sets of strictly increasing arithmetical complexity, and provide a representation of these sets by means of an operator G(x, φ) whose “revision” is carried out over ω2 beginning with any total function satisfying certain relatively simple conditions. Even this relatively simple constraint is later lifted, in a theorem whose proof is due to Anil Gupta. (shrink)

Likert scales are useful for collecting data on attitudes and perceptions from large samples of people. In particular, they have become a well-established tool in soundscape studies for conducting in situ surveys to determine how people experience urban public spaces. However, it is still unclear whether the metrics of the scales are consistently interpreted during a typical assessment task. The current work aims at identifying some general trends in the interpretation of Likert scale metrics and introducing a procedure for the (...) derivation of metric corrections by analyzing a case study dataset of 984 soundscape assessments across 11 urban locations in London. According to ISO/TS 12913-2:2018, soundscapes can be assessed through the scaling of 8 dimensions: pleasant, annoying, vibrant, monotonous, eventful, uneventful, calm, and chaotic. The hypothesis underlying this study is that a link exists between correlations across the percentage of assessments falling in each Likert scale category and a dilation/compression factor affecting the interpretation of the scales metric. The outcome of this metric correction value derivation is introduced for soundscape, and a new projection of the London soundscapes according to the corrected circumplex space is compared with the initial ISO circumplex space. The overall results show a general non-equidistant interpretation of the scales, particularly on the vibrant-monotonous direction. The implications of this correction have been demonstrated through a Linear Ridge Classifier task for predicting the London soundscape responses using objective acoustic parameters, which shows significant improvement when applied to the corrected data. The results suggest that the corrected values account for the non-equidistant interpretation of the Likert metrics, thereby allowing mathematical operations to be viable when applied to the data. (shrink)

Revision operation is the consistent expansion of a theory by a new belief-representing sentence. We consider that in a paraconsistent setting this desideratum can be accomplished in at least three distinct ways: the output of a revision operation should be either non-trivial or non-contradictory (in general or relative to the new belief). In this paper those distinctions will be explored in the constructive level by showing how the remainder sets could be refined, capturing the key concepts of paraconsistency in a (...) dynamical scenario. These are preliminaries results of a wider project on Paraconsistent Belief Change conduced by the authors. (shrink)

There have been a number of publications in recent years on generalising the AGM paradigm to the Horn fragment of propositional logic. Most of them focused on adapting AGM contraction and revision to the Horn setting. It remains an open question whether the adapted Horn contraction and Horn revision are inter-definable as in the AGM case through the Levi and Harper identities. In this paper, we give a positive answer by providing methods for generating contraction and revision from their dual (...) operations. Noticeably, we cannot apply the Levi and Harper identities directly in such methods as the Horn fragment does not fully support negation. To overcome this difficulty, a Horn approximation technique called Horn strengthening is used. We show that Horn contraction generated from Horn revision is always plausible whereas Horn revision generated from Horn contraction is, in general, implausible and, to regain plausibility, the generating contraction has to be properly restricted. (shrink)

For non-additive set functions, the independent product, in general, is not unique and the Fubini theorem is restricted to slice-comonotonic functions. In this paper, we use the representation theorem of Gilboa and Schmeidler (Math Oper Res 20:197–212, 1995) to extend the Möbius product for non-additive set functions to non-finite spaces. We extend the uniqueness result of Ghirardato (J Econ Theory 73:261–291, 1997) for products of two belief functions and weaken the requirements on the marginals necessary to obtain the Fubini property (...) in the product. More importantly, we show that for the Möbius product one side of the Fubini theorem holds for all integrable functions if one of the marginals either is a probability or a convex combination of a chain of unanimity games, i.e., we relax the requirement of slice-comonotonicity and enrich the set of possible applications. (shrink)