On generalized separating hash families

Separating hash families are useful combinatorial structures which are studied in a general form in this paper. Necessary and sufficient conditions for the existence of certain types of generalized hash functions are considered.     

Degrees of logics with Henkin quantifiers in poor vocabularies

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L* is of degree 0. We show that the same holds also for some weaker logics like L(H) and L(E). We show that each logic of the form L^(k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L^(k)(Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H₄) and L(F₂) of Krynicki and M. Mostowski from [KM92].Mathematics Subject Classification (2000): 03C80, 03D35, 03B25Revised version: 28 August 2003     

Local Density of Kleene Degrees

Concerning Post's problem for Kleene degrees and its relativization, Hrbacek showed in [1] and [2] that if V = L, then Kleene degrees of coanalytic sets are dense, and then for all K ?^ωω, there are N₁ sets which are Kleene semirecursive in K and not Kleene recursive in each other and K. But the density of Kleene semirecursive in K Kleene degrees is not obtained from these theorems. In this note, we extend these theorems by showing that if V = L, then for all K ? ^ωω, Kleene semirecursive in K Kleene degrees are dense above K.     

A Note on Closed Degrees of Difficulty of the Medvedev Lattice

We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty. Mathematics Subject Classification: 03D30.     

On the r.e. predecessors of d.r.e. degrees

Let d be a Turing degree containing differences of recursively enumerable sets (d.r.e.sets) and R[d] be the class of less than d r.e. degrees in whichd is relatively enumerable (r.e.). A.H.Lachlan proved that for any non-recursive d.r.e. d R[d] is not empty. We show that the r.e. degree defined by Lachlan for a d.r.e.set d is just the minimum degree in which D is r.e. Then we study for a given d.r.e. degree d class R[d] and show that there exists a d.r.e.d such that R d] has a minimum element 0. The most striking result of the paper is the existence of d.r.e. degrees for which R[d] consists of one element. Finally we prove that for some d.r.e. d R[d] can be the interval [a,b] for some r.e. degrees a,b, a b d. Received: 17 January 1996     

Bounds on degrees of p-adic separating polynomials

We study a discrete optimization problem introduced by Babai, Frankl, Kutin, and Štefankovi? (2001), which provides bounds on degrees of polynomials with p-adically controlled behavior. Such polynomials are of particular interest because they furnish bounds on the size of set systems satisfying Frankl-Wilson-type conditions modulo prime powers, with lower degree polynomials providing better bounds. We elucidate the asymptotic structure of solutions to the optimization problem, and we also provide an improved method for finding solutions in certain circumstances.     

Characterization of separating couples

Let A, B be two archimedean ℓ-algebras and let U,V be two positive linear maps from A to B. We call that the couple (U,V) is separating with respect to A and B if |a||b| = 0 in A implies |U (a)||V (b)| = 0 in B. In this paper, we prove that if A is an f-algebra with unit elment e, if B is an ℓ-algebra and if (U,V) is a separating couple with respect to A and B then (U ^∼∼,V ^∼∼), where U ^∼∼ (resp V ^∼∼) is the bi-adjoint of U (resp of V), is again a separating couple with respect to the order continuous order biduals (A′)′ _n and (B′)′ _n of A and B respectively furnished with their Arens products respectively. Moreover, in the case where B′ separates the points of B, we give a characterization of any separating couple with respect to A and B.      

DP-4-colorability of two classes of planar graphs

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced by Dvo?ák and Postle in 2017. In this paper, we prove that every planar graph without 4-cycles adjacent to $k$-cycles is DP-4-colorable for $k=5$ and 6. As a consequence, we obtain two new classes of 4-choosable planar graphs. We use identification of vertices in the proof, and actually prove stronger statements that every pre-coloring of some short cycles can be extended to the whole graph.     

A bound on the size of separating hash families

The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type.     

Factorizations of fitting classes

In this paper, we prove that there exists a infinite set of non-trivial local Fitting classes every element in which is decomposable as a non-trivial product of Fitting classes such that every factor in the product is neither local nor a formation. In particular, this gives a positive answer to Problem 11.25 a) in The Kourovka Notebook.     

On convergence determining and separating classes of functions

Herein, we generalize and extend some standard results on the separation and convergence of probability measures. We use homeomorphism-based methods and work on incomplete metric spaces, Skorokhod spaces, Lusin spaces or general topological spaces. Our contributions are twofold: we dramatically simplify the proofs of several basic results in weak convergence theory and, concurrently, extend these results to apply more immediately in a number of settings, including on Lusin spaces.     

New classes of generalized monotonicity

This paper introduces new classes of generalized monotone functions and relates them to classes previously introduced.This work was supported by NSERC Grant A5789     

Infima of d.r.e. degrees

Lachlan observed that the infimum of two r.e. degrees considered in the r.e. degrees coincides with the one considered in the D₂⁰{\Delta_2^0} degrees. It is not true anymore for the d.r.e. degrees. Kaddah proved in (Ann Pure Appl Log 62(3):207–263, 1993) that there are d.r.e. degrees a, b, c and a 3-r.e. degree x such that a is the infimum of b, c in the d.r.e. degrees, but not in the 3-r.e. degrees, as a < x < b, c. In this paper, we extend Kaddah’s result by showing that such a structural difference occurs densely in the r.e. degrees. Our result immediately implies that the isolated 3-r.e. degrees are dense in the r.e. degrees, which was first proved by LaForte.     

Isolated maximal d.r.e. degrees

There are very few results about maximal d.r.e. degrees as the construction is very hard to work with other requirements. In this paper we show that there exists an isolated maximal d.r.e. degree. In fact, we introduce a closely related notion called $(m,n)$-cupping degree and show that there exists an isolated $(2,\omega )$-cupping degree, and there exists a proper $(2,1)$-cupping degree. It helps understanding various degree structures in the Ershov Hierarchy.     

Graphs realised by r.e. equivalence relations

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.     

Traces of functions of generalized Sobolev classes

Considering the Sobolev type function classes on a metric space equipped with a Borel measure we address the question of compactness of embeddings of the space of traces into Lebesgue spaces on the sets of less “dimension.” Also, we obtain compactness conditions for embeddings of the traces of the classical Sobolev spaces W _p ¹ on the “zero” cusp with a Hölder singularity at the vertex.     

A Splitting with Infimum in the d‐c. e. Degrees

In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d‐c. e. degrees.     

Axiomatizability and completeness of some classes of partially ordered polygons

We study partially ordered monoids over which a class of free (over sets and over posets), projective, and (strongly, weakly) flat partially ordered polygons is axiomatizable, complete, or model complete. Similar issues for polygons were dealt with in papers by V. Gould and A. Stepanova. Supported by the Council for Grants (under RF President) and State Aid of Leading Scientific Schools (grant NSh-2810.2008.1). Translated from Algebra i Logika, Vol. 48, No. 1, pp. 90–121, January–February, 2009.     

两类锥广义伪不变凸性的刻画

研究了一类非光滑带约束的向量优化问题. 首先引入锥意义下的 FJ-伪不变凸I(II)型的概念; 然后将经典的Gordan择一定理推广到了带锥的情形,并在此基础上利用FJ向量驻点与(弱)有效解间的关系, 研究了锥FJ-伪不变凸I(II)型的等价刻画.