We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing limitwise monotonic sets on certain domains.

Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering ν of a family is limitwise monotonic (l.m.) if every set is the range of a limitwise monotonic function, uniformly in k. The set of all l.m. numberings of S induces the Rogers semilattice. The semilattices exhibit a peculiar behavior, which puts them in‐between the classical Rogers semilattices (for computable families) and (...) Rogers semilattices of ‐computable families. We show that every Rogers semilattice of a ‐computable family is isomorphic to some semilattice. On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices. In particular, there is an l.m. family S such that is isomorphic to the upper semilattice of c.e. m‐degrees. We prove that if an l.m. family S contains more than one element, then the poset is infinite, and it is not a lattice. The l.m. numberings form an ideal (w.r.t. reducibility between numberings) inside the class of all ‐computable numberings. We prove that inside this class, the index set of l.m. numberings is ‐complete. (shrink)

We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.

The main result is that for sets ${S \subseteq \omega + 1}$ , the following are equivalent: The shuffle sum σ(S) is computable.The set S is a limit infimum set, i.e., there is a total computable function g(x, t) such that ${f(x) = \lim inf_t g(x, t)}$ enumerates S.The set S is a limitwise monotonic set relative to 0′, i.e., there is a total 0′-computable function ${\tilde{g}(x, t)}$ satisfying ${\tilde{g}(x, t) \leq \tilde{g}(x, t+1)}$ such that ${{\tilde{f}(x) = \lim_t (...) \tilde{g}(x, t)}}$ enumerates S.Other results discuss the relationship between these sets and the ${\Sigma^0_3}$ sets. (shrink)

In this article we, given a free ultrafilter p on ω, consider the following classes of ultrafilters:(1) T(p) - the set of ultrafilters Rudin-Keisler equivalent to p,(2) S(p)={q ∈ ω*:∃ f ∈ ω ω , strictly increasing, such that q=f β (p)},(3) I(p) - the set of strong Rudin-Blass predecessors of p,(4) R(p) - the set of ultrafilters equivalent to p in the strong Rudin-Blass order,(5) P RB (p) - the set of Rudin-Blass predecessors of p, and(6) P RK (p) (...) - the set of Rudin-Keisler predecessors of p,and analyze relationships between them. We introduce the semi-P-points as those ultrafilters p ∈ ω* for which P RB (p)=P RK (p), and investigate their relations with P-points, weak-P-points and Q-points. In particular, we prove that for every semi-P-point p its α-th left power α p is a semi-P-point, and we prove that non-semi-P-points exist in ZFC. Further, we define an order ⊴ in T(p) by r⊴q if and only if r ∈ S(q). We prove that (S(p),⊴) is always downwards directed, (R(p),⊴) is always downwards and upwards directed, and (T(p),⊴) is linear if and only if p is selective.We also characterize rapid ultrafilters as those ultrafilters p ∈ ω* for which R(p)∖S(p) is a dense subset of ω*.A space X is M-pseudocompact (for ) if for every sequence (U n ) n < ω of disjoint open subsets of X, there are q ∈ M and x ∈ X such that x=q-lim (U n ); that is, for every neighborhood V of x. The P RK (p)-pseudocompact spaces were studied in [ST].In this article we analyze M-pseudocompactness when M is one of the classes S(p), R(p), T(p), I(p), P RB (p) and P RK (p). We prove that every Frolik space is S(p)-pseudocompact for every p ∈ ω*, and determine when a subspace with is M-pseudocompact. (shrink)

We build an א₁-categorical but not א₀-categorical theory whose only computably presentable model is the saturated one. As a tool, we introduce a notion related to limitwise monotonic functions.

We prove a result relating the author's monotone functional interpretation to the bounded functional interpretation due to Ferreira and Oliva. More precisely we show that largely a solution for the bounded interpretation also is a solution for the monotone functional interpretation although the latter uses the existence of an underlying precise witness. This makes it possible to focus on the extraction of bounds while using the conceptual benefit of having precise realizers at the same time without having to construct them.

We show that a set has an η-representation in a linear order if and only if it is the range of a 0'-computable limitwise monotonic function. We also construct a Δ₃ Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.

$\eta $ -representations are a way of coding sets in computable linear orders that were first introduced by Fellner in his thesis. Limitwise monotonic functions have been used to characterize the sets with $\eta $ -representations, and give characterizations for several variations of $\eta $ -representations. The one exception is the class of sets with strong $\eta $ -representations, the only class where the order type of the representation is unique.We introduce the notion of a connected approximation (...) of a set, a variation on $\Sigma ^0_2$ approximations. We use connected approximations to give a characterization of the many-one degrees of sets with strong $\eta $ -representations as well new characterizations of the variations of $\eta $ -representations with known characterizations. (shrink)

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering, such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.

Several properties of monotone functionals (MF) and monotone majorizable functionals (MMF) used in the earlier work by the author and van de Pol are proved. It turns out that the terms of the simply typed lambda-calculus define MF, but adding primitive recursion, and even monotonic primitive recursion changes the situation: already Z.Z(1 — sg) is not MMF. It is proved that extensionality is not Dialectica-realizable by MMF, and a simple example of a MF which is not hereditarily majorizable is (...) given. (shrink)

In this thesis, we study the least fixed point principle in a constructive setting. A constructive theory of functions and sets has been developed by Feferman. This theory deals both with sets and with functions over sets as independent notions. In the language of Feferman's theory, we are able to formulate the least fixed point principle for monotone inductive definitions as: every operation on classes to classes which satisfies the monotonicity condition has a least fixed point. This is (...) called the principle of monotone inductive definition. Furthermore, we may formulate this principle in a uniform way as: there is an operation which maps a monotone operation to its least fixed point. This is called the principle of uniform monotone inductive definition. Feferman raised the question of the strength of the principle of monotone inductive definition when adjoined to his theory . This question is our primary concern in this thesis. ;Our main results are the consistency of both the principle of monotone inductive definition and the principle of uniform monotone inductive definition adjoined to his theory, and the proof theoretical equivalence between the principle of monotone inductive definition with Feferman's system without the inductive generation axiom and the system of the Pi-one-one Comprehension Axiom. Determination of the proof-theoretical strength of the principle of monotone inductive definition adjoined to Feferman's theory still remains open. ;The consistency of both the principle of monotone inductive definition and the principle of uniform monotone inductive definition with Feferman's theory will be achieved by constructing their models in set theoretical sense. The proof theoretical equivalence between the principle of monotone inductive definition with Feferman's system without the inductive generation axiom and the system of the Pi-one-one Comprehension Axiom can be obtained by a careful examination of the model construction for the principle of monotone inductive definition with Feferman's system without the inductive generation axiom, which is parallel to the model construction for the principle of monotone inductive definition with his theory. (shrink)

In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems ${\cal T}^{\omega} :={\rm G}_n{\rm A}^{\omega} +{\rm AC}$ -qf $+\Delta$ , where (G $_n$ A $^{\omega})_{n \in {\Bbb N}}$ is a hierarchy of (weak) (...) subsystems of arithmetic in all finite types (introduced in [14]), AC-qf is the schema of quantifier-free choice in all types and $\Delta$ is a set of certain analytical principles which e.g. includes the binary König's lemma. We apply this method to show that the arithmetical closures of single instances of $\Pi^0_1$ -comprehension and -choice contribute to the growth of extractable bounds from proofs relative to ${\cal T}^\omega$ only by a primitive recursive functional in the sense of Kleene. In subsequent papers these results are widely generalized and the method is used to determine the arithmetical content of single sequences of instances of the Bolzano-Weierstraß principle for bounded sequences in ${\Bbb R}^d$ , the Ascoli-lemma and others. (shrink)

Given two internal sets X and Y we prove that every Borel function whose graph is a subset of the product X x Y is a member of the least set containing the class of all internal functions and closed with respect to the operations of monotone countable union and intersection. We also prove that any Souslin function can be extended to a Borel function and obtain, as a corollary, a new proof of the recent result of Henson and (...) Ross about the measure preserving property of injective Souslin functions. Further we give a new proof of the fact that injective Borel functions map Borel sets into Borel. A structural result for Souslin graphs all of whose Y-sections are of cardinality n is given. (shrink)

Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely ordered groups that are not weakly o-minimal. We introduce the even more general notion of inp-minimality and prove that in an inp-minimal densely ordered group, every definable unary function is a union of finitely many continuous locally monotonic functions (Theorem 3.2).

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. (shrink)

In view of an enhancement of our implementation on the computer, we explore the possibility of an algorithmic optimization of the various proof-theoretic techniques employed by Kohlenbach for the synthesis of new effective uniform bounds out of established qualitative proofs in Numerical Functional Analysis. Concretely, we prove that the method of “colouring” some of the quantifiers as “non-computational” extends well to ε-arithmetization, elimination-of-extensionality and model-interpretation.

Let $\Omega:= \aleph_1$ . For any $\alpha \Omega:\xi = \omega^\xi\}$ let EΩ (α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let $\alpha^\ast:= \max (E_\Omega(\alpha) \cup \{0\})$ . A function f: εΩ + 1 → Ω is called essentially increasing, if for any $\alpha < \varepsilon_{\Omega + 1}; f(\alpha) \geq \alpha^\ast: f$ is called essentially monotonic, if for any $\alpha,\beta < \varepsilon_{\Omega (...) + 1}$; $\alpha \leq \beta \wedge \alpha^\ast \leq \beta^\ast \Rightarrow f(\alpha) \leq f(\beta).$ Let Clf(0) be the least set of ordinals which contains 0 as an element and which satisfies the following two conditions: (a) $\alpha,\beta \epsilon \mathrm{Cl}_f(0) \Rightarrow \omega^\alpha + \beta \epsilon \mathrm{Cl}_f(0)$ , (b) $E_\Omega\alpha \subseteq \mathrm{Cl}_f(0) \Rightarrow f(\alpha) \epsilon \mathrm{Cl}_f(0)$ . Let ϑεΩ + 1 be the Howard-Bachmann ordinal, which is, for example, defined in [3]. The following theorem is shown: If f:εΩ + 1 → Ω is essentially monotonic and essentially increasing, then the order type of Clf(0) is less than or equal to ϑεΩ + 1. (shrink)

Let h : ℕ → ℚ be a computable function. A real number x is called h-monotonically computable if there is a computable sequence of rational numbers which converges to x h-monotonically in the sense that h|x – xn| ≥ |x – xm| for all n andm > n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h : ℕ → ℚ, we show that the class (...) h-MC coincides with the classes of computable and semi-computable real numbers if and only if Σi∈ℕ) = ∞and the sum Σi∈ℕ) is a computable real number, respectively. On the other hand, if h ≥ 1 and h converges to 1, then h-MC = SC no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h-MC = c-MC. Finally, if h is monotone and unbounded, then h-MC contains all ω-mc real numbers which are g-mc for some computable function g. (shrink)

We study the complexity of proving the Pigeon Hole Principle in a monotone variant of the Gentzen Calculus, also known as Geometric Logic. We prove a size-depth trade-off upper bound for monotone proofs of the standard encoding of the PHP as a monotone sequent. At one extreme of the trade-off we get quasipolynomia -size monotone proofs, and at the other extreme we get subexponential-size bounded-depth monotone proofs. This result is a consequence of deriving the basic properties of certain monotone formulas (...) computing the Boolean threshold functions. We also consider the monotone sequent expressing the Clique-Coclique Principle defined by Bonet, Pitassi and Raz [9]. We show that monotone proofs for this sequent can be easily reduced to monotone proofs of the one-to-one and onto PHP, and so CLIQUE also has quasipolynomia -size monotone proofs. As a consequence of our results, Resolution, Cutting Planes with polynomially bounded coefficients, and Bounded-Depth Frege are exponentially separated from the monotone Gentzen Calculus. Finally, a simple simulation argument implies that these results extend to the Intuitionistic Gentzen Calculus. Our results partially answer some questions left open by P. Pudlák. (shrink)

This paper focuses on the concept of collective essence: that some truths are essential to many items taken together. For example, that it is essential to conjunction and negation that they are truth-functionally complete. The concept of collective essence is one of the main innovations of recent work on the theory of essence. In a sense, this innovation is natural, since we make all sorts of plural predications. It stands to reason that there should be a distinction between essential and (...) accidental plural predications if there is a distinction among singular predications. In this paper I defend the view that the concept of collective essence is governed by the principle of Monotonicity: that something is essential to some items only if it is essential to any items to which they belong. (shrink)

This article presents a parametrized functional interpretation. Depending on the choice of two parameters one obtains well-known functional interpretations such as Gödel's Dialectica interpretation, Diller-Nahm's variant of the Dialectica interpretation, Kohlenbach's monotone interpretations, Kreisel's modified realizability, and Stein's family of functional interpretations. A functional interpretation consists of a formula interpretation and a soundness proof. I show that all these interpretations differ only on two design choices: first, on the number of counterexamples for A which became witnesses for ¬A when defining (...) the formula interpretation and, second, the inductive information about the witnesses of A which is considered in the proof of soundness. Sufficient conditions on the parameters are also given which ensure the soundness of the resulting functional interpretation. The relation between the parametrized interpretation and the recent bounded functional interpretation is also discussed. (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)

This paper has four parts. In the first part, I present Leniewski's protothetics and the complete system provided for that logic by Henkin. The second part presents a generalized notion of partial functions in propositional type theory. In the third part, these partial functions are used to define partial interpretations for protothetics. Finally, I present in the fourth part a complete system for partial protothetics. Completeness is proved by Henkin's method [4] using saturated sets instead of maximally saturated (...) sets. This technique provides a canonical representation of a partial semantic space and it is suggested that this space can be interpreted as an epistemic state of a non-omniscient agent. (shrink)

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)

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)

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 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 embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on $\Pi^1_2$ comprehension. (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)

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 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 $\Pi^1_2$ comprehension. [14] showed that T$_0 \upharpoonright$ + UMID and T$_0 \upharpoonright$ + IND$_\mathbb{N}$ + UMID have at least the strength of $\upharpoonright$ and, respectively. Here we are concerned with the exact reversals. Let UMID$_\mathbb{N}$ be the monotone fixed-point principle for subclassifications of the natural numbers. Among other results, it is shown that T$_0 \upharpoonright$ + UMID$_\mathbb{N}$ and T$_0 \upharpoonright$ + $IND_\mathbb{N}$ + UMID$_\mathbb{N}$ have the same strength as $ $\upharpoonright$ and, 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)

The development of recursion theory motivated Kleene to create regular three-valued logics. Remove it taking his inspiration from the computer science, Fitting later continued to investigate regular three-valued logics and defined them as monotonic ones. Afterwards, Komendantskaya proved that there are four regular three-valued logics and in the three-valued case the set of regular logics coincides with the set of monotonic logics. Next, Tomova showed that in the four-valued case regularity and monotonicity do not coincide. She counted that (...) there are 6400 four-valued regular logics, but only six of them are monotonic. The purpose of this paper is to create natural deduction systems for them. We also describe some functional properties of these logics. (shrink)

There has recently been some literature on the properties of a Health-Related Social Welfare Function (HRSWF). The aim of this article is to contribute to the analysis of the different properties of a HRSWF, paying particular attention to the monotonicity principle. For monotonicity to be fulfilled, any increase in individual health—other things equal—should result in an increase in social welfare. We elicit public preferences concerning trade-offs between the total level of health (concern for efficiency) and its distribution (concern for equality), (...) under different hypothetical scenarios through face-to-face interviews. Of key interests are: the distinction between non-monotonic preferences and Rawlsian preferences; symmetry of HRSWF; and the extent of inequality neutral preferences. The results indicate strong support for non-monotonic preferences, over Rawlsian preferences. Furthermore, the majority of those surveyed had preferences that were consistent with a symmetric and inequality averse HRSWF. (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 prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.

In recent years, proof theoretic transformations that are based on extensions of monotone forms of Gödel’s famous functional interpretation have been used systematically to extract new content from proofs in abstract nonlinear analysis. This content consists both in effective quantitative bounds as well as in qualitative uniformity results. One of the main ineffective tools in abstract functional analysis is the use of sequential forms of weak compactness. As we recently verified, the sequential form of weak compactness for bounded closed and (...) convex subsets of an abstract Hilbert space can be carried out in suitable formal systems that are covered by existing metatheorems developed in the course of the proof mining program. In particular, it follows that the monotone functional interpretation of this weak compactness principle can be realized by a functional Ω∗ definable from bar recursion of lowest type. While a case study on the analysis of strong convergence results that are based on weak compactness indicates that the use of the latter seems to be eliminable, things apparently are different for weak convergence theorems such as the famous Baillon nonlinear ergodic theorem. For this theorem we recently extracted an explicit bound on a metastable version of this theorem that is primitive recursive relative to Ω∗.In the current paper we for the first time give the construction of Ω∗ . As a corollary to the fine analysis of the use of bar recursion in this construction we obtain that Ω∗ elevates arguments in Tn at most to resulting functionals in Tn+2 . In particular, one can conclude from this that our bound on Baillon’s theorem is at least definable in T4. (shrink)

We show that many principles of first-order arithmetic, previously only known to lie strictly between [Formula: see text]-induction and [Formula: see text]-induction, are equivalent to the well-foundedness of [Formula: see text]. Among these principles are the iteration of partial functions of Hájek and Paris, the bounded monotone enumerations principle by Chong, Slaman, and Yang, the relativized Paris–Harrington principle for pairs, and the totality of the relativized Ackermann–Péter function. With this we show that the well-foundedness of [Formula: see text] is (...) a far more widespread than usually suspected. Further, we investigate the [Formula: see text]-iterated version of the bounded monotone iterations principle, and show that it is equivalent to the well-foundedness of the -height [Formula: see text]-tower [Formula: see text]. (shrink)

Any inferential system in which the addition of new premises can lead to the retraction of previous conclusions is a non-monotonic logic. Classical conditional probability provides the oldest and most widely respected example of non-monotonic inference. This paper presents a semantic theory for a unified approach to qualitative and quantitative non-monotonic logic. The qualitative logic is unlike most other non- monotonic logics developed for AI systems. It is closely related to classical (i.e., Bayesian) probability theory. The (...) semantic theory for qualitative non-monotonic entailments extends in a straightforward way to a semantic theory for quantitative partial entailment relations, and these relations turn out to be the classical probability functions. (shrink)

The strong continuity principle reads “every pointwise continuous function from a complete separable metric space to a metric space is uniformly continuous near each compact image.” We show that this principle is equivalent to the fan theorem for monotone \ bars. We work in the context of constructive reverse mathematics.

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes ${\cal E}^{\bot}_n$ similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra ${\cal R}^{\bot}$ generated by continuity preserving operations starting from computable initial (...) functions. Its layers ${\cal R}^{\bot}_n$ are related to those above by showing $\forall n \ge 2.{\cal E}^{\bot}_{n+1} ={\cal R}^{\bot}_n$ , thus generalising results of Schwichtenberg/Müller and Niggl. (shrink)

Executive function has become an important concept in explanations of psychiatric disorders, but we currently lack comprehensive models of normal executive function and of its malfunctions. Here we illustrate how defeasible logical analysis can aid progress in this area. We illustrate using autism and attention deficit hyperactivity disorder (ADHD) as example disorders, and show how logical analysis reveals commonalities between linguistic and non-linguistic behaviours within each disorder, and how contrasting sub-components of executive function are involved across disorders. This analysis reveals (...) how logical analysis is as applicable to fast, automatic and unconscious reasoning as it is to slow deliberate cogitation. (shrink)