In this note we investigate the question when a henselian valued field carries a nontrivial ∅-definable henselian valuation (in the language of rings). This is clearly not possible when the field is either separably or real closed, and, by the work of Prestel and Ziegler, there are further examples of henselian valued fields which do not admit a ∅-definable nontrivial henselian valuation. We give conditions on the residue field which ensure the existence of a parameter-free definition. In particular, we show that a henselian valued field admits a nontrivial henselian ∅-definable valuation when the residue field is separably closed or sufficiently nonhenselian, or when the absolute Galois group of the (residue) field is nonuniversal.

We prove a number of results in effective randomness, using methods in which Π1 0 classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.

The uniform reflection principle for the theory of uniform T-sentences is added to PA. The resulting system is justified on the basis of a disquotationalist theory of truth where the provability predicate is conceived as a special kind of analyticity. The system is equivalent to the system ACA of arithmetical comprehension. If the truth predicate is also allowed to occur in the sentences that are inserted in the T-sentences. yet not in the scope of negation, the system with the reflection schema for these T-sentences assumes the strength of the Kripke-Feferman theory KF. and thus of ramified analysis up to ε0.

We lean upon the usual variant of the logic of quantum mechanics [1]. Here the propositions correspond to the results of the quantum experiments. A beautiful essay [2] may be connected with a conservation of semantics. But we try to broaden the semantics, admitting propositions about the possibility of results of experiments. Doing so, we fulfil the old wish of W. A. Fock, who attracts our attention to the importance of the modal categories for the interpretation of the quantum theory [3].

We begin with the formal description of the modal system Br+. The alphabet contains the signs ~, ∨ and Ↄ (negation, alternative and the sign of necessity), the set V of the prepositional variables and parentheses. The rules of formation are: if A ∈ V, then A is a proposition; if X and Y are propositions, then ~ X, X ∨ Y and Ↄ X are propositions also; there are no other propositions. ℬ will design the set of all propositions.

The rules of transformation are the following:

.

Here X, Y ∈ ℬ. The sign ⊨ denotes the derivability in Br+ (in one step here).

The notion of algebraic closedness plays an important part in the theory of commutative fields. The corresponding notion in the theory of ordered fields is (not only intuitively but in a sense which can be made precise in a metamathematical framework, compare [4]) that of a real closed ordered field. Several suggestions have been made (see [2] and [8]) for the formulation of corresponding concepts in the theory of groups and in the theory of skew fields (division rings, noncommutative fields). Here we present a concept of this kind, which preserves the principal metamathematical properties of algebraically closed commutative fields and which applies to a wide class of first order theories K, including the theories of commutative and of skew fields and the theories of commutative and of general groups.

We study in this paper the projective ordinals , where = sup{ξ: ξis the length of a Δn 1prewellordering of the continuum}. These ordinals were introduced by Moschovakis in [8] to serve as a measure of the “definable length” of the continuum. We prove first in §2 that projective determinacy implies , for all even n > 0 (the same result for odd n is due to Moschovakis). Next, in the context of full determinacy, we partly generalize (in §3) the classical fact that δ1 1 = ℵ1 and the result of Martin that δ3 1 = ℵω+1 by proving that , where λ2n+1 is a cardinal of cofinality ω. Finally we discuss in §4 the connection between the projective ordinals and Solovay's uniform indiscernibles. We prove among other things that ∀α(α # exists) implies that every δn 1 with n ≥ 3 is a fixed point of the increasing enumeration of the uniform indiscernibles.

It is well known that the modal calculus S4 has infinitely many non-equivalent formulae in a single proposition letter (in standard terminology, infinitely many modal functions), whilst S5 has only finitely many. However, the situation regarding the intermediate modal calculi S4.2, S4.3, and Prior's Diodorean tense-logic D does not seem to have been settled. In this note we show that each of these systems, together with a certain proper supersystem D* of D, has infinitely many modal functions.

This is in contrast with the fact that in the intermediate propositional logics KC and LC, which correspond under the McKinsey-Tarski translations to S4.2 and S4.3, there are only finitely many non-equivalent formulae in a single proposition letter.2

One of the numerous characterizations of a Ramsey cardinal κ involves the existence of certain types of elementary embeddings for transitive sets of size κ satisfying a large fragment of ZFC. We introduce new large cardinal axioms generalizing the Ramsey elementary embeddings characterization and show that they form a natural hierarchy between weakly compact cardinals and measurable cardinals. These new axioms serve to further our knowledge about the elementary embedding properties of smaller large cardinals, in particular those still consistent with V = L.

We give a direct proof of admissibility of cut and contraction for the contraction-free sequent calculus G4ip for intuitionistic propositional logic and for a corresponding multi-succedent calculus: this proof extends easily in the presence of quantifiers, in contrast to other, indirect, proofs, i.e., those which use induction on sequent weight or appeal to admissibility of rules in other calculi.

In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NCℝ, PARℝ, EXPℝ and some others more.

This paper is intended to serve a twofold purpose. Its ultimate aim is the presentation of a syntactical definition of the degree of confirmation of a hypothesis on the basis of given evidence, a notion which is known to be of outstanding significance for the logic of inductive reasoning in the empirical sciences. The theory of confirmation to be developed here has as its foundation the theory of probability, and in order to make that foundation sufficiently secure, it was found expedient to present the theory of probability in axiomatic form and to introduce a syntactical interpretation of probability suitable for the intended application in the theory of confirmation. In this sense then to clarify the logical foundations of probability theory is this paper's first aim.

We discuss in the paper the following problem: Given a function in a given Baire class, into “how many” (in terms of cardinal numbers) functions of lower classes can it be decomposed? The decomposition is understood here in the sense of the set-theoretical union.

We investigate the possibility to characterize (multi)functions that are -definable with small i (i = 1, 2, 3) in fragments of bounded arithmetic T2 in terms of natural search problems defined over polynomial-time structures. We obtain the following results:

(1) A reformulation of known characterizations of (multi)functions that are and -definable in the theories and .

(2) New characterizations of (multi)functions that are and -definable in the theory .

(3) A new non-conservation result: the theory is not -conservative over the theory .

To prove that the theory is not -conservative over the theory , we present two examples of a -principle separating the two theories:

(a) the weak pigeonhole principle WPHP(a2, f, g) formalizing that no function f is a bijection between a2 and a with the inverse g,

(b) the iteration principle Iter(a, R, f) formalizing that no function f defined on a strict partial order ({0,…, a}, R) can have increasing iterates.

We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

Let be the class of recursively enumerable (r.e.) sets with infinite complements. A set M ϵ is maximal if every superset of M which is in is only finitely different from M. In [1] Friedberg shows that maximal sets exist, and it is an easy consequence of this fact that every non-simple set in has a maximal superset. The natural question which arises is whether or not this is also true for every simple set (Ullian [2]). In the present paper this question is answered negatively. However, the main concern of this paper is with demonstrating, and developing a few consequences of, what might be called the “density” of hyperhypersimple sets.

In [8] and [9] Urquhart presented the semilattice semantics for a relevance logic with conjunction and disjunction. These semantics combined the simplest known semantics for relevant implication, with minimal modification of the truth conditions for conjunction and disjunction. A slightly different approach leads to the distinct positive relevance logic of [7] and [5]. Sound and complete axiomatic logics for the semilattice semantics were readily available, so long as disjunction was left out.

The purpose of this paper is to report the remedy of this lack. In [1] the author developed work of Fine ([3], announced in [4]) and Prawitz [6] to show soundness and completeness of an axiomatic logic and two natural deduction logics, with respect to Urquhart's semantics. Thus Prawitz' positive relevance logic is equivalent to the semilattice logic, rather than the logic of [5]. We present here the axiomatic logic and show its equivalence to the semilattice semantics.

In §1 the languages and logic are given, along with a few proof-theoretic remarks. In §2 the semantics are defined, and the soundness proof is sketched. In §3, the completeness proof is given.

A careful exposition of Zilber's quasiminimal excellent classes and their categoricity is given, leading to two new results: the Lω1ω(Q)-definability assumption may be dropped, and each class is determined by its model of dimension ℵ0.

Model-theoretic concepts of saturation and categoricity are studied in the context of accessible categories. Accessible categories which are categorical in a strong sense are related to categories of M-sets (M is a monoid). Typical examples of such categories are categories of λ-saturated objects.

This paper continues the study of the Ramsey-like large cardinals introduced in [5] and [14]. Ramsey-like cardinals are defined by generalizing the characterization of Ramsey cardinals via the existence of elementary embeddings. Ultrafilters derived from such embeddings are fully iterable and so it is natural to ask about large cardinal notions asserting the existence of ultrafilters allowing only α-many iterations for some countable ordinal α. Here we study such α-iterable cardinals. We show that the α-iterable cardinals form a strict hierarchy for α ≤ ω1, that they are downward absolute to L for , and that the consistency strength of Schindler's remarkable cardinals is strictly between 1-iterable and 2-iterable cardinals.

We show that the strongly Ramsey and super Ramsey cardinals from [5] are downward absolute to the core model K. Finally, we use a forcing argument from a strongly Ramsey cardinal to separate the notions of Ramsey and virtually Ramsey cardinals. These were introduced in [14] as an upper bound on the consistency strength of the Intermediate Chang's Conjecture.

In this paper the theory of logical types will be examined, and certain departures from it will be suggested. Though the purpose of the paper is not primarily expository, an approach has been possible which presupposes no familiarity with special literature. Matters at variance with such an approach have been confined to appendices and footnotes.

In the early pages the logical paradoxes will be considered—an infinite series of them, of which Russell's paradox is the first. Then Russell's simple theory of types will be formulated, in adaptation to a minimal set of logical primitives: inclusion and abstraction. Two aspects of the theory will be distinguished: an ontological doctrine and a formal restriction. It will be found that by repudiating the former we can avoid certain unnatural effects of the type theory—notably the reduplication of logical constants from type to type, and the apparent dependence of finite arithmetic upon an axiom of infinity. But the formal restriction itself has unnatural effects, which survive, even in an aggravated form, after the type ontology has been dropped. A liberalization of the formal restriction will be proposed which removes the more irksome of these anomalies.