§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.

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.

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 .

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.

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 ϕ.

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M′ over the same vocabulary if Φ is true on M but false on M′. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M′. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M′.

We prove that every n-element structure M is identifiable by a formula with quantifier rank less than and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification.

The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than quantifiers suffice to identify M and. as long as we keep the number of universal quantifiers bounded by a constant, at total quantifiers are necessary.

We prove that an intermediate predicate logic characterized by a class of finite partially ordered sets is recursively axiomatizable iff it is “finite”, i.e., iff it is characterized by a single finite partially ordered set. Therefore, the predicate logic LFin of the class of all predicate Kripke frames with finitely many possible worlds is not recursively axiomatizable.

Let F be the class of complete, finitely axiomatizable ω-categorical theories. It is not known whether there are simple theories in F. We prove three results of the form: if T ∈ F has a sufficently well-behaved definable set J, then T is not simple. (In one case, we actually prove that T has the strict order property.) All of our arguments assume that the definable set J satisfies the Mazoyer hypothesis, which controls how an element of J can be algebraic over a subset of the model. For every known example in F, there is a definable set satisfying the Mazoyer hypothesis.

The concept of elementary epimorphism is introduced. Inverse systems of such maps are considered, and a dual of the elementary chain lemma is found (Cor. 4.2). The same is done for pure epimorphisms (Cor. 4.3 and 4.4). Finally, this is applied to certain inverse limits of flat modules (Thm. 6.4) and certain inverse limits of absolutely pure modules (Cor. 6.3).

Natural deduction systems with indefinite and definite descriptions (ε-terms and ι-terms) are presented, and interpreted in Martin-LÖf's intensional type theory. The interpretations are formalizations of ideas which are implicit in the literature of constructive mathematics: if we have proved that an element with a certain property exists, we speak of ‘the element such that the property holds’ and refer by that phrase to the element constructed in the existence proof. In particular, we deviate from the practice of interpreting descriptions by contextual definitions.

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅(n − 1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ∣x∣ − c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity.

Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those l-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω. sets coincide with the r.e. K-trivial ones.

Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees.

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinatory has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.

In the absence of Woodin cardinals, fine structural inner models for mild large cardinal hypotheses admit forcing extensions where bounded forcing axioms hold and yet the reals are projectively well-ordered.

We consider the reduct to the module language of certain theories of fields with a non surjective endomorphism. We show in some cases the existence of a model companion. We apply our results for axiomatizing the reduct to the theory of modules of non principal ultraproducts of separably closed fields of fixed but non zero imperfection degree.

We develop a dimension theory for D-semianalytic sets over an arbitrary non-Arehimedean eomplete field. Our main results are the equivalence of several notions of dimension and a theorem on additivity of dimensions of projections and fibers in characteristic 0. We also prove a parameterized version of normalization for D-semianalytic sets.

We consider exponentially large finite relational structures (with the universe {0, 1}n ) whose basic relations are computed by polynomial size (n O(1)) circuits. We study behaviour of such structures when pulled back by P/poly maps to a bigger or to a smaller universe. In particular, we prove that:

1. If there exists a P/poly map g: {0, 1}n → {0, 1}m , n < m, iterable for a proof system then a tautology (independent of g) expressing that a particular size n set is dominating in a size 2n tournament is hard for the proof system.

2. The search problem WPHP. decoding RSA or finding a collision in a hashing function can be reduced to finding a size m homogeneous subgraph in a size 22m graph.

Further we reduce the proof complexity of a concrete tautology (expressing a Ramsey property of a graph) in strong systems to the complexity of implicit proofs of implicit formulas in weak proof systems.

I prove a version of Schanuel's conjecture for Weierstrass equations in differential fields, answering a question of Zilber, and show that the linear independence condition in the statement cannot be relaxed.

This paper is devoted to the proof of the following upward categoricity theorem: Let be a tame abstract elementary class with amalgamation, arbitrarily large models, and countable Löwenheim-Skolem number. If is categorical in ℵ then is categorical in every uncountable cardinal. More generally, wc prove that if is categorical in a successor cardinal λ+ then is categorical everywhere above λ+.

It is proved that all groups of finite U-rank that have the descending chain condition on definable subgroups are totally transcendental. A corollary is that any stable group that is definable in an o -minimal structure is totally transcendental of finite Morley rank.

Non-perfect separably closed fields are stable, and not superstable. As a result, not all types can be ranked. We develop here a new tool, a “semi-rank”, which takes values in the non-negative reals, and gives a sufficient condition for forking of types. This semi-rank is built up from a transcendence function, analogous to the one considered by Kolehin in the context of differentially closed fields. It yields some orthogonality and stratification results.