The Projective Beth Property and Interpolation in Positive and Related Logics

We look at the interplay between the projective Beth property in non-classical logics and interpolation. Previously, we proved that in positive logics as well as in superintuitionistic and modal ones, the projective Beth property PB2 follows from Craig's interpolation property and implies the restricted interpolation property IPR. Here, we show that IPR and PB2 are equivalent in positive logics, and also in extensions of the superintuitionistic logic KC and of the modal logic Grz.2. Supported by RFBR grant No. 06-01-00358, by INTAS grant No. 04-77-7080, and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1. __________ Translated from Algebra i Logika, Vol. 45, No. 1, pp. 85–113, January–February, 2006.     

The characteristic of noncompact convexity and random fixed point theorem for set-valued operators

Let (Ω, Σ) be a measurable space, X a Banach space whose characteristic of noncompact convexity is less than 1, C a bounded closed convex subset of X, KC(C) the family of all compact convex subsets of C. We prove that a set-valued nonexpansive mapping T: C → KC(C) has a fixed point. Furthermore, if X is separable then we also prove that a set-valued nonexpansive operator T: Ω × C → KC(C) has a random fixed point.     

A note on Grzegorczyk's logic

Grzegorczyk's modal logic (Grz) corresponds to the class of upwards well‐founded partially ordered Kripke frames, however all known proofs of this fact utilize some form of the Axiom of Choice; G. Boolos asked in [1], whether it is provable in plain ZF. We answer his question negatively: Grz corresponds (in ZF) to a class of frames, which does not provably coincide with upwards well‐founded posets in ZF alone. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

PP-Rings of Generalized Power Series

Abstract As a generalization of power series rings, Ribenboim introduced the notion of the rings of generalized power series. Let R be a commutative ring, and (S, ≤) a strictly totally ordered monoid. We prove that (1) the ring [[R ^S,≤]] of generalized power series is a PP-ring if and only if R is a PP-ring and every S-indexed subset C of B(R) (the set of all idempotents of R) has a least upper bound in B(R) and (2) if (S, ≤) also satisfies the condition that 0 ≤s for any s∈S, then the ring [[R ^S,≤ ]] is weakly PP if and only if R is weakly PP. Research supported by National Natural Science Foundation of China, 19501007, and Natural Science Foundation of Gansu, ZQ-96-01     

A Note on the Homology of Signed Posets

Let S be a signed poset in the sense of Reiner [4]. Fischer [2] defines the homology of S, in terms of a partial ordering P (S) associated to S, to be the homology of a certain subcomplex of the chain complex of P (S).In this paper we show that if P (S) is Cohen-Macaulay and S has rank n, then the homology of S vanishes for degrees outside the interval [n/2, n].Research partially supported by the National Science Foundation and the John Simon Guggenheim Foundation.     

On delaunay oriented matroids for convex distance functions

For any finite point setS inE ^d, an oriented matroid DOM (S) can be defined in terms of howS is partitioned by Euclidean hyperspheres. This oriented matroid is related to the Delaunay triangulation ofS and is realizable, because of thelifting property of Delaunay triangulations. We prove that the same construction of aDelaunay oriented matroid can be performed with respect to any smooth, strictly convex distance function in the planeE ² (Theorem 3.5). For these distances, the existence of a Delaunay oriented matroid cannot follow from a lifting property, because Delaunay triangulations might be nonregular (Theorem 4.2(i). This is related to the fact that the Delaunay oriented matroid can be nonrealizable (Theorem 4.2(ii). This research was partially supported by the Spanish Grant DGICyT PB 92/0498-C02 and the David and Lucile Packard Foundation.     

Axiomatization and Polynomial Solvability of Strictly Positive Fragments of Certain Modal Logics

The fragment of the language of modal logic that consists of all implications A → B, where A and B are built from variables, the constant ⊤ (truth), and the connectives ∧ and ◊₁,◊₂,...,◊ _m . For the polymodal logic S5 _m (the logic of m equivalence relations) and the logic K4.3 (the logic of irreflexive linear orders), an axiomatization of such fragments is found and their algorithmic decidability in polynomial time is proved.

     

Implicative commutative semigroups are equivalent to a class of BCK algebras

Chan and Shum [2] introduced the notion of implicative semigroups and obtained some of its important properties. BCK algebras with condition (S) were introduced by Iséki [4] and extensively investigated by several authors. In this note, we prove that implicative commutative semigroups are equivalent to BCK algebras with condition (S), that is, given an algebra <S;≤,·,*,1> of type (2,2,0), define ⊗ by stipulatingx⊗y=y*x and ≺ by puttingx≺y if and only ify≤x, then <S≤,·,*,1> is an implicative commutative semigroup if and only if <S;≺,·,⊗, 1> is a BCK algebra with condition (S); a nonempty subsetF ofS is an ordered filter of <S;≤,·,*, 1> if and only ifF is an ideal of <S;≺,·, ⊗, 1>. The author would like to thank the referee for his valuable comments which helped in the modification of this paper.     

Minimal entropy and collapsing with curvature bounded from below

We show that if a closed manifold M admits an ℱ-structure (not necessarily polarized, possibly of rank zero) then its minimal entropy vanishes. In particular, this is the case if M admits a non-trivial S ¹-action. As a corollary we obtain that the simplicial volume of a manifold admitting an ℱ-structure is zero.?We also show that if M admits an ℱ-structure then it collapses with curvature bounded from below. This in turn implies that M collapses with bounded scalar curvature or, equivalently, its Yamabe invariant is non-negative.?We show that ℱ-structures of rank zero appear rather frequently: every compact complex elliptic surface admits one as well as any simply connected closed 5-manifold.?We use these results to study the minimal entropy problem. We show the following two theorems: suppose that M is a closed manifold obtained by taking connected sums of copies of S ⁴, ℂP ², ²,S ²×S ²and the K3 surface. Then M has zero minimal entropy. Moreover, M admits a smooth Riemannian metric with zero topological entropy if and only if M is diffeomorphic to S ⁴,ℂP ²,S ²×S ²,ℂP ²#  ² or ℂP ²# ℂP ². Finally, suppose that M is a closed simply connected 5-manifold. Then M has zero minimal entropy. Moreover, M admits a smooth Riemannian metric with zero topological entropy if and only if M is diffeomorphic to S ⁵,S ³×S ², then on trivial S ³-bundle over S ² or the Wu-manifold SU(3)/SO(3). Oblatum 13-III-2002 & 12-VIII-2002?Published online: 8 November 2002 G.P. Paternain was partially supported by CIMAT, Guanajuato, México.?J. Petean is supported by grant 37558-E of CONACYT.     

Homogeneous and ultrahomogeneous Steiner systems

A Steiner system (or t — (v, k, 1) design) S is said to be homogeneous if, whenever the substructures induced on two finite subsets S₁ and S₂ of S are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂, and is said to be ultrahomogeneous if each isomorphism between the substructures induced on two finite subsets of S can be extended to an automorphism of S. We give a complete classification of all homogeneous and ultrahomogeneous Steiner systems. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 153–161, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10034     

On the law S ( S ( x , y ), T ( x , y )) = S ( x , y ) of fuzzy logic

Motivated by some functional models arising in fuzzy logic, when classical boolean relations between sets are generalized, we study the functional equation S(S(x, y), T(x, y)) = S(x, y), where S is a continuous t-conorm and T is a continuous t-norm. Some interesting methods for solving this type of equations are introduced.     

The Ascending Chain Condition for Principal Ideals of Rings of Generalized Power Series

Abstract

Let (S, ≤) be a strictly totally ordered monoid and R a domain. It is shown in this paper that [[R ^S,≤]], the ring of generalized power series with coefficients in R and exponents in S, satisfies the ascending chain condition for principal ideals if and only if the ring R and the monoid S satisfy the ascending chain condition for principal ideals of R, and of S, respectively.     

N(2,2,0)代数的E-反演半群

本文研究了N(2,2,0)代数(S,*,△,0)的E-反演半群.利用N(2,2,0)代数的幂等元,弱逆元,中间单位元的性质和同宇关系,得到了N(2,2,0)代数的半群(S,*)构成E-反演半群的条件及元素α的右伴随非零零因子唯一,且为α的弱逆元等结论,这些结果进一步刻画了N(2,2,0)代数的结构.     

Morita Equivalence for Factorisable Semigroups

Recall that the semigroups S and R are said to be strongly Morita equivalent if there exists a unitary Morita context (S, R., _S P _R,R Q _S ,〈〉 , ⌈⌉) with 〈〉 and ⌈⌉ surjective. For a factorisable semigroup S, we denote ζ _S = {(s ₁, s ₂) ∈S×S|ss ₁ = ss ₂, ∀s∈S}, S' = S/ζ _S and US-FAct = { _S M∈S− Act |SM = M and SHom _S (S, M) ≅M}. We show that, for factorisable semigroups S and M, the categories US-FAct and UR-FAct are equivalent if and only if the semigroups S' and R' are strongly Morita equivalent. Some conditions for a factorisable semigroups to be strongly Morita equivalent to a sandwich semigroup, local units semigroup, monoid and group separately are also given. Moreover, we show that a semigroup S is completely simple if and only if S is strongly Morita equivalent to a group and for any index set I, S⊗SHom _S (S, ∐ _i∈I S) →∐ _i∈I S, s⊗t·ƒ↦ (st)ƒ is an S-isomorphism. The research is partially supported by a UGC(HK) grant #2160092. Project is supported by the National Natural Science Foundation of China     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Spectrum of resolvable directed quadruple systems

A t-(v, k, 1) directed design (or simply a t-(v, k, 1)DD) is a pair (S, ℐ), where S is a v-set and ℐ is a collection of k-tuples (called blocks) of S, such that every t-tuple of S belongs to a unique block. The t-(v, k, 1)DD is called resolvable if ℐ can be partitioned into some parallel classes, so that each parallel class is a partition of S. It is proved that a resolvable 3-(v, 4, 1)DD exists if and only if v = 0 (mod 4).     

The classification problem for S-local torsion-free abelian groups of finite rank

Suppose that n?2 and that S, T are sets of primes. Then the classification problem for the S-local torsion-free abelian groups of rank n is Borel reducible to the classification problem for the T-local torsion-free abelian groups of rank n if and only if S⊆T.     

The commuting graphs of some subsets in the quaternion algebra over the ring of integers modulo <Emphasis Type="Italic">N</Emphasis>

Let R be an arbitrary ring, S be a subset of R, and Z(S) = {s ∈ S | sx = xs for every x ∈ S}. The commuting graph of S, denoted by Γ(S), is the graph with vertex set S \ Z(S) such that two different vertices x and y are adjacent if and only if xy = yx. In this paper, let I _n , N _n be the sets of all idempotents, nilpotent elements in the quaternion algebra ℤ _n [i, j, k], respectively. We completely determine Γ(I _n ) and Γ(N _n ). Moreover, it is proved that for n ≥ 2, Γ(I _n ) is connected if and only if n has at least two odd prime factors, while Γ(N _n ) is connected if and only if n ∈ 2, 2², p, 2p for all odd primes p.     

Principal Weak Flatness and Regularity of Diagonal Acts

For a monoid S, the set S × S equipped with the componentwise right S-action is called the diagonal act of S and is denoted by D(S). A monoid S is a left PP (left PSF) monoid if every principal left ideal of S is projective (strongly flat). We shall call a monoid S left P(P) if all principal left ideals of S satisfy condition (P). We shall call a monoid S weakly left P(P) monoid if the equalities as = bs, xb = yb in S imply the existence of r ∈ S such that xar = yar, rs = s. In this article, we prove that a monoid S is left PSF if and only if S is (weakly) left P(P) and D(S) is principally weakly flat. We provide examples showing that the implications left PSF ? left P(P) ? weakly left P(P) are strict. Finally, we investigate regularity of diagonal acts D(S), and we prove that for a right PP monoid S the diagonal act D(S) is regular if and only if every finite product of regular acts is regular. Furthermore, we prove that for a full transformation monoid S = 𝒯 _X , D(S) is regular.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.