Every system of signs that is defined in logical syntax may be called a formal language. It need not always be a language in the ordinary sense of the word. The rules of chess, e.g., can be expressed in the terminology of the syntax, but it would not occur to anybody to call chess a language.

A language in the ordinary sense has a meaning. That is to say that certain words in it are names of things or states or properties or relationships. In general it can be said that in any language having meaning all words subject to the rule of types are names. (Even sentences might be called names, i.e. names of facts, but we will not go so far.)

A syntax of a language L is a language with meaning, for the words of a definite type (in this paper of the type of individuals) contained in it are names of expressions of L.

If to a language we add its syntax, we get a language containing the syntax of one of its parts. If we formulate the syntax of a language L, in so far as its means allow, in the language L itself, we get a language containing a part of its syntax. We call such languages autosyntactic. It is well known that languages containing the whole of their own syntax do not exist.

We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological space X. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense in X.

It is shown that there are exactly six normal DeMorgan monoids generated by the idntity element alone. The free DeMorgan monoid with no generators but the identity is characterised and shown to have exactly three thousand and eighty-eight elements. This result solves the “Ackermann constant problem” of describing the structure of sentential constants in the logic R.

Let M be an O-minimal structure. We use our understanding, acquired in [KPS], of the structure of definable sets of n-tuples in M, to study definable (in M) equivalence relations on Mn. In particular, we show that if E is an A-definable equivalence relation on Mn (A ⊂ M) then E has only finitely many classes with nonempty interior in Mn, each such class being moreover also A-definable. As a consequence, we are able to give some conditions under which an O-minimal theory T eliminates imaginaries (in the sense of Poizat [P]).

If L is a first order language and M an L-structure, then by a definable set in M, we mean something of the form X ⊂ Mn, n ≥ 1, where X = {(a1…,an) ∈ Mn: M ⊨ϕ(ā)} for some formula ∈ L(M). (Here L(M) means L together with names for the elements of M.) If the parameters from come from a subset A of M, we say that X is A-definable.

M is said to be O-minimal if M = (M, <,…), where < is a dense linear order with no first or last element, and every definable set X ⊂ M is a finite union of points, and intervals (a, b) (where a, b ∈ M ∪ {± ∞}). (This notion is as in [PS] except here we demand the underlying order be dense.) The complete theory T is said to be O-minimal if every model of T is O-minimal. (Note that in [KPS] it is proved that if M is O-minimal, then T = Th(M) is O-minimal.) In the remainder of this section and in §2, M will denote a fixed but arbitrary O-minimal structure. A,B,C,… will denote subsets of M.

In this paper we show that in Zermelo-Fraenkel set theory (ZF) sets of reals are determinate.

Before proceeding to the proof it will be helpful to consider some previous work in this area. The first major result was obtained by Gale and Stewart [3] who showed that in ZF open games are determinate. This was then successively improved by Wolfe [4] to (and so of course ) and then by Morton Davis [1] to . The results of Morton Davis further showed that countable unions of sufficiently ‘simple’ determinate sets are also determinate. At this time, however, sets did not appear sufficiently simple for this method to be applied in order to get determinacy.

The next major advance was made by D. A. Martin who showed, using indiscernibles, that with large cardinal assumptions games are equivalent to certain open games (i.e., player I (II) has a winning strategy for the game iff I (II) has a winning strategy for the open game). Thus, by the Gale–Stewart result, games are determinate. Martin's result also showed that under these large cardinal assumptions sets are sufficiently simple for the Morton Davis method to be applied to them.

The following is part of a series of papers on theories for (iterated) admissible sets (cf. [10], [11], [12], [14], [15]). Although these theories are weak subsystems of Zermelo-Fraenkel set theory, they allow one to formalize and prove a fair amount of definability theory and generalized recursion theory. Using this machinery it is in general not very hard to establish the connections between theories for admissible sets and (for example) systems of second order arithmetic. A proof-theoretic analysis of theories for admissible sets therefore provides quite a uniform and powerful framework for the proof-theoretic treatment of many systems of set theory, second order arithmetic and constructive mathematics (see [12] and [15]). The strongest result in this direction so far is the pair of proof-theoretic equivalences

where T0 is Feferman's system for explicit mathematics of [5] and [6], (-CA) + (BI) is the usual system of second order arithmetic with the axiom of -comprehension and bar induction and KPi is Kripke-Platek set theory with ∈-induction

for arbitrary formulas and the additional axiom

.

The least standard model of KPi is L(i0) where i0 is the first recursively inaccessible ordinal.

In this paper we are mainly interested in the theory KPi0 which results from KPi by severely restricting the principles of induction. Basically, complete induction on the natural numbers

is allowed only for ∆0-formulas, and (IND∈) is omitted completely.

The system of formal logic to be presented in this paper has the following main properties:

(1). The Mengenlehre paradoxes do not arise in it.

(2). It seems to be free from other contradictions.

(3). It does not resort to a theory of types.

(4). It uses negation and material implication and does not weaken the principle of excluded middle.

(5). It contains no analogue to the Curry W operator; consequently, given a propositional function ϕ, a propositional function Ψ cannot always be found such that, for all x, ϕ(x, x) and Ψ(x) are equivalent propositions.

(6). It employs a universal quantifier, G, such that (x)f(x), (x)f(x, x), (x)f(x, x, x), …, would be respectively expressed thus, G(f, f), G(f, f, f), G(f, f, f, f), ….

(7). It employs Schönfinkel's functional notation, so that f(x1, x2, …, xn) will be written as (( … ((fx1)x2) …)xn) and abbreviated to (fx1x2… xn) and, when no ambiguity results, to fx1x2…xn.

(8). A theory of integers and real numbers cannot, apparently, be deduced from it.

(9). A form of the axiom of choice is provable in it.

In this work we describe a new approach to the notions of relevance and paraconsistency. Unlike the works of Anderson and Belnap or da Costa (see [2], [8] and [7]) we shall mainly be guided in it by semantical intuitions. In the first two sections we introduce and investigate the algebraic structures that reflect those intuitions. The corresponding formal systems are briefly described in the third section (a more detailed treatment of these systems, including full proofs, will be given in another paper).

Our basic intuitive idea is that of “domains of discourse” or “relevance domains”. Classical logic, so we think, is valid in as much as sentences get values inside one domain; limitations on its use can be imposed only with respect to inferences in which more than one domain is involved. There are two basic binary relations over the collection of domains. One is relevance. It is reflexive and symmetric (but not necessarily transitive). Under a given interpretation two sentences are relevant to each other when their values are in relevant domains. Another basic relation between domains, no less important, is that of grading according to “degrees of reality”. The idea behind it is not new. Gentzen, for example, divided in [9] the world of mathematics into three grades, representing three “levels of reality”. The elementary theory of numbers has the highest degree or level of reality; set theory has the smallest degree and mathematical analysis occupies the intermediate level. In the theory of types, or in the accumulative von Neumann universe for set theory, we can find indication of a richer hierarchy.

The present work was inspired by Mostowski's paper [3] in which he considers classes of sequences of real numbers, and associated sets of primitive recursive real numbers. The present treatment will differ from that of [3] in that we consider the real numbers in (0, ∞), instead of just those in (0, 1), but this will make little difference. In §1 we develop a general theory, and in §2 we show the relation of this theory to the results contained in [3], and to those of other authors.

1. The purpose of this paper is to show that, if the axioms of a system G of set theory are consistent, then it is impossible to prove from them the following weak form of the axiom of choice: (H1) For every denumerable set x of disjoint two-element sets, there is a set y, called a choice set for x, which contains exactly one element in common with each element of x. Among the axioms of the system G, we take, with minor modifications, Axioms A, B, C of Gödel [6]. Clearly, the independence of H1 implies that of all stronger propositions, including the general axiom of choice and the generalized continuum hypothesis.

The proof depends upon ideas of Fraenkel and Mostowski, and proceeds in the following manner. Let a be a denumerable set of objects Δ0, Δ1, Δ2, …, the exact nature of which will be specified later. Let μj = {Δ2j, Δ2j+1} for each j, c = {μ0, μ1, μ2, …}, and b = [the sum set of a]. By transfinite induction, construct the class Vc which is the closure of b under the power-set operation. For each j, it is possible to define a 1–1 mapping of Vc onto itself with the following properties. The mapping preserves the ε-relation, or, more precisely, .

An effective translation of the fact that any infinite ordered set contains an infinite ascending or descending sequence is that any infinite recursive set A ⊆ Q has a recursive subset with order type ω or ω*. Tennenbaum's theorem states that this translation is false, and there is a counterexample A with order type ω + ω*. Tennenbaum suggested that this counterexample is an infinite recursive linearly ordered set which is effectively finite, and that the collection of all such counterexamples could provide a concrete model of nonstandard arithmetic. The purpose of this paper is to determine the collection of order types for which there is a counterexample.

It is readily seen that any counterexample to the effective translation must have order type ω + Z · α + ω* for some α [2], [3]. Let be the collection of order types α for which there is a counterexample. As a test case, we have previously shown that contains the constructive scattered orderings [3], [4]. In this paper we determine exactly which order types are in . We easily show that if ω+ Z · α + ω* is recursive, then α is . The main result is that . Consequently, .

The problem of characterizing the finite lattices which can be embedded into the recursively enumerable degrees has a long history, which is summarized in [AL]. This problem is an important one, as its solution is necessary if a decision procedure for the ∀∃-theory of the poset of recursively emumerable degrees is to be found. A recursive nonembeddability condition, NEC, which subsumes all known nonembeddability conditions was presented in [AL]. This paper focuses on embeddability. An embeddability condition, EC, is introduced, and we prove that every finite lattice having EC can be embedded (as a lattice) into . EC subsumes all known embeddability conditions.

EC is a Π3 condition which states that certain obstructions to proving embeddability do not exist. It seems likely that the recursive labeled trees used in EC can be replaced with trees which are effectively generated from uniformly defined finite trees, in which case EC would be equivalent to a recursive condition. We do not know whether EC and NEC are complementary. This problem seems to be combinatorial, rather than recursion-theoretic in nature. Our efforts to find a finite lattice satisfying neither EC nor NEC have, to this point, been unsuccessful. It is the second author's conjecture that the techniques for proving embeddability which are used in this paper cannot be refined very much to obtain new embeddability results.

EC is introduced in §2, and the various conditions and definitions are motivated by presenting examples of embeddable lattices and indicating how the embedding proof works in those particular cases. The embedding construction is presented in §3, and the proof in §4.

We prove that in the Solovay model, every OD equivalence relation, Ε, over the reals, either admits an OD reduction to the equality relation on the set of all countable (of length < ω1) binary sequences, or continuously embeds Ε0, the Vitali equivalence.

If Ε is a (resp. ) relation then the reduction above can be chosen in the class of all Δ1 (resp. Δ2) functions.

The proofs are based on a topology generated by OD sets.

Let λ denote a singular cardinal. Zeman, improving a previous result of Shelah, proved that together with 2λ = λ+ implies ⋄S for every S ⊆ λ+ that reflects stationarily often.

In this paper, for a set S ⊆ λ+, a normal subideal of the weak approachability ideal is introduced, and denoted by I[S; λ]. We say that the ideal is fat if it contains a stationary set. It is proved:

1. if I[S; λ] is fat, then NSλ + ∣ S is non-saturated;

2. if I[S; λ] is fat and 2λ = λ+, then ⋄S holds;

3. implies that I[S; λ] is fat for every S ⊆ λ+ that reflects stationarily often;

4. it is relatively consistent with the existence of a supercompact cardinal that fails, while I[S; λ] is fat for every stationary S ⊆ λ+ that reflects stationarily often.

The stronger principle is studied as well.

In the last years several research projects have been motivated by the problem of constructing the usual geometrical spaces by admitting “regions” and “inclusion” between regions as primitives and by defining the points as suitable sequences or classes of regions (for references see [2]).

In this paper we propose and examine a system of axioms for the pointless space theory in which “regions”, “inclusion”, “distance” and “diameter” are assumed as primitives and the concept of point is derived. Such a system extends a system proposed by K. Weihrauch and U. Schreiber in [5].

In the sequel R and N denote the set of real numbers and the set of natural numbers, and E is a Euclidean metric space. Moreover, if X is a subset of R, then ⋁X is the least upper bound and ⋀X the greatest lower bound of X.

In [MP] Marker and Pillay showed that if X ⊂ Cn is constructible but (C, +, X) is not locally modular, then multiplication is definable in the structure (C, +,X). That result extended earlier results of Martin [M] and Rabinovich and Zil'ber [RZ]. Here we will examine additive reducts of R and Qp.

Definition. A subset X of Rn is called semialgebraic if it is definable in the structure (R, +,·). A subset X of Rn is called semilinear if it is definable in the structure (R, +, <,λr)r∈b, where λr is the function x ↦ rx [scalar multiplication by r].

Every semilinear set is a Boolean combination of sets of the form {: p () = 0} and {: q() > 0}, where p() and q() are linear polynomials.

Van den Dries asked the following question: if X is semialgebraic but not semilinear, can we define multiplication in (R, +, <,X)? This was answered negatively by Pillay, Scowcroft and Steinhorn.

Theorem 1.1 [PSS]. Suppose X ⊂ Rnis semialgebraic and X ⊂ Infor some bounded interval I. Then multiplication is not definable in (R, +, <,X,λr)r∈R.

In particular if X = · ∣ [0, l ]2, the graph of multiplication restricted to the unit interval, then X is not semilinear so we have a negative answer to van den Dries' question. Peterzil showed that this is the only restriction.

We study the long-standing open problem of giving $\forall {\rm{\Sigma }}_1^b$ separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the $\forall {\rm{\Sigma }}_1^b$ Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole principle for FPNP functions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of $T_2^1$ augmented with the surjective weak pigeonhole principle for polynomial time functions.

In this paper, we shall prove two theorems involving the construction of core models with infinitely many Woodin cardinals. We assume familiarity with [12], which develops core model theory the one Woodin level, and with [10] and [6], which extend the fine structure theory of [5] to mice having many Woodin cardinals. The most important new problem of a general nature which we must face here concerns the iterability of Kc with respect to uncountable iteration trees.

Our first result is the following theorem, a slightly stronger version of which was proved independently and earlier by Woodin. The theorem settles positively a conjecture of Feng, Magidor, and Woodin [2].

Theorem. Let Ω be measurable. Then the following are equivalent:

(a) for all posets,

(b) for every poset,

(c) for every poset ℙ ∈ VΩ, Vℙ ⊨ there is no uncountable sequence of distinct reals in L(ℝ)

(d) there is an Ω-iterable premouse of height Ω which satisfies “there are infinitely many Woodin cardinals”.

It is an immediate corollary that if every set of reals in L(ℝ) is weakly homogeneous, then ADL(ℝ) holds. We shall also indicate some extensions of the theorem to pointclasses beyond L(ℝ), and mice with more than ω Woodin cardinals.

Large cardinal properties divide rather strikingly into two groups. “Small” large cardinal properties such as weak compactness always relativize to L, while in contrast “large” large cardinal properties such as Ramsey are incompatible with L. These properties seem to be similar otherwise and this sense of similarity is reinforced by the fact that many of the large cardinals do exist in the L-like model L(μ). This paper will show that the division is caused by an artificially restrictive class of “constructible” sets rather than an essential difference in the properties themselves. Specifically, we consider the class K of sets constructible from mice as defined by Dodd and Jensen [3] and prove

Theorem 1. If ρ is Ramsey then ρ is Ramsey in K.

A modification of the proof will show

Theorem 2. If ρ is Jonson, then ρ is Ramsey in K.

Since Ramsey implies Jonson this shows that the notions are equiconsistent. Theorem 2 was proved by Kunen [5] under the assumption that V = L(μ).

The proof of Theorems 1 and 2 depends heavily on results of Dodd and Jensen [3] about K and mice. These results are stated without proof in §2. §2 also contains elementary (to a reader familiar with the theory of iterated ultrapowers) proofs of special cases of some of these lemmas sufficient to give a self contained proof of the following corollary of Theorem 1:

Corollary. If ρ ≤ κ,ρ is Ramsey and L(μ) ⊨ μ is a measure on κ then L(μ) ⊨ ρ is Ramsey.

We investigate ideals of the form {A ⊆ ω: Σn∈Axn is unconditionally convergent} where (xn)n∈ω is a sequence in a Polish group or in a Banach space. If an ideal on ω can be seen in this form for some sequence in X, then we say that it is representable in X.

After numerous examples we show the following theorems: (1) An ideal is representable in a Polish Abelian group iff it is an analytic P-ideal. (2) An ideal is representable in a Banach space iff it is a nonpathological analytic P-ideal.

We focus on the family of ideals representable in c0. We characterize this property via the defining sequence of measures. We prove that the trace of the null ideal, Farah’s ideal, and Tsirelson ideals are not representable in c0, and that a tall Fσ P-ideal is representable in c0 iff it is a summable ideal. Also, we provide an example of a peculiar ideal which is representable in ℓ1 but not in ℝ.

Finally, we summarize some open problems of this topic.