CZF does not have the existence property

Constructive theories usually have interesting metamathematical properties where explicit witnesses can be extracted from proofs of existential sentences. For relational theories, probably the most natural of these is the existence property, EP, sometimes referred to as the set existence property  . This states that whenever (∃x)?(x)$(\exists x)?(x)$ is provable, there is a formula χ(x)$\chi (x)$ such that (∃!x)?(x)∧χ(x)$(\exists !x)?(x)\wedge \chi (x)$ is provable. It has been known since the 80s that EP holds for some intuitionistic set theories and yet fails for IZF. Despite this, it has remained open until now whether EP holds for the most well known constructive set theory, CZF. In this paper we show that EP fails for CZF.     

Generic global rigidity of body–bar frameworks

A basic geometric question is to determine when a given framework G(p)$G(\mathbf{p})$ is globally rigid in Euclidean space R^d${\mathbb{R}}^d$, where G is a finite graph and p is a configuration of points corresponding to the vertices of G  . G(p)$G(\mathbf{p})$ is globally rigid in  R^d${\mathbb{R}}^d$ if for any other configuration q for G   such that the edge lengths of G(q)$G(\mathbf{q})$ are the same as the corresponding edge lengths of G(p)$G(\mathbf{p})$, then p is congruent to q. A framework G(p)$G(\mathbf{p})$ is redundantly rigid, if it is rigid and it remains rigid after the removal of any edge of G.     

Consistency,optimality, and incompleteness

Assume that the problem _P0$P_0$ is not solvable in polynomial time. Let T   be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{_ConT}$T\cup \{{\mathit{Con}}_T\}$ as the minimal extension of T   proving for some algorithm that it decides _P0$P_0$ as fast as any algorithm B$\mathbb{B}$ with the property that T   proves that B$\mathbb{B}$ decides _P0$P_0$. Here, _ConT${\mathit{Con}}_T$ claims the consistency of T. As a byproduct, we obtain a version of Gödel?s Second Incompleteness Theorem. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.     

A feasible theory of truth over combinatory algebra

We define an applicative theory of truth _TPT${\mathsf{T}}_{\mathsf{PT}}$ which proves totality exactly for the polynomial time computable functions. _TPT${\mathsf{T}}_{\mathsf{PT}}$ has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system _TPT${\mathsf{T}}_{\mathsf{PT}}$ has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic.     

Best quadrature formula on Sobolev class with Chebyshev weight

Using best interpolation function based on a given function information, we present a best quadrature rule of function on Sobolev class KW^r[-1,1]${\mathit{KW}}^r[-1,1]$ with Chebyshev weight. The given function information means that the values of a function f∈KW^r[-1,1]$f\in {\mathit{KW}}^r[-1,1]$ and its derivatives up to r-1$r-1$ order at a set of nodes x$\mathbf{x}$ are given. Error bounds are obtained, and the method is illustrated by some examples.     

Fluctuations,effective learnability and metastability in analysis

This paper discusses what kind of quantitative information one can extract under which circumstances from proofs of convergence statements in analysis. We show that from proofs using only a limited amount of the law-of-excluded-middle, one can extract functionals (B,L)$(B,L)$, where L   is a learning procedure for a rate of convergence which succeeds after at most B(a)$B(a)$-many mind changes. This (B,L)$(B,L)$-learnability provides quantitative information strictly in between a full rate of convergence (obtainable in general only from semi-constructive proofs) and a rate of metastability in the sense of Tao (extractable also from classical proofs). In fact, it corresponds to rates of metastability of a particular simple form. Moreover, if a certain gap condition is satisfied, then B and L yield a bound on the number of possible fluctuations. We explain recent applications of proof mining to ergodic theory in terms of these results.     

Meixner polynomials in several variables satisfying bispectral difference equations

We construct a set _Md${\mathfrak{M}}_d$ whose points parametrize families of Meixner polynomials in d   variables. There is a natural bispectral involution b$\mathfrak{b}$ on _Md${\mathfrak{M}}_d$ which corresponds to a symmetry between the variables and the degree indices of the polynomials. We define two sets of d   commuting partial difference operators diagonalized by the polynomials. One of the sets consists of difference operators acting on the variables of the polynomials and the other one on their degree indices, thus proving their bispectrality. The two sets of partial difference operators are naturally connected via the involution b$\mathfrak{b}$.     

On matrices over an arbitrary semiring and their generalized inverses

In this paper, we consider matrices with entries from a semiring S. We first discuss some generalized inverses of rectangular and square matrices. We establish necessary and sufficient conditions for the existence of the Moore–Penrose inverse of a regular matrix. For an m×n$m\times n$ matrix A  , an n×m$n\times m$ matrix P and a square matrix Q of order m, we present necessary and sufficient conditions for the existence of the group inverse of QAP   with the additional property that P(QAP)^#Q$P{(QAP)}^{\mathrm{\#}}Q$ is a {1,2}$\{1,2\}$ inverse of A  . The matrix product used here is the usual matrix multiplication. The result provides a method for generating elements in the set of {1,2}$\{1,2\}$ inverses of an m×n$m\times n$ matrix A starting from an initial {1} inverse of A  . We also establish a criterion for the existence of the group inverse of a regular square matrix. We then consider a semiring structure (_Mm×n(S),+,°)$({\mathbf{M}}_{m\times n}(\mathbf{S}),+,°)$ made up of m×n$m\times n$ matrices with the addition defined entry-wise and the multiplication defined as in the case of the Hadamard product of complex matrices. In the semiring (_Mm×n(S),+,°)$({\mathbf{M}}_{m\times n}(\mathbf{S}),+,°)$, we present criteria for the existence of the Drazin inverse and the Moore–Penrose inverse of an m×n$m\times n$ matrix. When S is commutative, we show that the Hadamard product preserves the Hermitian property, and provide a Schur-type product theorem for the product A°(CC^?)$A°(C{C}^{?})$ of a positive semidefinite n×n$n\times n$ matrix A   and an n×n$n\times n$ matrix C.