We define a property of substructures of models of arithmetic, that of being length-initial, and show that sharply bounded formulae are absolute between a model and its length-initial submodels. We use this to prove independence results for some weak fragments of bounded arithmetic by constructing appropriate models as length-initial submodels of some given model.

We prove that the sharply bounded arithmetic T02 in a language containing the function symbol ⌊x /2y⌋ is equivalent to PV1.

The purpose of this note is to show that the independence results for sharply bounded arithmetic of Takeuti [4] and Tada and Tatsuta [3] can be obtained and, in case of the latter, improved by the model-theoretic method developed by the author in [2].

The theory , axiomatized by the induction scheme for sharply bounded formulae in Buss’ original language of bounded arithmetic , has recently been unconditionally separated from full bounded arithmetic S2. The method used to prove the separation is reminiscent of those known from the study of open induction.We make the connection to open induction explicit, showing that models of can be built using a “nonstandard variant” of Wilkie’s well-known technique for building models of IOpen. This makes (...) it possible to transfer many results and methods from open to sharply bounded induction with relative ease.We provide two applications: the Shepherdson model of IOpen can be embedded into a model of , which immediately implies some independence results for ; extended by an axiom which roughly states that every number has a least 1 bit in its binary notation, while significantly stronger than plain , does not prove the infinity of primes. (shrink)

We show that the arithmetical theory -INDx5, formalized in the language of Buss, i.e. with x/2 but without the MSP function x/2y, does not prove that every nontrivial divisor of a power of 2 is even. It follows that this theory proves neither NP=coNP nor.

We prove some independence results for the bounded arithmetic theoryR 2 0 , and we define a class of functions that is shown to be an upper bound for the class of functions definable by a certain restricted class of ∑ 1 b in extensions ofR 2 0.

This paper proves that the division operation \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\lfloor a/m\rfloor$\end{document} is provably total in the system \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $S_2^0$\end{document} of bounded arithmetic if and only if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $m$\end{document} is of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $2^n$\end{document} for some \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} (...) \begin{document} $n$\end{document}. (shrink)

There are several areas in applied logic where deletion from databases is involved in one way or another:Belief contraction Triggers of the form ‘If condition then remove A’, which are extensively used in database management systemsResource considerations as in relevance and linear logics, where addition or removal of resource can affect provabilityFree logic and the like, where existence and non-existence of individuals affects quantification.All of these areas have certain logical difficulties relating to the removal of elements. These difficulties are normally (...) overcome by working on the meta-level. This paper offers a comprehensive model in which the various forms of removal are treated on the object level, i.e., as connectives of the object language. (shrink)

There are several areas in applied logic where deletion from databases is involved in one way or another:Belief contraction Triggers of the form ‘If condition then remove A’, which are extensively used in database management systemsResource considerations as in relevance and linear logics, where addition or removal of resource can affect provabilityFree logic and the like, where existence and non-existence of individuals affects quantification.All of these areas have certain logical difficulties relating to the removal of elements. This paper points out (...) the difficulties and offers a comprehensive logical model. (shrink)

We introduce a three-tiered framework for modelling and reasoning about agents who (i) can use possibly complete reasoning systems without any restrictions but who nevertheless are (ii) bounded in the sense that they never reach infinitely many results and, finally, who (iii) perform their reasoning in time. This last aspect does not concern so much the time it takes for agents to actually carry out their reasoning, as the time which can bring about external changes in the agents’ states (...) such as arriving of new information or discarding previously available information due to bounds of the agent’s resources. These three aspects are treated with the maximal possible degree of independence from each other. The treatment of layer (iii) can be combined with arbitrary logic at level (ii) which, in turn, can be combined with arbitrary agent logic at level (i). At the level (iii), we discuss briefly the duality (or rather, complementarity) of system descriptions based on actions and transitions, on the one hand, and states and their changes, on the other. We settle for the latter and present a simple language, for describing state changes, which is parameterized by an arbitrary language for describing properties of the states. The language can be viewed as a simple fragment of step logic, admitting however various extensions by appropriate choices of the underlying logic. Alternatively, it can be seen as a very specific fragment of temporal logic (with a variant of ‘until’ or ‘chop’ operator), and is interpreted over dense linear time. The reasoning system presented here is sound, as well as strongly complete and decidable (provided that so is the parameter logic for reasoning about single states). We give the main idea of the completeness proof and suggest a wide range of possible applications, which is a simple consequence of the parametric character of both the language and the reasoning system. We address then in more detail the case of non-omniscient rational agents, (ii). Their models are syntactic structures (sets of available formulae) similar in spirit, though not in the technical formulation, to the models used in other syntax oriented approaches and in active logic. We give a new sound, complete and decidable system for reasoning about such agents. Finally, we illustrate its extensions with the internal reasoning of agents, (i), by equipping them with some example logics. (shrink)

ABSTRACT Quine insisted that the satisfaction of an open modalised formula by an object depends on how that object is described. Kripke's ‘objectual’ interpretation of quantified modal logic, whereby variables are rigid, is commonly thought to avoid these Quinean worries. Yet there remain residual Quinean worries for epistemic modality. Theorists have recently been toying with assignment-shifting treatments of epistemic contexts. On such views an epistemic operator ends up binding all the variables in its scope. One might worry that this (...) yields the undesirable result that any attempt to ‘quantify in’ to an epistemic environment is blocked. If quantifying into the relevant constructions is vacuous, then such views would seem hopelessly misguided and empirically inadequate. But a famous alternative to Kripke's semantics, namely Lewis' counterpart semantics, also faces this worry since it also treats the boxes and diamonds as assignment-shifting devices. As I'll demonstrate, the mere fact that a variable is bound is no obstacle to binding it. This provides a helpful lesson for those modelling de re epistemic contexts with assignment sensitivity, and perhaps leads the way toward the proper treatment of binding in both metaphysical and epistemic contexts: Kripke for metaphysical modality, Lewis for epistemic modality. (shrink)

We define an easily verifiable notion of an atomic formula having uniformly bounded arrays in a structure M. We prove that if T is a complete L-theory, then T is mutually algebraic if and only if there is some model M of T for which every atomic formula has uniformly bounded arrays. Moreover, an incomplete theory T is mutually algebraic if and only if every atomic formula has uniformly bounded arrays in every model M (...) of T. (shrink)

We consider small-weight Cutting Planes (CP * ) proofs; that is, Cutting Planes (CP) proofs with coefficients up to $\operatorname{Poly}(n)$ . We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP * proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following (...) two theorems: (1) Tree-like CP * proofs cannot polynomially simulate non-tree-like CP * proofs. (2) Tree-like (CP * proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other. Our proofs also work for some generalizations of the CP * proof system. In particular, they work for CP * with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference. (shrink)

The relativized propositional calculus is a system of Boolean formulas with query symbols. A formula in this system is called a one-query formula if the number of occurrences of query symbols is just one. If a one-query formula is a tautology with respect to a given oracle A then it is called a one-query tautology with respect to A. By extending works of Ambos-Spies (1986) and us (2002), we investigate the measure of the class of all oracles (...) A such that the set of all one-query tautologies with respect to A does not p-btt-reduce to A, where p-btt denotes polynomial-time bounded-truth-table. We show that certain Dowd-type generic oracles all belong to the class, and hence measure of the class is one. (shrink)

This paper obtains lower and upper bounds for the number of alternations of bounded quantifiers needed to express all formulas in certain ordered Abelian groups admitting elimination of unbounded quantifiers. The paper also establishes model-theoretic tests for equivalence to a formula with a given number of alternations of bounded quantifiers.

If [Formula: see text] is a proper Polish metric space and [Formula: see text] is any countable dense submetric space of [Formula: see text], then the Scott rank of [Formula: see text] in the natural first-order language of metric spaces is countable and in fact at most [Formula: see text], where [Formula: see text] is the Church–Kleene ordinal of [Formula: see text] which is the least ordinal with no presentation on [Formula: see (...) text] computable from [Formula: see text]. If [Formula: see text] is a rigid Polish metric space and [Formula: see text] is any countable dense submetric space, then the Scott rank of [Formula: see text] is countable and in fact less than [Formula: see text]. (shrink)

Let $T$ be a theory in a countable fragment of $\mathcal{L}_{\omega_{1},\omega}$ whose extensions in countable fragments have only countably many types. Sacks proves a bounding theorem that generates models of high Scott rank. For this theorem, a tree hierarchy is developed for $T$ that enumerates these extensions. In this paper, we effectively construct a predecessor function for formulas defining types in this tree hierarchy as follows. Let $T_{\gamma}\subseteq T_{\delta}$ with $T_{\gamma}$- and $T_{\delta}$-theories on level $\gamma$ and $\delta$, respectively. Then if (...) $\ulcorner p\urcorner $ is a formula that defines a type for $T_{\delta}$, our predecessor function provides a formula for defining its subtype in $T_{\gamma}$. By constructing this predecessor function, we weaken an assumption for Sacks’s result. (shrink)

We obtain a nonasymptotic lower time bound for deciding sentences of bounded second-order arithmetic with respect to a form of the random access machine with stored programs. More precisely, let P be an arbitrary program for the model under consideration which recognized true formulas with a given range of parameters. Let p be the length of P and let N be an arbitrary natural number. We show how to construct a formula G with one free variable with length (...) not more than 400 symbols and a value f of x such that the time required by P to decide the truth of G is at least N+1 steps. Furthermore, the G constructed does not depend on P and the length of f is less than p+400. (shrink)

We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ (...) on A (equivalently, it is not definable by a computable $\Sigma _\alpha $ formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α. (shrink)

V i 2 ⊢A iff for some term t :S i 2 ⊢ “2 i exists→ A”, a bounded first-order formula, i ≥1. V i 2 is not Π b 1 -conservative over S i 2 . Any model of V 2 not satisfying Exp satisfies the collection scheme BΣ 0 1 . V 1 3 is not Π b 1 -conservative over S 2.

In this paper, we consider multiplicative-additive fragments of affine propositional classical linear logic extended with n-contraction. To be specific, n-contraction (n 2) is a version of the contraction rule where (n+ 1) occurrences of a formula may be contracted to n occurrences. We show that expansions of the linear models for (n + 1)- valued ukasiewicz logic are models for the multiplicative-additive classical linear logic, its affine version and their extensions with n-contraction. We prove the finite axiomatizability for the (...) classes of finite models, as well as for the class of infinite linear models based on the set of rational numbers in the interval [0, 1]. The axiomatizations obtained in a Gentzen-style formulation are equivalent to finite and infinite-valued ukasiewicz logics. (shrink)

In this paper, we study temporal logic for finite linear structures and surjective bounded morphisms between them. We give a characterisation of such structures by modal formulas and show that every pair of linear structures with a bounded morphism between them can be uniquely characterised by a temporal formula up to an isomorphism. As the main result, we prove Kripke completeness of the logic with respect to the class of finite linear structures with bounded morphisms between (...) them. (shrink)

The theories Si1 and Ti1 are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σbi+1-formula TOPi, which expresses a form of the total ordering principle, is exhibited that is provable in Si+11 , but unprovable in Ti1. This is in contrast with the classical situation, where Si+12 is conservative over Ti2 w. r. t. (...) Σbi+1-sentences. The independence results are proved by translations into propositional logic, and using lower bounds for corresponding propositional proof systems. (shrink)

The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total (...) in [Formula: see text]. Furthermore, the [Formula: see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. (shrink)

We study the logic of strategic ability of coalitions of agents with bounded memory by introducing Alternating-time Temporal Logic with Bounded Memory (ATLBM), a variant of Alternating-time Temporal Logic (ATL). ATLBM accounts for two main consequences of the assumption that agents have bounded memory. First, an agent can only remember a strategy that specifies actions in a bounded number of different circumstances. While the ATL-formula means that coalition C has a joint strategy which will make (...) φ true forever, the ATLBM-formula means that C has a joint strategy which for each agent in C specifies what to do in no more than n different circumstances and which will make φ true forever. Second, an agent has bounded recall—a strategy can only take the last m states of the system into account. We use the logic to study the interaction between strategic ability, bounded number of decisions, bounded recall and incomplete information. We discuss the logical properties and expressiveness of ATLBM, and its relationship to ATL. We show that ATLBM can express properties of strategic ability under bounded memory which cannot be expressed in ATL. (shrink)

This paper is about two topics: 1. systems of explicit mathematics with universes and a non-constructive quantification operator $\mu$; 2. iterated fixed point theories with ordinals. We give a proof-theoretic treatment of both families of theories; in particular, ordinal theories are used to get upper bounds for explicit theories with finitely many universes.

We investigate the problem how to lift the non - $\forall \Sigma^b_1(\alpha)$ - conservativity of $T^2_2(\alpha)$ over $S^2_2(\alpha)$ to the expected non - $\forall \Sigma^b_i(\alpha)$ - conservativity of $T^{i+1}_2(\alpha)$ over $S^{i+1}_2(\alpha)$ , for $i > 1$ . We give a non-trivial refinement of the “lifting method” developed in [4,8], and we prove a sufficient condition on a $\forall \Sigma^b_1(f)$ -consequence of $T_2(f)$ to yield the non-conservation result. Further we prove that Ramsey's theorem, a $\forall \Sigma^b_1(\alpha)$ - formula, is not (...) provable in $T^1_2(\alpha)$ , and that $\forall \Sigma^b_j(\alpha)$ - conservativity of $T^{i+1}_2(\alpha)$ over $T^{i}_2(\alpha)$ implies $\forall \Sigma^b_j(\alpha)$ - conservativity of the whole $T_2(\alpha)$ over $T^{i}_2(\alpha)$ , for any $j \geq 2$. (shrink)

We present a sound and complete tableau calculus for the class of regular grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for regular grammar logics can be obtained using our tableau calculus. We also give an effective Craig interpolation lemma for regular grammar (...) logics using our calculus. (shrink)

We show that length initial submodels of S12 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.

In first order logic without equality, but with arbitrary relations and functions the ∃*∀∃* class is the unique maximal solvable prefix class. We show that the satisfiability problem for this class is decidable in deterministic exponential time The result is established by a structural analysis of a particular infinite subset of the Herbrand universe and by a polynomial space bounded alternating procedure.

We introduce frame-equivalence games tailored for reasoning about the size, modal depth, number of occurrences of symbols and number of different propositional variables of modal formulae defining a given frame property. Using these games, we prove lower bounds on the above measures for a number of well-known modal axioms; what is more, for some of the axioms, we show that they are optimal among the formulae defining the respective class of frames.

Periodic orbit quantization requires an analytic continuation of non-convergent semiclassical trace formulae. We propose two different methods for semiclassical quantization. The first method is based upon the harmonic inversion of semiclassical recurrence functions. A band-limited periodic orbit signal is obtained by analytical frequency windowing of the periodic orbit sum. The frequencies of the periodic orbit signal are the semiclassical eigenvalues, and are determined by either linear predictor, Padé approximant, or signal diagonalization. The second method is based upon the direct application (...) of the Padé approximant to the periodic orbit sum. The Padé approximant allows the resummation of the, typically exponentially, divergent periodic orbit terms. Both techniques do not depend on the existence of a symbolic dynamics, and can be applied to bound as well as to open systems. Numerical results are presented for two different systems with chaotic and regular classical dynamics, viz. the three-disk scattering system and the circle billiard. (shrink)

A bounded formula is a pair consisting of a propositional formula φ in the first coordinate and a real number within the unit interval in the second coordinate, interpreted to express the lower-bound probability of φ. Converting conjunctive/disjunctive combinations of bounded formulas to a single bounded formula consisting of the conjunction/disjunction of the propositions occurring in the collection along with a newly calculated lower probability is called absorption. This paper introduces two inference rules for (...) effecting conjunctive and disjunctive absorption and compares the resulting logical system, called System Y, to axiom System P. Finally, we demonstrate how absorption resolves the lottery paradox and the paradox of the preference. (shrink)

By suitably adapting an argument of Hirschfeld , we show that there is a single Δ1 formula that defeats “bounded collection” for any model of II2 Arithmetic that is either a recursive ultrapower or an existentially complete model. Some related facts are noted. MSC: 03F30, 03C62.

In this paper, I pursue such a logical foundation for arithmetic in a variant of Zermelo set theory that has axioms of subset separation only for quantifier-free formulae, and according to which all sets are Dedekind finite. In section 2, I describe this variant theory, which I call ZFin0. And in section 3, I sketch foundations for arithmetic in ZFin0 and prove that certain foundational propositions that are theorems of the standard Zermelian foundation for arithmetic are independent of ZFin0.<br><br>An equivalent (...) theory of sets and an equivalent foundation for arithmetic was introduced by John Mayberry and developed by the current author in his doctoral thesis. In that thesis, the independence results mentioned above are proved using proof-theoretic methods. In this paper, I offer model-theoretic proofs of the central independence results using the technique of cumulation models, which was introduced by Steve Popham, a doctoral student of Mayberry<br>from the early 1980s. (shrink)

Aeschylus' imagery has for some time now been discussed as a feature of his dramatic technique which does more than merely adorn his work. Lebeck, for example, has described how images articulate the Oresteia: The images of the Oresteia are not isolated units which can be examined separately. Each one is part of a larger whole: a system of kindred imagery. They are connected to one another by verbal similarity rather than verbal duplication. Formulaic repetition is rare, except in the (...) cases of single ‘key’ words; it is replaced by associative or reminiscent repetition. Such repetition may evoke several different passages, yet correspond exactly to none. Each occurrence adds a new element to those with which it is associated. Often this expansion will be a blend of two images previously separate, preserving features reminiscent of both. In this way the different systems of imagery are intricately interwoven. The significance of a recurrent image unfolds in successive stages, keeping time with the action of the drama. (shrink)

For any n, we construct a model of in which each formula is equivalent to an formula.

As anyone who has flown out of a cloud knows, the boundaries of a cloud are a lot less sharp up close than they can appear on the ground. Even when it seems clearly true that there is one, sharply bounded, cloud up there, really there are thousands of water droplets that are neither determinately part of the cloud, nor determinately outside it. Consider any object that consists of the core of the cloud, plus an arbitrary selection of (...) these droplets. It will look like a cloud, and circumstances permitting rain like a cloud, and generally has as good a claim to be a cloud as any other object in that part of the sky. But we cannot say every such object is a cloud, else there would be millions of clouds where it seemed like there was one. And what holds for clouds holds for anything whose boundaries look less clear the closer you look at it. And that includes just about every kind of object we normally think about, including humans. Although this seems to be a merely technical puzzle, even a triviality, a surprising range of proposed solutions has emerged, many of them mutually inconsistent. It is not even settled whether a solution should come from metaphysics, or from philosophy of language, or from logic. Here we survey the options, and provide several links to the many topics related to the Problem. (shrink)

Gödel's second incompleteness theorem is proved for Herbrand consistency of some arithmetical theories with bounded induction, by using a technique of logarithmic shrinking the witnesses of bounded formulas, due to Z. Adamowicz [Herbrand consistency and bounded arithmetic, Fundamenta Mathematical vol. 171 (2002), pp. 279-292]. In that paper, it was shown that one cannot always shrink the witness of a bounded formula logarithmically, but in the presence of Herbrand consistency, for theories I∆₀+ Ωm, with m ≥ (...) 2, any witness for any bounded formula can be shortened logarithmically. This immediately implies the unprovability of Herbrand consistency of a theory T ⊇ I∆₀ + Ω₂ in t itself. In this paper, the above results are generalized for I∆₀ + Ω₁. Also after tailoring the definition of Herbrand consistency for I∆₀ we prove the corresponding theorems for I∆₀. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories I∆₀ + Ω₁ and I∆₀. (shrink)

We show that \, the basic theory of bounded arithmetic corresponding to the complexity class \, proves the \ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \ can also prove the integer division axiom, and the \-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \ and \. (...) As a side result, we also prove that there is a well-behaved \ definition of modular powering in \\). (shrink)

We construct a weak second-order theory of arithmetic which includes Weak König's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with Σ b 1 -graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae.

We show that VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document}, the basic theory of bounded arithmetic corresponding to the complexity class TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document}, proves the IMUL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ IMUL $$\end{document} axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the TC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {TC}^0$$\end{document} (...) iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, VTC0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ VTC ^0$$\end{document} can also prove the integer division axiom, and the RSUV\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ RSUV $$\end{document}-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories Δ1b-CR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta ^b_1\text{- } CR $$\end{document} and C20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C^0_2$$\end{document}. As a side result, we also prove that there is a well-behaved Δ0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _0$$\end{document} definition of modular powering in IΔ0+WPHP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$I\Delta _0+ WPHP $$\end{document}. (shrink)

We introduce and discuss a concept of approximation of a topological algebraic system A by finite algebraic systems from a given class K. If A is discrete, this concept agrees with the familiar notion of a local embedding of A in a class K of algebraic systems. One characterization of this concept states that A is locally embedded in K iff it is a subsystem of an ultraproduct of systems from K. In this paper we obtain a similar characterization of (...) approximability of a locally compact system A by systems from K using the language of nonstandard analysis. In the signature of A we introduce positive bounded formulas and their approximations; these are similar to those introduced by Henson [14] for Banach space structures (see also [15, 16]). We prove that a positive bounded formula φ holds in A if and only if all precise enough approximations of φ hold in all precise enough approximations of A. We also prove that a locally compact field cannot be approximated arbitrarily closely by finite (associative) rings (even if the rings are allowed to be non-commutative). Finite approximations of the field R can be considered as possible computer systems for real arithmetic. Thus, our results show that there do not exist arbitrarily accurate computer arithmetics for the reals that are associative rings. (shrink)

It is generally supposed that borderline cases account for the tolerance of vague terms, yet cannot themselves be sharply bounded, leading to infinite levels of higher order vagueness. This higher order vagueness subverts any formal effort to make language precise. However, it is possible to show that tolerance must diminish at higher orders. The attempt to derive it from indiscriminability founders on a simple empirical test, and we learn instead that there is no limit to how small higher (...) order tolerance may become. That means there is no limit to how precisely we may draw the boundaries of borderline cases, thus forestalling any requirement for higher order vagueness. (shrink)