An Independence Result on Weak Second Order Bounded Arithmetic

We show that length initial submodels of S¹₂ can be extended to a model of weak second order arithmetic. As a corollary we show that the theory of length induction for polynomially bounded second order existential formulae cannot define the function division.     

Elementary submodels of parametrizable models

We introduce the notion of F-parametrizable model and prove some general results on elementary submodels of F-parametrizable models. Using this notion, we can uniformly characterize all elementary submodels for the field of real numbers and for the group of all permutations on natural numbers in the first order language as well as in the language of hereditarily finite superstructures. Assuming the constructibility axiom, we obtain a simpler characterization of elementary submodels of F-parametrizable models and prove some additional properties of the structure of their elementary submodels.     

A saturation property of structures obtained by forcing with a compact family of random variables

A method for constructing Boolean-valued models of some fragments of arithmetic was developed in Krají?ek (Forcing with Random Variables and Proof Complexity, London Mathematical Society Lecture Notes Series, Cambridge University Press, Cambridge, 2011), with the intended applications in bounded arithmetic and proof complexity. Such a model is formed by a family of random variables defined on a pseudo-finite sample space. We show that under a fairly natural condition on the family [called compactness in Krají?ek (Forcing with Random Variables and Proof Complexity, London Mathematical Society Lecture Notes Series, Cambridge University Press, Cambridge, 2011)] the resulting structure has a property that is naturally interpreted as saturation for existential types. We also give an example showing that this cannot be extended to universal types.     

Preservation theorems for bounded formulas

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV₁. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict formulas proves decidability of formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves , then P=NP.     

The arithmetic of cuts in models of arithmetic

We present a number of results on the structure of initial segments of models of Peano arithmetic with the arithmetic operations of addition, subtraction, multiplication, division, exponentiation and logarithm. Each of the binary operations introduced is defined in two dual ways, often with quite different results, and we attempt to systematise the issues and show how various calculations may be carried out. To understand the behaviour of addition and subtraction we introduce a notion of derivative on cuts, analogous to differentiation in the calculus. Multiplication, division and other operations are described by higher order versions of derivative. The work here is presented as important preliminary work related to a nonstandard measure theory of non‐definable bounded subsets of a model of Peano arithmetic.     

Bounded arithmetic,proof complexity and two papers of Parikh

This article surveys R. Parikh's work on feasibility, bounded arithmetic and the complexity of proofs. We discuss in depth two of Parikh's papers on these subjects and some of the subsequent progress in the areas of feasible arithmetic and lengths of proofs.     

The Theory of Finite Models without Equal Sign

In this paper, it is the first time ever to suggest that we study the model theory of all finite structures and to put the equal sign in the same situtation as the other relations. Using formulas of infinite lengths we obtain new theorems for the preservation of model extensions, submodels, model homomorphisms and inverse homomorphisms. These kinds of theorems were discussed in Chang and Keisler＇s Model Theory, systematically for general models, but Gurevich obtained some different theorems in this direction for finite models. In our paper the old theorems manage to survive in the finite model theory. There are some differences between into homomorphisms and onto homomorphisms in preservation theorems too. We also study reduced models and minimum models. The characterization sentence of a model is given, which derives a general result for any theory T to be equivalent to a set of existential-universal sentences. Some results about completeness and model completeness are also given.     

A hierarchy of submodels of differential equations

We consider a system of differential equations admitting a group of transformations. The Lie algebra of the group generates a hierarchy of submodels. This hierarchy can be chosen so that the solutions to each of submodels are solutions to some other submodel in the same hierarchy. For this we must calculate an optimal system of subalgebras and construct a graph of embedded subalgebras and then calculate the differential invariants and invariant differentiation operators for each subalgebra. The invariants of a superalgebra are functions of the invariants of the algebra. The invariant differentiation operators of a superalgebra are linear combinations of invariant differentiation operators of a subalgebra over the field of invariants of the subalgebra. The comparison of the representations of group solutions gives a relation between the solutions to the models of the superalgebra and the subalgebra. Some examples are given of embedded submodels for the equations of gas dynamics.     

The polynomial and linear time hierarchies in V0

We show that the bounded arithmetic theory V⁰ does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stationary lower probabilities and unstable averages

Summary This paper explores the possibilities for probability-like models of stationary nondeterministic phenomena that possess divergent but bounded time averages. A random sequence described by a stationary probability measure must have almost surely convergent time averages whenever it has almost surely bounded time averages. Hence, no measure can provide the mathematical model we desire. In turning to lower probability based models we first explore the relationships between divergence, stationarity, and monotone continuity and those between monotone continuity and unicity of extensions. We then construct several examples of stationary lower probabilities for sequences of uniformly bounded random variables such that divergence of time averages occurs with lower probability one. We conclude with some remarks on the problem of estimating lower probability models on the basis of cylinder set observations.     

On the convergence of averages of mixing sequences

We construct an absolutely regular stationary random sequence which is an instantaneous bounded function of an aperiodic recurrent Markov chain with a countable state space, such that the large deviation principle fails for the arithmetic means of the sequence, while the exponential convergence holds. We also show that exponential convergence holds for the arithmetic means of a vector valued strictly stationary bounded -mixing sequence.     

Pursuing polynomial bounds on torsion

It is well known that surface groups admit free and proper actions on finite products of infinite valence trees. In this note, we address the question of whether there can be a free and proper action on a finite product of bounded valence trees. We provide both some obstructions and an arithmetic criterion for existence. The bulk of the paper is devoted to an approach to verifying the arithmetic criterion which involves studying the character variety of certain surface groups over a field of positive characteristic. These methods may be useful for attempting to determine when groups admit good linear representations in other contexts.     

On the use of the predictive likelihood of a Gaussian model

The predictive likelihood of a model specified by data is defined when the model satisfies certain conditions. It reduces to the conventional definition when the model is specified independently of the data. The definition is applied to some Gaussian models and a method of handling the improper uniform prior distributions is obtained for the Bayesian modeling of a multi-model situation where the submodels may have different numbers of parameters. The practical utility of the method is checked by a Monte Carlo experiment of some quasi-Bayesian procedures realized by using the predictive likelihoods. The Institute of Statistical Mathematics     

Intuitionistic nonstandard bounded modified realisability and functional interpretation

We present a bounded modified realisability and a bounded functional interpretation of intuitionistic nonstandard arithmetic with nonstandard principles.The functional interpretation is the intuitionistic counterpart of Ferreira and Gaspar's functional interpretation and has similarities with Van den Berg, Briseid and Safarik's functional interpretation but replacing finiteness by majorisability.We give a threefold contribution: constructive content and proof-theoretical properties of nonstandard arithmetic; filling a gap in the literature; being in line with nonstandard methods to analyse compactness arguments.     

Subsets of models of arithmetic

We define certain properties of subsets of models of arithmetic related to their codability in end extensions and elementary end extensions. We characterize these properties using some more familiar notions concerning cuts in models of arithmetic.     

Estimating a mean matrix: boosting efficiency by multiple affine shrinkage

The unknown matrix M is the mean of the observed response matrix in a multivariate linear model with independent random errors. This paper constructs regularized estimators of M that dominate, in asymptotic risk, least squares fits to the model and to specified nested submodels. In the first construction, the response matrix is expressed as the sum of orthogonal components determined by the submodels; each component is replaced by an adaptive total least squares fit of possibly lower rank; and these fits are then summed. The second, lower risk, construction differs only in the second step: each orthogonal component is replaced by a modified Efron-Morris fit before summation. Singular value decompositions yield computable formulae for the estimators and their asymptotic and estimated risks. In the asymptotics, the row dimension of M tends to infinity while the column dimension remains fixed. Convergences are uniform when signal-to-noise ratio is bounded. This research was supported in part by National Science Foundation Grant DMS 0404547.     

The equivalence between the TE,TM model and the Darwin models

In this paper,we study the TE,TM model by using the decompositions of the vector fields in 2-D bounded multiply connected domains and 2-D unbounded domains,respectively.We find that the TE,TM model and the Darwin models are equivalent if we assume some regularity of the initial data.     

Stochastic population dynamics under regime switching

In this paper we will develop a new stochastic population model under regime switching. Our model takes both white and color environmental noises into account. We will show that the white noise suppresses explosions in population dynamics. Moreover, from the point of population dynamics, our new model has more desired properties than some existing stochastic population models. In particular, we show that our model is stochastically ultimately bounded.     

The function \lfloor a/m\rfloor in sharply bounded arithmetic

This paper proves that the division operation is provably total in the system of bounded arithmetic if and only if is of the form for some . Received: May 29, 1996     

Logic programs,well-orderings and forward chaining

We investigate the construction of stable models of general propositional logic programs. We show that a forward-chaining technique, supplemented by a properly chosen safeguard can be used to construct stable models of logic programs. Moreover, the proposed method has the advantage that if a program has no stable model, the result of the construction is a stable model of a subprogram. Further, in such a case the proposed method “isolates the inconsistency” of the program, that is it points to the part of the program responsible for the inconsistency. The results of computations are called stable submodels. We prove that every stable model of a program is a stable submodel. We investigate the complexity issues associated with stable submodels. The number of steps required to construct a stable submodel is polynomial in the sum of the lengths of the rules of the program. In the infinite case the outputs of the forward chaining procedure have much simpler complexity than those for general stable models. We show how to incorporate other techniques for finding models (e.g. Fitting operator, Van Gelder-Ross-Schlipf operator) into our construction.