We show that every reduct of a stable. CM-trivial theory of finite U-rank is CM-trivial.

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ2–theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ1–theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation.

We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.

The research presented in this paper was motivated by our aim to study a problem due to J. Bourgain [3]. The problem in question concerns the uniform boundedness of the classical separation rank of the elements of a separable compact set of the first Baire class. In the sequel we shall refer to these sets (separable or non-separable) as Rosenthal compacta and we shall denote by ∝(f) the separation rank of a real-valued function f in B1(X), with X a Polish space. Notice that in [3], Bourgain has provided a positive answer to this problem in the case of K satisfying with X a compact metric space. The key ingredient in Bourgain's approach is that whenever a sequence of continuous functions pointwise converges to a function f, then the possible discontinuities of the limit function reflect a local ℓ1-structure to the sequence (fn)n. More precisely the complexity of this ℓ1-structure increases as the complexity of the discontinuities of f does. This fruitful idea was extensively studied by several authors (c.f. [5], [7], [8]) and for an exposition of the related results we refer to [1]. It is worth mentioning that A.S. Kechris and A. Louveau have invented the rank rND(f) which permits the link between the c0-structure of a sequence (fn)n of uniformly bounded continuous functions and the discontinuities of its pointwise limit. Rosenthal's c0-theorem [11] and the c0-index theorem [2] are consequences of this interaction.

Passing to the case where either (fn)n are not continuous or X is a non-compact Polish space, this nice interaction is completely lost.

§1. Introduction. Our understanding of Nature comes in layers, so should the development of logic. Classic logic is an indispensable part of our knowledge, and its interactions with computer science have recently dramatically changed our life. A new layer of logic has been developing ever since the discovery of quantum mechanics. G. D. Birkhoff and von Neumann introduced quantum logic in a seminal paper in 1936 [1]. But the definition of quantum logic varies among authors (see [2]). How to capture the logic structure inherent in quantum mechanics is very interesting and challenging. Given the close connection between classical logic and theoretical computer science as exemplified by the coincidence of computable functions through Turing machines, recursive function theory, and λ-calculus, we are interested in how to gain some insights about quantum logic from quantum computing. In this note we make some observations about quantum logic as motivated by quantum computing (see [5]) and hope more people will explore this connection.

The quantum logic as envisioned by Birkhoff and von Neumann is based on the lattice of closed subspaces of a Hilbert space, usually an infinite dimensional one. The quantum logic of a fixed Hilbert space ℍ in this note is the variety of all the true equations with finitely many variables using the connectives meet, join and negation. Quantum computing is theoretically based on quantum systems with finite dimensional Hilbert spaces, especially the states space of a qubit ℂ2. (Actually the qubit is merely a convenience.

§1. Introduction. Let M be a totally ordered set. A (Dedekind) cut p of M is a couple (pL, pR) of subsets pL, pR of M such that pL ⋃ pR = M and pL < pR, i.e., a < b for all a ∈ pL, b ∈ pR. In this article we are looking for model completeness results of o-minimal structures M expanded by a set pL for a cut p of M. This means the following. Let M be an o-minimal structure in the language L and suppose M is model complete. Let D be a new unary predicate and let p be a cut of (the underlying ordered set of) M. Then we are looking for a natural, definable expansion of the L(D)-structure (M, pL) which is model complete.

The first result in this direction is a theorem of Cherlin and Dickmann (cf. [Ch-Dic]) which says that a real closed field expanded by a convex valuation ring has a model complete theory. This statement translates into the cuts language as follows. If Z is a subset of an ordered set M we write Z+ for the cut p with pR = {a ∈ M ∣ a > Z} and Z− for the cut q with qL = {a ∈ M ∣ a < Z}.

We investigate club guessing sequences and filters. We prove that assuming V = L, there exists a strong club guessing sequence on μ if and only if μ is not ineffable for every uncountable regular cardinal μ. We also prove that for every uncountable regular cardinal μ, relative to the existence of a Woodin cardinal above μ, it is consistent that every tail club guessing ideal on μ is precipitous.

Two linear orderings are equimorphic if each can be embedded into the other. We prove that every hyperarithmetic linear ordering is equimorphic to a recursive one.

On the way to our main result we prove that a linear ordering has Hausdorff rank less than if and only if it is equimorphic to a recursive one. As a corollary of our proof we prove that, given a recursive ordinal α, the partial ordering of equimorphism types of linear orderings of Hausdorff rank at most α ordered by embeddablity is recursively presentable.

Minimal predicates P satisfying a given first-order description ϕ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order ‘PIA conditions’ ϕ(P) which guarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of ‘predicate intersection’. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond.

Up to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these.

In this paper we introduce canonical extensions of partially ordered sets and monotone maps and a corresponding discrete duality. We then use these to give a uniform treatment of completeness of relational semantics for various substructural logics with implication as the residual(s) of fusion.

Let T be simple, work in Ceq over a boundedly closed set. Let p Є S(∅) be internal in a quasi-stably-embedded type-definable set Q (e.g., Q is definable or stably-embedded) and suppose (p, Q) is ACL-embedded in Q (see definitions below). Then Aut(p/Q) with its action on pc is type-definable in Ceq over ∅. In particular, if p Є S(∅) is internal in a stably-embedded type-definable set Q, and pc ⋃ Q is stably-embedded, then Aut(p/Q) is type-definable with its action on pc .

In 1984. Danecki proved that satisfiability in IPDL, i.e., Propositional Dynamic Logic (PDL) extended with an intersection operator on programs, is decidabie in deterministic double exponential time. Since then, the exact complexity of IPDL has remained an open problem: the best known lower bound was the ExpTime one stemming from plain PDL until, in 2004. the first author established ExpSpace-hardness. In this paper, we finally close the gap and prove that IPDL is hard for 2-ExpTime. thus 2-ExpTime-complete. We then sharpen our lower bound, showing that it even applies to IPDL without the test operator interpreted on tree structures.

We show that every nonzero Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, e-degrees which bound no minimal pair.

The lexicographic power ΔΓ of chains Δ and Γ is, roughly, the Cartesian power ΠγЄΓΔ totally ordered lexicographically from the left. Here the focus is on certain powers in which either Δ = ℝ or ℚ = ℝ, with emphasis on when two such powers are isomorphic and on when ΔΓ is 2-homogeneous. The main results are:

(1) For a countably infinite ordinal

(2) ℝℝ ≄ ℝℚ.

(3) For Δ a countable ordinal ≥ 2, Δℝ with its smallest element deleted, is 2-homogeneous.

The logics considered here are the propositional Linear Logic and propositional Intuitionistic Linear Logic extended by a knotted structural rule: . It is proved that the class of algebraic models for such a logic has the finite embeddability property, meaning that every finite partial subalgebra of an algebra in the class can be embedded into a finite full algebra in the class. It follows that each such logic has the finite model property with respect to its algebraic semantics and hence that the logic is decidable.

A fragment with the same provably recursive functions as n iterated inductive definitions is obtained by restricting second order arithmetic in the following way. The underlying language allows only up to n + 1 nested second order quantifications and those are in such a way. that no second order variable occurs free in the scope of another second order quantifier. The amount of induction on arithmetical formulae only affects the arithmetical consequences of these theories, whereas adding induction for arbitrary formulae increases the strength by one inductive definition.

We construct a model in which there is a strongly compact cardinal κ such thai the set S(κ, κ+) ={ a Є Pκκ+: o.t.(a) = (a⋂ κ)+}is non-stationary.

We prove that the theory of fields with a derivation of Frobenius has the model companion which is stable and admits elimination of quantifiers up to the level of the λ-functions. Along the way, we give new geometric axioms of DCFp.

In this paper we introduce a new natural deduction system for the logic of lattices, and a number of extensions of lattice logic with different negation connectives. We provide the class of natural deduction proofs with both a standard inductive definition and a global graph-theoretical criterion for correctness, and we show how normalisation in this system corresponds to cut elimination in the sequent calculus for lattice logic. This natural deduction system is inspired both by Shoesmith and Smiley's multiple conclusion systems for classical logic and Girard's proofnets for linear logic.

Let ℝ be an o-minimal expansion of (ℝ, <, +) and (ϕ k )kЄℕ be a sequence of positive real numbers such that limtk →+∞ f (ϕ k )/ϕ k +1 = 0 for every f: ℝ → ℝ definable in ℜ (Such sequences always exist under some reasonable extra assumptions on ℜ, in particular, if ℜ is exponentially bounded or if the language is countable.) Then (ℜ, (S)) is d-minimal. where S ranges over all subsets of cartesian powers of the range of ϕ.