Forcing for hat inductive definitions in arithmetic

By forcing, we give a direct interpretation of into Avigad's . To the best of the author's knowledge, this is one of the simplest applications of forcing to “real problems”.     

The grounded Martin's axiom

We introduce a variant of Martin's axiom, called the grounded Martin's axiom, or , which asserts that the universe is a c.c.c. forcing extension in which Martin's axiom holds for posets in the ground model. This principle already implies several of the combinatorial consequences of . The new axiom is shown to be consistent with the failure of and a singular continuum. We prove that is preserved in a strong way when adding a Cohen real and that adding a random real to a model of preserves (even though it destroys itself). We also consider the analogous variant of the proper forcing axiom.     

Schatunowsky's theorem,Bonse's inequality,and Chebyshev's theorem in weak fragments of Peano arithmetic

In 1893, Schatunowsky showed that 30 is the largest number all of whose totatives are primes; we show that this result cannot be proved, in any form, in Chebyshev's theorem (Bertrand's postulate), even if all irreducibles are primes. Bonse's inequality is shown to be indeed weaker than Chebyshev's theorem. Schatunowsky's theorem holds in together with Bonse's inequality, the existence of the greatest prime dividing certain types of numbers, and the condition that all irreducibles be prime.     

Reverse mathematics and Isbell's zig‐zag theorem

The paper explores the logical strength of Isbell's zig‐zag theorem using the framework of reverse mathematics. Working in , we show that is equivalent to Isbell's zig‐zag theorem for countable monoids: If B is a monoid extension of A, then is dominated by A if and only if b has a zig‐zag over A. Our proof of Isbell's zig‐zag theorem avoids use of strong comprehension axioms common in traditional proofs. We also analyze the strength of theorems concerning binary relations.     

The strong reflecting property and Harrington's Principle

In this paper we characterize the strong reflecting property for ‐cardinals for all , characterize Harrington's Principle and its generalization and discuss the relationship between the strong reflecting property for ‐cardinals and Harrington's Principle .     

Bounded dagger principles

For an uncountable cardinal κ, let be the assertion that every ω₁‐stationary preserving poset of size is semiproper. We prove that is a strong principle which implies a strong form of Chang's conjecture. We also show that implies that is presaturated.     

Three‐space type Hahn‐Banach properties

In set theory without the axiom of choice , three‐space type results for the Hahn‐Banach property are provided. We deduce that for every Hausdorff compact scattered space K , the Banach space C(K ) of real continuous functions on K satisfies the (multiple) continuous Hahn‐Banach property in . We also prove in Rudin's theorem: “Radon measures on Hausdorff compact scattered spaces are discrete”.     

A note on decidability of variables in intuitionistic propositional logic

An answer to the following question is presented: given a proof in classical propositional logic, for what small set of propositional variables p does it suffice to add all the formulae to Γ in order to intuitionistically prove A? This answer is an improvement of Ishihara's result for some cases.     

Lipschitz extensions of definable p‐adic functions

In this paper, we prove a definable version of Kirszbraun's theorem in a non‐Archimedean setting for definable families of functions in one variable. More precisely, we prove that every definable function , where and , that is λ‐Lipschitz in the first variable, extends to a definable function that is λ‐Lipschitz in the first variable.     

A note on the deductive strength of the Nielsen‐Schreier theorem

We show that the Boolean Prime Ideal Theorem () does not imply the Nielsen‐Schreier Theorem () in , thus strengthening the result of Kleppmann from “Nielsen‐Schreier and the Axiom of Choice” that the (strictly weaker than ) Ordering Principle () does not imply in . We also show that is false in Mostowski's Linearly Ordered Model of . The above two results also settle the corresponding open problems from Howard and Rubin's “Consequences of the Axiom of Choice”.     

On the strength of a weak variant of the axiom of counting

In this paper is used to denote Jensen's modification of Quine's ‘new foundations’ set theory () fortified with a type‐level pairing function but without the axiom of choice. The axiom is the variant of the axiom of counting which asserts that no finite set is smaller than its own set of singletons. This paper shows that proves the consistency of the simple theory of types with infinity (). This result implies that proves that consistency of , and that proves the consistency of .     

Classical provability of uniform versions and intuitionistic provability

Along the line of Hirst‐Mummert 9 and Dorais 4 , we analyze the relationship between the classical provability of uniform versions Uni(S) of Π₂‐statements S with respect to higher order reverse mathematics and the intuitionistic provability of S. Our main theorem states that (in particular) for every Π₂‐statement S of some syntactical form, if its uniform version derives the uniform variant of over a classical system of arithmetic in all finite types with weak extensionality, then S is not provable in strong semi‐intuitionistic systems including bar induction in all finite types but also nonconstructive principles such as K?nig's lemma and uniform weak K?nig's lemma . Our result is applicable to many mathematical principles whose sequential versions imply .     

Decreasing sentences in Simple Type Theory

We present various results regarding the decidability of certain sets of sentences by Simple Type Theory (). First, we introduce the notion of decreasing sentence, and prove that the set of decreasing sentences is undecidable by Simple Type Theory with infinitely many zero‐type elements (); a result that follows directly from the fact that every sentence is equivalent to a decreasing sentence. We then establish two different positive decidability results for a weak subtheory of . Namely, the decidability of (a subset of Σ₁) and (the set of all sentences , where φ is strictly decreasing). Finally, we present some consequences for the set of existential‐universal sentences. All the above results have direct implications for Quine's theory of “New Foundations” () and its weak subtheory .     

Fermat's last theorem and Catalan's conjecture in weak exponential arithmetics

We study Fermat's last theorem and Catalan's conjecture in the context of weak arithmetics with exponentiation. We deal with expansions of models of arithmetical theories (in the language ) by a binary (partial or total) function e intended as an exponential. We provide a general construction of such expansions and prove that it is universal for the class of all exponentials e which satisfy a certain natural set of axioms . We construct a model and a substructure with e total and (Presburger arithmetic) such that in both and Fermat's last theorem for e is violated by cofinally many exponents n and (in all coordinates) cofinally many pairwise linearly independent triples . On the other hand, under the assumption of ABC conjecture (in the standard model), we show that Catalan's conjecture for e is provable in (even in a weaker theory) and thus holds in and . Finally, we also show that Fermat's last theorem for e is provable (again, under the assumption of ABC in ) in “coprimality for e ”.     

A construction of real closed fields

We introduce a new construction of real closed fields by using an elementary extension of an ordered field with an integer part satisfying . This method can be extend to a finite extension of an ordered field with an integer part satisfying . In general, a field obtained from our construction is either real closed or algebraically closed, so an analogy of Ostrowski's dichotomy holds. Moreover we investigate recursive saturation of an o‐minimal extension of a real closed field by finitely many function symbols.     

Computable axiomatizability of elementary classes

The goal of this paper is to generalise Alex Rennet's proof of the non‐axiomatizability of the class of pseudo‐o‐minimal structures. Rennet showed that if is an expansion of the language of ordered fields and is the class of pseudo‐o‐minimal ‐structures (‐structures elementarily equivalent to an ultraproduct of o‐minimal structures) then is not computably axiomatizable. We give a general version of this theorem, and apply it to several classes of structures.     

Intermediate arithmetic operations on ordinal numbers

There are two well‐known ways of doing arithmetic with ordinal numbers: the “ordinary” addition, multiplication, and exponentiation, which are defined by transfinite iteration; and the “natural” (or “Hessenberg”) addition and multiplication (denoted ⊕ and ⊗), each satisfying its own set of algebraic laws. In 1909, Jacobsthal considered a third, intermediate way of multiplying ordinals (denoted × ), defined by transfinite iteration of natural addition, as well as the notion of exponentiation defined by transfinite iteration of his multiplication, which we denote . (Jacobsthal's multiplication was later rediscovered by Conway.) Jacobsthal showed these operations too obeyed algebraic laws. In this paper, we pick up where Jacobsthal left off by considering the notion of exponentiation obtained by transfinitely iterating natural multiplication instead; we shall denote this . We show that and that ; note the use of Jacobsthal's multiplication in the latter. We also demonstrate the impossibility of defining a “natural exponentiation” satisfying reasonable algebraic laws.     

Shelah's eventual categoricity conjecture in tame abstract elementary classes with primes

A new case of Shelah's eventual categoricity conjecture is established:

相似文献   

Embedding classical in minimal implicational logic

Consider the problem which set V of propositional variables suffices for whenever , where , and ?_c and ?_i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula . It is an easy consequence of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary.     

Continued fractions of primitive recursive real numbers

A theorem, proven in the present author's Master's thesis 2 states that a real number is ‐computable, whenever its continued fraction is in (the third Grzegorczyk class). The aim of this paper is to settle the matter with the converse of this theorem. It turns out that there exists a real number, which is ‐computable, but its continued fraction is not primitive recursive, let alone in . A question arises, whether some other natural condition on the real number can be combined with ‐computability, so that its continued fraction has low complexity. We give two such conditions. The first is ‐irrationality, based on a notion of Péter, and the second is polynomial growth of the terms of the continued fraction. Any of these two conditions, combined with ‐computability gives an (elementary) continued fraction. We conclude that all irrational algebraic real numbers and the number π have continued fractions in . All these results are generalized to higher levels of Grzegorczyk's hierarchy as well.