Let NBG be von Neumann-Bemays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.

In [1], McCall and I offered an axiomatization of the implicational fragment of the 3-valued Łukasiewiczian system defined in [2]. The following axiom schemata sufficed, together with the rule of modus ponens.1

In a simple theory with elimination of finitary hyperimaginaries if tp(a) is real and analysable over a definable set Q, then there exists a finite sequence (ai \ i ≤ n*) ⊆ dcleq(a) with an* = a such that for every i ≤ n* if pi = tp(ai/{aj |j < i}) then Aut(pi / Q) is type-definable with its action on . A unidimensional simple theory eliminates the quantifier ∃∞ and either interprets (in Ceq) an infinite type-definable group or has the property that ACL(Q) = C for every infinite definable set Q.

We show that strongly compact cardinals and MM are sensitive to λ-closed forcings for arbitrarily large λ. This is done by adding ‘regressive’ λ-Kurepa trees in either case. We argue that the destruction of regressive Kurepa trees requires a non-standard application of MM. As a corollary, we find a consistent example of an ω2-closed poset that is not forcing equivalent to any ω2-directed-closed poset.

We shall define a general notion of dimension, and study groups and rings whose interpretable sets carry such a dimension. In particular, we deduce chain conditions for groups, definability results for fields and domains, and show that a pseudofinite $\widetilde {\mathfrak M}_c$ -group of finite positive dimension contains a finite-by-abelian subgroup of positive dimension, and a pseudofinite group of dimension 2 contains a soluble subgroup of dimension 2.

A monadic formula ψ(Y) is a selector for a formula φ(Y) in a structure if there exists a unique subset P of which satisfies ψ and this P also satisfies φ. We show that for every ordinal α ≥ ωω there are formulas having no selector in the structure (α, <). For α ≤ ω1, we decide which formulas have a selector in (α, <) , and construct selectors for them. We deduce the impossibility of a full generalization of the Büchi-Landweber solvability theorem from (ω, <) to (ωω, <). We state a partial extension of that theorem to all countable ordinals. To each formula we assign a selection degree which measures “how difficult it is to select”. We show that in a countable ordinal all non-selectable formulas share the same degree.

The purpose of this paper is to provide a formal system which is (a) adequate (functionally complete), (b) consistent, and (c) complete, relative to 3-valued logic with one designated value, and for which, furthermore, (d) a simple normal form theorem, and (e) the Craig-Lyndon Interpolation Theorem [1], [2] holds.

A first-order sentence is quasi-modal if its class of models is closed under the modal validity preserving constructions of disjoint unions, inner substructures and bounded epimorphic images.

It is shown that all members of the proper class of canonical structures of a modal logic Λ have the same quasi-modal first-order theory ΨΛ. The models of this theory determine a modal logic Λe which is the largest sublogic of Λ to be determined by an elementary class. The canonical structures of Λe also have ΨΛ as their quasi-modal theory.

In addition there is a largest sublogic Λe of Λ that is determined by its canonical structures, and again the canonical structures of Λe have ΨΛ are their quasi-modal theory. Thus . Finally, we show that all finite structures validating Λ are models of ΨΛ, and that if Λ is determined by its finite structures, then ΨΛ is equal to the quasi-modal theory of these structures.

The negative solution of Hilbert's Tenth Problem brought with it a number of unsolvable Diophantine problems. Moreover, by actually providing a Diophantine characterization of recursive enumerability, the proof of the negative solution opened the door to the techniques of recursion theory. In this note, we wish to apply several recursion-theoretic facts and an improvement on the exponential Diophantine representation to refine the exponential case of a result of Davis [1972] regarding the difficulty of determining the number of zeros of a polynomial.

P, Q, etc. will denote polynomials or exponential polynomials–exactly which will be clear from the context. Let # (P) denote the number of distinct nonnegative zeros of P. Further, let C = {0,1, …,ℵ0} be the set of possible values of # (P). For A ⊆ C, we define A * to be

With this notation, Davis' result reads:

Theorem 0.1 (DAVIS). A* is recursive iff A = ∅ or A = C.

The refinement we will prove is:

Theorem 0.2 (Exponential Case). A * is r.e. iff A = ∅ or A = {c: c ≥ a: m} for some finite m.

We will show it is consistent with GCH that there is a minimal non-σ-scattered linear order which does not contain any real or Aronszajn type. In particular the assumption PFA+ in the main result of [5] is necessary, and there are other obstructions than real and Aronszajn types to the sharpness of Laver’s theorem in [8].

This paper investigates indifferent sets for comeager classes in Cantor space focusing of the class of all 1-generic sets and the class of all weakly 1-generic sets. Jockusch and Posner showed that there exist 1-generic sets that have indifferent sets [10]. Figueira, Miller and Nies have studied indifferent sets for randomness and other notions [7]. We show that any comeager class in Cantor space contains a comeager class with a universal indifferent set. A forcing construction is used to show that any 1-generic set, or weakly 1-generic set, has an indifferent set. Such an indifferent set can by computed by any set in which bounds the (weakly) 1-generic. We show by approximation arguments that some, but not all, 1-generic sets can compute an indifferent set for themselves. We show that all weakly 1-generic sets can compute an indifferent set for themselves. Additional results on indifferent sets, including one of Miller, and two of Fitzgerald, are presented.

1.1 The system K* of basic logic, as presented in a previous paper, will be shown to be formalizable in an alternative way according to which the rule [E],

is replaced by the rule [F],

1.2. General recursive functions will be shown to be definable in K* in a way that retains functional notation, so that the equation,

will be formalized in K* by the formula,

where ‘f’, ‘p1’, … ‘pn’ respectively denote φ, x1, …, xn, and where ‘≐’ plays the role of numerical equality. Partial recursive functions may be handled in a similar way. The rule [E] is not required for dealing with primitive recursive functions by this method.

1.3. An operator ‘G’ will be defined such that ‘[Ga ≐ p]’ is a theorem of K* if and only if ‘p’ denotes the Gödel number of ‘a’.

1.4. In reformulating K* we assume ‘o0’, ‘o1,’ ‘o2’, …, have been so chosen that we can determine effectively whether or not a given U-expression is the mth member of the above series. The revised rules for K* are then as follows. (Double-arrow forms of these rules are derivable, except in the case of rule [V].)

Let be an o-minimal expansion of the ordered field of real numbers , and let S be an -definable subset (parameters allowed unless otherwise stated) of ℝn. In this note I investigate questions concerning the distribution of points on S with integer coordinates. My main theorem gives an estimate which, though probably far from best possible, at least shows that the o-minimal assumption does have diophantine consequences. This is, perhaps, surprising in view of the flexibility that we now seem to have in constructing o-minimal expansions of (see, e. g. [7], [8], [9]).

Starting points of this article are fixed point axioms for set-bounded monotone Σ1 definable operators in the context of Kripke–Platek set theory $KP$. We analyze their relationship to other principles such as maximal iterations, bounded proper injections, and Σ1 subset-bounded separation. One of our main results states that in $KP + (V\, = \,L)$ all these principles are equivalent to Σ1 separation.

An ω-set is a subset of the recursive ordinals whose complement with respect to the recursive ordinals is unbounded and has order type ω. This concept has proved fruitful in the study of sets in relation to metarecursion theory. We prove that the metadegrees of the sets coincide with those of the meta-r.e. ω-sets. We then show that, given any set, a metacomplete set can be found which is weakly metarecursive in it. It then follows that weak relative metarecursiveness is not a transitive relation on the sets, extending a result of G. Driscoll [2, Theorem 3.1]. Coincidentally, we discuss the notions of total and complete regularity. Finally, we solve Post's problem for the transitive closure of weak relative metarecursiveness. We recommend the reader look at pp. 324–328 of the fundamental article [6] of Kreisel and Sacks before proceeding. He will find there a proof of the following very basic fact: a subset of the integers is iff it is metarecursively enumerable (metafinite).

We show that if add(null) = c, then the globally Baire and universally measurable chromatic numbers of the graph of any Borel function on a Polish space are equal and at most three. In particular, this holds for the graph of the unilateral shift on [ℕ]ℕ, although its Borel chromatic number is ℵ0. We also show that if add(null) = c, then the universally measurable chromatic number of every treeing of a measure amenable equivalence relation is at most three. In particular, this holds for “the” minimum analytic graph with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all κ Є6 (2, 3…..ℵ0, c), there is a treeing of E0 with Borel and Baire measurable chromatic number κ. Finally, we use a Glimm–Effros style dichotomy theorem to show that every basis for a non-empty initial segment of the class of graphs of Borel functions of Borel chromatic number at least three contains a copy of (ℝ<ℕ, ⊇).

Gödel's second incompleteness theorem is proved for Herbrand consistency of some arithmetical theories with bounded induction, by using a technique of logarithmic shrinking the witnesses of bounded formulas, due to Z. Adamowicz [Herbrand consistency and bounded arithmetic, Fundamenta Mathematicae, vol. 171 (2002), pp. 279–292]. In that paper, it was shown that one cannot always shrink the witness of a bounded formula logarithmically, but in the presence of Herbrand consistency, for theories IΔ0 + Ωm with m ≥ 2, any witness for any bounded formula can be shortened logarithmically. This immediately implies the unprovability of Herbrand consistency of a theory T ⊇ IΔ0 + Ω2 in T itself.

In this paper, the above results are generalized for Δ0 + Ω1. Also after tailoring the definition of Herbrand consistency for IΔ0 we prove the corresponding theorems for IΔ0. Thus the Herbrand version of Gödel's second incompleteness theorem follows for the theories IΔ0 + Ω1 and IΔ0.