We show that IE1 proves that every element greater than 1 has a unique factorization into prime powers, although we have no way of recovering the exponents from the prime powers which appear. The situation is radically different in Bézout models of open induction. To facilitate the construction of counterexamples, we describe a method of changing irreducibles into powers of irreducibles, and we define the notion of a frugal homomorphism into , the product of the p-adic integers for each prime p.

Our framework is ZFC, and we view cardinals as initial ordinals. Baumgartner ([Bal] and [Ba2]) studied properties of large cardinals by considering these properties as properties of normal ideals and not as properties of cardinals alone. In this paper we study these combinatorial properties by defining operations which take as input one or more ideals and give as output an ideal associated with a large cardinal property. We consider four operations T, P, S and C on ideals of a regular cardinal κ, and study the structure of the collection of subsets they give, and the relationships between them.

The operation T is defined using combinatorial properties based on trees 〈X, <T〉 on subsets X ⊆ κ (where α <T β → α < β). Given an ideal I, consider the property *: “every tree on κ with every branching set in I has a branch of size κ” (where a branching set is a maximal set with the same set of <T-predecessors, and a chain is a maximal <T-linearly ordered set; for definitions see §2). Now consider the collection T(I) of all subsets of κ that do not satisfy * (see Definition 2.2 and the introduction to §5). The operation T provides us with the large cardinal property (whether κ ∈ T(I) or not) and it also provides us with the ideal associated with this large cardinal property (namely T(I)); in general, we obtain different notions depending on the ideal I.

The Baire number of the real line (see 1.1(c)) has uncountable cofinality [Mi]. This number is equal to the Baire number of the space 2ω and also to the Baire number (1.1(d)) of every countable partial order. Our research is motivated by the following open question (1.13) (see also [BPS] and [Mi]): can the cofinality of nκ, the Baire number of the space (2κ)κ (1.1(b)), be less than or equal to κ? This question is nontrivial when κ is regular and 2κ = κ (1.3). A. Miller proved that the answer is “no” if κ is strongly inaccessible (see [Mi] and 1.11). Assuming CH, is equal to the Baire number of the Stone space of ℘(ω)/Fin.

In §1 we discuss , the Baire number of the space (2λ)κ. If κ is regular, then , and using 1.3 and 1.5, we may rule out the easy cases and restrict ourselves to cases where κ is regular with 2<κ = κ, and κ ≤ λ 2κ. If λ > κ, then it is consistent to have cof()=κ ([Mi] and 1.7). We do not know whether is consistent (1.9). Next, the cardinal number eκ is defined (1.10). It is easy to see that nκ ≤ eκ and that cof(eκ) > κ. If κ is strongly inaccessible (s.i.), then nκ = eκ ([Mil], [Bar], [MF] and 1.11). For κ accessible, the question of whether nκ = eκ is open.

Another open question (Fremlin) is stated as follows: assume W ⊇ V and f ∈ ωω ∩ W is such that, for every g ∈ ω ω ∩ V, ∣(f = g)∣ = ℵ0, does this imply that W contains sets which are ω-Cohen (1.1(a)) over V? If κ is accessible regular with 2<κ = κ, then the answer to the analog of Fremlin's question for κ is “no”. In fact, any κ-closed forcing that adds new subsets of κ, also adds a new function f ∈ κκ such that, for every g ∈ κκ ∩V, (f = g) is stationary (4.1(a)). On the other hand, perfect-set forcing on κ (see [Ka] and §5) adds a new subset of κ but produces a minimal extension (5.4(b)), and hence adds no sets which are κ-Cohen over V.

We try to count the number of countable models M of T with a fixed set Q = Φ(M) of realizations of a type Φ. Also, for stable T, we define an ordinal rank measuring multiplicity of types, with additivity properties similar to those of U-rank.

The notion of a ptyx (plural, ptykes) is obtained by generalising the ordinals On and the dilators Dil introduced by Girard [1] into a typed hierarchy. The notion is due to Girard, and a detailed treatment will appear in Girard [2].

In this Introduction we will give a summary of the theory of ptykes. It will be an advantage to be familiar with the theory of dilators as introduced in Girard [1] or as presented in Girard and Normann [3].

The class On of ordinals is organised into a category ON by using strictly increasing maps f: x → y as morphisms. A dilator will be a functor F: ON → ON commuting with pullbacks and direct limits. Associated with each dilator F there is a denotation system DF, obtained as follows: For each x ∈ On and y ∈ F(x), y can be given a unique denotation (c; x0,…, xn−1;x)F, where c∈F(n) (n = {0,…, n − 1}), y = F(ϕ)(c) (where ϕ is defined by ϕ(i) = xi for i < n), and for no m < n and ψ: m → n do we have c ∈ im(ψ).

We let the trace Tr(F) be the set of pairs (c, n) occurring in a denotation.

This paper presents several proof-theoretic results concerning weak fixed point theories over second order number theory with arithmetic comprehension and full or restricted induction on the natural numbers. It is also shown that there are natural second order theories which are proof-theoretically equivalent but have different proof-theoretic ordinals.

In 1986, Beigel [Be87] (see also [Od89, III.5.9]) proved the nonspeedup theorem: if A, B ⊆ ω, and as a function of 2n variables can be computed by an algorithm which makes at most n queries to B, then A is recursive (informally, 2n parallel queries to a nonrecursive oracle A cannot be answered by making n sequential (or “adaptive”) queries to an arbitrary oracle B). Here, 2n cannot be replaced by 2n − 1. In subsequent papers of Beigel, Gasarch, Gill, Hay, and Owings the theory of “bounded query classes” has been further developed (see, for example, [BGGOta], [BGH89], and [Ow89]). The topic has also been studied in the context of structural complexity theory (see, for example, [AG88], [Be90], and [JY90]).

If A ⊆ ω and n ≥ 1, let . Beigel [Be87] stated the powerful “cardinality conjecture” (CC): if A, B ⊆ ω, and can be computed by an algorithm which makes at most n queries to B, then A is recursive. Owings [Ow89] verified CC for n = 1, and, for n 1, he proved that A is recursive in the halting problem. We prove that CC is true for all n.

We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.

In 1960 G. F. Rose [R] made the following definition: A function f: ω → ω is (m, n)-computable, where 1 ≤ m ≤ n, iff there exists a recursive function R: ωn → ωn such that, for all n-tuples (x1,…, xn) of distinct natural numbers,

J. Myhill (see [McN, p. 393]) asked if f had to be recursive if m was close to n; B. A. Trakhtenbrot [T] responded by showing in 1963 that f is recursive whenever 2m > n. This result is optimal, because, for example, the characteristic function of any semirecursive set is (1,2)-computable. Trakhtenbrot's work was extended by E. B. Kinber [Ki1], using similar techniques. In 1986 R. Beigel [B] made a powerful conjecture, much more general than the above results. Partial verification, falling short of a full proof, appeared in [O]. Using new techniques, M. Kummer has recently established the conjecture, which will henceforth be referred to as the cardinality theorem (CT). It is the goal of this paper to show the connections between these various theorems, to review the methods used by Trakhtenbrot, and to use them to prove a special case of CT strong enough to imply Kinber's theorem (see §3). We thus have a hierarchy of results, with CT at the top. We will also include a discussion of Kummer's methods, but not a proof of CT.