Axiomatisability and hardness for universal Horn classes of hypergraphs

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht–Fraïssé game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.     

Fibered universal algebra for first-order logics

We extend Lawvere-Pitts prop-categories (aka. hyperdoctrines) to develop a general framework for providing fibered algebraic semantics for general first-order logics. This framework includes a natural notion of substitution, which allows first-order logics to be considered as structural closure operators just as propositional logics are in abstract algebraic logic. We then establish an extension of the homomorphism theorem from universal algebra for generalized prop-categories and characterize two natural closure operators on the prop-categorical semantics. The first closes a class of structures (which are interpreted as morphisms of prop-categories) under the satisfaction of their common first-order theory and the second closes a class of prop-categories under their associated first-order consequence. It turns out that these closure operators have characterizations that closely mirror Birkhoff's characterization of the closure of a class of algebras under the satisfaction of their common equational theory and Blok and Jónsson's characterization of closure under equational consequence, respectively. These algebraic characterizations of the first-order closure operators are unique to the prop-categorical semantics. They do not have analogues, for example, in the Tarskian semantics for classical first-order logic. The prop-categories we consider are much more general than traditional intuitionistic prop-categories or triposes (i.e., topos representing indexed partially ordered sets). Nonetheless, to the best of our knowledge, our results are new, even when restricted to these special classes of prop-categories.     

SOME RESULTS ON UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTION

1. IntroductionLet G = (V, E) be an undirected graph. The open neighborhood N(v) of vertex v E Vis given by N(v) = {u E V: tv E E}. A total dominating function (TDF) of G is afunction f: V - [0, 11 such that Z f(u) 2 1 for each vertex v. A TDF f is minimaladN(~)(MTDF) if no function g < f is also a TDF of G. The illteger valued TDFs are preciselythe characteristic functions of total dominating sets of G (i.e., subset X G V such that anyv is adjacellt to at leajst one x E X). T…     

Some universal graphs

It is shown that various classes of graphs have universal elements. In particular, for eachn the class of graphs omitting all paths of lengthn and the class of graphs omitting all circuits of length at leastn possess universal elements in all infinite powers. Research partially supported by Hungarian Science Research Fund No. 1805. Research partially supported by NSERC of Canada Grant #A8948.     

On universal nilpotent groups

AbstractWe show that some classes of nilpotent groups have countable universal members and others do not.Presented by Bjarni Jónsson.     

Natural classes of universal algebras

A natural class of universal algebras is a class which is closed under isomorphism, subalgebras, disjoint suprema, and essential extensions. In suitable varieties, natural classes form a boolean lattice, and lead to a decomposition of any universal algebra into continuous molecular, discrete, and bottomless subalgebras.Dedicated to Professor John DaunsReceived March 29, 2004; accepted in final form May 20, 2004     

Positive universal classes in locally finite varieties

In some recent papers, the concept of a Q-independent sequence of finite lattices was utilized. We investigate this concept in universal algebras and apply it to positive universal classes in locally finite varieties, with emphasis on semilattices, lattices, and their expansions.     

A universal algebraic approach for conditional independence

In this paper we show that elementary properties of joint probability density functions naturally induce a universal algebraic structure suitable for studying probabilistic conditional independence (PCI) relations. We call this algebraic system the cain. In the cain algebra, PCI relations are represented in equational forms. In particular, we show that the cain satisfies the axioms of the graphoid of Pearl and Paz (Advances in artificial intelligence. North-Holland, Amsterdam, 1987) and the separoid of Dawid (Ann. Math. Artif. Intell. 32:335–372, 2001), these axiomatic systems being useful for general probabilistic reasoning.     

Banach spaces and groups — Order properties and universal models

We deal with two natural examples of almost-elementary classes: the class of all Banach spaces (over ℝ or ℂ) and the class of all groups. We show that both of these classes do not have the strict order property, and find the exact place of each one of them in Shelah’sSOP _n (strong order property of ordern) hierarchy. Remembering the connection between this hierarchy and the existence of universal models, we conclude, for example, that there are “few” universal Banach spaces (under isometry) of regular density characters. This publication is numbered 789 in the list of publications of Saharon Shelah. The research was supported by The Israel Science Foundation.     

Interpolation by universal,hypercyclic functions

In the present article we study an interpolation problem for classes of analytic functions, in a systematic manner. More precisely, we provide sufficient conditions so that proper and “big”, in the Baire category sense, subclasses of analytic functions have an interpolation property at an infinite set of points. We then apply our main theorems to several classes of universal, hypercyclic functions.     

Imaginary quadratic points on toric varieties via universal torsors

Inspired by a paper of Salberger we give a new proof of Manin’s conjecture for toric varieties over imaginary quadratic number fields by means of universal torsor parameterizations and elementary lattice point counting.     

On isometrically universal spaces, mappings, and actions of groups

In this paper we first consider some well-known classes of separable metric spaces which are isometrically ω-saturated (see [S.D. Iliadis, Universal Spaces and Mappings, North-Holland Mathematics Studies, vol. 198, Elsevier, 2005, xvi+559]) and, therefore, contain isometrically universal spaces. We put some problems concerning such spaces most of which are related with the properties of the isometrically universal Urysohn space. Furthermore, using the defined notions of isometrically universal mappings and G-spaces (which are analogies of the notion of isometrically universal spaces) we introduce the notions of an isometrically ω-saturated class of mappings and an isometrically ω-saturated class of G-spaces (in which there are “many” isometrically universal elements). We prove that all results of Sections 6.1 and 7.1 of [S.D. Iliadis, Universal Spaces and Mappings, North-Holland Mathematics Studies, vol. 198, Elsevier, 2005, xvi+559] can be reformulated for isometrically ω-saturated classes of spaces and G-spaces, respectively. In particular, we prove that if D and R are isometrically ω-saturated classes of spaces, then the class of all mappings with the domain in D and range in R is an isometrically ω-saturated class of mappings and, therefore, in this class there are isometrically universal elements. As a corollary of this result we have that since the class of all mappings is isometrically ω-saturated, in this class there are isometrically universal mappings. Similarly, if G is an arbitrary separable metric group and P is an isometrically ω-saturated class of spaces, then the class of all G-spaces (X,F), where X is an element of P, is an isometrically ω-saturated class of G-spaces and, therefore, in this class there are isometrically universal elements. In particular, for any separable metric group G, in the class of all G-spaces there are isometrically universal G-spaces. We also pose some problems concerning isometrically universal mappings and G-spaces some of which concern the Urysohn space.     

On universal formal power series

The point source of this work is Seleznev's theorem which asserts the existence of a power series which satisfies universal approximation properties in C^∗. The paper deals with a strengthened version of this result. We establish a double approximation theorem on formal power series using a weighted backward shift operator. Moreover we give strong conditions that guarantee the existence of common universal series of an uncountable family of weighted backward shift with respect to the simultaneous approximation. Finally we obtain results on admissible growth of universal formal power series. We especially prove that you cannot control the defect of analyticity of such a series even if there exist universal series in the well-known intersection of formal Gevrey classes.     

Implicitly equivalent universal algebras

The concept of implicit operation on pseudovarieties of semigroups goes back to Eilenberg and Schutzenberger [1]. The author in [2?C5] generalized this concept to other classes of algebras and established a connection between these operations and positively conditional termal functions in the case of uniform local finiteness of the algebras of the class in question. In this article we put forth the concept of an implicit operation for an arbitrary universal algebra, not necessarily locally finite, and establish a connection between these operations and infinite analogs of positively conditional terms, as well as ??-quasi-identities arising in the algebraic geometry of universal algebras. We also consider conditions for implicit equivalence of algebras to lattices, semilattices, and Boolean algebras.     

Hall's universal group has ample generic automorphisms

We show that the automorphism group of Hall's universal locally finite group has ample generics, that is, it admits comeager diagonal conjugacy classes in all dimensions. Consequently, it has the small index property, is not the union of a countable chain of non‐open subgroups, and has the automatic continuity property. Also, we discuss some algebraic and topological properties of the automorphism group of Hall's universal group. For example, we show that every generic automorphism of Hall's universal group is conjugate to all of its powers, and hence has roots of all orders.     

Canonical and existential groups in universal classes of Abelian groups

Universal classes of Abelian groups are classified in terms of sets of finitely generated groups closed with respect to the discrimination operator. The notions of a principal universal class and a canonical group for such a class are introduced. For any universal class K, the class K^ec of existentially closed groups generated by the universal theory of K is described. It is proved that K^ec is axiomatizable and, therefore, the universal theory of K has a model companion.     

Existential definability of modal frame classes

We prove an existential analogue of the Goldblatt-Thomason Theorem which characterizes modal definability of elementary classes of Kripke frames using closure under model theoretic constructions. The less known version of the Goldblatt-Thomason Theorem gives general conditions, without the assumption of first-order definability, but uses non-standard constructions and algebraic semantics. We present a non-algebraic proof of this result and we prove an analogous characterization for an alternative notion of modal definability, in which a class is defined by formulas which are satisfiable under any valuation (the so-called existential validity). Continuing previous work in which model theoretic characterization for this type of definability of elementary classes was proved, we give an analogous general result without the assumption of the first-order definability. Furthermore, we outline relationships between sets of existentially valid formulas corresponding to several well-known modal logics.     

Numerical experiments with universal barrier functions for cones of Chebyshev systems

Based on previous explicit computations of universal barrier functions, we describe numerical experiments for solving certain classes of convex optimization problems. The comparison is given of the performance of the classical affine-scaling algorithm with the similar algorithm built upon the universal barrier function.     

Short universal generators via generalized ratio-of-uniforms method

We use inequalities to design short universal algorithms that can be used to generate random variates from large classes of univariate continuous or discrete distributions (including all log-concave distributions). The expected time is uniformly bounded over all these distributions for a particular generator. The algorithms can be implemented in a few lines of high level language code.

     

Implicit operations on the categories of universal algebras

We present a series of concepts and prove some results on implicit operations on the various categories of universal algebras. This generalizes the previous results for pseudovarieties, pseudouniversal classes of algebras, positively conditional pseudovarieties, and so on.