Our main results are:

Theorem 1. Con(ZFC + “every function f: ω1 → ω1 is dominated by a canonical function”) implies Con(ZFC + “there exists an inaccessible limit of measurable cardinals”). [In fact equiconsistency holds.]

Theorem 3. Con(ZFC + “there exists a non-regular uniform ultrafilter on ω1”) implies Con(ZFC + “there exists an inaccessible stationary limit of measurable cardinals”).

Theorem 5. Con (ZFC + “there exists an ω1-sequence of ω1-complete uniform filters on ω1 s.t. every A ⊆ ω1 is measurable w.r.t. a filter in (Ulam property)”) implies Con(ZFC + “there exists an inaccessible stationary limit of measurable cardinals”).

We start with a discussion of the canonical functions and look at some combinatorial principles. Assuming the domination property of Theorem 1, we use the Ketonen diagram to show that ω2V is a limit of measurable cardinals in Jensen's core model KMO for measures of order zero. Using related arguments we show that ω2V is a stationary limit of measurable cardinals in KMO, if there exists a weakly normal ultrafilter on ω1. The proof yields some other results, e.g., on the consistency strength of weak*-saturated filters on ω1, which are of interest in view of the classical Ulam problem.

The generality of a derivation is an equivalence relation on the set of occurrences of variables in its premises and conclusion such that two occurrences of the same variable are in this relation if and only if they must remain occurrences of the same variable in every generalization of the derivation. The variables in question are propositional or of another type. A generalization of the derivation consists in diversifying variables without changing the rules of inference.

This paper examines in the setting of categorial proof theory the conjecture that two derivations with the same premises and conclusions stand for the same proof if and only if they have the same generality. For that purpose generality is defined within a category whose arrows are equivalence relations on finite ordinals, where composition is rather complicated. Several examples are given of deductive systems of derivations covering fragments of logic, with the associated map into the category of equivalence relations of generality.

This category is isomorphically represented in the category whose arrows are binary relations between finite ordinals, where composition is the usual simple composition of relations. This representation is related to a classical representation result of Richard Brauer.

Restricted to first-order formulas, the rules of inference in the Curry-Howard type theory are equivalent to those of first-order predicate logic as formalized by Heyting, with one exception: ∃-elimination in the Curry-Howard theory, where ∃x: A,F(x) is understood as disjoint union, are the projections, and these do not preserve first-orderedness. This note shows, however, that the Curry-Howard theory is conservative over Heyting's system.

We study the problem of existence and generic existence of ultrafilters on ω. We prove a conjecture of Jörg Brendle's showing that there is an ultrafilter that is countably closed but is not an ordinal ultrafilter under CH. We also show that Canjar's previous partial characterization of the generic existence of Q-points is the best that can be done. More simply put, there is no normal cardinal invariant equality that fully characterizes the generic existence of Q-points. We then sharpen results on generic existence with the introduction of σ-compact ultrafilters. We show that the generic existence of said ultrafilters is equivalent to . This result, taken along with our result that there exists a Kσ, non-countably closed ultrafilter under CH, expands the size of the class of ultrafilters that were known to fit this description before. From the core of the proof, we get a new result on the cardinal invariants of the continuum, i.e., the cofinality of the sets with σ-compact closure is .

Let M be an o-minimal expansion of an ordered field. Let φ be a formula in the language of ordered domains. In this note we establish some topological properties which are transferred from φM to φR and vice versa. Then, we apply these transfer results to give a new proof of a result of M. Edmundo—based on the work of A. Strzebonski—showing the existence of torsion points in any definably compact group defined in an o-minimal expansion of an ordered field.

In the constructive theory of uniform spaces there occurs a technique of proof in which the application of a weak form of the law of excluded middle is circumvented by purely analytic means. The essence of this proof–technique is extracted and then applied in several different situations.

For n < ω, expand the structure (n, S, I, F) (with S the successor relation, I, F as the initial and final element) by forming graphs with edge probability n−α for irrational α, with 0 < α < 1. The sentences in the expanded language, which have limit probability 1, form a complete and stable theory.

It is proved in this paper that the positive abstraction scheme is consistent with extensionality only if one drops equality out of the language. The theory obtained is then compared with GPK, a well-known set theory based on an extended positive comprehension scheme.

We strengthen a theorem of Gitik and Shelah [6] by showing that if κ is either weakly inaccessible or the successor of a singular cardinal and S is a stationary subset of κ such that NSκ↾S is saturated then κ ∖ S is fat. Using this theorem we derive some results about the existence of fat stationary sets. We then strengthen some results due to Baumgartner and Taylor [2], showing in particular that if I is a λ+++-saturated normal ideal on Pκλ then the conditions of being λ+-preserving, weakly presaturated, and presaturated are equivalent for I.

Dividing independence for ultraimaginaries is neither symmetric nor transitive. Moreover, any notion of independence satisfying certain axioms (weaker than those for independence in a simple theory) and denned for all ultraimaginary sorts, is necessarily trivial.

This paper points out an error of Parigot's proof of strong normalization of second order classical natural deduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.

We show that a solution to Hilbert's Tenth Problem in the rings of algebraic integers and bigger subrings of number fields where it is currently not known, is equivalent to a problem of bounding archimedean valuations over non-real number fields.

Tarski [5] showed that for any set X, its set ω(X) of well-orderable subsets has cardinality strictly greater than that of X, even in the absence of the axiom of choice. We construct a Fraenkel-Mostowski model in which there is an infinite strictly descending sequence under the relation ∣ω(X)∣ = ∣Y∣. This contrasts with the corresponding situation for power sets, where use of Hartogs' ℵ-function easily establishes that there can be no infinite descending sequence under the relation .

A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0′-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. So the main criterion for such classification is the variety of the effective ways we have to approximate a real number. We exhibit extreme cases of such approximation structures and prove a number of related results.

Fields of characteristic zero with several commuting derivations can be treated as fields equipped with a space of derivations that is closed under the Lie bracket. The existentially closed instances of such structures can then be given a coordinate-free characterization in terms of differential forms. The main tool for doing this is a generalization of the Frobenius Theorem of differential geometry.

In [12] we proved the following isotropy-reflection principle:

Theorem. Let F be a formally real field and let Fp denote its Pythagorean closure. The natural embedding of reduced special groups from Gred(F) into Gred(Fp) = G(FP) induced by the inclusion of fields, reflects isotropy.

Here Gred(F) denotes the reduced special group (with underlying group Ḟ/ΣḞ2) associated to the field F, henceforth assumed formally real; cf. [11], Chapter 1, §3, for details.

The result proved in [12] is, in fact, more general. For example, the Pythagorean closure Fp can be replaced in the statement above by the intersection of all real closures of F (inside a fixed algebraic closure). Similar statements hold, more generally, for all relative Pythagorean closures of F in the sense of Becker [3], Chapter II, §3.

Since the notion of isotropy of a quadratic form can be expressed by a first-order formula in the natural language LSG for special groups (with the coefficients as parameters), this result raises the question whether the embedding ιFFp: Gred(F) ↪ G (Fp) is elementary. Further, since the LSG-formula expressing isotropy is positive-existential, one may also ask whether ιFFp reflects all (closed) formulas ofthat kind with parameters in Gred(F).

In this paper we give a negative answer to the first of these questions, for a vast class of formally real (non-Pythagorean) fields F (Prop. 5.1). This follows from rather general preservation results concerning the “Boolean hull” and the “reduced quotient” operations on special groups.

We say that a computably enumerable (c. e.) degree a is plus-cupping, if for every c.e. degree x with 0 < x ≤ a, there is a c. e. degree y ≠ 0′ such that x ∨ y = 0′. We say that a is n-plus-cupping, if for every c. e. degree x, if 0 < x ≤ a, then there is a lown c. e. degree I such that x ∨ I = 0′. Let PC and PCn be the set of all plus-cupping, and n-plus-cupping c. e. degrees respectively. Then PC1 ⊆ PC2 ⊆ PC3 = PC. In this paper we show that PC1 ⊂ PC2, so giving a nontrivial hierarchy for the plus cupping degrees. The theorem also extends the result of Li, Wu and Zhang [14] showing that LC1 ⊂ LC2, as well as extending the Harrington plus-cupping theorem [8].

We prove that every countable jump upper semilattice can be embedded in , where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, and is the jusl of Turing degrees. As a corollary we get that the existential theory of 〈D, ≤T, ∨, ′〉 is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier free 1-type of jusl with 0 is realized in . On the other hand, we show that every quantifier free 1-type of jump partial ordering (jpo) with 0 is realized in . Moreover, we show that if every quantifier free type, p(x1,…, xn), of jpo with 0, which contains the formula x1 ≤ 0(m) & … & xn ≤ 0(m) for some m, is realized in , then every quantifier free type of jpo with 0 is realized in .

We also study the question of whether every jusl with the c.p.p. and size is embeddable in . We show that for the answer is no, and that for κ = ℵ1 it is independent of ZFC. (It is true if MA(κ) holds.)

This paper introduces an extension of Kleene's axiomatization of Brouwer's intuitionistic analysis, in which the classical arithmetical and analytical hierarchies are faithfully represented as hierarchies of the domains of continuity. A domain of continuity is a relation R(α) on Baire space with the property that every constructive partial functional defined on {α: R(α)} is continuous there. The domains of continuity for coincide with the stable relations (those equivalent in to their double negations), while every relation R(α) is equivalent in to ∃βA(α, β) for some stable A(α, β) (which belongs to the classical analytical hierarchy).

The logic of is intuitionistic. The axioms of include countable comprehension, bar induction, Troelstra's generalized continuous choice, primitive recursive Markov's Principle and a classical axiom of dependent choices proposed by Krauss. Constructive dependent choices, and constructive and classical countable choice, are theorems, is maximal with respect to classical Kleene function realizability, which establishes its consistency. The usual disjunction and (recursive) existence properties ensure that preserves the constructive sense of “or” and “there exists.”

We show that if A and are automorphic via Φ then the structures (A) and () are Δ30-isomorphic via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.