The aim of the paper is to prove the completeness theorem for biprobability models. This also solves Keisler's Problem 5.4 (see [4]).

Let be a countable admissible set and ω ∈ . The logic is similar to the standard probability logic . The only difference is that two types of probability quantifiers and are allowed.

A biprobability model is a structure (, μ1, μ2) where is a classical structure without operations and μ1, μ2 are two types of probability measures such that μ1 is absolutely continuous with respect to μ2, i.e. μ1 ≪ μ2.

The quantifiers are interpreted in the natural way, i.e.

for i = 1, 2. (The measure is the restriction of the completion of to the σ-algebra generated by the measurable rectangles and the diagonal sets

Axioms and rules of inference are those of , as listed in [2] with the axiom B4 from [4], with the remark that both P1 and P2 can play the role of P, together with the following axioms:

Axioms of continuity.

• 1) .

• 2) .

Axiom of absolute continuity:

where and Φn = {φ ∈ Φ: φ has n free variables}.

One of the most extensive parts of Tarski's contributions to logic is his work on the algebraization of the subject. His work here involves Boolean algebras, relation algebras, cylindric algebras, Boolean algebras with operators, Brouwerian algebras, and closure algebras. The last two are less developed in his work, although his contributions are basic to other work in those subjects. At any rate, not being conversant with the latest developments in those fields, we shall concentrate on an exposition of Tarski's work in the first four areas, trying to put them in the perspective of present-day developments.

For useful comments, criticisms, and suggestions, the author is indebted to Steven Givant, Leon Henkin, Wilfrid Hodges, Bjarni Jónsson, Roger Lyndon, and Robert Vaught.

In this paper we consider various properties of Jensen's □ principles and use them to construct several examples concerning the so-called Novák number of partially ordered sets.

In §1 we give the relevant definitions and review some facts about □ principles. Apart from some simple observations most of the results in this section are known.

In §2 we consider the Novák number of partially ordered sets and, using □ principles, give counterexamples to the productivity of this cardinal function. We also formulate a principle, show by forcing that it is consistent and use it to construct an ℵ2-Suslin tree T such that forcing with T × T collapses ℵ1.

In §3 we briefly consider games played on partially ordered sets and relate them to the problems of the previous section. Using a version of □ we give an example of a proper partial order such that the game of length ω played on is undetermined.

In §4 we raise the question of whether the Novák number of a homogenous partial order can be singular, and show that in some cases the answer is no.

We assume familiarity with the basic techniques of forcing. In §1 some facts about large cardinals (e.g. weakly compact cardinals are -indescribable) and elementary properties of the constructible hierarchy are used. For this and all undefined terms we refer the reader to Jech [10].

If a uniform ultrafilter U over an uncountable cardinal κ is not outright countably complete, probably the next best thing is that it have a finest partition: a master function f:κ → ω with ƒ −({n}) ∉ U for each n ϵ ω such that for any g: κ → κ, either (a) it is one-to-one on a set in U, or (b) it factors through ƒ (mod U), i.e. for some function h, {α < κ ∣ h(f(α)) = g(α)} ϵ U. In this paper, it is shown that recent contructions of irregular ultrafilters over ω 1 can be amplified to incorporate a finest partition.

Henceforth, let us assume that all ultrafilters are uniform.

There has been an extensive study of substantial hypotheses, which are nonetheless weaker than countable completeness, on ultrafilters over uncountable cardinals. To survey some results and to establish a context, let us first recall the Rudin-Keisler (RK) ordering on ultrafilters: If U i is an ultrafilter over I i i for i = 1, 2, then U 1 ≤RK U 2 iff there is a projecting function Ψ:I 2 → I 1 such that U 1 = Ψ *(U 2) = {X ⊆, I 1∣ Ψ −1(X) ϵ U 2}· U 1, =RK U 2 iff U 1, ≤RK and U 2 and U 2≤RK U 1; and U 1<RK U 2 iff U 1≤RK U 2 yet U 1 ≠RK U 2. In terms of this ordering, if an ultrafilter U has a finest partition ƒ, then ƒ *(U) over ω is maximum amongst all RK predecessors of U: for any g:κ → κ, if g *(U) <RK U, then g is not one-to-one on a set in U, so since g factors through ƒ with some h,g *(U) = h *(ƒ *(U)). Say now that an ultrafilter U over κ > ω is indecomposable iff whenever ω < λ < κ, there is no V ≤RK U such that V is a (uniform) ultrafilter over λ.

Tarski published his first geometry paper, [24b], in 1924. As is well known, the area of the union of two disjoint figures is the sum of the areas of these two figures. This observation is the basis of a method for proving that two figures, say A and B, have the same area: if we can divide each of the two figures A and B into a finite number of pairwise disjoint subfigures A1,…,An and B1,…,Bn such that for every i, figures Ai and Bi are congruent (we say that two such figures are equivalent by finite decomposition), then figures A and B have the same area. The method is by no means universal. For example a disc and a rectangle can never be equivalent by finite decomposition, even if they have the same area. Hilbert [1922, Kapitel IV] proved from his axiom system the so-called De Zolt axiom:

If a polygon V is a proper subset of a polygon W then they are not equivalent by a finite decomposition.

Hilbert's proof is elementary but difficult. In [24b] Tarski gave an easy but nonelementary proof of a stronger version of the De Zolt axiom:

If a polygon V is a proper subset of a polygon W then they are not equivalent by finite decomposition into any figures.

The theory of large cardinals in the absence of the axiom of choice (AC) has been examined extensively by set theorists. A particular motivation has been the study of large cardinals and their interrelationships with the axiom of determinacy (AD). Many important and beautiful theorems have been proven in this area, especially by Woodin, who has shown how to obtain, from hypermeasurability, models for the theories “ZF + DC + ∀α < ℵ1(ℵ1 → (ℵ1)α)” and . Thus, consequences of AD whose consistency strength appeared to be beyond that of the more standard large cardinal hypotheses were shown to have suprisingly weak consistency strength.

In this paper, we continue the study of large cardinals in the absence of AC and their interrelationships with AD by examining what large cardinal structures are possible on cardinals below ℵω in the absence of AC. Specifically, we prove the following theorems.

Theorem 1. Con(ZFC + κ1 < κ2are supercompact cardinals) ⇒ Con(ZF + DC + The club filter on ℵ1is a normal measure + ℵ1and ℵ2are supercompact cardinals).

Theorem 2. Con(ZF + AD) ⇒ Con(ZF + ℵ1, ℵ2and ℵ3are measurable cardinals which carry normal measures + μωis not a measure on any of these cardinals).

We say that a first order theory T is locally finite if every finite part of T has a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theory T a locally finite theory FIN(T) which is syntactically (in a sense) isomorphic to T.

Our construction draws upon the main idea of Paris and Harrington [6] (I have been influenced by some unpublished notes of Silver [7] on this subject) and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. (Our proof is syntactic, and it is simpler than the proofs of [5], [6] and [7]. This reminds me of the simple syntactic proofs of several variants of the Craig-Lyndon interpolation theorem, which seem more natural than the semantic proofs.)

The first mathematically strong locally finite theory, called FIN, was defined in [1] (see also [2]). Now we get much stronger ones, e.g. FIN(ZF).

From a physicalistic point of view the theorems of ZF and their FIN(ZF)-counterparts may have the same meaning. Therefore FIN(ZF) is a solution of Hilbert's second problem. It eliminates ideal (infinite) objects from the proofs of properties of concrete (finite) objects.

In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN(ZF) is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.

The results of this paper were announced in [3].

Let L be a first order language containing a binary relation symbol <.

Definition. Suppose ℳ is an L-structure and < is a total ordering of the domain of ℳ. ℳ is ordered minimal (-minimal) if and only if any parametrically definable X ⊆ ℳ can be represented as a finite union of points and intervals with endpoints in ℳ.

In any ordered structure every finite union of points and intervals is definable. Thus the -minimal structures are the ones with no unnecessary definable sets. If T is a complete L-theory we say that T is strongly (-minimal if and only if every model of T is -minimal.

The theory of real closed fields is the canonical example of a strongly -minimal theory. Strongly -minimal theories were introduced (in a less general guise which we discuss in §6) by van den Dries in [1]. Extending van den Dries' work, Pillay and Steinhorn (see [3], [4] and [2]) developed an extensive structure theory for definable sets in strongly -minimal theories, generalizing the results for real closed fields. They also established several striking analogies between strongly -minimal theories and ω-stable theories (most notably the existence and uniqueness of prime models). In this paper we will examine the construction of models of strongly -minimal theories emphasizing the problems involved in realizing and omitting types. Among other things we will prove that the Hanf number for omitting types for a strongly -minimal theory T is at most (2∣T∣)+, and characterize the strongly -minimal theories with models order isomorphic to (R, <).

C. U. Jensen suggested the following construction, starting from a field K:

and asked when two fields Kα and Kβ are equivalent. We give a complete answer in the case of a field K of characteristic 0.

We characterize some large cardinal properties, such as μ-measurability and P2(κ)-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 Löwenheim-Skolem property, and settles a question about directed versus chain-type unions on Pκλ.

It is a theorem of Rowbottom [12] that if κ is measurable and I is a normal prime ideal on κ, then for each λ < κ,

In this paper a natural structural property of ideals, distributivity, is considered and shown to be related to this and other ideal theoretic partition relations.

The set theoretical terminology is standard (see [7]) and background results on the theory of ideals may be found in [5] and [8]. Throughout κ will denote an uncountable regular cardinal, and I a proper, nonprincipal, κ-complete ideal on κ. NSκ is the ideal of nonstationary subsets of κ, and Iκ = {X ⊆ κ∣∣X∣<κ}. If A ∈ I+ (= P(κ) − I), then an I-partition of A is a maximal collection W ⊆, P(A) ∩ I+ so that X ∩ Y ∈ I whenever X, Y ∈ W, X ≠ Y. The I-partition W is said to be disjoint if distinct members of W are disjoint, and in this case, for denotes the unique member of W containing ξ. A sequence 〈Wα ∣ α < η} of I-partitions of A is said to be decreasing if whenever α < β < η and X ∈ Wβ there is a Y ∈ Wα such that X ⊆ Y. (i.e., Wβ refines Wα).

In this paper we prove a boundedness theorem in the theory ID1(W). This answers a question asked by Feferman, for example in [3]. The background is the following.

Let A[X, x] be an X-positive formula arithmetic in X. The theory ID1(PA) is an extension of Peano arithmetic PA by the following axioms:

for arbitrary formulas F; PA is a constant for the least fixed point of A[X, x]. Set-theoretically, PA can be defined by recursion on the ordinals as follows:

where is the first nonrecursive ordinal.

Now let a ≺ b be the arithmetic relation which expresses that the recursive tree coded by a is a proper subtree of the tree coded by b, and define

The least fixed point of Tree[X, x] is the set PTree of all well-founded recursive trees. We write W or Wα for PTree or , respectively. Since W is complete we have for all α < . If we define for each element a ∈ W its inductive norm ∣a∣ by ∣a∣≔ min{ξ: a ∈ Wξ}, then we have = {∣a∣: a ∈ W} and the elements of W can be used as codes for the ordinals less than .

Assume that B[X, x] is an X-positive formula arithmetic in X with the only free variables X and x, and assume that QB is a relation that satisfies

If we define

then we obviously have PB = IB.

Let A and B be subsets of the reals. Say that A K ≥ B, if there is a real a such that the relation “x ∈ B” is uniformly ⊿1 (a, A) in . This reducibility induces an equivalence relation ≡ K on the sets of reals; the ≡ K -equivalence class of a set is called its Kleene degree. Let be the structure that consists of the Kleene degrees and the induced partial order ≥. A substructure of that is of interest is , the Kleene degrees of the sets of reals. If sharps exist, then there is not much to , as Steel [9] has shown that the existence of sharps implies that has only two elements: the degree of the empty set and the degree of the complete set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in ; in the context of V = L, Hrbáček has shown that is dense and has no minimal pairs. The Hrbáček results led Simpson [6] to make the following conjecture: if V = L, then forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Gödel's maximal thin set is the infimum of two strictly larger elements of .

The second main result deals with the notion of jump in . Let A′ be the complete Kleene enumerable set relative to A. Say that A is low-n if A (n) has the same degree as ⊘(n), and A is high-n if A(n) has the same degree as ⊘(n+1). Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete set in L. They have also shown that various other sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x# does not exist, then there is an element of that, for all n, is neither low-n nor high-n. In §2, ZFC is used to show that, for all n, if A is and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp].

It is proved that for a variety of groups in which the relatively free groups are solvable, the relatively free groups of distinct finite rank are not elementarily equivalent.

We give a new elementary proof of the comparison theorem relating and ; the proof does not use Skolem theories.

By the same method we prove:

a) , for suitable classes of sentences;

b) proves the consistency of , for finite k, and hence is stronger than .

a) and b) answer a question of Feferman and Sieg.

We study the first order theory of function fields in the language of fields by using fundamental results on curves in algebraic geometry. We give some applications; for example, using a theorem of G. Cherlin, we prove the undecidability of function fields with nonzero characteristic over an algebraically closed field.

A natural deduction formulation is given for the intermediate logic called MH by Gabbay in [4]. Proof-theoretic methods are used to show that every deduction can be normalized, that MH is the weakest intermediate logic for which the Glivenko theorem holds, and that the Craig-Lyndon interpolation theorem holds for it.

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:

1. 1. The first-order theory generated by the infinite models of Σ is complete.

2. 2. The first-order theory generated by the infinite models of Σ is model-complete.

3. 3. Σ has the joint-embedding property.

4. 4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.

5. 5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.

A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.

If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.