Kripke submodels and universal sentences

We define two notions for intuitionistic predicate logic: that of a submodel of a Kripke model, and that of a universal sentence. We then prove a corresponding preservation theorem. If a Kripke model is viewed as a functor from a small category to the category of all classical models with (homo)morphisms between them, then we define a submodel of a Kripke model to be a restriction of the original Kripke model to a subcategory of its domain, where every node in the subcategory is mapped to a classical submodel of the corresponding classical model in the range of the original Kripke model. We call a sentence universal if it is built inductively from atoms (including ? and ⊥) using ∧, ∨, ?, and →, with the restriction that antecedents of → must be atomic. We prove that an intuitionistic theory is axiomatized by universal sentences if and only if it is preserved under Kripke submodels. We also prove the following analogue of a classical model‐consistency theorem: The universal fragment of a theory Γ is contained in the universal fragment of a theory Δ if and only if every rooted Kripke model of Δ is strongly equivalent to a submodel of a rooted Kripke model of Γ. Our notions of Kripke submodel and universal sentence are natural in the sense that in the presence of the rule of excluded middle, they collapse to the classical notions of submodel and universal sentence. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A probabilistic extension of intuitionistic logic

We introduce a probabilistic extension of propositional intuitionistic logic. The logic allows making statements such as P_≥sα, with the intended meaning “the probability of truthfulness of α is at least s”. We describe the corresponding class of models, which are Kripke models with a naturally arising notion of probability, and give a sound and complete infinitary axiomatic system. We prove that the logic is decidable.     

Depth Two,Normality, and a Trace Ideal Condition for Frobenius Extensions

A ring extension A ‖ B is depth two if its tensor-square satisfies a projectivity condition w.r.t. the bimodules _A A _B and _B A _A . In this case the structures (A ? _B A) ^B and End  _B A _B are bialgebroids over the centralizer C _A (B) and there is a certain Galois theory associated to the extension and its endomorphism ring. We specialize the notion of depth two to induced representations of semisimple algebras and character theory of finite groups. We show that depth two subgroups over the complex numbers are normal subgroups. As a converse, we observe that normal Hopf subalgebras over a field are depth two extensions. A generalized Miyashita–Ulbrich action on the centralizer of a ring extension is introduced, and applied to a study of depth two and separable extensions, which yields new characterizations of separable and H-separable extensions. With a view to the problem of when separable extensions are Frobenius, we supply a trace ideal condition for when a ring extension is Frobenius.     

A Note on Relative Efficiency of Axiom Systems

We introduce a notion of relative efficiency for axiom systems. Given an axiom system A_β for a theory T consistent with S¹₂, we show that the problem of deciding whether an axiom system A_α for the same theory is more efficient than A_β is II₂-hard. Several possibilities of speed-up of proofs are examined in relation to pairs of axiom systems A_α, A_β, with A_α ? A_β, both in the case of A_α, A_β having the same language, and in the case of the language of A_α extending that of A_β: in the latter case, letting Pr_α, Pr_β denote the theories axiomatized by A_α, A_β, respectively, and assuming Pr_α to be a conservative extension of Pr_β, we show that if A_α — A_β contains no nonlogical axioms, then A_α can only be a linear speed-up of A_β; otherwise, given any recursive function g and any A_β, there exists a finite extension A_α of A_β such that A_α is a speed-up of A_β with respect to g. Mathematics Subject Classification: 03F20, 03F30.     

Polynomials in a matrix

Let A be a matrixp(x) a polynomial. Put B=p(A). It is shown that necessary and sufficient conditions for A to be a polynomial in B are (i) if λ is any eigenvalue of A, and if some elementary divisor of A corresponding to λ is nonlinear, thenp ^′(λ)≠0;and (ii) if λ,μ are distinct eigenvalues of A, then p(λ)p(μ) are also distinct. Here all computations are over some algebraically closed field.     

Basic Propositional Calculus I

We present an axiomatization for Basic Propositional Calculus BPC and give a completeness theorem for the class of transitive Kripke structures. We present several refinements, including a completeness theorem for irreflexive trees. The class of intermediate logics includes two maximal nodes, one being Classical Propositional Calculus CPC, the other being E₁, a theory axiomatized by T → ⊥. The intersection CPC ∩ E₁ is axiomatizable by the Principle of the Excluded Middle A V ∨ ?A. If B is a formula such that (T → B) → B is not derivable, then the lattice of formulas built from one propositional variable p using only the binary connectives, is isomorphically preserved if B is substituted for p. A formula (T → B) → B is derivable exactly when B is provably equivalent to a formula of the form ((T → A) → A) → (T → A).     

On the structure of kripke models of heyting arithmetic

Since in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ₁ (PA^- with induction for provably Δ₁ formulas) and that the relation between these classical structures must be that of a Δ₁-elementary submodel. MSC: 03F30, 03F55.     

Weak Arithmetics and Kripke Models

In the first section of this paper we show that i Π₁ ≡ W⌝⌝lΠ₁ and that a Kripke model which decides bounded formulas forces iΠ₁ if and only if the union of the worlds in any (complete) path in it satisflies IΠ₁. In particular, the union of the worlds in any path of a Kripke model of HA models IΠ₁. In the second section of the paper, we show that for equivalence of forcing and satisfaction of Π_m‐formulas in a linear Kripke model deciding Δ₀‐formulas it is necessary and sufficient that the model be Σ_m‐elementary. This implies that if a linear Kripke model forces PEM_prenex, then it forces PEM. We also show that, for each n ≥ 1, iΦ_n does not prove ℋ︁(IΠ_n's are Burr's fragments of HA.     

Ideal extensions of graph algebras

Let A and B be graph algebras. In this paper we present the notion of an ideal in a graph algebra and prove that an ideal extension of A by B always exists. We describe (up to isomorphism) all such extensions.     

Homomorphisms and chains of Kripke models

In this paper we define a suitable version of the notion of homomorphism for Kripke models of intuitionistic first-order logic and characterize theories that are preserved under images and also those that are preserved under inverse images of homomorphisms. Moreover, we define a notion of union of chain for Kripke models and define a class of formulas that is preserved in unions of chains. We also define similar classes of formulas and investigate their behavior in Kripke models. An application to intuitionistic first-order arithmetic is also given.     

The computation of Kronecker's canonical form of a singular pencil

We develop stable algorithms for the computation of the Kronecker structure of an arbitrary pencil. This problem can be viewed as a generalization of the well-known eigenvalue problem of pencils of the type λI?A. We first show that the elementary divisors (λ ? α)ⁱ of a regular pencil λB?A can be retrieved with a deflation algorithm acting on the expansion (λ ? α)B ? (A ? αB). This method is a straightforward generalization of Kublanovskaya's algorithm for the determination of the Jordan structure of a constant matrix. We also show how to use this method to determine the structure of the infinite elementary divisors of λB?A. In the case of singular pencils, the occurrence of Kronecker indices—containing the singularity of the pencil—somewhat complicates the problem. Yet our algorithm retrieves these indices with no additional effort, when determining the elementary divisors of the pencil. The present ideas can also be used to separate from an arbitrary pencil a smaller regular pencil containing only the finite elementary divisors of the original one. This is shown to be an effective tool when used together with the QZ algorithm.     

Codepth Two and Related Topics

A depth two extension A | B is shown to be weak depth two over its double centralizer V _A (V _A (B)) if this is separable over B. We consider various examples and non-examples of depth one and two properties. Depth two and its relationship to direct and tensor product of algebras as well as cup product of relative Hochschild cochains is examined. Section 6 introduces a notion of codepth two coalgebra homomorphism g : C → D, dual to a depth two algebra homomorphism. It is shown that the endomorphism ring of bicomodule endomorphisms End ^D C ^D forms a right bialgebroid over the centralizer subalgebra g ^* : D ^* → C ^* of the dual algebra C ^*. Dedicated to Daniel Kastler on his eightieth birthday.     

Foliated Lie and Courant Algebroids

If A is a Lie algebroid over a foliated manifold (M, F){(M, {\mathcal {F}})}, a foliation of A is a Lie subalgebroid B with anchor image TF{T{\mathcal {F}}} and such that A/B is locally equivalent with Lie algebroids over the slice manifolds of F{\mathcal F}. We give several examples and, for foliated Lie algebroids, we discuss the following subjects: the dual Poisson structure and Vaintrob's supervector field, cohomology and deformations of the foliation, integration to a Lie groupoid. In the last section, we define a corresponding notion of a foliation of a Courant algebroid A as a bracket–closed, isotropic subbundle B with anchor image TF{T{\mathcal {F}}} and such that B ^{^} /B{B^{ \bot } /B} is locally equivalent with Courant algebroids over the slice manifolds of F{\mathcal F}. Examples that motivate the definition are given.     

On matrices stochastically similar to matrices with equal diagonal elements

A necessary and sufficient condition for a matrix to be stochastically similar to a matrix with equal diagonal elements is obtained Aand B are called Stochastically similar if B=SAS ^{? 1} where S is quasi-stochastic i.e., all row sums of .S are I. An inverse elementary divisor problem for quasi-stochastic matrices is also considered.     

Submodels of Kripke models

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus. In Appendix A we prove that for theories with decidable identity we can take as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. Received: 4 February 1999 / Published online: 25 January 2001     

Positivity and Convexity in Rings of Fractions

Given a commutative ring A equipped with a preordering A⁺ (in the most general sense, see below), we look for a fractional ring extension (= “ring of quotients” in the sense of Lambek et al. [L]) as big as possible such that A⁺ extends to a preordering R⁺ of R (i.e. with A ∩ R⁺ = A⁺) in a natural way. We then ask for subextensions A ⊂ B of A ⊂ R such that A is convex in B with respect to B⁺ : = B ∩ R⁺. Supported by DFG. A short form of this article has been delivered at the conference Carthapos 2006 at Carthago (Tunisia).     

Hilbert's Theorem 90 for Hopf Galois Extensions

For a faithfully flat extension A/B and a right A-module M, we give a new characterization of the set of descent data on M. Assuming that B is a simple Artinian ring and A/B is H-Galois, for a certain finite dimensional Hopf algebra H, we prove that Sweedler's noncommutative cohomology H ¹(H?, A) is trivial as a pointed set.     

Reduced products which are not saturated

Summary IfT is a complete theory of Boolean algebra, then we writeA ⊲_T B to denote that for every cardinal κ and every κ-regular filter over a setI such that the Boolean algebra 2 _F ^I of all subsets ofI reduced byF is a model ofT, the reduced powerA _F ^I isK ⁺-saturated wheneverB _F ^I isK ⁺-saturated. The relation ⊲_T generalizes the relation ◃ introduced by Keisler. As in the case of Keisler's ◃ it happens that ⊲_T’s are relations between complete theories, i.e. ifA≡B thenA ⊲_T B andB ⊲_T A. In this paper some examples of theories which are maximal (minimal) with respect to ⊲_T’s are provided and the relations ⊲_T are compared with each other. Presented by J. Mycielski     

Equivalence of Hadamard matrices

Supposem is a square-free odd integer, andA andB are any two Hadamard matrices of order 4m. We will show thatA andB are equivalent over the integers (that is,B can be obtained fromA using elementary row and column operations which involve only integers).     

Principal minors and diagonal similarity of matrices

Let A, B be n × n matrices with entries in a field F. Our purpose is to show the following theorem: Suppose n⩾4, A is irreducible, and for every partition of {1,2,…,n} into subsets α, β with ¦α¦⩾2, ¦β¦⩾2 either rank A[α¦β]⩾2 or rank A[β¦α]⩾2. If A and B have equal corresponding principal minors, of all orders, then B or B^t is diagonally similar to A.