In this paper we study a certain class of Lie algebras over commutative von Neumann algebras satisfying a certain finiteness condition. By using Boolean valued methods developed by Takeuti [8]−[11], we will establish the basic structure and representation theorems.

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S 2 = ⋃ i . These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.

The main result of this paper is that if κ is not a weakly Mahlo cardinal, then the following two conditions are equivalent:

1. is κ+-complete.

2. is a prenormal ideal.

Our result is a generalization of an announcement made in [Z]. We say that is selective iff for every -function f: κ → κ there is a set X ∈ such that f∣(κ − X) is one-to-one. Our theorem provides a positive partial answer to a question of B. Wȩglorz from [BTW, p. 90], viz.: is every selective ideal with κ+-complete, isomorphic to a normal ideal?

The theorem is also true for fine ideals on [λ]<κ for any κ ≤ λ, i.e. if κ is not a weakly Mahlo cardinal then the Boolean algebra is λ+-complete iff is a prenormal ideal (in the sense of [λ/<κ).

Let X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = , graphs. If X = Y = ωω, P may be taken to be . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy.

The most basic construction of an r.e. nonrecursive set—e.g. of the halting problem—proceeds by taking the diagonal of a recursive enumeration of all r.e. sets. We will answer the question of which r.e. sets can be constructed in this manner.

If ψ is a computable numbering of some class of partial recursive functions, we define the diagonal of ψ to be the set K ψ ≔ {i ∈ ω ∣ ψ i (i)↓}- It is well known that K φ is creative if φ is a Gödelnumbering, and that for each creative set K there exists a Gödelnumbering φ such that K = K φ. That is to say, the class of diagonals of Gödelnumberings is characterized as the class of creative sets. This class was shown to be elementary lattice theoretic (e.l.t.) by Harrington (see [So87, XV. 1.1]).

We give a characterization of diagonals of arbitrary computable numberings of the class P 1 of all partial recursive functions. To this end we introduce the notion of a semihyperhypersimple (shhs) set, which generalizes the notion of hyperhypersimplicity to nonsimple sets. It is shown that the diagonals of numberings of P 1 are exactly the non-shhs sets. Then, properties of shhs sets are discussed. For example, for each nonrecursive r.e. set A there exists a nonrecursive shhs set B ≤ T A, but not every r.e. T-degree contains a shhs set. These results build upon previous work by Downey and Stob [DSta].

The question whether the property “shhs” is (elementary) lattice theoretic remains open. A positive answer would give both an analog of Harrington's result mentioned above, and a generalization of the well-known fact, due to Lachlan [La68], that hyperhypersimplicity is e.l.t. Therefore, we suspect that shhs sets turn out to be useful in the study of the lattice of r.e. sets.

Previously, for several constructions from recursion theory the role of the underlying numbering of P 1 was investigated; see Martin ([Ma66a] or [So87, V.4.1]) and Lachlan ([La75] or [Od89, III.9.2]) for Post's simple set, and Jockusch and Soare ([JS73]; cf. also [So87, XII.3.6, 3.7]) for Post's hypersimple set. However, only Gödelnumberings were considered. An explanation for the greater variety which arises when arbitrary numberings of P 1 are admitted is provided by the fact that the index set of Gödelnumberings is less complex than the index set of all numberings of P 1. The former is Σ1-complete; the latter is Π4-complete.

Let ω be the set of natural numbers, i.e. {0, 1, 2, 3, …}. A string is a mapping from an initial segment of ω into {0, 1}. We identify a set A ≤ ω with its characteristic function. A set A ≤ ω is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every set of strings S, there is a σ < A such that σ ∈ S or (∀ν ≥ σ)(ν ∉ S). By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, D(≤ a) denotes the set of degrees recursive in a.

The relation between generic degrees and minimal degrees has been widely studied. Spector [9] proved the existence of minimal degrees. Shoenfield [8] simplified the proof by using trees. In the construction of a minimal degree, given σ we extend σ to ν so that ν is in the (splitting or nonsplitting) subtree of a given tree. But in the construction of a generic set, given σ we extend σ to ν to meet the given dense set. So these two constructions are quite different. Jockusch [5] showed that any 2-generic degree bounds no minimal degree. Chong and Jockusch [3] showed that any 1-generic degree below 0′ bounds no minimal degree.