Let L = 〈<, +, hq, 1〉q∈ℚ where ℚ is the set of rational numbers and hq is a one-place function symbol corresponding to multiplication by q. Then the L-theory of Scott's model for intuitionistic analysis is decidable.

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.

Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.

We introduce and discuss a concept of approximation of a topological algebraic system A by finite algebraic systems from a given class . If A is discrete, this concept agrees with the familiar notion of a local embedding of A in a class of algebraic systems. One characterization of this concept states that A is locally embedded in iff it is a subsystem of an ultraproduct of systems from . In this paper we obtain a similar characterization of approximability of a locally compact system A by systems from using the language of nonstandard analysis.

In the signature of A we introduce positive bounded formulas and their approximations; these are similar to those introduced by Henson [14] for Banach space structures (see also [15, 16]). We prove that a positive bounded formula φ holds in A if and only if all precise enough approximations of φ hold in all precise enough approximations of A.

We also prove that a locally compact field cannot be approximated arbitrarily closely by finite (associative) rings (even if the rings are allowed to be non-commutative). Finite approximations of the field ℝ can be considered as possible computer systems for real arithmetic. Thus, our results show that there do not exist arbitrarily accurate computer arithmetics for the reals that are associative rings.

Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results.

We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree computable from a weakly 2-generic one. While there have been full approximation constructions of ${\rm{\Delta }}_3^0$ minimal degrees before, our proof is rather novel since it is a computable full approximation construction where both the generic and the minimal degrees are ${\rm{\Delta }}_3^0 - {\rm{\Delta }}_2^0$.

It is proved in $\mathsf {ZF}$ (without the axiom of choice) that, for all infinite sets M, there are no surjections from $\omega \times M$ onto $\operatorname {\mathrm {\mathscr {P}}}(M)$.

In this article, a notion of Schauder equivalence relation ℝℕ/L is introduced, where L is a linear subspace of ℝℕ and the unit vectors form a Schauder basis of L. The main theorem is to show that the following conditions are equivalent:

(1) the unit vector basis is boundedly complete;

(2) L is a Fσ in ℝℕ;

(3) ℝℕ/L is Borel reducible to ℓ∞.

We show that any Schauder equivalence relation generalized by a basis of ℓ2 is Borel bireducible to ℝℕ/ℓ2 itself, but it is not true for bases of c0 or ℓ1. Furthermore, among all Schauder equivalence relations generated by sequences in c0, we find the minimum and the maximum elements with respect to Borel reducibility.

We explore the structural properties of the inner model L(Vδ+1) under the assumption that δ is a singular limit of Berkeley cardinals each of which is itself limit of extendible cardinals, lifting some of the main results of the theory of the axiom I0 to the level of Berkeley cardinals, the strongest known large cardinal axioms. Berkeley cardinals have been recently introduced in [1] and contradict the Axiom of Choice.1 In fact, our background theory will be ZF.

In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as $\mathsf {P}\neq \mathsf {NP}$ [23–25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been proved in [20, 22].In this paper, we generalize and strengthen these results. Another question that we address concerns the dependence between these conjectures. We construct two oracles that enable us to answer questions about relativized separations asked in [19, 25] (i.e., for the pairs of conjectures mentioned in the questions, we construct oracles such that one conjecture from the pair is true in the relativized world and the other is false and vice versa). We also show several new connections between the studied conjectures. In particular, we show that the relation between the finite reflection principle and proof systems for existentially quantified Boolean formulas is similar to the one for finite consistency statements and proof systems for non-quantified propositional tautologies.

We introduce the notion of ${\cal C}$-system of filters, generalizing the standard definitions of both extenders and towers of normal ideals. This provides a framework to develop the theory of extenders and towers in a more general and concise way. In this framework we investigate the topic of definability of generic large cardinals properties.

Let $\mathcal {I}$ be an ideal on $\omega $ . For $f,\,g\in \omega ^{\omega }$ we write $f \leq _{\mathcal {I}} g$ if $f(n) \leq g(n)$ for all $n\in \omega \setminus A$ with some $A\in \mathcal {I}$ . Moreover, we denote $\mathcal {D}_{\mathcal {I}}=\{f\in \omega ^{\omega }: f^{-1}[\{n\}]\in \mathcal {I} \text { for every } n\in \omega \}$ (in particular, $\mathcal {D}_{\mathrm {Fin}}$ denotes the family of all finite-to-one functions).

We examine cardinal numbers $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))$ and $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathrm {Fin}}\times \mathcal {D}_{\mathrm {Fin}}))$ describing the smallest sizes of unbounded from below with respect to the order $\leq _{\mathcal {I}}$ sets in $\mathcal {D}_{\mathrm {Fin}}$ and $\mathcal {D}_{\mathcal {I}}$ , respectively. For a maximal ideal $\mathcal {I}$ , these cardinals were investigated by M. Canjar in connection with coinitial and cofinal subsets of the ultrapowers.

We show that $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathrm {Fin}} \times \mathcal {D}_{\mathrm {Fin}})) =\mathfrak {b}$ for all ideals $\mathcal {I}$ with the Baire property and that $\aleph _1 \leq \mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}})) \leq \mathfrak {b}$ for all coanalytic weak P-ideals (this class contains all $\bf {\Pi ^0_4}$ ideals). What is more, we give examples of Borel (even $\bf {\Sigma ^0_2}$ ) ideals $\mathcal {I}$ with $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))=\mathfrak {b}$ as well as with $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}})) =\aleph _1$ .

We also study cardinals $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {J}} \times \mathcal {D}_{\mathcal {K}}))$ describing the smallest sizes of sets in $\mathcal {D}_{\mathcal {K}}$ not bounded from below with respect to the preorder $\leq _{\mathcal {I}}$ by any member of $\mathcal {D}_{\mathcal {J}}\!$ . Our research is partially motivated by the study of ideal-QN-spaces: those cardinals describe the smallest size of a space which is not ideal-QN.

It is a classic result in modal logic, often referred to as Jónsson-Tarski duality, that the category of modal algebras is dually equivalent to the category of descriptive frames. The latter are Kripke frames equipped with a Stone topology such that the binary relation is continuous. This duality generalizes the celebrated Stone duality for boolean algebras. Our goal is to generalize descriptive frames so that the topology is an arbitrary compact Hausdorff topology. For this, instead of working with the boolean algebra of clopen subsets of a Stone space, we work with the ring of continuous real-valued functions on a compact Hausdorff space. The main novelty is to define a modal operator on such a ring utilizing a continuous relation on a compact Hausdorff space.

Our starting point is the well-known Gelfand duality between the category ${\sf KHaus}$ of compact Hausdorff spaces and the category $\boldsymbol {\mathit {uba}\ell }$ of uniformly complete bounded archimedean $\ell $ -algebras. We endow a bounded archimedean $\ell $ -algebra with a modal operator, which results in the category $\boldsymbol {\mathit {mba}\ell }$ of modal bounded archimedean $\ell $ -algebras. Our main result establishes a dual adjunction between $\boldsymbol {\mathit {mba}\ell }$ and the category ${\sf KHF}$ of what we call compact Hausdorff frames; that is, Kripke frames equipped with a compact Hausdorff topology such that the binary relation is continuous. This dual adjunction restricts to a dual equivalence between ${\sf KHF}$ and the reflective subcategory $\boldsymbol {\mathit {muba}\ell }$ of $\boldsymbol {\mathit {mba}\ell }$ consisting of uniformly complete objects of $\boldsymbol {\mathit {mba}\ell }$ . This generalizes both Gelfand duality and Jónsson-Tarski duality.

Quasiminimal pregeometry classes were introduced by [6] to isolate the model theoretical core of several interesting examples. He proves that a quasiminimal pregeometry class satisfying an additional axiom, called excellence, is categorical in all uncountable cardinalities. Recently, [2] showed that the excellence axiom follows from the rest of the axioms. In this paper we present a direct proof of the categoricity result without using excellence.

We prove first-order definability of the prime subring inside polynomial rings, whose coefficient rings are (commutative unital) reduced and indecomposable. This is achieved by means of a uniform formula in the language of rings with signature $(0,1,+,\cdot )$. In the characteristic zero case, the claim implies that the full theory is undecidable, for rings of the referred type. This extends a series of results by Raphael Robinson, holding for certain polynomial integral domains, to a more general class.

The Ladd-Franklin “antilogism” provides a very convenient procedure for testing syllogistic arguments, especially when they are expressed algebraically. It is well known, however, that the antilogism test indicates the invalidity of certain moods which the traditional logic regards as valid. These are the moods in which a particular conclusion is inferred from two universal premises. It is the aim of this paper to show that the antilogism can be generalized in such a way as to cover these moods, and also to be applicable to certain forms of “immediate inference” and “sorites,” as these designations have been traditionally employed.

We shall find that when generalized in this fashion there are two principal kinds of antilogisms: (1) those which include an inequation of the form ab≠0, and (2) those which include an inequation of the form a≠0.

Definition. An antilogism is a group of propositions so constructed that the contradictory of any one of them is implied by the logical product of the others.