Although there are many characterizations of weakly compact cardinals (e.g. in terms of indescnbability and tree properties as well as compactness) the most interesting set-theoretic (combinatorial) one is in terms of partition relations. To be more precise we define for κ and α cardinals and n an integer the partition relation of Erdös, Hajnal and Rado [2] as follows:

For every function F: [κ]n→ α (called a partition of [κ]n, the n-element subsets of κ, into α pieces), there exists a set C⊆ κ (called homogeneous for F) such that card C = κ and F″[C]n≠ α, i.e. some element of the range is omitted when F is restricted to the n-element subsets of C. It is the simplest (nontrivial) of these relations, i.e. , that is the well-known equivalent of weak compactness.1

Two directions of inquiry immediately suggest themselves when weak compactness is described in terms of these partition relations: (a) Trying to strengthen the relation by increasing the superscript—e.g., —and (b) trying to weaken the relation by increasing the subscript—e.g., . As it turns out, the strengthening to is only illusory for using the equivalence of to the tree property one quickly sees that implies (and so is equivalent to) for every n. Thus is the strongest of these partition relations. The second question seems much more difficult.

In this note we prove that the abstract property “weakly subdirectly indecomposable” does not characterize the class IWsα of weak cylindric set algebras. However, we give another (similar) abstract property characterizing IWsα. The original property does characterize the directed unions of members of IWsα iff α is countable. Free algebras will be shown to satisfy the original property.

Let Kr be the class of all those quantificational formulas whose matrices are conjunctions of binary disjunctions of signed atomic formulas. Decision problems for subclasses of Kr do not invariably coincide with those for the corresponding classes of quantificational formulas with unrestricted matrices; for example, the ∀∃∀ prefix subclass of Kr is solvable, but the full ∀∃∀ class is not ([AaLe],- [KMW]). Moreover, the straightforward encodings of automata which have been used to show the unsolvability of various subclasses of Kr ([Aa], [Bö], [AaLe]) yield but little information about signature subclasses, i.e. subclasses determined by the number and degrees of the predicate letters occurring in a formula. By a new and highly complex construction Theorem 1 establishes the best possible result on classification by signature.

Theorem 1. Let C be the class of all formulas in Kr with a single predicate letter, which is dyadic; then C is a reduction class for satisfiability.

Thus a signature subclass of Kr is solvable just in case the corresponding class of unrestricted quantificational formulas is solvable, to wit, just in case no predicate letter of degree exceeding one may occur. To obtain a richer classification by signature we consider further restrictions on the matrix. Let Or be the class of formulas in Kr having disjunctive normal forms with only two disjuncts. Theorem 2 sharpens Orevkov's proof of the unsolvability of Or ([Or]; see also [LeGo]).

Theorem 2. Let D be the class of formulas in Or with just two predicate letters, both pentadic; then D is a reduction class for satisfiability.

We generalise the main theorems from the paper “The Borel cardinality of Lascar strong types” by I. Kaplan, B. Miller and P. Simon to a wider class of bounded invariant equivalence relations. We apply them to describe relationships between fundamental properties of bounded invariant equivalence relations (such as smoothness or type-definability) which also requires finding a series of counterexamples. Finally, we apply the generalisation mentioned above to prove a conjecture from a paper by the first author and J. Gismatullin, showing that the key technical assumption of the main theorem (concerning connected components in definable group extensions) from that paper is not only sufficient but also necessary to obtain the conclusion.

We show that, assuming the existence of the canonical inner model with one Woodin cardinal $M_1 $ , there is a model of $ZFC$ in which the nonstationary ideal on $\omega _1 $ is $\aleph _2 $-saturated and whose reals admit a ${\rm{\Sigma }}_4^1 $-wellorder.

Working under AD, we investigate the length of prewellorderings given by the iterates of ℳ2k+1, which is the minimal proper class mouse with 2k + 1 many Woodin cardinals. In particular, we answer some questions from [4] (the discussion of the questions appears in the last section of [2]).

We examine the computable part of the differentiability hierarchy defined by Kechris and Woodin. In that hierarchy, the rank of a differentiable function is an ordinal less than ${\omega _1}$ which measures how complex it is to verify differentiability for that function. We show that for each recursive ordinal $\alpha > 0$, the set of Turing indices of $C[0,1]$ functions that are differentiable with rank at most α is ${{\rm{\Pi }}_{2\alpha + 1}}$-complete. This result is expressed in the notation of Ash and Knight.

In this paper we present some metapredicative subsystems of analysis. We deal with reflection principles, ω-model existence axioms (limit axioms) and axioms asserting the existence of hierarchies. We show several equivalences among the introduced subsystems. In particular we prove the equivalence of Σ11 transfinite dependent choice and Π21 reflection on ω-models of Σ11-DC.

It will be proved that the Shoenfield cupping conjecture holds in R/M, the quotient of the recursively enumerable degrees modulo the cappable r.e. degrees. Namely, for any [a], [b] ∈ R/M such that [0] ≺ [b] ≺ [a] there exists [c] ∈ R/M such that [c] ≺ [a] and [a] = [b] ∨ [c].

Markov's principle is more than a convenience in constructive arithmetic and analysis; it is absolutely essential to significant areas of constructive cardinal arithmetic. In turn, logical relations among intuitively appealing principles of constructive cardinal arithmetic parallel relations between MPS and other “problematic axioms” for constructive mathematics, such as the limited principle of omniscience. Finally, simple closure properties on the Dedekind finite sets provide ready examples of statements which are strictly weaker than Markov's principle and yet are independent of extensions of IZF.

MPS, Markov's principle with variables over sets, is equivalent to each of these elementary properties of ⊿, the class of Dedekind finite sets:

1. ∀A(A Є ⊿ ↔ CP(A)).

2. [*]A Є ⊿ ↔ ∀B (A + B is infinite ↔ B is infinite).

3. [**]A Є ⊿ ↔ ∀B((A + 1) x B is infinite ↔ B is infinite).

CP is Tarski's cancellation property. Consequently, MPS is tantamount, in constructive mathematics, to the standard classical characterizations of ⊿ in terms of cardinality.

[*] and [**] imply that ⊿ is closed under addition and multiplication. Closure under addition is, in turn, constructively equivalent to the closure of ⊿ under all combinatorial functions and to the fact that ⊿ is closed under each strict combinatorial function individually. Generally speaking, a function on P(ω) is combinatorial whenever it preserves finiteness, respects cardinality and has a “moduluslike” associate function. It is strict when it is strictly increasing relative to the subset ordering, [cf. §6 for precise definitions.] From this, we see that MPS is foundational for cardinal arithmetic on the constructive Dedekind finite sets.

We investigate Borel reducibility between equivalence relations E(X; p) = Xℕ/ℓp(X)'s where X is a separable Banach space. We show that this reducibility is related to the so called Hölder(α) embeddability between Banach spaces. By using the notions of type and cotype of Banach spaces, we present many results on reducibility and unreducibility between E(Lr; p)'s and E(c0; p)'s for r, p Є [1, +∞).

We also answer a problem presented by Kanovei in the affirmative by showing that C(ℝ+)/C0(ℝ+) is Borel bireducible to ℝℕ/c0.

Let {Wk }k ≥ 0 be a standard enumeration of all recursively enumerable (r.e.) sets. If A is any class of r.e. sets, let θ A denote the index set of A, i.e., θA = {k ∣ Wk ∈ A}. The one-one degrees of index sets form a partial order ℐ which is a proper subordering of the partial order of all one-one degrees. Denote by ⌀ the one-one degree of the empty set, and, if b is the one-one degree of θB, denote by the one-one degree of . Let . Let {Ym }m≥0 be the sequence of index sets of nonempty finite classes of finite sets (classified in [5] and independently, in [2]) and denote by a m the one-one degree of Ym . As shown in [2], these degrees are complete at each level of the difference hierarchy generated by the r.e. sets. It was proved in [3] that, for each m ≥ 0,

(a) a m+1 and ā m+1 are incomparable immediate successors of a m and ā m, and

(b) .

For m = 0, since Y 0 = θ{⌀}, it follows from (a) that

(c) .

Hence it follows that

(d) {⌀, , a o, ā 0, a 1, ā 1 is an initial segment of ℐ.

It is known that in differentially closed fields of characteristic zero, the ranks of stability RU, RM and the topological rank RH need not to be equal. Pillay and Pong have just shown however that the ranks RU and RM coincide in a group definable in this theory. At the opposite, we will show in this paper that the ranks RM and RH of a definable group can also be different, and even lead to non-equivalent notions of generic type.

By Frege's Theorem is meant the result, implicit in Frege's Grundlagen, that, for any set E, if there exists a map υ from the power set of E to E satisfying the condition

then E has a subset which is the domain of a model of Peano's axioms for the natural numbers. (This result is proved explicitly, using classical reasoning, in Section 3 of [1].) My purpose in this note is to strengthen this result in two directions: first, the premise will be weakened so as to require only that the map υ be defined on the family of (Kuratowski) finite subsets of the set E, and secondly, the argument will be constructive, i.e., will involve no use of the law of excluded middle. To be precise, we will prove, in constructive (or intuitionistic) set theory, the following

Theorem. Let υ be a map with domain a family of subsets of a set E to E satisfying the following conditions:

(i) ø ϵdom(υ)

(ii)∀U ϵdom(υ)∀x ϵ E − UU ∪ x ϵdom(υ)

(iii)∀UV ϵdom(5) υ(U) = υ(V) ⇔ U ≈ V.

Then we can define a subset N of E which is the domain of a model of Peano's axioms.

In the past sixty years or so, a real forest of intuitionistic models for classical theories has grown. In this paper we will compare intuitionistic models of first order classical theories according to relevant issues, like completeness (w.r.t. first order classical provability), consistency, and relationship between a connective and its interpretation in a model. We briefly consider also intuitionistic models for classical ω-logic.

All results included here, but a part of the proposition (a) below, are new. This work is, ideally, a continuation of a paper by McCarty, who considered intuitionistic completeness mostly for first order intuitionistic logic.

Given a family ${\cal C}$ of infinite subsets of ${\Bbb N}$, we study when there is a Borel function $S:2^{\Bbb N} \to 2^{\Bbb N} $ such that for every infinite $x \in 2^{\Bbb N} $, $S\left( x \right) \in {\Cal C}$ and $S\left( x \right) \subseteq x$. We show that the family of homogeneous sets (with respect to a partition of a front) as given by the Nash-Williams’ theorem admits such a Borel selector. However, we also show that the analogous result for Galvin’s lemma is not true by proving that there is an $F_\sigma $ tall ideal on ${\Bbb N}$ without a Borel selector. The proof is not constructive since it is based on complexity considerations. We construct a ${\bf{\Pi }}_2^1 $ tall ideal on ${\Bbb N}$ without a tall closed subset.

This paper is an appendix to Keisler's papers [3], [4]. We assume that the reader is fully acquainted with these papers and use their terminology without further explanation. One of the main tools in a number of proofs in [4] is the following result which is all but stated explicitly in [4].

We introduce a notion of complexity for interpretations, which is used to prove some new results about interpretations of sequential theories. In particular, we give a new, elementary proof of Pudlák's theorem that sequential theories are connected. We also demonstrate a counterexample to the infinitary distributive law

in the lattice of chapters, in which the chapters a and bi are compact. (Counterexamples in which a is not compact have been found previously.)

1. In this paper we construct a model for part of the system NF of [4]. Specifically, we define a relation R of natural numbers such that the R-relativiseds of all the axioms except P9 of Hailperin's finitization [2] of NF become theorems of say Zermelo set theory. We start with an informal explanation of the model.

2. Scrutiny of P1-P8 of [2] suggests that a model for these axioms might be constructed by so to speak starting with a universe that contained a “universe set” and a “cardinal 1”, and passing to its closure under the operations implicit in P1-P7, viz., the Boolean, the domain, the direct product, the converse, and the mixtures of product and inverse operations represented by P3 and P4. To obtain such closure we must find a way of representing the operations that involve ordered pairs and triples.

We take as universe of the model the set of natural numbers ω; we let 0 represent the “universe set” and 1 represent “cardinal 1”. Then, in order to be able to refer in the model to the unordered pair of two sets, we determine all representatives of unordered pairs in advance by assigning them the even numbers in unique fashion (see d3 and d25); we can now define the operations that involve ordered pairs and triples, and obtain closure under them using the odd numbers. It remains to weed out, as in d26, the unnecessary sets so as to satisfy the axiom of extensionality.