We obtain a p-adic semilinear cell decomposition theorem using methods developed by Denef in [Journal für die Reine und Angewandte Mathematik, vol. 369 (1986), pp. 154–166]. We also prove that any set definable with quantifiers in (0,1, +, —, λq, Pn){n∈ℕ,q∈ℚp} may be defined without quantifiers, where λq is scalar multiplication by q and Pn is a unary predicate which denotes the nonzero nth powers in the p-adic field ℚp. Such a set is called a p-adic semilinear set in this paper. Some further considerations are discussed in the last section.

Martin [10] has computed the degrees of several classes of ω-r.e. sets. Lachlan [3] and Shoenfield [14] have obtained some additional results. For most of the examples, a class of r.e. sets is given by a property that is first-order definable over the lattice of ω-r.e. sets. Then the set of degrees of sets in this class is computed. The only sets of nonzero degrees which arise from the known examples are the following: ϕ, {a∣a is ω-r.e. and a ≠ 0}, {a∣a is ω-r.e. and a′ = 0″}, and {a∣a is ω-r.e. and a″ > 0″} (see [14]).

There have been some results in this direction for α an arbitrary admissible ordinal. Sacks [13] has shown that every nonzero α-r.e. α-degree contains a regular α-r.e. set. Thus regularity does not separate the α-r.e. α-degrees. Simpson [18] has several theorems which give information about the kinds of α-r.e. sets a given α-degree can contain. The classes of α-r.e. sets considered do separate the α-r.e. α-degrees into two nonempty pieces for some α's, but they are not necessarily given by properties which are definable over the lattice of α-r.e. sets. Using some definability results of Lerman [6], we shall make some comments about the definability of these classes of sets.

Lewis, in the presentation of his calculus of strict implication, contends that this calculus accords with the usual meaning of “implies” such that “p strictly implies q” is synonymous with “q is deducible from p” (pp. 126–127, 235–262). It is the purpose of this paper to present, in 1, certain considerations in the light of which this statement does not hold, and in 2, a new implicative relation upon which a calculus of propositions can be based such that it will accord with the relation of deducibility and from which it is possible to derive the calculi of strict and material implications.

1. Strict implication regarded as synonymous with deducibility. In the presentation of his calculus of strict implication Lewis observes that despite inclusion of both intensional and extensional propositions in this calculus, the meaning of its elements, p, q, r, etc., “remain fixed, whether it is their extensional or their intensional relations which are in question” (p. 120). But if the meaning or content of the elements of this calculus is irrelevant to the logical truth which it contains, then, as Weiss has already remarked, the propositions of this calculus “are really extensionally treated, involving multiple values,” e.g., possibility, on the analogy of truth and falsity. The importance of this fact is that, in consequence, the relation of strict implication is subject to certain paradoxes, such as (19.74) “a proposition which is impossible strictly implies any proposition” or (19.75) “a proposition which is necessarily true is strictly implied by any proposition” (p. 174) or (19.84) “any two necessarily true propositions are strictly equivalent” (p. 176).

Following [1] we write {n} for the nth recursively enumerable (re) set; that is, {n} = {x|VyT(n, x, y)}. By a “pair (T, α)” we mean a consistent re extension T of Peano arithmetic P and an RE-formula α which numerates the non-logical axioms of T in P [4]. Given a pair (T, α) and a particular formula which binumerates the Kleene T predicate in P, there can be defined a primitive recursive function Nα such that and which has the additional property that {Nα(Nα(n))} = ø for all n.

An operator Γ mapping P(ω) to itself is inductive if Γ(A) ⊇ A for all A. For such an inductive operator Γ we define {Γα : α ∈ ORD} by letting Γ = ⌀, Γα + 1 = Γ(Γα ) for all α, and Γβ = ⋃{Γα : α < β} for limit ordinals β. The closure ordinal ∣Γ∣ of Γ is the least ordinal α such that Γα+1 = Γα and the closure is Γ∣Γ∣.

Let be a class of operators over the natural numbers. The closure ordinal ∣∣ of is the supremum of {∣Γ∣: Γ is an inductive operator and }. The closure algebra generated by is {A ⊆ ω: A is 1-1 reducible to for some inductive operator }. The inductive algebra generated by is {Γα : Γ is an inductive operator in and α < ∣Γ∣}.

For A ∈ P(ω), is the supremum of the ordinals of well-orderings recursive in A. For , let be the supremum of . For example, it is well known that ω() = ω(∆1 0 = ω 1, ω(Π1 1) = ω 1 and ω(Δn 1) = δn 1 for n > 1 (the latter by definition).

We say that a real X is n-generic relative to a perfect tree T if X is a path through T and for all sets S, there exists a number k such that either X∣k ϵ S or for all a σ ϵ T extending X∣k we have a σ ∉ S. A real X is n-generic relative to some perfect tree if there exists such a T. We first show that for every number n all but countably many reals are n-generic relative to some perfect tree. Second, we show that proving this statement requires ZFC− + “∃ infinitely many iterates of the power set of ω”. Third, we prove that every finite iterate of the hyperjump, , is not 2-generic relative to any perfect tree and for every ordinal α below the least λ such that supβ<λ (βth admissible) = λ, the iterated hyperjump is not 5-generic relative to any perfect tree. Finally, we demonstrate some necessary conditions for reals to be 1-generic relative to some perfect tree.

Although Church and Turing presented their path-breaking undecidability results immediately after their explication of effective decidability in 1936, it has been generally felt that these results do not have any direct bearing on ordinary mathematics but only contribute to logic, metamathematics and the theory of computability. Therefore it was such a celebrated achievement when Yuri Matiyasevich in 1970 demonstrated that the problem of the solvability of Diophantine equations is undecidable. His work was building essentially on the earlier work by Julia Robinson, Martin Davis and Hilary Putnam (1961), who had showed that the problem of solvability of exponential Diophantine equations is undecidable. One should note, however, that although it was only Matiyasevich's result which finally solved Hilbert's tenth problem, already the earlier result had provided a perfectly natural problem of ordinary number theory which is undecidable.

Nevertheless, both the set of Diophantine equations with solutions and the set of exponential Diophantine equations with solutions are still semi-decidable, that is, recursively enumerable (i.e., Σ10); if an equation in fact has a solution, this can be eventually verified. More generally, they are — as are their complements, the sets of equations with no solutions, which are Π10, — also Trial and Error decidable (Putnam [1965]), or decidable in the limit (Shoenfield [1959]), for every Δ20 set is (and conversely). This last-mentioned natural “liberalized” notion of decidability has begun more recently to play an essential role e.g., in so-called Formal Learning Theory (see e.g., Osherson, Stob, and Weinstein [1986], Kelly [1996]).

We show that for every enumeration degree a < 0′e there exists an e-degree c such that a ≤ c < 0′e, and all degrees b, with c ≤ b < 0′e, are properly Σ20.

D'après Lascar et Poizat [10], la déviation pour une théorie stable est associée à un préordre partiel sur l'ensemble des types. L'ordre induit a été nommé par Poizat ordre fondamental. Il mesure combien un type est loin d'être réalisé et il donne un certain nombre d'informations sur la théorie. Une question naturelle, est de décrire completément tous les ordres fondamentaux [13]. Il semble que cela soit difficile. Un problème moins ambitieux est de trouver des conditions pour qu'un ordre soit l'ordre fondamental d'une théorie, ou bien de trouver des exemples.

Le but de cet article est de trouver de nouveaux exemples d'ordres fondamentaux. Nous nous concentrons principalement sur les théories stables et 1-basées car, comme nous allons voir dans la Section 2, avec cette hypothèse, il y a une représentation simple de l'ordre fondamental grâce aux ensembles algébriquement clos d'éléments des modèles de la thé;orie considégrée. Dans la Section 3, nous généralisons une idée de Baldwin et Berman [2] pour construire de “nouveaux” exemples d'ordres fondamentaux. En combinant cette construction avec les résultats de la Section 2, on caractérise de manière complete les ordres fondamentaux de theories triviales et 1-basées: les blocs des ordres fondamentaux d'une théorie triviale et 1-basée sont les inverses des posets de la forme I(L)/G où L est un treillis distributif borné et G un groupe compact d'automorphismes localement fini de L. De plus, tout ordre partiel de cette forme est l'ordre fondamental d'une théorie triviale et 1-basá. En particulier, l'ordre fondamental n'est pas toujours un treillis.

By a classical theorem of Harvey Friedman (1973), every countable nonstandard model $\mathcal {M}$ of a sufficiently strong fragment of ZF has a proper rank-initial self-embedding j, i.e., j is a self-embedding of $\mathcal {M}$ such that $j[\mathcal {M}]\subsetneq \mathcal {M}$ , and the ordinal rank of each member of $j[\mathcal {M}]$ is less than the ordinal rank of each element of $\mathcal {M}\setminus j[\mathcal {M}]$ . Here, we investigate the larger family of proper initial-embeddings j of models $\mathcal {M}$ of fragments of set theory, where the image of j is a transitive submodel of $\mathcal {M}$ . Our results include the following three theorems. In what follows, $\mathrm {ZF}^-$ is $\mathrm {ZF}$ without the power set axiom; $\mathrm {WO}$ is the axiom stating that every set can be well-ordered; $\mathrm {WF}(\mathcal {M})$ is the well-founded part of $\mathcal {M}$ ; and $\Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ is the full scheme of dependent choice of length $\alpha $ .

Theorem A.

There is an $\omega $ -standard countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^-+\mathrm {WO}$ that carries no initial self-embedding $j:\mathcal {M} \longrightarrow \mathcal {M}$ other than the identity embedding.

Theorem B.

Every countable $\omega $ -nonstandard model $\mathcal {M}$ of $\ \mathrm {ZF}$ is isomorphic to a transitive submodel of the hereditarily countable sets of its own constructible universe $L^{\mathcal {M}}$ .

Theorem C.

The following three conditions are equivalent for a countable nonstandard model $\mathcal {M}$ of $\mathrm {ZF}^{-}+\mathrm {WO}+\forall \alpha \ \Pi ^1_\infty \text{-}\mathrm {DC}_\alpha $ .

1. (I) There is a cardinal in $\mathcal {M}$ that is a strict upper bound for the cardinality of each member of $\mathrm {WF}(\mathcal {M})$ .

2. (II) $\mathrm {WF}(\mathcal {M})$ satisfies the powerset axiom.

3. (III) For all $n \in \omega $ and for all $b \in M$ , there exists a proper initial self-embedding $j: \mathcal {M} \longrightarrow \mathcal {M}$ such that $b \in \mathrm {rng}(j)$ and $j[\mathcal {M}] \prec _n \mathcal {M}$ .

We study a strengthening of the notion of a perfectly meager set. We say that a subset A of a perfect Polish space X is countably perfectly meager in X, if for every sequence of perfect subsets $\{P_n: n \in \mathbb N\}$ of X, there exists an $F_\sigma $ -set F in X such that $A \subseteq F$ and $F\cap P_n$ is meager in $P_n$ for each n. We give various characterizations and examples of countably perfectly meager sets. We prove that not every universally meager set is countably perfectly meager correcting an earlier result of Bartoszyński.

We prove that if ℵα is uncountable and regular, then the Beth-closure of ℒωω(Qα) is not a sublogic of ℒαω(Qn), where Qn is the class of all n-ary generalized quantifiers. In particular, B(ℒωω(Qα)) is not a sublogic of any finitely generated logic; i.e., there does not exist a finite set Q of Lindström quantifiers such that B(ℒωω(Qα)) ≤ ℒωω(Q).

In this paper we discuss an interpretation of intuitionistic type theory in many-sorted arithmetic with so-called conditional application. Via the formulas-as-types correspondence the arithmetical system in turn can be embedded in ML, resulting in a characterization of strong Σ-elimination by an axiom of conditional choice.