Recall that a group G has finitely satisfiable generics (fsg) or definable f-generics (dfg) if there is a global type p on G and a small model $M_0$ such that every left translate of p is finitely satisfiable in $M_0$ or definable over $M_0$, respectively. We show that any abelian group definable in a p-adically closed field is an extension of a definably compact fsg definable group by a dfg definable group. We discuss an approach which might prove a similar statement for interpretable abelian groups. In the case where G is an abelian group definable in the standard model $\mathbb {Q}_p$, we show that $G^0 = G^{00}$, and that G is an open subgroup of an algebraic group, up to finite factors. This latter result can be seen as a rough classification of abelian definable groups in $\mathbb {Q}_p$.

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees.

In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).

A distinctive feature of modern mathematics is the interaction between its various branches and the blurring of the boundaries between different areas. This is strikingly illustrated in the work of Alfred Tarski. He was a logician first and an algebraist second. His contributions to algebra can be divided into three (ill-defined and overlapping) categories, general algebra, the study of various algebraic structures arising from problems outside algebra, mostly in logic and set theory, and the use of concepts and techniques from logic in the study of algebraic structures. Even more roughly, these three categories could be labeled as pure algebra, applications of algebra to logic, and applications of logic to algebra.

Before Tarski came to the United States in 1939, he had written a series of papers on both the axiomatic and the structural aspects of Boolean algebras, and his inclination to algebraize mathematical problems is well illustrated by his paper [38g], Algebraische Fassung des Massproblems. Many of his later investigations of various types of algebraic structures are inspired by work done in this earlier period. However, beginning around 1940 there is a much greater emphasis on the study of algebra in its various aspects.

The paper [41], On the calculus of relations, is a landmark event in this respect. The object here was to find an axiomatic basis for the arithmetic of binary relations. The axioms that he chose are simple and natural (see Monk [1986]).

Given a finite lexicon L of relational symbols and equality, one may view the collection of all L-structures on the set of natural numbers ω as a space in several different ways. We consider it as: (i) the space of outcomes of certain infinite two-person games; (ii) a compact metric space; and (iii) a probability measure space. For each of these viewpoints, we can give a notion of relative ubiquity, or largeness, for invariant sets of structures on ω. For example, in every sense of relative ubiquity considered here, the set of dense linear orderings on ω is ubiquitous in the set of linear orderings on ω.

Mr. L. J. Cohen's interesting example of a logical truth of indirect discourse appears to be capable of a simple formalisation and proof in a variant of first order predicate calculus. His example has the form:

If A says that anything which B says is false, and B says that something which A says is true, then something which A says is false and something which B says is true.

Let ‘A says x’ be formalised by ‘A(x)’ and let assertions of truth and falsehood be formalised as in the following table.

We treat both variables x and predicates A (x) as sentences and add to the familiar axioms and inference rules of predicate logic a rule permitting the inference of A(p) from (x)A(x), where p is a closed sentence.

We have to prove that from

In the fourth edition of Hilbert-Ackermann's Grundzüge der Theoretischen Logik (Springer-Verlag: Berlin-Göttingen-Heidelberg 1959) the following assertion is “proved” (p. 131):

Ein Ausdruck, der keine freien Individuenvariablen enthält, ist dann und nur dann allgemeingültig, wenn allgemeingültig ist. Die Ausdrücke, die die Identität enthalten, sind dabei eingeschlossen.

As a counter example one can cite: ∃x(¬∃xFx ∨ Fx), which is universally valid yet the generalized form: ∀x(¬∃xFx ∨ Fx) is not (e.g. let the domain of individuals be the natural numbers and let ‘Fx’ be ‘x is factorable’).

It may be of interest to see where the alleged proof went astray. It is argued (correctly) that any expression can only be derived by the given rules from a formula , or from this formula with any other variable in place of y. Moreover (still correctly) any upper formula of such a formula is of the form (“Upper formula” in the transitive sense of an upper formula of an upper formula being an upper formula). But then it is stated (incorrectly) that if is an upper formula of , then is an upper formula of . To show that this is incorrect we here append a proof of the universally valid formula mentioned above:

Nielsen [7] has proved that every subgroup of a free group of finite rank is free. The theorem was later strengthened by Schreier [8] by eliminating the finiteness restriction on the rank. Several proofs of this theorem (known as the Nielsen-Schreier theorem, henceforth denoted by NS) have appeared since Schreier's 1927 paper (see [1] and [2]). All proofs of NS use the axiom of choice (AC) and it is natural to ask whether NS is equivalent to AC. Läuchli has given a partial answer to this question by proving [6] that the negation of NS is consistent with ZFA (Zermelo-Fraenkel set theory weakened to permit the existence of atoms). By the Jech-Sochor embedding theorem (see [3] and [4]) ZFA can be replaced by ZF. Some form of AC, therefore, is needed to prove NS. The main purpose of this paper is to give a further answer to this question.

In §2 we prove that NS implies ACffin (the axiom of choice for sets of finite sets). In §3 we show that a strengthened version of NS implies AC and in §4 we give a partial list of open problems.

Let y be a set; ∣y∣ denotes the cardinal number of y and (y) is the power set of y. If p is a permutation of y and t ∈ y, the p-orbit of t is the set {pn(t): n is an integer}. If

we call p a cyclic permutation of y. If f is a function with domain y and x ⊆ y, f″x denotes the set {f(t):t ∈ x}. If A is a subset of a group (G, °) (sometimes (G, °) will be denoted by G) then A−1= {x−1:x ∈ A} and [A] denotes the subgroup of G generated by A.

The theory of large cardinals in the absence of the axiom of choice (AC) has been examined extensively by set theorists. A particular motivation has been the study of large cardinals and their interrelationships with the axiom of determinacy (AD). Many important and beautiful theorems have been proven in this area, especially by Woodin, who has shown how to obtain, from hypermeasurability, models for the theories “ZF + DC + ∀α < ℵ1(ℵ1 → (ℵ1)α)” and . Thus, consequences of AD whose consistency strength appeared to be beyond that of the more standard large cardinal hypotheses were shown to have suprisingly weak consistency strength.

In this paper, we continue the study of large cardinals in the absence of AC and their interrelationships with AD by examining what large cardinal structures are possible on cardinals below ℵω in the absence of AC. Specifically, we prove the following theorems.

Theorem 1. Con(ZFC + κ1 < κ2are supercompact cardinals) ⇒ Con(ZF + DC + The club filter on ℵ1is a normal measure + ℵ1and ℵ2are supercompact cardinals).

Theorem 2. Con(ZF + AD) ⇒ Con(ZF + ℵ1, ℵ2and ℵ3are measurable cardinals which carry normal measures + μωis not a measure on any of these cardinals).

We study the effects of Vopěnka's principle on properties of model theoretic logics. We show that Vopěnka's principle is equivalent to the assumption that every finitely generated logic has a compact cardinal. We show also that it is equivalent to the assumption that every such logic has a global Hanf number.

Many phrases have been used to express what are sometimes called anti-realist conceptions of truth: ‘verifiability’, ‘knowability’, ‘rational acceptability’, ‘warranted assertability’. In spite of their obvious differences, all four of these phrases have a common form; each is a cognitive attitude modified by ‘-ability’. They speak of the possibility of verification, knowledge, rational acceptance or warranted assertion. Schematically, it seems to be claimed that it is true that A if and only if it is possible that it is E'd that A, where ‘E’ is to be replaced by some cognitive verb and ‘A’ by any indicative sentence of the class to which the anti-realist conception is being claimed to apply. Since truth is redundant as a sentential operator, this boils down to the following thesis, where ‘p’ is a propositional variable and ‘M’ expresses the appropriate kind of possibility:

(*) also formalizes views such as Putnam's: ‘To claim a statement is true is to claim it could be justified’ [11, p. 56]. It is no doubt a crude model for anti-realism, but one has to start somewhere; by seeing how and why more sophisticated versions of anti-realism differ from (*) one should be able to understand them better too. Moreover, if an anti-realist rejects the equation of truth with, say, warranted assertibility, arguing that truth is rather to be identified with the possibility of getting into a position in which one's warrant to assert somehow cannot be overturned, the form of (*) is preserved, for truth is still being identified with the possibility of something.

This paper proposes a generalization of several reducibilities in the sense of recursive function theory. For this purpose two structures are introduced as models of combinatory logic and reducibilities are defined in a rather natural way by means of the application operation in each model. The first model we consider is called the graph model and was introduced by Dana Scott in [11]. Reducibilities in this model are generalizations of enumeration and Turing reducibilities. The second model is called the hypergraph model and induces reducibilities which are generalizations of hyperenumeration and hyperarithmetical reducibilities.

The possibility of formulating reducibilities in this way is not new. For the graph model it is implicit in [7] and for the hypergraph model in [9]. On the other hand it is possible to look at the present method as a variant of the well-known technique of relativization in recursive function theory. We think that this does not exhaust the power of the method, which is conceptually elegant and provides a natural frame for the results of this paper.

In the first part of the paper we discuss the definition and general properties of the models. Then we introduce the reducibilities in the graph model and prove several theorems which are generalizations of properties already Known for enmeration and Turing reducibilities. Next we define reducibilities in the hypergraph model and try to extend the preceding results. For this purpose we prove two theorems showing significant relations between the operators in both models. In fact we prove that each operator in the hypergraph model can be simulated on a comeager set by an operator of the graph model.

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of ω-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton and a Büchi automaton such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(), L()); (2) There exists a model of ZFC in which the Wadge game W(L(), L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(), L()).

In 2007, Terence Tao wrote on his blog an essay about soft analysis, hard analysis and the finitization of soft analysis statements into hard analysis statements. One of his main examples was a quasi-finitization of the infinite pigeonhole principle IPP, arriving at the “finitary” infinite pigeonhole principle FIPP1. That turned out to not be the proper formulation and so we proposed an alternative version FIPP2. Tao himself formulated yet another version FIPP3 in a revised version of his essay.

We give a counterexample to FIPP1 and discuss for both of the versions FIPP2 and FIPP3 the faithfulness of their respective finitization of IPP by studying the equivalences IPP ↔ FIPP2 and IPP ↔ FIPP3 in the context of reverse mathematics ([9]). In the process of doing this we also introduce a continuous uniform boundedness principle CUB as a formalization of Tao's notion of a correspondence principle and study the strength of this principle and various restrictions thereof in terms of reverse mathematics, i.e., in terms of the “big five” subsystems of second order arithmetic.

In this paper we show that it is consistent with ZFC that the cardinality of every maximal cofinitary group of Sym(ω) is strictly greater than the cardinal numbers and .

The notion J is independent in (M, M0, N) was established by Shelah, for an AEC (abstract elementary class) which is stable in some cardinal λ and has a non-forking relation, satisfying the good λ-frame axioms and some additional hypotheses. Shelah uses independence to define dimension.

Here, we show the connection between the continuity property and dimension: if a non-forking satisfies natural conditions and the continuity property, then the dimension is well-behaved.

As a corollary, we weaken the stability hypothesis and two additional hypotheses, that appear in Shelah's theorem.

We consider IOpen, the subsystem of PA (Peano Arithmetic) with the induction scheme restricted to quantifier-free formulas.

We prove that each model of IOpen can be embedded in a model where the equation has a solution. The main lemma states that there is no polynomial f{x,y) with coefficients in a (nonstandard) DOR M such that ∣f(x,y) ∣ < 1 for every (x,y) Є C, where C is the curve defined on the real closure of M by C: x2 + y2 = a and a > 0 is a nonstandard element of M.

Introduction. In [Sh, Chapter IX], Shelah constructs a model of set theory in which Suslin's hypothesis is true, yet there is an Aronszajn tree which is not special. In his model, we have . He asks whether the same result could be obtained consistently with CH. In this paper, we answer his question in the affirmative.

Let us say that a tree T is S-st-special iff there is a function ƒ with dom(f) = {t ∈ T: rank(t) ∈ S} and for every t1 < t2 both in dom(t) we have f(t2) ≠ f(t1) < rank(t1). In Shelah's model, every tree is S-st-special for some fixed stationary costationary set S. Also, there is some tree T such that T is not S′-st-special whenever S′ – S is stationary. These properties, which are sufficient to ensure that Suslin's hypothesis holds and that T is not special, also hold in the model constructed in this paper. These properties also ensure that every Aronszajn tree has a stationary antichain (i.e., an antichain A such that {rank(t): t ∈ A} is stationary). Hence, it is natural to ask whether there is a model of Suslin's hypothesis in which some Aronszajn tree has no stationary antichain. We answer in the affirmative in [S].

The construction we use owes much to Shelah's approach to the theorem, due to Jensen (see [DJ]), that CH is consistent with Suslin's hypothesis. This is given in [Sh, Chapter V].

We study automorphism groups of randomizations of separable structures, with focus on the ℵ0-categorical case. We give a description of the automorphism group of the Borel randomization in terms of the group of the original structure. In the ℵ0-categorical context, this provides a new source of Roelcke precompact Polish groups, and we describe the associated Roelcke compactifications. This allows us also to recover and generalize preservation results of stable and NIP formulas previously established in the literature, via a Banach-theoretic translation. Finally, we study and classify the separable models of the theory of beautiful pairs of randomizations, showing in particular that this theory is never ℵ0-categorical (except in basic cases).

We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height O(n).