Friedman has posed (see [F, p. 117]) the following problem: “35. Define the set E of expressions by (i) Con is an expression; (ii) if A, B are expressions so are (~ A), (A&B), and Con(A). Each expression ϕ in E determines a sentence ϕ in PA [classical first-order arithmetic] by taking Con* to be “PA is consistent,” ( ~ A) * to be ~ (A*), (A&B)* to be A*&B*, and Con(A)* to be “PA + ‘A*’ is consistent.” The set of expressions ϕ ∈ E such that ϕ* is true is recursive.

The formalized second incompleteness theorem reads

In order to simplify notation, we will reformulate Friedman's problem slightly. Let Con be the usual sentence of PA expressing the consistency of PA, ~ A the negation of A, (A&B) the conjunction of A and B, etc., and Bew(A) the result of substituting the numeral for the Gödel number of A for the free variable in the usual provability predicate for PA. Let Con(A) = ~ Bew(~ A). (Con(A) is equivalent in PA to the usual sentence expressing the consistency of PA + A.) And let the class of F-sentences be the smallest class which contains Con and which also contains ~ A, (A&B) and Con(A) whenever it contains A and B. Since ⊦PA Bew(A) ↔ Bew(B) if ⊦PAA ↔ B, Friedman's problem is then the question whether the class of true F-sentences is recursive.

The answer is that it is recursive. To see why, we need a definition and a theorem.

Definition. An atom is a sentence Conn for some n ≥ 1, where Cont = Con and Conn + 1 = Con(Conn).

This paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable-supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces by .

In this paper we will present an application of generalized recursion theory to (noncombinatorial) set theory. More precisely we will combine a priority argument in α-recursion theory with a forcing construction to prove a theorem about the interdefinability of certain subsets of admissible ordinals.

Our investigation was prompted by G. Sacks and S. Simpson asking [6] if it is obvious that there are, for each Σn-admissible α, Σn (over L α ) subsets of α which are Δn -incomparable. If one understands “B is Δn in C” to mean that there are Σn /L α reduction procedures which put out B and when one feeds in C, then the answer is an unqualified “yes.” In this sense “Δn in” is a direct generalization of “α-recursive in” (replace Σ1 by Σn in the definition) and so amenable to the methods of [7, §§3, 5]. Indeed one simply chooses a complete Σn−1 set A and mimics the construction of [6] as modified in [7, §5] to produce two α-A-r.e. sets B and C neither of which is α-A-recursive in the other. By the remarks on translation [7, §3] this will immediately give the desired result for this definition of “Δn in.”

There is, however, the more obvious and natural notion of “Δn in” to be considered: B is Δn in C iff there are Σn and Πn formulas of ⟨L α , C⟩ which define B.

We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

The notion of CM-triviality was introduced by Hrushovski, who showed that his new strongly minimal sets have this property. Recently Baudisch has shown that his new ω1-categorical group has this property. Here we show that any group of finite Morley rank definable in a CM-trivial theory is nilpotent-by-finite, or equivalently no simple group of finite Morley rank can be definable in a CM-trivial theory.

A stable theory is finitely based if every set of indiscernibles is based on a finite subset. This is a common generalization of superstability and 1-basedness. We show that if such theories have more than one model they must have infinitely many, and prove some other conjectures.

We study o-minimal expansions of Archimedean totally ordered groups. We first prove that any such expansion must be elementarily embeddable via a unique (provided some nonzero element is 0-definable) elementary embedding into a unique o-minimal expansion of the additive ordered group of real numbers . We then show that a definable function in an o-minimal expansion of enjoys good differentiability properties and use this to prove that an Archimedean real closed field is definable in any nonsemilinear expansion of . Combining these results, we obtain several restrictions on possible o-minimal expansions of arbitrary Archimedean ordered groups and in particular of the rational ordered group.

We show that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first order arithmetic. We introduce a novel coding method, using the notion of a -pair, to code a large class of countable relations.

Since Cohen [1] showed the independence of the axiom of choice from the other axioms of ZF, a number of people have used his forcing technique to show how badly choice can fail while certain vestiges of it remain. Many of these arguments involve the introduction of a generic sequence or generic set of generic sets of ordinals into a countable standard model of ZF + V = L. The desired results then follow by the use of clever permutation and forcing arguments. (See Cohen [2, pp. 136–142].)

In the following we try to answer a simple question, “what does forking look like in an o-minimal theory”, or more generally, “what kinds of notions of independence with what kinds of properties are admissible in an o-minimal theory?” The motivation of these question begin with the study of simple theories and generalizations of simple theories. In [3] Kim and Pillay prove that the class of simple theories may be described exactly as those theories bearing a notion of independence satisfying various axioms. Thus it is natural to ask, if we weaken the assumptions as to which axioms must hold, what kind of theories do we get? Another source of motivation, also stemming from the study of simple theories, comes from the work of Shelah in [8] and [7]. Here Shelah addresses a “classification” type problem for class of models of a theory, showing that a theory will have the appropriate “structure” type property if one can construct a partially ordered set, satisfying various properties, of models of the theory. Using this criterion Shelah shows that the class of simple theories has this “structure” property, yet also that several non-simple examples do as well (though it should be pointed out that o-minimal theories can not be among these since any theory with the strict order property will have the corresponding “non-structure” property [8]). Thus one is lead to ask, what are the non-simple theories meeting this criterion, and one is once again led to study the types of independence relation a theory might bear. Finally, Shelah in [6] provides some possible definitions of what axioms for a notion of independence one should possibly look for in order to hope that theories bearing such a notion of independence should be amenable closer analysis. In studying all of the above mentioned situations it readily becomes clear that dividing and forking play a central role in all of them, even though we are no longer dealing with the simple case where we know that dividing and forking are very well behaved. All of these considerations lead one to look for classes of non-simple theories of which something is known where one can construct interesting notions of independence and consequently also say something about the nature of forking and dividing in these contexts. Given this one is naturally lead to one of the most well behaved classes of non-simple theories, namely the o-minimal theories.

In this paper we investigate the reverse mathematics of higher-order analogues of the theory $$ATR_0$$ within the framework of higher order reverse mathematics developed by Kohlenbach [11]. We define a theory $$RCA_0^3$$, a close higher-type analogue of the classical base theory $$RCA_0$$ which is essentially a conservative subtheory of Kohlenbach’s base theory $$RCA_{\rm{0}}^\omega$$. Working over $$RCA_0^3$$, we study higher-type analogues of statements classically equivalent to $$ATR_0$$, including open and clopen determinacy, and examine the extent to which $$ATR_0$$ remains robust at higher types. Our main result is the separation of open and clopen determinacy for reals, using a variant of Steel’s tagged tree forcing; in the presentation of this result, we develop a new, more flexible framework for Steel-type forcing.

We give new proofs of both incompleteness theorems. We do not use the diagonalization lemma, but work with some quickly growing functions instead.

We present an axiomatic framework for nonstandard analysis—the Nonstandard Class Theory (NCT) which extends von Neumann–Gödel–Bernays Set Theory (NBG) by adding a unary predicate symbol St to the language of NBG (St(X) means that the class X is standard) and axioms—related to it—analogs of Nelson's idealization, standardization and transfer principles. Those principles are formulated as axioms, rather than axiom schemes, so that NCT is finitely axiomatizable. NCT can be considered as a theory of definable classes of Bounded Set Theory by V. Kanovei and M. Reeken. In many aspects NCT resembles the Alternative Set Theory by P. Vopenka. For example there exist semisets (proper subclasses of sets) in NCT and it can be proved that a set has a standard finite cardinality iff it does not contain any proper subsemiset. Semisets can be considered as external classes in NCT. Thus the saturation principle can be formalized in NCT.

Let M be an o-minimal expansion of an ordered field. Let φ be a formula in the language of ordered domains. In this note we establish some topological properties which are transferred from φM to φR and vice versa. Then, we apply these transfer results to give a new proof of a result of M. Edmundo—based on the work of A. Strzebonski—showing the existence of torsion points in any definably compact group defined in an o-minimal expansion of an ordered field.

When equational logic for partial functions is interpreted using Kleene equality as the predicate, the relation of logical consequence may be said to express what identities of partial functions follow from a given set of identities. In the analogous situation for total functions, there is a complete set of inference rules consisting of reflexivity, symmetry, transitivity, replacement, and substitution; in the case of partial functions, unrestricted substitution fails to be a valid inference rule, and there remains the question of how to obtain a complete set of rules. The first part of the present paper shows that completeness cannot be obtained by a mere restriction of the substitution rule, for a counterexample shows that even a rule allowing substitution in all consequentially valid instances fails, in conjunction with the other four rules, to yield a complete set of rules.

The second part of the paper defines a combined rule of transitivity-substitution which, in conjunction with reflexivity, symmetry, replacement, and substitution only of variables, yields a complete set of rules. The new rule is first stated in a form that allows an unbounded number of premises, and then is altered to a three-premise form. In both forms, the rule suffers from the shortcoming that in its formulation an auxiliary notion of conditional existence is involved, which is given by a recursive syntactic definition. As a result, the set of instantiations of the rule is recursively enumerable, but not (apparently) recursive (assuming a recursive set of premises).

We consider successor-invariant first-order logic (FO + succ)inv, consisting of sentences Φ involving an “auxiliary” binary relation S such that (, S1) ⊨ Φ ⇔ (, S2) ⊨ Φ for all finite structures and successor relations S1, S2 on . A successor-invariant sentence Φ has a well-defined semantics on finite structures with no given successor relation: one simply evaluates Φ on (, S) for an arbitrary choice of successor relation S. In this article, we prove that (FO + succ)inv is more expressive on finite structures than first-order logic without a successor relation. This extends similar results for order-invariant logic [8] and epsilon-invariant logic [10].

Bei dem Bestreben, die Mathematik zu logisieren, erschienen die von Russell u.a. entdeckten Paradoxieen als das größte Hindernis. Zu ihrer Überwindung wurde die Typentheorie von Russell aufgestellt, die aber auch in ihrer gemilderten Form die Mathematiker nicht befriedigt. Ich bin diesen Schwierigkeiten nie begegnet, und zwar deshalb nicht, weil logisieren für mich immer bedeutet hat: in Schröderschen Relativkalkul einkleiden.

Ich bedaure es aus mehr als einem Grunde schwer, daß man von dem eleganten Peirce-Schröderschen Kalkul abgewichen ist und die Peano-Russellschen Zeichen benutzt, in denen aus bestimmten (m.A.n. nicht stichhaltigen) Gründen die sonst selbstverständliche Harmonie und Schönheit der Mathematik preisgegeben wurde, wodurch die Forschung ziemlich einseitig in eine bestimmte Richtung gedrängt wurde (in der freilich Hochbedeutendes geleistet wurde) während beim Peirce-Schröderschen Kalkul auf Schönheit besonderer Wert gelegt und mit wunderbarer Instinktsicherheit gerade das mathematisch Bedeutsame und Fruchtbare getroffen wurde. Ich bin der Überzeugung, daß in Wissenschaft und Technik das Zweckmäßige immer auch zugleich das Schöne ist. Mit Russells Zeichen hätte ich manches nicht entdeckt, was ich gefunden habe, und besäße jedenfalls nicht meine grosse Kalkulfreudigkeit. Ungünstige Zeichen lähmen die Produktivität. Der heutige Logikkalkul entbehrt daher jeder Eleganz und Geschmeidigkeit, was ganz und gar nicht in der Natur der Sache liegt. Meine Bemühungen, bestimmte Teile des Kalkuls flüssiger, geschmeidiger zu handhaben, sind unbeachtet geblieben.

In [4], Metakides and Nerode define a recursively presented vector space V∞. over a (finite or infinite) recursive field F to consist of a recursive subset U of the natural numbers N and operations of vector addition and scalar multiplication which are partial recursive and under which V∞ becomes a vector space. Throughout this paper, we will identify V∞ with N, say via some fixed Gödel numbering, and assume V∞ is infinite dimensional and has a dependence algorithm, i.e., there is a uniform effective procedure which determines whether any given n-tuple v0, …, vn−1 from V∞ is linearly dependent. Given a subspace W of V∞, we write dim(W) for the dimension of W. Given subspaces V and W of V∞, V + W will denote the weak sum of V and W and if V ∩ W = {0) (where 0 is the zero vector of V∞), we write V ⊕ W instead of V + W. If W ⊇ V, we write W mod V for the quotient space. An independent set A ⊆ V∞ is extendible if there is a r.e. independent set I ⊇ A such that I − A is infinite and A is nonextendible if it is not the case that A is extendible.

Each of the various “large cardinal” axioms currently studied in set theory owes its inspiration to concrete phenomena in various fields. For example, the statement of the well-known compactness theorem for first-order logic can be generalized in various ways to infinitary languages to yield definitions of compact cardinals, and the reflection principles provable in ZF, when modified in the appropriate way, yields indescribable cardinals.

In this paper we concern ourselves with two kinds of large cardinals which are probably the two best known of those whose origins lie in model theory. They are the Rowbottom cardinals and the Jonsson cardinals.

Let us be more specific. A cardinal κ is said to be a Jonsson cardinal if every structure of cardinality κ has a proper elementary substructure of cardinality κ. (It is routine to see that only uncountable cardinals can be Jonsson. Erdös and Hajnal have shown [2] that for n < ω no ℵn is Jonsson. (In fact, they showed that if κ is not Jonsson then neither is the successor cardinal of κ and that, assuming GCH, no successor cardinal can be Jonsson.) Keisler and Rowbottom first showed that the existence of a Jonsson cardinal contradicts V = L.) The definition of a Rowbottom cardinal is only slightly more intricate. We assume for the moment that our similarity type has a designated one-place relation.

By concepts will be meant propositions (or truth-values), attributes (or classes), and relations of all degrees. The degree of a concept will be said to be 0, 1, or n (> 1), and the concept will be said to be medadic, monadic, or n-adic, according as the concept is a proposition, an attribute, or an n-adic relation. The common procedure in systematizing logistic is to treat these successive degrees as ultimately separate categories. The partition is not rested upon properties of the thus classified elements within the formal system, but is imposed rather at the metamathematical level, through stipulations as to what combinations of signs are to be accorded or denied meaning. Each function of the formal system is restricted, thus metamathematically, to one degree for its values and to one for each of its arguments. The theory of types imports a further scheme of infinite partition, imposed by metamathematical stipulations as to the relative types of admissible arguments of the several functions and stipulations as to the types of the values of the functions relative to the types of the arguments.

The elaborateness of the metamathematical grillwork which thus underlies formal logistic accounts in part for the tendency of those interested in logistic less for the matters treated than for the structures exemplified to limit their attention to the propositional calculus and the Boolean calculus of attributes (or classes), which, taken separately, are independent of the partitioning. A second reason for the algebraic appeal of these departments is their freedom from bound (apparent) variables: for use of bound variables fuses systematic considerations with notational or metamathematical ones in a way which resists ordinary formulation in terms of fixed functions and their arguments. Freedom from bound variables may be regarded, indeed, as the feature distinguishing algebra from analysis.