It is shown in ZF (without choice) that if there is a finite-to-one map (X) → X, then X is finite.

Let θ, θ′ be two multiplicatively independent Pisot numbers, and let U, U′ be two linear numeration systems whose characteristic polynomial is the minimal polynomial of θ and θ′, respectively. For every n ≥ 1, if A ⊆ ℕn is U-and U′ -recognizable then A is definable in 〈ℕ: + 〉.

We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results.

Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε0-recursive function []0: T → ω so that a reduces to b implies [a]0 > [b]0. The construction of [ ]0 is based on a careful analysis of the Howard-Schütte treatment of Gödel's T and utilizes the collapsing function ψ: ε0 → ω which has been developed by the author for a local predicativity style proof-theoretic analysis of PA. The construction of [ ]0 is also crucially based on ideas developed in the 1995 paper “A proof of strongly uniform termination for Gödel's T by the method of local predicativity” by the author. The results on complexity bounds for the fragments of T which are obtained in this paper strengthen considerably the results of the 1995 paper.

Indeed, for given n let Tn be the subsystem of T in which the recursors have type level less than or equal to n + 2. (By definition, case distinction functionals for every type are also contained in Tn.) As a corollary of the main theorem of this paper we obtain (reobtain?) optimal bounds for the Tn-derivation lengths in terms of ω+2-descent recursive functions. The derivation lengths of type one functionals from Tn (hence also their computational complexities) are classified optimally in terms of <ωn+2 -descent recursive functions.

In particular we obtain (reobtain?) that the derivation lengths function of a type one functional a ∈ T0 is primitive recursive, thus any type one functional a in T0 defines a primitive recursive function. Similarly we also obtain (reobtain?) a full classification of T1 in terms of multiple recursion.

As proof-theoretic corollaries we reobtain the classification of the IΣn+1-provably recursive functions. Taking advantage from our finitistic and constructive treatment of the terms of Gödel's T we reobtain additionally (without employing continuous cut elimination techniques) that PRA + PRWO(ε0) ⊢ Π20 − Refl(PA) and PRA + PRWO(ωn+2) ⊢ Π20 − Refl(IΣn+1), hence PRA + PRWO(ε0) ⊢ Con(PA) and PRA + PRWO(ωn+2) ⊢ Con(IΣn+1).

For programmatic reasons we outline in the introduction a vision of how to apply a certain type of infinitary methods to questions of finitary mathematics and recursion theory. We also indicate some connections between ordinals, term rewriting, recursion theory and computational complexity.

The Hanf number for sentences of a language L is defined to be the least cardinal κ with the property that for any sentence φ of L, if φ has a model of power ≥ κ then φ has models of arbitrarily large cardinality. We shall be interested in the language Lω1,ω (see [3]), which is obtained by adding to the formation rules for first-order logic the rule that the conjunction of countably many formulas is also a formula.

Lopez-Escobar proved [4] that the Hanf number for sentences of Lω1,ω is ⊐ω1, where the cardinals ⊐α are defined recursively by ⊐0 = ℵ0 and ⊐α = Σ{2⊐β: β < α} for all cardinals α > 0. Here ω1 denotes the least uncountable ordinal.

A sentence of Lω1,ω is complete if all its models satisfy the same Lω1,ω-sentences. In [5], Malitz proved that the Hanf number for complete sentences of Lω1,ω is also ⊐ω1, but his proof required the generalized continuum hypothesis (GCH). The purpose of this paper is to give a proof that does not require GCH.

More precisely, we will prove the following:

Theorem 1. For any countable ordinal α, there is a complete Lω1,ω-sentence σαwhich has models of power ⊐α but no models of higher cardinality.

Our basic approach is identical with Malitz's. We simply use a different combinatorial fact at the crucial point.

We investigate club guessing sequences and filters. We prove that assuming V = L, there exists a strong club guessing sequence on μ if and only if μ is not ineffable for every uncountable regular cardinal μ. We also prove that for every uncountable regular cardinal μ, relative to the existence of a Woodin cardinal above μ, it is consistent that every tail club guessing ideal on μ is precipitous.

The formalism of P(redicate) P(rovability) L(ogic) is the result of adjoining the unary operator □ to first-order logic without identity, constants, or function symbols. The term “provability” indicates that □ is to be “read” as “it is provable in P(eano) A(rithmetic) that…” and that the formulae of predicate provability logic are to be interpreted via formulae of PA as follows.

Pr(x), alias Bew(x), is the standard provability predicate of PA. For any formula F of PA, Pr[F] is the formula of PA that expresses the PA-provability of F “of” the values of the variables free in F, i.e., it is the formula of PA with the same free variables as F that expresses the PA-provability of the result of substituting for each variable free in F the numeral for the value of that variable. For the details of the construction of Pr[F], the reader may consult [B2, p. 42]. If F is a sentence of PA, then Pr[F] = Pr(‘F’), the sentence that expresses the PA-provability of F.

Let υ 1, υ 2,… be an enumeration of the variables of PA. An interpretation * of a formula ϕ of PPL is a function which assigns to each predicate symbol P of ϕ a formula P* of the language of arithmetic whose free variables are the first n variables of PA, where n is the degree of P.

A structure is locally finite if every finitely generated substructure is finite; local sentences are universal sentences all models of which are locally finite. The stretching theorem for local sentences expresses a remarkable reflection phenomenon between the finite and the infinite models of local sentences. This result in part requires strong axioms to be proved; it was studied by the second named author, in a paper of this Journal, volume 53. Here we correct and extend this paper; in particular we show that the stretching theorem implies the existence of inaccessible cardinals, and has precisely the consistency strength of Mahlo cardinals of finite order. And we present a sequel due to the first named author:

(i) decidability of the spectrum Sp(φ) of a local sentence φ, below ωω; where Sp(φ) is the set of ordinals α such that φ has a model of order type α

(ii) proof that bethω = sup{Sp(φ): φ local sentence with a bounded spectrum}

(iii) existence of a local sentence φ such that Sp(φ) contains all infinite ordinals except the inaccessible cardinals.

In the present paper, the various means used by the author in attempting to find a contradiction in Quine's New foundations are sketched, and the reason why each method failed is indicated. It was not Quine's system itself which was tested, but a stronger one obtained by adding a rule of Kleene's type to Quine's system. Reasons are presented why a contradiction in the stronger system should be as damning to Quine's system as a contradiction in Quine's system itself. Two other features of the system are worthy of note. One is the fact that only two symbols are used in building up the formulas of the system. Other systems have been built using only two symbols, but the particular method used in this paper is very flexible and simple, and is peculiarly adapted to the use of the Gödel technique. It was suggested by the consideration that the formulas of any system can be written by the use of only two symbols by first assigning Gödel numbers to the formulas and then writing those numbers in the binary scale of notation. The second feature is that ι (to be used in ιxp, meaning “the x such that p”) is an explicit and integral part of the system, and the axioms and rules governing its use are such as to make it very simple to handle. By a process similar to “Die Eliminierbarkeit der ι-Symbole” of Hilbert-Bernays, it is shown that the system involving the ι can be reduced to one not involving it. The points of difference with the Hilbert-Bernays technique make possible an especially unhampered use of ι.

We study the problem of extending an abstract independence notion for types of singletons (what Shelah calls a good frame) to longer types. Working in the framework of tame abstract elementary classes, we show that good frames can always be extended to types of independent sequences. As an application, we show that tameness and a good frame imply Shelah’s notion of dimension is well-behaved, complementing previous work of Jarden and Sitton. We also improve a result of the first author on extending a frame to larger models.

We study Turing degrees a for which there is a countable structure ${\cal A}$ whose degree spectrum is the collection {x : x ≰ a}. In particular, for degrees a from the interval [0′, 0″], such a structure exists if a′ = 0″, and there are no such structures if a″ > 0‴.

In [12] Slaman and Steel posed the following problem:

Assume ZF + DC + AD. Suppose we have a function assigning to each Turing degree d a linear order <d of d. Then must the rationals embed order preservingly in <d for a cone of d's?

They had already obtained a partial answer to this question by showing that there is no such d ↦ <d with <d of order type ζ = ω* + ω on a cone. Already the possibility that <d has order type ζ · ζ was left open.

We use here, ideas and methods associated with the concept of amenability (of groups, actions, equivalence relations, etc.) to prove some general results from which one can obtain a positive answer to the above problem.

We consider the following properties of uncountable-dimensional quadratic spaces (E, Φ):

(*) For all subspaces U ⊆ E of infinite dimension: dim U˔ < dim E.

(**) For all subspaces U ⊆ E of infinite dimension: dim U˔ < ℵ0.

Spaces of countable dimension are the orthogonal sum of straight lines and planes, so they cannot have (*), but (**) is trivially satisfied.

These properties have been considered first in [G/O] in the process of investigating the orthogonal group of quadratic spaces. It has been shown there (in ZFC) that over arbitrary uncountable fields (**)-spaces of uncountable dimension exist.

In [B/G], (**)-spaces of dimension ℵ1 (so (*) = (**)) have been constructed over arbitrary finite or countable fields. But this could be done only under the assumption that the continuum hypothesis (CH) holds in the underlying set theory.

For a fixed set A. the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A:

and, for m > 2,

where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.)

If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA:

• ODDnA can be decided with n parallel queries to A, but not with n − 1.

• ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1.

• MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1.

• MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1.

The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.)

In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree.

For a fixed set A,

Q(n, A) = {S: S can be decided with n sequential queries to A}.

Q∥ (n, A) = {S : S can be decided with n parallel queries to A}.

We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies:

• Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ …

Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ …

The same is true if A is a jump.

In this paper, we prove the wellfoundedrtess of recursive notation systems for reflecting ordinals up to Π3-reflection by relevant inductive definitions.

In combinatory logic there is a system of objects which intuitively represent functions, and a binary relation between these objects, which represents the process of evaluating the result of applying a function to an argument. (This is explained fully in [1].) From this relation called weak reduction, “≥,” an equivalence relation is defined by saying that X is weakly equivalent to Y if and only if there exist n (with 0 ≤ n) and X0,…,Xη such that

It turns out that equivalent objects represent the same function, but two objects representing the same function need not be equivalent.

Here an example will be given of a complete Lω1ω-sentence with a model of power ℵ1 but with no model of higher power. The continuum hypothesis is not assumed. The question of whether such an example exists was brought to the author's attention by Professor M. Makkai.

An Lω1ω-sentence is said to be complete if its models all satisfy the same Lω1ω-sentences, or, equivalently, if all of the countable L-structures satisfying the sentence are isomorphic. Scott [5] showed that any countable L -structure (where L is countable) must satisfy a complete Lω1ω-sentence. Such a sentence is called a Scott sentence for the structure. An uncountable L-structure need not satisfy any complete Lω1ω -sentence.

A complete Lω1ω-sentence σ is said to characterize the infinite cardinal k if σ has a model of power k but not of any higher power. The set of cardinals characterized by complete Lω1ω -sentences will be denoted by CC. By a result of Lopez-Escobar [3], if k ∈ CC, k <⊐ω1.

Assuming GCH (so that ⊐α = ℵα, ), Malitz [4] showed that CC = {ℵα: α < ω1}.

Without assuming GCH, Baumgartner [1] showed that ⊐α ∈ CC for all α < ω1.

Without GCH, it is unknown whether ℵn ∈ CC for n ≥ 2. Now it will be shown that ℵ1, ∈ CC.

A class is the set of paths through a computable tree. Given classes P and Q, P is Medvedev reducible to Q, P ≤MQ, if there is a computably continuous functional mapping Q into P. We look at the lattice formed by subclasses of 2ω under this reduction. It is known that the degree of a splitting class of c.e. sets is non-branching. We further characterize non-branching degrees, providing two additional properties which guarantee non-branching: inseparable and hyperinseparable. Our main result is to show that non-branching iff inseparable if hyperinseparable if homogeneous and that all unstated implications do not hold. We also show that inseparable and not hyperinseparable degrees are downward dense.

Methods are being developed for treating questions of decidability in fewer than Ω steps, Ω being a regular nondenumerable cardinal. In this paper we consider the set-theoretical predicate Taut(x), “x is a tautology,” taken in the infinitary sense. In case x is hereditarily finite there is no question that it is decidable in finitely many steps. But what if x is infinite? We are not assuming that x is in any way constructive or even that the propositional formulas can be well-ordered, so it is not appropriate to treat this predicate as one of natural numbers or even as one of ordinals.