An infinitary probability logic for type spaces

Type spaces in the sense of Harsanyi (1967/68) play an important role in the theory of games of incomplete information. They can be considered as the probabilistic analog of Kripke structures. By an infinitary propositional language with additional operators “individual i assigns probability at least α to” and infinitary inference rules, we axiomatize the class of (Harsanyi) type spaces. We prove that our axiom system is strongly sound and strongly complete. To the best of our knowledge, this is the very first strong completeness theorem for a probability logic with σ-additive probabilities. We show this by constructing a canonical type space whose states consist of all maximal consistent sets of formulas. Furthermore, we show that this canonical space is universal (i.e., a terminal object in the category of type spaces) and beliefs complete.     

On normal 2-geodesic transitive Cayley graphs

We investigate connected normal 2-geodesic transitive Cayley graphs Cay(T,S). We first prove that if Cay(T,S) is neither cyclic nor K_4[2], then 〈a〉?{1}??S for all a∈S. Next, as an application, we give a reduction theorem proving that each graph in this family which is neither a complete multipartite graph nor a bipartite 2-arc transitive graph, has a normal quotient that is either a complete graph or a Cayley graph in the family for a characteristically simple group. Finally we classify complete multipartite graphs in the family.     

Algebraic density property of Danilov–Gizatullin surfaces

A Danilov–Gizatullin surface is an affine surface V which is the complement of an ample section S for the ruling of a Hirzebruch surface. The remarkable theorem of Danilov and Gizatullin states that the isomorphism class of V depends only on the self-intersection number (S.S). In this paper we apply the theorem of Danilov–Gizatullin to prove that the Lie algebra generated by the complete algebraic vector fields on V coincides with the set of all algebraic vector fields of V.     

A complete rewrite system and normal forms for (S) reg

The (·)_reg construction was introduced in order to make an arbitrary semigroup S divide a regular semigroup (S) _reg which shares some important properties with S (e.g., finiteness, subgroups, torsion bounds, J-order structure). We show that (S) _reg can be described by a rather simple complete string rewrite system, as a consequence of which we obtain a new proof of the normal form theorem for (S) _reg. The new proof of the normal form theorem is conceptually simpler than the previous proofs.     

A short proof of Glivenko theorems for intermediate predicate logics

We give a simple proof-theoretic argument showing that Glivenko’s theorem for propositional logic and its version for predicate logic follow as an easy consequence of the deduction theorem, which also proves some Glivenko type theorems relating intermediate predicate logics between intuitionistic and classical logic. We consider two schemata, the double negation shift (DNS) and the one consisting of instances of the principle of excluded middle for sentences (REM). We prove that both schemata combined derive classical logic, while each one of them provides a strictly weaker intermediate logic, and neither of them is derivable from the other. We show that over every intermediate logic there exists a maximal intermediate logic for which Glivenko’s theorem holds. We deduce as well a characterization of DNS, as the weakest (with respect to derivability) scheme that added to REM derives classical logic.     

Unitary Representations of Oligomorphic Groups

We obtain a complete classification of the continuous unitary representations of oligomorphic permutation groups (those include the infinite permutation group S ^??, the automorphism group of the countable dense linear order, the homeomorphism group of the Cantor space, etc.). Our main result is that all irreducible representations of such groups are obtained by induction from representations of finite quotients of open subgroups and, moreover, every representation is a sum of irreducibles. As an application, we prove that many oligomorphic groups have property (T). We also show that the Gelfand?CRaikov theorem holds for topological subgroups of S ^??: for all such groups, continuous irreducible representations separate points in the group.     

Embeddings of 2-dimensional cell complexes in S3 determined by their 1-skeletons

We prove the following theorem: A polyhedral embedding of a 2-dimensional cell complex in S³ is determined up to ambient isotopy rel the 1-skeleton by the embedding of the 1-skeleton, provided the cell complex is ‘proper’ and ‘fine enough’. Applications of the theorem are given in distinguishing certain graphs in S³ from their mirror images. (This is of interest to chemists studying stereoisomerism.) Examples are given to illustrate that the theorem can fail without either hypothesis ‘proper’ or ‘fine enough’. The main theorem may be generalized by replacing S³ by an irreducible 3-manifold with nonempty boundary.     

The Sylvester-Gallai theorem, colourings and algebra

Our point of departure is the following simple common generalisation of the Sylvester-Gallai theorem and the Motzkin-Rabin theorem:

LetSbe a finite set of points in the plane, with each point coloured red or blue or with both colours. Suppose that for any two distinct pointsA,B∈Ssharing a colour there is a third pointC∈S, of the other colour, collinear withAandB. Then all the points inSare collinear.

We define a chromatic geometry to be a simple matroid for which each point is coloured red or blue or with both colours, such that for any two distinct points A,B∈S sharing a colour there is a third point C∈S, of the other colour, collinear with A and B. This is a common generalisation of proper finite linear spaces and properly two-coloured finite linear spaces, with many known properties of both generalising as well. One such property is Kelly’s complex Sylvester-Gallai theorem. We also consider embeddings of chromatic geometries in Desarguesian projective spaces. We prove a lower bound of 51 for the number of points in a three-dimensional chromatic geometry in projective space over the quaternions. Finally, we suggest an elementary approach to the corollary of an inequality of Hirzebruch used by Kelly in his proof of the complex Sylvester-Gallai theorem.     

On quasi completely regular semirings

We extend the concepts of a completely π-regular semigroup and a GV semigroup to semirings and find a semiring analogue of a structure theorem on GV semigroups. We also show that a semiring S is quasi completely regular if and only if S is an idempotent semiring of quasi skew-rings.     

Sémantique algébrique ďun système logique basé sur un ensemble ordonné fini

In order to modelize the reasoning of an intelligent agent represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems a set of constants constitutes a fundamental tool. In this papers, we consider logic systems called L′_T without this kind of constants but limited to the case where T is a finite poset. We prove a weak deduction theorem. We introduce also an algebraic semantics using Hey ting algebra with operators. To prove the completeness theorem of the L′_T system with respect to the algebraic semantics, we use the method of H. Rasiowa and R. Sikorski for first order logic. In the propositional case, a corollary allows us to assert that it is decidable to know “if a propositional formula is valid”. We study also certain relations between the L′_T logic and the intuitionistic and classical logics.     

A simple logic for reasoning about incomplete knowledge

The semantics of modal logics for reasoning about belief or knowledge is often described in terms of accessibility relations, which is too expressive to account for mere epistemic states of an agent. This paper proposes a simple logic whose atoms express epistemic attitudes about formulae expressed in another basic propositional language, and that allows for conjunctions, disjunctions and negations of belief or knowledge statements. It allows an agent to reason about what is known about the beliefs held by another agent. This simple epistemic logic borrows its syntax and axioms from the modal logic KD. It uses only a fragment of the S5 language, which makes it a two-tiered propositional logic rather than as an extension thereof. Its semantics is given in terms of epistemic states understood as subsets of mutually exclusive propositional interpretations. Our approach offers a logical grounding to uncertainty theories like possibility theory and belief functions. In fact, we define the most basic logic for possibility theory as shown by a completeness proof that does not rely on accessibility relations.     

Cut‐elimination Theorems for Some Infinitary Modal Logics

In this article, a cut‐free system TLM_ω1 for infinitary propositional modal logic is proposed which is complete with respect to the class of all Kripke frames.The system TLM_ω1 is a kind of Gentzen style sequent calculus, but a sequent of TLM_ω1 is defined as a finite tree of sequents in a standard sense. We prove the cut‐elimination theorem for TLM_ω1 via its Kripke completeness.     

Banaschewski’s theorem for S-posets: regular injectivity and completeness

In this paper we study the notion of injectivity in the category Pos-S of S-posets for a pomonoid S. First we see that, although there is no non-trivial injective S-poset with respect to monomorphisms, Pos-S has enough (regular) injectives with respect to regular monomorphisms (sub S-posets). Then, recalling Banaschewski’s theorem which states that regular injectivity of posets with respect to order-embeddings and completeness are equivalent, we study regular injectivity for S-posets and get some homological classification of pomonoids and pogroups. Among other things, we also see that regular injective S-posets are exactly the retracts of cofree S-posets over complete posets.     

Strong S-domains

S-domains and strong S-rings are studied extensively with special emphasis on integral and polynomial ring extensions. The main theorem of this paper is that for a Prüfer domain R, the polynomial ring R[X₁,…X_n] in finitely many indeterminates is a strong S-domain. We also prove that any Prüfer υ-multiplication domain is an S-domain.     

Generalization of the Chinese remainder theorem

Sufficient conditions for a system Ax = r to have an integral solution in the case of a basic matrix A in terms of submatrices and permanents of A are derived. Matrix A in the Chinese remainder theorem is a particular case of a basic matrix. The derivation can be extended to the case where the propositional formula that describes the sign scheme of A is a minimal unsatisfiable CNF.     

An Empirical Study of MAX-2-SAT Phase Transitions

The decision version of the maximum satisfiability problem (MAX-SAT) is stated as follows: Given a set S of propositional clauses and an integer g, decide if there exists a truth assignment that falsifies at most g clauses in S, where g is called the allowance for false clauses. We conduct an extensive experiment on over a million of random instances of 2-SAT and identify statistically the relationship between g, n (number of variables) and m (number of clauses). In our experiment, we apply an efficient decision procedure based on the branch-and-bound method. The statistical data of the experiment confirm not only the “scaling window” of MAX-2-SAT discovered by Chayes, Kim and Borgs, but also the recent results of Coppersmith et al. While there is no easy-hard-easy pattern for the complexity of 2-SAT at the phase transition, we show that there is such a pattern for the decision problem of MAX-2-SAT associated with the phase transition. We also identify that the hardest problems are among those with high allowance for false clauses but low number of clauses.     

On supplementation and generalized projective modules

Discrete (quasi) modules form an important class in module theory, they are studied extensively by many authors. The decomposition theorem for quasidiscrete modules plays an important rule in the better understanding of such modules. In fact, every quasidiscrete module is a direct sum of hollow submodules. Here we introduce some new concepts (weak quasidiscrete, and S ₁- and S ₂-supplemented modules) which generalize the concept of quasidiscrete module. We show that some of the properties of quasidiscrete modules still hold in the class of weak quasidiscrete modules. We also obtain some properties of weak quasidiscrete modules, which are similar to the properties known for quasidiscrete modules. We introduce the concept of generalized relative projectivity (relative S-projectivemodules), and use it to characterize direct sums of hollowmodules. In fact, relative S-projectivity is an essential condition for direct sums of hollow modules to be weak quasidiscrete modules.     

Positive integers expressible as a sum of three squares in essentially only one way

The set S consisting of those positive integers n which are uniquely expressible in the form n = a² + b² + c², $\text{a ≧ b ≧ c ≧ 0}$, is considered. Since n ∈ S if and only if 4n ∈ S, we may restrict attention to those n not divisible by 4. Classical formulas and the theorem that there are only finitely many imaginary quadratic fields with given class number imply that there are only finitely many n ∈ S with n = 0 (mod 4). More specifically, from the existing knowledge of all the imaginary quadratic fields with odd discriminant and class number 1 or 2 it is readily deduced that there are precisely twelve positive integers n such that n ∈ S and n ≡ 3 (mod 8). To determine those n ∈ S such that n ≡ 1, 2, 5, 6 (mod 8) requires the determination of the imaginary quadratic fields with even discriminant and class number 1, 2, or 4. While the latter information is known empirically, it has not been proved that the known list of 33 such fields is complete. If it is complete, then our arguments show that there are exactly 21 positive integers n such that n ∈ S and n ≡ 1, 2, 5, 6 (mod 8).     

On the applicability to semirings of two theorems from the theory of rings and modules

Problems concerning the extension of the Baer criterion for injectivity and embedding theorem of an arbitrary module over a ring into an injective module to the case of semirings are treated. It is proved that a semiring S satisfies the Baer criterion and every S-semimodule can be embedded in an injective semimodule if and only if S is a ring.     

On strictly weakly mixing <Emphasis Type="Italic">C</Emphasis>*-dynamical systems

We consider strictly ergodic and strictly weakly mixing C*-dynamical cystems. We establish that a system is strictly weakly mixing if and only if its tensor product is strictly ergodic and strictly weakly mixing. We also investigate some weighted uniform ergodic theorem with respect to S-Besicovitch sequences for strictly weakly mixing dynamical systems.