On the finite axiomatizability of

The question of whether the bounded arithmetic theories and are equal is closely connected to the complexity question of whether is equal to . In this paper, we examine the still open question of whether the prenex version of , , is equal to . We give new dependent choice‐based axiomatizations of the ‐consequences of and . Our dependent choice axiomatizations give new normal forms for the ‐consequences of and . We use these axiomatizations to give an alternative proof of the finite axiomatizability of and to show new results such as is finitely axiomatized and that there is a finitely axiomatized theory, , containing and contained in . On the other hand, we show that our theory for splits into a natural infinite hierarchy of theories. We give a diagonalization result that stems from our attempts to separate the hierarchy for .     

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.     

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”.     

Free sets for set‐mappings relative to a family of sets

Given a family of subsets of , we try to compute the least natural number n such that for every function there exists a bijection such that for all .     

Some properties of infinite factorials

With the Axiom of Choice , for any infinite cardinal but, without , we cannot conclude any relationship between and for an arbitrary infinite cardinal . In this paper, we give some properties of in the absence of and compare them to those of for an infinite cardinal . Among our results, we show that “ for any infinite cardinal and any natural number n” is provable in although “ for any infinite cardinal ” is not.     

Two new equivalents of Lindelöf metric spaces

In the realm of Lindelöf metric spaces the following results are obtained in : (i) If is a Lindelöf metric space then it is both densely Lindelöf and almost Lindelöf. In addition, under the countable axiom of choice , the three notions coincide. (ii) The statement “every separable metric space is almost Lindelöf” implies that every infinite subset of has a countably infinite subset). (iii) The statement “every almost Lindelöf metric space is quasi totally bounded implies . (iv) The proposition “every quasi totally bounded metric space is separable” lies, in the deductive hierarchy of choice principles, strictly between the countable union theorem and . Likewise, the statement “every pre‐Lindelöf (or Lindelöf) metric space is separable” lies strictly between and .     

What is the theory without power set?

We show that the theory , consisting of the usual axioms of but with the power set axiom removed—specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well‐ordered—is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context. For example, there are models of in which ω₁ is singular, in which every set of reals is countable, yet ω₁ exists, in which there are sets of reals of every size , but none of size , and therefore, in which the collection axiom fails; there are models of for which the ?o? theorem fails, even when the ultrapower is well‐founded and the measure exists inside the model; there are models of for which the Gaifman theorem fails, in that there is an embedding of models that is Σ₁‐elementary and cofinal, but not elementary; there are elementary embeddings of models whose cofinal restriction is not elementary. Moreover, the collection of formulas that are provably equivalent in to a Σ₁‐formula or a Π₁‐formula is not closed under bounded quantification. Nevertheless, these deficits of are completely repaired by strengthening it to the theory , obtained by using collection rather than replacement in the axiomatization above. These results extend prior work of Zarach 18 .     

The Hypothesis and a supercompact cardinal

In this paper, we prove that: if κ is supercompact and the Hypothesis holds, then there is a proper class of regular cardinals in which are measurable in . Woodin also proved this result independently 11 . As a corollary, we prove Woodin's Local Universality Theorem. This work shows that under the assumption of the Hypothesis and supercompact cardinals, large cardinals in are reflected to be large cardinals in in a local way, and reveals the huge difference between ‐supercompact cardinals and supercompact cardinals under the Hypothesis.     

Two kinds of fixed point theorems and reverse mathematics

In this paper, we investigate the logical strength of two types of fixed point theorems in the context of reverse mathematics. One is concerned with extensions of the Banach contraction principle. Among theorems in this type, we mainly show that the Caristi fixed point theorem is equivalent to over . The other is dedicated to topological fixed point theorems such as the Brouwer fixed point theorem. We introduce some variants of the Fan‐Browder fixed point theorem and the Kakutani fixed point theorem, which we call and , respectively. Then we show that is equivalent to and is equivalent to , over . In addition, we also study the application of the Fan‐Browder fixed point theorem to game systems.     

Models of : when two elements are necessarily order automorphic

We are interested in the question of how much the order of a non‐standard model of can determine the model. In particular, for a model M, we want to characterize the complete types of non‐standard elements such that the linear orders and are necessarily isomorphic. It is proved that this set includes the complete types such that if the pair realizes it (in M) then there is an element c such that for all standard n, , , , and . We prove that this is optimal, because if holds, then there is M of cardinality ?₁ for which we get equality. We also deal with how much the order in a model of may determine the addition.     

The tree property and the continuum function below

We say that a regular cardinal κ, , has the tree property if there are no κ‐Aronszajn trees; we say that κ has the weak tree property if there are no special κ‐Aronszajn trees. Starting with infinitely many weakly compact cardinals, we show that the tree property at every even cardinal , , is consistent with an arbitrary continuum function below which satisfies , . Next, starting with infinitely many Mahlo cardinals, we show that the weak tree property at every cardinal , , is consistent with an arbitrary continuum function below which satisfies , . Thus the tree property has no provable effect on the continuum function below except for the trivial requirement that the tree property at implies for every infinite κ.     

Ramsey for ultrafilter mappings and their Dedekind cuts

Associated to each ultrafilter on ω and each map is a Dedekind cut in the ultrapower . Blass has characterized, under , the cuts obtainable when is taken to be either a p‐point ultrafilter, a weakly‐Ramsey ultrafilter or a Ramsey ultrafilter. Dobrinen and Todor?evi? have introduced the topological Ramsey space . Associated to the space is a notion of Ramsey ultrafilter for generalizing the familiar notion of Ramsey ultrafilter on ω. We characterize, under , the cuts obtainable when is taken to be a Ramsey for ultrafilter and p is taken to be any map. In particular, we show that the only cut obtainable is the standard cut, whose lower half consists of the collection of equivalence classes of constants maps. Forcing with using almost‐reduction adjoins an ultrafilter which is Ramsey for . For such ultrafilters , Dobrinen and Todor?evi? have shown that the Rudin‐Keisler types of the p‐points within the Tukey type of consists of a strictly increasing chain of rapid p‐points of order type ω. We show that for any Rudin‐Keisler mapping between any two p‐points within the Tukey type of the only cut obtainable is the standard cut. These results imply existence theorems for special kinds of ultrafilters.     

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

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

相似文献   

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 ”.     

Many symmetrically indivisible structures

A structure in a first‐order language is indivisible if for every colouring of its universe M in two colours, there is a monochromatic such that . Additionally, we say that is symmetrically indivisible if can be chosen to be symmetrically embedded in (that is, every automorphism of can be extended to an automorphism of ). In the following paper we give a general method for constructing new symmetrically indivisible structures out of existing ones. Using this method, we construct many non‐isomorphic symmetrically indivisible countable structures in given (elementary) classes and answer negatively the following question from 6 : Let be a symmetrically indivisible structure in a language . Let . Is symmetrically indivisible?     

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 .     

A wild model of linear arithmetic and discretely ordered modules

Linear arithmetics are extensions of Presburger arithmetic () by one or more unary functions, each intended as multiplication by a fixed element (scalar), and containing the full induction schemes for their respective languages. In this paper, we construct a model of the 2‐linear arithmetic (linear arithmetic with two scalars) in which an infinitely long initial segment of “Peano multiplication” on is ‐definable. This shows, in particular, that is not model complete in contrast to theories and that are known to satisfy quantifier elimination up to disjunctions of primitive positive formulas. As an application, we show that , as a discretely ordered module over the discretely ordered ring generated by the two scalars, does not have the NIP, answering negatively a question of Chernikov and Hils.     

A Groszek‐Laver pair of undistinguishable ‐classes

A generic extension of the constructible universe by reals is defined, in which the union of ‐classes of x and y is a lightface set, but neither of these two ‐classes is separately ordinal‐definable.     

The existence of free ultrafilters on ω does not imply the extension of filters on ω to ultrafilters

Let X be an infinite set and let and denote the propositions “every filter on X can be extended to an ultrafilter” and “X has a free ultrafilter”, respectively. We denote by the Stone space of the Boolean algebra of all subsets of X. We show:

相似文献   

The length of an intersection

A poset is well‐partially ordered (WPO) if all its linear extensions are well orders; the supremum of ordered types of these linear extensions is the length , of p . We prove that if the vertex set X is infinite, of cardinality κ, and the ordering ⩽ is the intersection of finitely many well partial orderings of X , , then, letting , with , denote the euclidian division by κ (seen as an initial ordinal) of the length of each corresponding poset: where denotes the least initial ordinal greater than the ordinal . This inequality is optimal. This result answers questions of Forster.