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.

The price is failure on a class of inductive inference problems that are easily solved, in contrast, by nonBayesian mechanical learners. By “mechanical” is meant “simulable by Turing machine”.

One of the central tenets of Bayesianism, which is common to the heterogeneous collection of views which fall under this rubric, is that hypothesis change proceeds via conditionalization on accumulated evidence, the posterior probability of a given hypothesis on the evidence being computed using Bayes's theorem. We show that this strategy for hypothesis change precludes the solution of certain problems of inductive inference by mechanical means—problems which are solvable by mechanical means when the restriction to this Bayesian strategy is lifted. Our discussion proceeds as follows. After some technical preliminaries, the concept of (formal) learner is introduced along with a criterion of inferential success. Next we specify a class of inductive inference problems, and then define the notion of “Bayesian behavior” on those problems. Finally, we exhibit an inductive inference problem from the specified class such that (a) some nonmechanical Bayesian learner solves the problem, (b) some nonBayesian mechanical learner solves the problem, (c) some mechanical learner manifests Bayesian behavior on the problem, but (d) no mechanical Bayesian learner solves the problem.

Insofar as possible terminology and notation are drawn from Osherson, Stob, and Weinstein [1986].

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

With the help of various square principles, we obtain results concerning the consistency strength of several statements about trees containing ascent paths, special trees, and strong chain conditions. Building on a result that shows that Todorčević’s principle $\square \left( {\kappa ,\lambda } \right)$ implies an indexed version of $\square \left( {\kappa ,\lambda } \right)$, we show that for all infinite, regular cardinals $\lambda < \kappa$, the principle $\square \left( \kappa \right)$ implies the existence of a κ-Aronszajn tree containing a λ-ascent path. We then provide a complete picture of the consistency strengths of statements relating the interactions of trees with ascent paths and special trees. As a part of this analysis, we construct a model of set theory in which ${\aleph _2}$-Aronszajn trees exist and all such trees contain ${\aleph _0}$-ascent paths. Finally, we use our techniques to show that the assumption that the κ-Knaster property is countably productive and the assumption that every κ-Knaster partial order is κ-stationarily layered both imply the failure of $\square \left( \kappa \right)$.

We consider the problem whether the theorems of the fragments form a strictly increasing hierarchy. We shall show a link to some results about the lengths of proofs in predicate logic that supports the conjecture that the hierarchy is strictly increasing.

We make a more systematic study of the van Douwen diagram for cardinal coefficients related to combinatorial properties of partitions of natural numbers.

This paper constitutes a short report on the proof theory which developed in the course of an investigation of Essenin-Volpin's foundational studies (see his paper in Infinitistic methods.) The Infinitistic methods paper is primarily concerned with proving the consistency of ZF. His arguments employ some very unusual ideas, especially that of the possibility of different length natural number series. The modal setting which he uses for these ideas and which is really all important is not reflected in the present paper. Only a simple representation of this idea is considered, namely, the use of *N, the nonstandard natural numbers, together with N, the standard natural numbers, to play the roles of a “long” and a “short” number series.

It will be useful to make a few general remarks before beginning on the technical details. These remarks are especially directed towards those people who have read Essenin-Volpin's work, the above-mentioned paper in particular and the one appearing in the proceedings of the 1968 Conference on Intuitionism and Proof Theory at Buffalo, New York.

I want to draw a comparison between the ultra-intuitionistic position of Essenin-Volpin on the one hand with the intuitionistic and realistic positions on the foundations of mathematics on the other hand. Intuitionism makes a transition from the traditional mathematical position (realism) that the rules of mathematical reasoning must be constructed so as to preserve truth (as known by an omniscient being about “the real world” of abstract mathematical objects) to the position that the rules of mathematical reasoning must be in accord with the process of knowing (performed by the “ideal mathematician” or “creative subject”) about the world of mental constructions. Ultra-intuitionism deepens and extends this transition to the position that the fundamental rules of mathematical reasoning must be in accord with processes of knowing accessible to human beings.

In this paper, we analyze structures of Zermelo degrees via a list of four degree theoretic questions (see §2) in various fine structure extender models, or under large cardinal assumptions. In particular we give a detailed analysis of the structures of Zermelo degrees in the Mitchell model for ω many measurable cardinals. It turns out that there is a profound correlation between the complexity of the degree structures at countable cofinality singular cardinals and the large cardinal strength of the relevant cardinals. The analysis applies to general degree notions, Zermelo degree is merely the author’s choice for illustrating the idea.

I0(λ) is the assertion that there is an elementary embedding j : L(Vλ+1) → L(Vλ+1) with critical point < λ. We show that under I0(λ), the structure of Zermelo degrees at λ is very complicated: it has incomparable degrees, is not dense, satisfies Posner–Robinson theorem etc. In addition, we show that I0 together with a mild condition on the critical point of the embedding implies that the degree determinacy for Zermelo degrees at λ is false in L(Vλ+1). The key tool in this paper is a generic absoluteness theorem in the theory of I0, from which we obtain an analogue of Perfect Set Theorem for “projective” subsets of Vλ+1, and the Posner–Robinson follows as a corollary. Perfect Set Theorem and Posner–Robinson provide evidences supporting the analogy between $$AD$$ over L(ℝ) and I0 over L(Vλ+1), while the failure of degree determinacy is one for disanalogy. Furthermore, we conjecture that the failure of degree determinacy for Zermelo degrees at any uncountable cardinal is a theorem of $$ZFC$$.

We know from [H1], [H2] that in a stable theory, given a nontrivial locally modular regular type q, one can define a group with generic domination equivalent to q, and that the dependence relation on q can be analyzed in terms of this group. In a stable one-based theory, every regular type is locally modular; hence, this result holds for every nontrivial regular type. We show here that, in fact, in a stable one-based theory, a similar type of construction can be done without the assumption of regularity. More precisely, we show that for any type q, the nontrivial part of q can be analyzed by generics of groups and that any nontrivial relation can be described by affine relations (Theorem A).

This construction is then used to answer a question about homogeneity in pairs of models which is still open in the case of arbitrary stable theories (Theorem C).

We characterize Morita equivalence of theories in the sense of Johnstone in terms of a new syntactic notion of a common definitional extension developed by Barrett and Halvorson for cartesian, regular, coherent, geometric and first-order theories. This provides a purely syntactic characterization of the relation between two theories that have equivalent categories of models naturally in any Grothendieck topos.

We show that every two-dimensional class of topological similarity, and hence every diagonal conjugacy class of pairs, is meager in the group of order preserving bijections of the rationale and in the group of automorphisms of the ordered rational Urysohn space.

Let ${\cal I}$ be an ideal on ω. By cov${}_{}^{\rm{*}}({\cal I})$ we denote the least size of a family ${\cal B} \subseteq {\cal I}$ such that for every infinite $X \in {\cal I}$ there is $B \in {\cal B}$ for which $B\mathop \cap \nolimits X$ is infinite. We say that an AD family ${\cal A} \subseteq {\cal I}$ is a MAD family restricted to${\cal I}$ if for every infinite $X \in {\cal I}$ there is $A \in {\cal A}$ such that $|X\mathop \cap \nolimits A| = \omega$. Let a$\left( {\cal I} \right)$ be the least size of an infinite MAD family restricted to ${\cal I}$. We prove that If $max${a,cov${}_{}^{\rm{*}}({\cal I})\}$ then a$\left( {\cal I} \right) = {\omega _1}$, and consequently, if ${\cal I}$ is tall and $\le {\omega _2}$ then a$\left( {\cal I} \right) = max$ {a,cov${}_{}^{\rm{*}}({\cal I})\}$. We use these results to prove that if c$\le {\omega _2}$ then o$= \overline o$ and that as$= max${a,non$({\cal M})\}$. We also analyze the problem whether it is consistent with the negation of CH that every AD family of size ω1 can be extended to a MAD family of size ω1.

The monadic second-order theory of trees allows quantification over elements and over arbitrary subsets. We classify the class of trees with respect to the question: does a tree T have a definable choice function (by a monadic formula with parameters)? A natural dichotomy arises where the trees that fall in the first class don't have a definable choice function and the trees in the second class have even a definable well ordering of their elements. This has a close connection to the uniformization problem.

In [5], Kleene extended previous notions of computations to objects of higher finite type in the maximal type-structure of functionals given by:

Tp(0) = N = the natural numbers,

Tp(n + 1) = NTp(n) = the set of total maps from Tp(n) to N.

He gave nine schemata, S1–S9, for describing algorithms for computations from a finite list of functionals, and indices to denote these algorithms. It is generally agreed that S1-S9 give a natural concept of computations in higher types.

The type-structure of countable functions, Ct(n) for n ϵ N, was first developed by Kleene [6] and Kreisel [7]. It arises from the notions of ‘constructivity’, and has been extensively studied as a domain for higher type recursion theory. Each countable functional is globally described by a countable amount of information coded in its associate, and it is determined locally by a finite amount of information about its argument. The countable functionals are well summarised in Normann [9], and treated in detail in Normann [8].

The purpose of this paper is to discuss a generalisation of the countable functionals, which we shall call the countably based functions, Cb(n) for n ϵ N. It is suggested by the notions of ‘predicativity’, in which we view N as a completed totality, and build higher types on it in a constructive manner. So we shall allow quantification over N and include application of 2E in our schemata. Each functional is determined locally by a countable amount of information about its argument, and so is globally described by a continuum of information coded in its associate, which will now be a type-2 object. This generalisation, obtained via associates, was proposed by Wainer, and seems to reflect topological properties of the countable functionals.

We associate with any abstract logic L a family F(L) consisting, intuitively, of the limit ultrapowers which are complete extensions in the sense of L.

For every countably generated [ω, ω]-compact logic L, our main applications are:

(i) Elementary classes of L can be characterized in terms of ≡L only.

(ii) If and are countable models of a countable superstable theory without the finite cover property, then .

(iii) There exists the “largest” logic M such that complete extensions in the sense of M and L are the same; moreover M is still [ω, ω]-compact and satisfies an interpolation property stronger than unrelativized ⊿-closure.

(iv) If L = Lωω(Qx), then cf(ωx) > ω and λω < ωx, for all λ < ωx.

We also prove that no proper extension of Lωω generated by monadic quantifiers is compact. This strengthens a theorem of Makowsky and Shelah. We solve a problem of Makowsky concerning Lκλ-compact cardinals. We partially solve a problem of Makowsky and Shelah concerning the union of compact logics.

In a recent series of papers Kanamori ([4], [5], and [6]) defines generalizations of several combinatorial principles known to follow from the existence of morasses. Kanamori proves the consistency of his generalizations by forcing arguments which come close to satisfying the hypotheses of the Martin's Axiom-type characterizations of morasses developed independently by Shelah and Stanley [9] and the author [12]. A similar “almost application” of morasses appears in [11], in which Todorčević uses forcing to prove the consistency of the existence of Kurepa trees with no Aronszajn or Cantor subtrees. In all cases the attempted proofs using morasses fail for the same reason: the partial orders involved do not have strong enough closure properties.

In an attempt to solve this problem Shelah and Stanley strengthened their characterization of morasses to allow applications to what they called “good canonical limit” partial orders. However, for rather subtle reasons even this strengthened forcing axiom is not good enough for the proposed applications. The problem this time is that Shelah and Stanley's “weak commutativity of Lim and restriction” requirement (see [9, 3.9(iv)]) is not satisfied. Furthermore, there is reason to believe that an ordinary morass is just not good enough for these applications, since in L morasses exist at all regular uncountable cardinals, but even a weak form of Todorčević's conclusion cannot hold at ineffable cardinals (see the end of §4).

A possible solution to this problem is suggested by the fact that □κ is equivalent to a forcing axiom which applies to partial orders satisfying precisely the kind of weak closure conditions involved in the examples described above (see [13]). What is needed to make the proposed morass applications work is something which will do for morass constructions what □κ does for ordinary transfinite recursion constructions. In this paper we show how extra structure can be built into a morass to accomplish this goal.

We characterize omissibility of a type, or a family of types, in a countable theory in terms of non-existence of a certain tree of formulas. We extend results of L. Newelski on omitting < covK non-isolated types. As a consequence we prove that omissibility of a family of < covK types is equivalent to omissibility of each countable subfamily.

Monotone inductive definitions occur frequently throughout mathematical logic. The set of formulas in a given language and the set of consequences of a given axiom system are examples of (monotone) inductively defined sets. The class of Borel subsets of the continuum can be given by a monotone inductive definition. Kleene's inductive definition of recursion in a higher type functional (see [6]) is fundamental to modern recursion theory; we make use of it in §2.

Inductive definitions over the natural numbers have been studied extensively, beginning with Spector [11]. We list some of the results of that study in §1 for comparison with our new results on inductive definitions over the continuum. Note that for our purposes the continuum is identified with the Baire space ωω.

It is possible to obtain simple inductive definitions over the continuum by introducing real parameters into inductive definitions over N—as in the definition of recursion in [5]. This is itself an interesting concept and is discussed further in [4]. These parametric inductive definitions, however, are in general weaker than the unrestricted set of inductive definitions, as is indicated below.

In this paper we outline, for several classes of monotone inductive definitions over the continuum, solutions to the following characterization problems:

(1) What is the class of sets which may be given by such inductive definitions ?

(2) What is the class of ordinals which are the lengths of such inductive definitions ?

These questions are made more precise below. Most of the results of this paper were announced in [2].

A remarkable result of Henson and Ross [HR] states that if a function whose graph is Souslin in the product of two hyperfinite sets in an ℵ1 saturated nonstandard universe possesses a certain nice property (capacity) then there exists an internal subfunction of the given one possessing the same property. In particular, they prove that every 1-1 Souslin function preserves any internal counting measure, and show that every two internal sets A and B with ∣A∣/∣B∣ ≈ 1 are Borel bijective. As a supplement to the last-mentioned result of Henson and Ross, Keisler, Kunen, Miller and Leth showed [KKML] that two internal sets A and B are bijective by a countably determined bijection if and only if ∣A∣/∣B∣ is finite and not infinitesimal.

In this paper we first show that injective Borel functions map Borel sets into Borel sets, a fact well known in classical descriptive set theory. Then, we extend the result of Henson and Ross concerning the Borel bijectivity of internal sets whose quotient of cardinalities is infinitely closed to 1. We prove that two Borel sets, to which we may assign a counting measure not equal to 0 or ∞, are Borel bijective if and only if they have the same counting measure ≠0, ∞. This, together with the similar characterization for Souslin and measurable countably determined sets, extends the above-mentioned results from [HR] and [KKML].