M. E. Rudin proved, under CH, that for each P-point p there exists a P-point q strictly RK-greater than p. This result was proved under ${\mathfrak {p}= \mathfrak {c}}$ by A. Blass, who also showed that each RK-increasing $ \omega $ -sequence of P-points is upper bounded by a P-point, and that there is an order embedding of the real line into the class of P-points with respect to the RK-ordering. In this paper, the results cited above are (...) proved under the assumption that $\mathfrak { b}=\mathfrak {c}$. A. Blass asked in 1973 which ordinals can be embedded in the set of P-points, and pointed out that such an ordinal cannot be greater than $ \mathfrak {c}^{+}$. In this paper it is proved, under $\mathfrak {b}=\mathfrak {c}$, that for each ordinal $\alpha < \mathfrak {c}^{+}$, there is an order embedding of $ \alpha $ into P-points. It is also proved, under $\mathfrak {b}=\mathfrak {c}$, that there is an embedding of the long line into P-points. (shrink)

The Rudin-Keisler ordering of ultrafilters is extended to complete Boolean algebras and characterised in terms of elementary embeddings of Boolean ultrapowers. The result is applied to show that the Rudin-Keisler poset of some atomless complete Boolean algebras is nontrivial.

In this article we, given a free ultrafilter p on ω, consider the following classes of ultrafilters:(1) T(p) - the set of ultrafilters Rudin-Keisler equivalent to p,(2) S(p)={q ∈ ω*:∃ f ∈ ω ω , strictly increasing, such that q=f β (p)},(3) I(p) - the set of strong Rudin-Blass predecessors of p,(4) R(p) - the set of ultrafilters equivalent to p in the strong Rudin-Blass order,(5) P RB (p) - the set of Rudin-Blass predecessors (...) of p, and(6) P RK (p) - the set of Rudin-Keisler predecessors of p,and analyze relationships between them. We introduce the semi-P-points as those ultrafilters p ∈ ω* for which P RB (p)=P RK (p), and investigate their relations with P-points, weak-P-points and Q-points. In particular, we prove that for every semi-P-point p its α-th left power α p is a semi-P-point, and we prove that non-semi-P-points exist in ZFC. Further, we define an order ⊴ in T(p) by r⊴q if and only if r ∈ S(q). We prove that (S(p),⊴) is always downwards directed, (R(p),⊴) is always downwards and upwards directed, and (T(p),⊴) is linear if and only if p is selective.We also characterize rapid ultrafilters as those ultrafilters p ∈ ω* for which R(p)∖S(p) is a dense subset of ω*.A space X is M-pseudocompact (for ) if for every sequence (U n ) n < ω of disjoint open subsets of X, there are q ∈ M and x ∈ X such that x=q-lim (U n ); that is, for every neighborhood V of x. The P RK (p)-pseudocompact spaces were studied in [ST].In this article we analyze M-pseudocompactness when M is one of the classes S(p), R(p), T(p), I(p), P RB (p) and P RK (p). We prove that every Frolik space is S(p)-pseudocompact for every p ∈ ω*, and determine when a subspace with is M-pseudocompact. (shrink)

In this paper, we study some new examples of ideals on $$\omega $$ with maximal Tukey type (that is, maximal among partial orders of size continuum). This discussion segues into an examination of a refinement of the Tukey order—known as the weak Rudin–Keisler order—and its structure when restricted to these ideals of maximal Tukey type. Mirroring a result of Fremlin (Note Mat 11:177–214, 1991) on the Tukey order, we also show that there is an analytic (...) P-ideal above all other analytic P-ideals in the weak Rudin–Keisler order. (shrink)

A 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ 1 -sequence of ultrafilters D α such that the strict Rudin-Keisler predecessors of D α are precisely the isomorphs of the D β 's for $\beta.

We study the Rudin–Keisler pre-order on Fréchet–Urysohn ideals on $\omega $. We solve three open questions posed by S. García-Ferreira and J. E. Rivera-Gómez in the articles [5] and [6] by establishing the following results: •For every AD family $\mathcal {A},$ there is an AD family $\mathcal {B}$ such that $\mathcal {A}^{\perp } <_{{\textsf {RK}}}\mathcal {B}^{\perp }.$ •If $\mathcal {A}$ is a nowhere MAD family of size $\mathfrak {c}$ then there is a nowhere MAD family $\mathcal {B}$ (...) such that $\mathcal {I}\left $ and $\mathcal {I}\left $ are Rudin–Keisler incomparable.•There is a family $\left \{ \mathcal {B}_{\alpha }\mid \alpha \in \mathfrak {c}\right \} $ of nowhere MAD families such that if $\alpha \neq \beta $, then $\mathcal {I}\left $ and $\mathcal {I}\left $ are Rudin–Keisler incomparable.Here $\mathcal {I}$ denotes the ideal generated by an AD family $\mathcal {A}$.In the context of hyperspaces with the Vietoris topology, for a Fréchet–Urysohn-filter $\mathcal {F}$ we let $\mathcal {S}_{c}\left \right ) $ be the hyperspace of nontrivial convergent sequences of the space consisting of $\omega $ as discrete subset and only one accumulation point $\mathcal {F}$ whose neighborhoods are the elements of $\mathcal {F}$ together with the singleton $\{\mathcal {F}\}$. For a FU-filter $\mathcal {F}$ we show that the following are equivalent: • $\mathcal {F}$ is a FUF-filter.• $\mathcal {S}_{c}\left \right ) $ is Baire. (shrink)

We discuss the finite-to-one Rudin-Keisler ordering of ultrafilters on the natural numbers, which we baptize the Rudin-Blass ordering in honour of Professor Andreas Blass who worked extensively in the area. We develop and summarize many of its properties in relation to its bounding and dominating numbers, directedness, and provide applications to continuum theory. In particular, we prove in ZFC alone that there exists an ultrafilter with no Q-point below in the Rudin-Blass ordering.

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory , has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In (...) this paper we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

THE DESTINY OF MAN: Beyond Socrates to Programmed PhilosophyThe Destiny of Man tells the scientific story of the world that is based on a Theory of the World: which Unifies knowledge, Simplifies education and creates one culture thus realizing mankind's quest to find his destiny by knowing the worldThe story starts with the first Western scientists, Thales and his colleagues in pre-Hellenic Greece, through the contributions of modern scientists. Conclusion: The world is a programmed system and mankind has discovered its (...) program. This partly realizes the enduring quest of mankind, namely, to find his destiny by knowing the world. The world program enables the following selected transitions among others:- From: To:- Information Understanding- Fragmented language Comprehensive language- Classical philosophy Scientific philosophy- The Age of Specialties The Age of Generalism or Universal Science- 18th century Literary Enlightenment 21st century Scientific Enlightenment- Eclectic education Systematic, axiomatic education- The religious-scientific polemic Its resolution- Fragmented cultures One world culture. (shrink)

We settle a number of questions concerning definability in first order logic with an extra predicate symbol ranging over semi-linear sets. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes (...) small restrictions on the semi-linear sets considered. (shrink)

We show that each of the five basic theories of second order arithmetic that play a central role in reverse mathematics has a natural counterpart in the language of nonstandard arithmetic. In the earlier paper [3] we introduced saturation principles in nonstandard arithmetic which are equivalent in strength to strong choice axioms in second order arithmetic. This paper studies principles which are equivalent in strength to weaker theories in second order arithmetic.

The randomization of a complete first-order theory [Formula: see text] is the complete continuous theory [Formula: see text] with two sorts, a sort for random elements of models of [Formula: see text] and a sort for events in an underlying atomless probability space. We study independence relations and related ternary relations on the randomization of [Formula: see text]. We show that if [Formula: see text] has the exchange property and [Formula: see text], then [Formula: see text] has a strict (...) independence relation in the home sort, and hence is real rosy. In particular, if [Formula: see text] is o-minimal, then [Formula: see text] is real rosy. (shrink)

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As (...) a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.We introduce another operation alt on properties which has the same relationship with the Circuit Value Problem as reach has with the Directed Reachability Problem. We use alt to show that Πn⊈ FO, Σn⊈ FO, and Δn+1⊈ FOB, solving some open problems raised in [Mat98]. (shrink)

In a nonstandard universe, the κ-saturation property states that any family of fewer than κ internal sets with the finite intersection property has a nonempty intersection. An ordered field F is said to have the λ-Bolzano-Weierstrass property iff F has cofinality λ and every bounded λ-sequence in F has a convergent λ-subsequence. We show that if $\kappa < \lambda$ are uncountable regular cardinals and $\beta^\alpha < \lambda$ whenever $\alpha < \kappa$ and $\beta < \lambda$, then there is a κ-saturated nonstandard (...) universe in which the hyperreal numbers have the λ-Bolzano-Weierstrass property. The result also applies to certain fragments of set theory and second order arithmetic. (shrink)

In a nonstandard universe, the $\kappa$-saturation property states that any family of fewer than $\kappa$ internal sets with the finite intersection property has a nonempty intersection. An ordered field $F$ is said to have the $\lambda$-Bolzano-Weierstrass property iff $F$ has cofinality $\lambda$ and every bounded $\lambda$-sequence in $F$ has a convergent $\lambda$-subsequence. We show that if $\kappa < \lambda$ are uncountable regular cardinals and $\beta^\alpha < \lambda$ whenever $\alpha < \kappa$ and $\beta < \lambda$, then there is a $\kappa$-saturated nonstandard (...) universe in which the hyperreal numbers have the $\lambda$-Bolzano-Weierstrass property. The result also applies to certain fragments of set theory and second order arithmetic. (shrink)

A general metatheorem is proved which reduces a wide class of statements about continuous time stochastic processes to statements about discrete time processes. We introduce a strong language for stochastic processes, and a concept of forcing for sequences of discrete time processes. The main theorem states that a sentence in the language is true if and only if it is forced. Although the stochastic process case is emphasized in order to motivate the results, they apply to a wider class (...) of random variables. At the end of the paper we illustrate how the theorem can be used with three applications involving submartingales. (shrink)

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory, has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this (...) paper we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

In prior work [7] we considered networks of agents who have knowledge bases in first order logic, and report facts to their neighbors that are in their common languages and are provable from their knowledge bases, in order to help a decider verify a single sentence. In report complete networks, the signatures of the agents and the links between agents are rich enough to verify any deciderʼs sentence that can be proved from the combined knowledge base. This paper (...) introduces a more general setting where new observations may be added to knowledge bases and the decider must choose a sentence from a set of alternatives. We consider the question of when it is possible to prepare in advance a finite plan to generate reports within the network. We obtain conditions under which such a plan exists and is guaranteed to produce the right choice under any new observations. (shrink)

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a (...) more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (shrink)

We consider extensions of Peano arithmetic suitable for doing some of nonstandard analysis, in which there is a predicate N(x) for an elementary initial segment, along with axiom schemes approximating ω 1 -saturation. We prove that such systems have the same proof-theoretic strength as their natural analogues in second order arithmetic. We close by presenting an even stronger extension of Peano arithmetic, which is equivalent to ZF for arithmetic statements.

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that (...) every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees, that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$, this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$, which shows that the Borel version of Sacks’ question has a negative answer.We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.prepared by Patrick Lutz.E-mail: [email protected]. (shrink)

An ordering (≤K) on maximal almost disjoint (MAD) families closely related to destructibility of MAD families by forcing is introduced and studied. It is shown that the order has antichains of size.

We study ultrafilters onω2produced by forcing with the quotient of${\cal P}$(ω2) by the Fubini square of the Fréchet filter onω. We show that such an ultrafilter is a weak P-point but not a P-point and that the only nonprincipal ultrafilters strictly below it in the Rudin–Keisler order are a single isomorphism class of selective ultrafilters. We further show that it enjoys the strongest square-bracket partition relations that are possible for a non-P-point. We show that it is not (...) basically generated but that it shares with basically generated ultrafilters the property of not being at the top of the Tukey ordering. In fact, it is not Tukey-above [ω1]<ω, and it has only continuum many ultrafilters Tukey-below it. A tool in our proofs is the analysis of similar (but not the same) properties for ultrafilters obtained as the sum, over a selective ultrafilter, of nonisomorphic selective ultrafilters. (shrink)

We characterize some large cardinal properties, such as μ-measurability and P 2 (κ)-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on P κ (2 κ ). This leads to the characterization of 2 κ -supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, Full κ , of P κ (2 κ ), whose elements code measures on cardinals less (...) than κ. The hypothesis that Full κ is stationary (a weaker assumption than 2 κ -supercompactness) is equivalent to a higher order Lowenheim-Skolem property, and settles a question about directed versus chain-type unions on P κ λ. (shrink)

We characterize some large cardinal properties, such as $\mu$-measurability and $P^2(\kappa)$-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on $P_\kappa(2^\kappa)$. This leads to the characterization of $2^\kappa$-supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, $\mathrm{Full}_\kappa$, of $P_\kappa(2^\kappa)$, whose elements code measures on cardinals less than $\kappa$. The hypothesis that $\mathrm{Full}_\kappa$ is stationary (a weaker assumption than $2^\kappa$-supercompactness) is (...) equivalent to a higher order Lowenheim-Skolem property, and settles a question about directed versus chain-type unions on $P_\kappa\lambda$. (shrink)

In this paper, we provide a new characterization of Keisler’s order in terms of saturation of Boolean ultrapowers. To do so, we apply and expand the framework of ‘separation of variables’ recently developed by Malliaris and Shelah. We also show that good ultrafilters on Boolean algebras are precisely the ones which capture the maximum class in Keisler’s order, answering a question posed by Benda in 1974.

We continue the study of Rosenthal families initiated by Damian Sobota. We show that every Rosenthal filter is the intersection of a finite family of ultrafilters that are pairwise incomparable in the Rudin-Keisler partial ordering of ultrafilters. We introduce a property of filters, called an \-filter, properly between a selective filter and a \-filter. We prove that every \-ultrafilter is a Rosenthal family. We prove that it is consistent with ZFC to have uncountably many \-ultrafilters such that any (...) intersection of finitely many of them is a Rosenthal filter. (shrink)

There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

We show that the analysis of Keisler’s order can be localized to the study of φ-types. Specifically, if is a regular ultrafilter on λ such that and M is a model whose theory is countable, then is λ+-saturated iff it realizes all φ-types of size λ.

We study the structure of analytic ideals of subsets of the natural numbers. For example, we prove that for an analytic ideal I, either the ideal {X (Ω × Ω: En X ({0, 1,…,n} × Ω } is Rudin-Keisler below I, or I is very simply induced by a lower semicontinuous submeasure. Also, we show that the class of ideals induced in this manner by lsc submeasures coincides with Polishable ideals as well as analytic P-ideals. We study this (...) class of ideals and characterize, for example, when the ideals in it are Fσ or when they carry a locally compact group topology. We apply these results to Borel partial orders to rederive a theorem of Todorcevic and to Borel equivalence relations to answer a question of Kechris and Louveau. As another application we give a characterization of σ-ideals of μ-zero sets for Maharam submeasures μ on the Cantor set which is to a large extent analogous to a characterization of the meager ideal due to Kechris and the author. (shrink)

We generalize the Bolzano-Weierstrass theorem on ideal convergence. We show examples of ideals with and without the Bolzano-Weierstrass property, and give characterizations of BW property in terms of submeasures and extendability to a maximal P-ideal. We show applications to Rudin-Keisler and Rudin-Blass orderings of ideals and quotient Boolean algebras. In particular we show that an ideal does not have BW property if and only if its quotient Boolean algebra has a countably splitting family.

The generic ultrafilter${\cal G}_2 $forced by${\cal P}\left/\left$was recently proved to be neither maximum nor minimum in the Tukey order of ultrafilters, but it was left open where exactly in the Tukey order it lies. We prove${\cal G}_2 $that is in fact Tukey minimal over its projected Ramsey ultrafilter. Furthermore, we prove that for each${\cal G}_2 $, the collection of all nonprincipal ultrafilters Tukey reducible to the generic ultrafilter${\cal G}_k $forced by${\cal P}\left/{\rm{Fin}}^{ \otimes k} $forms a chain of lengthk. (...) Essential to the proof is the extraction of a dense subsetεkfrom +which we prove to be a topological Ramsey space. The spacesεk,k≥ 2, form a hierarchy of high dimensional Ellentuck spaces. New Ramsey-classification theorems for equivalence relations on fronts on εkare proved, extending the Pudlák–Rödl Theorem for fronts on the Ellentuck space, which are applied to find the Tukey and Rudin–Keisler structures below${\cal G}_k $. (shrink)