Search

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11]. Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček and Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Let T be the standard Veblen 1908 ordinal notation system for Γ0 as defined, for example, in Schütte's 1977 textbook [13] on Proof Theory. We define a slight modification of the standard assignment of fundamental sequences for the limit ordinals in T and prove that Γ0 is subrecursively inaccessible for this assignment, i.e. the induced slow and fast growing hierarchy match up at Γ0 for the first time.The results of this paper also indicate that ϕℇ00 may be considered as a new slow growing ordinal of PA in the sense that the induced slow growing hierarchy up to ϕℇ00 classifies the PA-provablyrecursive functions.We show how the results of this paper can be used to bui d a subrecursive hierarchyover the predicative ordinals in the spirit of Wainer's 1970 abstract [16 ]. [ABSTRACT FROM AUTHOR]

In this paper we give characterizations of the stable and ℵ0-stable theories, in terms of an external property called representation. In the sense of the representation property, the mentioned classes of first-order theories can be regarded as 'not very complicated'. [ABSTRACT FROM AUTHOR]

As far as algebraic properties are concerned, the usual addition on the class of ordinal numbers is not really well behaved; for example, it is not commutative, nor left cancellative etc. In a few cases, the natural Hessenberg sum is a better alternative, since it shares most of the usual properties of the addition on the naturals. A countably infinite iteration of the natural sum has been used in a recent paper by Väänänen and Wang, with applications to infinitary logics. We present a detailed study of this infinitary operation, showing that there are many similarities with the ordinary infinitary sum, providing an order theoretical characterization, and finding connections with certain kinds of infinite mixed sums. [ABSTRACT FROM AUTHOR]

In this paper, the positive fragment of the logic [ABSTRACT FROM AUTHOR]

This paper presents a comparison of three approaches to the teaching of probability to demonstrate how the truth table of elementary mathematical logic can be used to teach the calculations of conditional probabilities. Students are typically introduced to the topic of conditional probabilities-especially the ones that involve Bayes' rule-with the help of such traditional approaches as formula use or conversion to natural frequencies. The truth table approach is an alternative method for explaining the concept and calculation procedure of conditional probability and Bayes' rule. [ABSTRACT FROM AUTHOR]

The main result of this paper is Theorem [1.1], which shows that it is possible for derived models to satisfy [ABSTRACT FROM AUTHOR]

Here we study properties of weakly circularly minimal cyclically ordered groups. The main result of the paper is that any weakly circularly minimal cyclically ordered group is abelian. [ABSTRACT FROM AUTHOR]

It is often alleged that, unlike typical axioms of mathematics, the Continuum Hypothesis (CH) is indeterminate. This position is normally defended on the ground that the CH is undecidable in a way that typical axioms are not. Call this kind of undecidability 'absolute undecidability'. In this paper, I seek to understand what absolute undecidability could be such that one might hope to establish that (a) CH is absolutely undecidable, (b) typical axioms are not absolutely undecidable, and (c) if a mathematical hypothesis is absolutely undecidable, then it is indeterminate. I shall argue that on no understanding of absolute undecidability could one hope to establish all of (a)-(c). However, I will identify one understanding of absolute undecidability on which one might hope to establish both (a) and (c) to the exclusion of (b). This suggests that a new style of mathematical antirealism deserves attention-one that does not depend on familiar epistemological or ontological concerns. The key idea behind this view is that typical mathematical hypotheses are indeterminate because they are relevantly similar to CH. [ABSTRACT FROM AUTHOR]

In this paper we present a contribution to a classical result of E. Ellentuck in the theory of regressive isols. E. Ellentuck introduced the concept of a hyper-torre isol, established their existence for regressive isols, and then proved that associated with these isols a special kind of semi-ring of isols is a model of the true universal-recursive statements of arithmetic. This result took on an added significance when it was later shown that for regressive isols, the property of being hyper-torre is equivalent to being hereditarily odd-even. In this paper we present a simplification to the original proof for establishing that equivalence. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

This paper is concerned with implicit computational complexity of the exptime computable functions. Modifying the lexicographic path order, we introduce a path order EPO. It is shown that a termination proof for a term rewriting system via EPO implies an exponential bound on the lengths of derivations. The path order EPO is designed so that every exptime function is representable as a term rewrite system compatible with EPO (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA0*, which consists of the axioms of discrete ordered semi-rings with exponentiation, Δ10 comprehension and Π00 induction, and which is known as a weaker system than the popularbase theory RCA0: 1. Bisep(Δ10, Σ10)-Det* ↔ WKL0,2. Bisep(Δ10, Σ20)-Det* ↔ ATR0 + Σ11 induction,3. Bisep(Σ10, Σ20)-Det* ↔ Sep(Σ10, Σ20)-Det* ↔ Π11-CA0,4. Bisep(Δ20, Σ20)-Det* ↔ Π11-TR0, where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In [10] it is claimed that the set of predicate tautologies of all complete BL-chains and the set of all standard tautologies (i. e., the set of predicate formulas valid in all standard BL-algebras) coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL-chain B satisfies all standard BL-tautologies iff for any transfinite sequence (ai: i ∈ I) of elements of B, the condition ∧i ∈ I (a2i) = (∧i ∈ Iai)2 holds in B. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Constructive set theory started with Myhill's seminal 1975 article [8]. This paper will be concerned with axiomatizations of the natural numbers in constructive set theory discerned in [3], clarifying the deductive relationships between these axiomatizations and the strength of various weak constructive set theories. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Let f, g ∈ ωω . We will denote by g ≫ f that for every k < ω, f (nk) ≤ g (n ) except for finitely many n . The ideal ℐf on ω2 is the collection of sets X such that, for some g ≫ f and τ ∈ ∏n <ωg (n )2, every x ∈ X satisfies τ (n ) ⊂ x for infinitely many n . In the present paper, we will prove the consistency of cov(ℐf) < &cfr; and non(ℐf) < &cfr;. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Given a π -institution I , a hierarchy of π -institutions I(n ) is constructed, for n ≥ 1. We call I(n ) the n-th order counterpart of I . The second-order counterpart of a deductive π -institution is a Gentzen π -institution, i.e. a π -institution associated with a structural Gentzen system in a canonical way. So, by analogy, the second order counterpart I(2) of I is also called the “Gentzenization” of I . In the main result of the paper, it is shown that I is strongly Gentzen , i.e. it is deductively equivalent to its Gentzenization via a special deductive equivalence, if and only if it has the deduction-detachment property . (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

It is known that there is a close relation between Prikry forcing and the iteration of ultrapowers: If U is a normal ultrafilter on a measurable cardinal κ and 〈Mn, jm,n | m ≤ n ≤ ω〉 is the iteration of ultrapowers of V by U, then the sequence of critical points 〈j0,n(κ) | n ∈ ω〉 is a Prikry generic sequence over Mω. In this paper we generalize this for normal precipitous filters. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In Aczel [1], the existence of largest (written “greatest” in Barwise and Moss [2]) fixed points of set continuous operators is proved assuming the schema version of dependent choices in Zermelo-Fraenkel set theory without the axiom of Foundation. In the present paper, we study whether the existence of largest fixed points of set continuous operators is provable without the schema version of dependent choices, using Boffa's weak antifoundation axioms. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

This paper is concerned with topological set theory, and particularly with Skala's and Manakos' systems for which we give a topological characterization of the models. This enables us to answer natural questions about those theories, reviewing previous results and proving new ones. One of these shows that Skala's set theory is in a sense compatible with any ‘normal’ set theory, and another appears on the semantic side as a ‘Cantor theorem’ for the category of Alexandroff spaces. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In this paper we give an axiomatisation of the concept of a computability structure with partial sequences on a many-sorted metric partial algebra, thus extending the axiomatisation given by Pour-El and Richards in [9] for Banach spaces. We show that every Banach-Mazur computable partial function from an effectively separable computable metric partial Σ-algebra A to a computable metric partial Σ-algebra B must be continuous, and conversely, that every effectively continuous partial function with semidecidable domain and which preserves the computability of a computably enumerable dense set must be computable. Finally, as an application of these results we give an alternative proof of the first main theorem for Banach spaces first proved by Pour-El and Richards. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

The paper proposes a flexible way to build concepts within fuzzy logic and set theory. The framework is general enough to capture some important particular cases, with their own independent interpretations, like “antitone” or “isotone” concepts constructed from fuzzy binary relations, but also to allow the two universes (of objects and attributes) to be equipped each with its own truth structure. Perhaps the most important feature of our approach is that we do not commit ourselves to any kind of logical connector, covering thus the case of a possibly non-commutative conjunction too. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

In this paper we propose a Kripke-style semantics for second order intuitionistic propositional logic and we provide a semantical proof of the disjunction and the explicit definability property. Moreover, we provide a tableau calculus which is sound and complete with respect to such a semantics. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We study the situation when the automorphism group of a recursively saturated structure acts on an ℝ-tree. The cases of (ℚ, <) and models of Peano Arithmetic are central in the paper. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

There are two versions of the Proper Iteration Lemma. The stronger (but less well-known) version can be used to give simpler proofs of iteration theorems (e.g., [7, Lemma 24] versus [9, Theorem IX.4.7]). In this paper we give another demonstration of the fecundity of the stronger version by giving a short proof of Shelah's theorem on the preservation of the ωω-bounding property. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

A basic result in intuitionism is Π02-conservativity. Take any proof p in classical arithmetic of some Π02-statement (some arithmetical statement ∀x.∃y.P(x, y), with P decidable). Then we may effectively turn p in some intuitionistic proof of the same statement. In a previous paper [1], we generalized this result: any classical proof p of an arithmetical statement ∀x.∃y.P(x, y), with P of degree k, may be effectively turned into some proof of the same statement, using Excluded Middle only over degree k formulas. When k = 0, we get the original conservativity result as particular case. This result was a by-product of a semantical construction. J. Avigad of Carnegie Mellon University, found a short, direct syntactical derivation of the same result, using H. Friedman's A-translation. His proof is included here with his permission. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Derndinger [2] and Krupa [5] defined the F-product of a (strongly continuous one-parameter) semigroup (of linear operators) and presented some applications (e. g. to spectral theory of positive operators, cf. [3]). Wolff (in [7] and [8]) investigated some kind of nonstandard analogon and applied it to spectral theory of group representations. The question arises in which way these constructions are related. In this paper we show that the classical and the nonstandard F-product are isomorphic (Theorem 2.6). We also prove a little “classical” corollary (2.7.). (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

This paper deals with Kripke-style semantics for many-valued logics. We introduce various types of Kripke semantics, and we connect them with algebraic semantics. As for modal logics, we relate the axioms of logics extending MTL to properties of the Kripke frames in which they are valid. We show that in the propositional case most logics are complete but not strongly complete with respect to the corresponding class of complete Kripke frames, whereas in the predicate case there are important many-valued logics like BL, Ł and Π, which are not even complete with respect to the class of all predicate Kripke frames in which they are valid. Thus although very natural, Kripke semantics seems to be slightly less powerful than algebraic semantics. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

A computably enumerable (c.e.) degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, and show that there exists a minimal pair which join to a plus cupping degree, so that PC ⊈ NB. This gives a first known difference between NB and PC. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Dual-intuitionistic logics are logics proposed by Czermak (1977), Goodman (1981) and Urbas (1996). It is shown in this paper that there is a correspondence between Goodman's dual-intuitionistic logic and Nelson's constructive logic N-. [ABSTRACT FROM AUTHOR]

Compact Bilinear Logic (CBL), introduced by Lambek [14], arises from the multiplicative fragment of Noncommutative Linear Logic of Abrusci [1] (also called Bilinear Logic in [13]) by identifying times with par and 0 with 1. In this paper, we present two sequent systems for CBL and prove the cut-elimination theorem for them. We also discuss a connection between cut-elimination for CBL and the Switching Lemma from [14]. [ABSTRACT FROM AUTHOR]

Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC0 and FO(PLUS, TIMES). We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first-order define PLUS, that < and DIVIDES can first-order define TIMES, and that < and COPRIME can first-order define TIMES. The first result sharpens the equivalence FO(PLUS, TIMES) =FO(BIT) to FO(<, TIMES) = FO(BIT), answering a question raised by Barrington et al. about the Crane Beach Conjecture. Together with previous results on the Crane Beach Conjecture, our results imply that FO(PLUS) is strictly less expressive than FO(<, TIMES) = FO(<, DIVIDES) = FO(<,COPRIME). In more colorful language, one could say that, for parallel computation, multiplication is harder than addition. [ABSTRACT FROM AUTHOR]

In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type-2 complexity. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to investigate constructively the relationship between proximal convergence, uniform sequential convergence and uniform convergence for sequences of mappings between apartness spaces. It is also shown that if the second space satisfies the Efremovic axiom, then proximal convergence preserves strong continuity. [ABSTRACT FROM AUTHOR]

This paper proves some independence results for weak fragments of Heyting arithmetic by using Kripke models. We present a necessary condition for linear Kripke models of arithmetical theories which are closed under the negative translation and use it to show that the union of the worlds in any linear Kripke model of HA satisfies PA. We construct a two-node PA-normal Kripke structure which does not force iΣ2. We prove i∀1 ⊬ i∃1, i∃1 ⊬ i∀1, iΠ2 ⊬ iΣ2 and iΣ2 ⊬ iΠ2. We use Smorynski's operation Σ′ to show HA ⊬ lΠ1. [ABSTRACT FROM AUTHOR]

In this paper we study the modal behavior of Σ-preservativity, an extension of provability which is equivalent to interpretability for classical superarithmetical theories. We explain the connection between the principles of this logic and some well-known properties of HA, like the disjunction property and its admissible rules. We show that the intuitionistic modal logic given by the preservativity principles of HA known so far, is complete with respect to a certain class of frames. [ABSTRACT FROM AUTHOR]

For a ⊆ b ⊆ ω with b\ a infinite, the set D = {x ∈ [ω]ω : a ⊆ x ⊆ b} is called a doughnut. A set S ⊆ [ω]ω has the doughnut property &Dscr; if it contains or is disjoint from a doughnut. It is known that not every set S ⊆ [ω]ω has the doughnut property, but S has the doughnut property if it has the Baire property &Bscr; or the Ramsey property ℛ. In this paper it is shown that a finite support iteration of length ω1 of Cohen forcing, starting from L, yields a model for CH + $ \sum ^1 _2 $(&Dscr;) + $ \neg \sum ^1 _2 $(&Bscr;) + $ \neg \sum ^1 _2 $(ℛ). [ABSTRACT FROM AUTHOR]

The paper investigates the strength of the Anti-Foundation Axiom, AFA, on the basis of Kripke-Platek set theory without Foundation. It is shown that the addition of AFA considerably increases the proof theoretic strength. [ABSTRACT FROM AUTHOR]

In this paper, we will give a general description of subdirectly irreducible Heyting algebras with operators under some weak conditions, which includes the finite case, the normal case and the case for Boolean algebras with diamond operator. This can be done by normalizing these operators. This answers the question posed in Wolter [4]. [ABSTRACT FROM AUTHOR]

In this paper we provide quantifier-free, constructive axiomatizations for 2-dimensional absolute, Euclidean, and hyperbolic geometry. The main novelty consists in the first-order languages in which the axiom systems are formulated. [ABSTRACT FROM AUTHOR]

The paper deals with proximal convergence and Leader's theorem, in the constructive theory of uniform apartness spaces. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

A (large) superstable homogeneous structure is said to be simple if every complete type over any set A has a free extension over any B ⊇ A. In this paper we give a characterization for this property in terms of U-rank. As a corollary we get that if the structure has finite U-rank, then it is simple. (© 2003 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Mathematical logic and foundations of mathematics experienced a large boom in the 1950s and 60s due to their close connections to the theoretical fundamentals of computer science. The theory of algorithms and automata developed in line with computer technology; cybernetics was the buzzword of the times. It was during this exciting period that G?nter Asser founded the Zeitschrift für Mathematische Logik und Grundlagen der Mathematik while doing his doctorate at the Humboldt-Universität in Berlin, together with his supervisor, Karl Schröter. The first issue appeared in 1955 and, alongside work by R. Péter and K. Schröter, contained a paper by Günter Asser entitled “Eine semantische Charakterisierung der deduktiv abgeschlossenen Mengen des Prädikatenkalküls der ersten Stufe”. Numerous further works would cement his status as a central figure in logic in East Germany as well as his international reputation. In 1960 Günter Asser was called to Greifswald University. He gave his students not merely a holistic view of the mathematical disciplines, but also of their history and philosophical background. As time went on, he became Dean of his faculty and Deputy Vice Chancellor (Prorektor) of the University. He went on to become a board member of the GDR Mathematical Society and, in 1977, was elected a member of the Academy of Science. His companion and mentor of many years, Karl Schröter, died that same year and Günter Asser assumed sole responsibility of the Zeitschrift für Mathematische Logik und Grundlagen der Mathematik. From a scientific viewpoint, the 70s were characterized by a tendency towards complexity theory. Günter Asser's influence was now mainly reflected in many publications from his field as well as in his opening up the journal to contributions on complexity theory. It is due to Günter Asser that the ZML, which in the meantime is called Mathematical Logic Quarterly, continues to enjoy such an eminent standing among the community, despite scientific and political paradigm shifts. As its editor, he ensured not only the high quality of the papers, but was also actively involved in the technical side of the journal's production. Günter Asser has accompanied the journal with his untiring, personal commitment for 50 years. We now wish to express our heartfelt thanks to the co-founder and retiring editor for his efforts on behalf of the journal, and wish him all the best for the future. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]