We show that there is a first order sentence φ(x: a, b, l) such that for every computable partial order and -degree u > 0e, there are -enumeration degrees a ≤ u, b, and l such that . Allowing to be a suitably defined standard model of arithmetic gives a parameterized interpretation of true arithmetic in the -enumeration degrees. Finally we show that there is a first order sentence that correctly identifies a subset of the standard models, which gives a parameterless interpretation of true arithmetic in the -enumeration degrees.

We show that it is relatively consistent with ZFC to have PCF structures of height δ, for all ordinals δ < ω3.

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of . Corollaries include the decidability of the two quantifier theory of , and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of ω1 ck . Somewhat surprisingly, the set theoretic analogof this forcing does not preserve ω1. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of .

A meadow is a commutative ring with an inverse operator satisfying 0−1 = 0. We determine the initial algebra of the meadows of characteristic 0 and prove a normal form theorem for it. As an immediate consequence we obtain the decidability of the closed term problem for meadows and the computability of their initial object.

We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continuum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.

We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing (support strictly increasing) limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing (support strictly increasing) limitwise monotonic sets on certain domains.

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.

We show that for an uncountable κ in a suitable Cohen real model for any family {Av}v<κ of sets of reals there is a σ-homomorphism h from the σ-algebra generated by Borel sets and the sets Av, into the algebra of Baire subsets of 2κ modulo meager sets such that for all Borel B,

The proof is uniform, works also for random reals and the Lebesgue measure, and in this way generalizes previous results of Carlson and Solovay for the Lebesgue measure and of Kamburelis and Zakrzewski for the Baire property.

Building on Hrushovski's work in [5], we study definable groupoids in stable theories and their relationship with 3-uniqueness and finite internal covers. We introduce the notion of retractability of a definable groupoid (which is slightly stronger than Hrushovski's notion of eliminability), give some criteria for when groupoids are retractable, and show how retractability relates to both 3-uniqueness and the splitness of finite internal covers. One application we give is a new direct method of constructing non-eliminable groupoids from witnesses to the failure of 3-uniqueness. Another application is a proof that any finite internal cover of a stable theory with a centerless liaison groupoid is almost split.

Computability logic (CL) is a recently launched program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Formulas in it represent computational problems, “truth” means existence of an algorithmic solution, and proofs encode such solutions. Within the line of research devoted to finding axiomatizations for ever more expressive fragments of CL, the present paper introduces a new deductive system CL12 and proves its soundness and completeness with respect to the semantics of CL. Conservatively extending classical predicate calculus and offering considerable additional expressive and deductive power, CL12 presents a reasonable, computationally meaningful, constructive alternative to classical logic as a basis for applied theories. To obtain a model example of such theories, this paper rebuilds the traditional, classical-logicbased Peano arithmetic into a computability-logic-based counterpart. Among the purposes of the present contribution is to provide a starting point for what, as the author wishes to hope, might become a new line of research with a potential of interesting findings—an exploration of the presumably quite unusual metatheory of CL-based arithmetic and other CL-based applied systems.

We construct a model of ZFC satisfying the Dual Borel Conjecture in which there is a set of size ℵ1 that does not have measure zero.

This paper aims to give a correct proof of Tait's conservative extension theorem. Tait's own proof is flawed in the sense that there are some invalid steps in his argument, and there is a counterexample to the main theorem from which the conservative extension theorem is supposed to follow. However, an analysis of Tait's basic idea suggests a correct proof of the conservative extension theorem and a corrected version of the main theorem.

An open U ⊆ ℝ is produced such that (ℝ, +, ·, U) defines a Borel isomorph of (ℝ, +, ·, ℕ) but does not define ℕ. It follows that (ℝ, +, ·, U) defines sets in every level of the projective hierarchy but does not define all projective sets. This result is elaborated in various ways that involve geometric measure theory and working over o-minimal expansions of (ℝ, +, ·). In particular, there is a Cantor set E ⊆ ℝ such that (ℝ, +, ·, ℕ) defines a Borel isomorph of (ℝ, +, ·, ℕ) and, for every exponentially bounded o-minimal expansion of (ℝ, +, ·), every subset of ℝ definable in (, E) either has interior or is Hausdorff null.

If one wants to compute with infinite objects like real numbers or data streams, continuity is a necessary requirement: better and better (finite) approximations of the input are transformed into better and better (finite) approximations of the output. In case the objects are constructively generated, they can be represented by a finite description of the generating procedure. By effectively transforming such descriptions for the generation of the input (respectively, their codes) into (the code of) a description for the generation of the output another type of computable operation is obtained. Such operations are also called effective. The relationship of both classes of operations has always been a question of great interest.

In this paper the setting is extended to the case of multifunctions. Various ways of coding (indexing) sets are discussed and their relationship is investigated. Moreover, effective versions of several continuity notions for multifunctions are introduced. For each of these notions an indexing system for sets is exhibited so that the multifunctions that are effective with respect to this indexing system are exactly the multifunction which are effectively continuous with respect to the continuity notion under consideration. Mostly, in addition to being effective the multifunctions need also possess certain witnessing functions. Important special cases are discussed where such witnessing functions always exist.

This paper provides a Bishop-style constructive analysis of the contrapositive of the statement that a continuous homomorphism of R onto a compact abelian group is periodic. It is shown that, subject to a weak locatedness hypothesis, if G is a complete (metric) abelian group that is the range of a continuous isomorphism from R, then G is noncompact. A special case occurs when G satisfies a certain local path-connectedness condition at 0. A number of results about one-one and injective mappings are proved en route to the main theorem. A Brouwerian example shows that some of our results are the best possible in a constructive framework.

Continuous first-order logic has found interest among model theorists who wish to extend the classical analysis of “algebraic” structures (such as fields, group, and graphs) to various natural classes of complete metric structures (such as probability algebras, Hilbert spaces, and Banach spaces). With research in continuous first-order logic preoccupied with studying the model theory of this framework, we find a natural question calls for attention. Is there an interesting set of axioms yielding a completeness result?

The primary purpose of this article is to show that a certain, interesting set of axioms does indeed yield a completeness result for continuous first-order logic. In particular, we show that in continuous first-order logic a set of formulae is (completely) satisfiable if (and only if) it is consistent. From this result it follows that continuous first-order logic also satisfies an approximated form of strong completeness, whereby Σ⊧φ (if and) only if Σ⊢φ ∸2−n for all n < ω. This approximated form of strong completeness asserts that if Σ⊧φ, then proofs from Σ, being finite, can provide arbitrarily better approximations of the truth of φ.

Additionally, we consider a different kind of question traditionally arising in model theory—that of decidability. When is the set of all consequences of a theory (in a countable, recursive language) recursive? Say that a complete theory T is decidable if for every sentence φ, the value φ T is a recursive real, and moreover, uniformly computable from φ. If T is incomplete, we say it is decidable if for every sentence φ the real number φ T o is uniformly recursive from φ, where φ T o is the maximal value of φ consistent with T. As in classical first-order logic, it follows from the completeness theorem of continuous first-order logic that if a complete theory admits a recursive (or even recursively enumerable) axiomatization then it is decidable.

It is shown that under GCH every poset preserves its cofinality in any cofinality preserving extension. On the other hand, starting with ω measurable cardinals, a model with a partial ordered set which can change its cofinality in a cofinality preserving extension is constructed.

An instance of Stratified Comprehension

is called strictly impredicative iff, under minimal stratification, the type of x is 0. Using the technology of forcing, we prove that the fragment of NF based on strictly impredicative Stratified Comprehension is consistent. A crucial part in this proof, namely showing genericity of a certain symmetric filter, is due to Robert Solovay.

As a bonus, our interpretation also satisfies some instances of Stratified Comprehension which are not strictly impredicative. For example, it verifies existence of Frege natural numbers.

Apparently, this is a new subsystem of NF shown to be consistent. The consistency question for the whole theory NF remains open (since 1937).

We show, relative to the base theory RCA0: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA0. Ramsey's Theorem for singletons for the complete binary tree is stronger than . hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers to questions, of Chubb, Hirst, and McNicholl [3].

We study the connection between Schnorr triviality and genericity. We show that while no 2-generic is Turing equivalent to a Schnorr trivial and no 1-generic is tt-equivalent to a Schnorr trivial, there is a 1-generic that is Turing equivalent to a Schnorr trivial. However, every such 1-generic must be high. As a corollary, we prove that not all K-trivials are Schnorr trivial. We also use these techniques to extend a previous result and show that the bases of cones of Schnorr trivial Turing degrees are precisely those whose jumps are at least 0″.