Discriminator positively complete classes of ternary logic

The article addresses the operator of positive closure on the set P _k of functions of k-valued logic. For each k ? 3, k ≠ 4, the set H _k of all homogeneous functions from P _k is proved to form an atom in the lattice of the positively closed classes from P _k . Also, we find all 17 positively closed classes from P ₃ containing the class H ₃ (i.e., discriminator positively closed classes). Positively generating systems of these classes are defined.     

Invariant sets and Lyapunov pairs for differential inclusions with maximal monotone operators

We give different conditions for the invariance of closed sets with respect to differential inclusions governed by a maximal monotone operator defined on Hilbert spaces, which is subject to a Lipschitz continuous perturbation depending on the state. These sets are not necessarily weakly closed as in [3], [4], while the invariance criteria are still written by using only the data of the system. So, no need to the explicit knowledge of neither the solution of this differential inclusion, nor the semi-group generated by the maximal monotone operator. These invariant/viability results are next applied to derive explicit criteria for a-Lyapunov pairs of lower semi-continuous (not necessarily weakly-lsc) functions associated to these differential inclusions. The lack of differentiability of the candidate Lyapunov functions and the consideration of general invariant sets (possibly not convex or smooth) are carried out by using techniques from nonsmooth analysis.     

On orders of closed classes containing a homogeneous switching function

Closed classes of k-valued logical functions containing the homogeneous switching function s are considered for any k. It is proved that any such closed class has an order not exceeding k. Examples are presented that demonstrate the upper estimate is attainable.     

Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.     

A criterion for positive completeness in ternary logic

The operator of positive closure is considered on the set P _k of functions of k-valued logic. Some positive complete systems of functions are defined. It is proved that every positive complete class of functions from P _k is positive generated by the set of all functions depending on at most k variables. For each k ? 3, the three families of positive precomplete classes are defined. It is shown that, for k = 3, the 10 classes of these families constitute a criterion system.     

Classes of functions closed with respect to a special superposition operation

Functions of the k-valued logic with k = 2 ^m , m > 1 are studied in the paper. Such functions are encoded in the binary numeric system and a special operation of binary superposition is defined. R is shown that the set of classes containing only the functions taking not more than two values and closed under the operations of binary superposition and adding of fictitious variables is countable.     

On a Sufficient Condition for Equality of Two Maximal Monotone Operators

We establish minimal conditions under which two maximal monotone operators coincide. Our first result is inspired by an analogous result for subdifferentials of convex functions. In particular, we prove that two maximal monotone operators T,S which share the same convex-like domain D coincide whenever $T(x)\cap S(x)\not=\emptyset $ for every x?∈?D. We extend our result to the setting of enlargements of maximal monotone operators. More precisely, we prove that two operators coincide as long as the enlargements have nonempty intersection at each point of their common domain, assumed to be open. We then use this to obtain new facts for convex functions: we show that the difference of two proper lower semicontinuous and convex functions whose subdifferentials have a common open domain is constant if and only if their ε-subdifferentials intersect at every point of that domain.     

On maximal and minimal elements of partially ordered sets of Boolean degrees

The paper addresses the “weakest” algorithmic reducibility—Boolean reducibility. Under study are the partially ordered sets of Boolean degrees L _Q corresponding to the various closed classes of Boolean functions Q. The set L _Q is shown to have no maximal elements for many closed classes Q. Some examples are given of a sufficiently large classes Q for which L _Q contains continuum many maximal elements. It is found that the sets of degrees corresponding to the closed classes T ₀₁ and SM contain continuum many minimal elements.     

Transformations of discrete closure systems

Discrete systems such as sets, monoids, groups are familiar categories. The internal structure of the latter two is defined by an algebraic operator. In this paper we concentrate on discrete systems that are characterized by unary operators; these include choice operators σ, encountered in economics and social theory, and closure operators φ, encountered in discrete geometry and data mining. Because, for many arbitrary operators α, it is easy to induce a closure structure on the base set, closure operators play a central role in discrete systems. Our primary interest is in functions f that map power sets 2 ^U into power sets 2 ^U′, which are called transformations. Functions over continuous domains are usually characterized in terms of open sets. When the domains are discrete, closed sets seem more appropriate. In particular, we consider monotone transformations which are “continuous”, or “closed”. These can be used to establish criteria for asserting that “the closure of a transformed image under f is equal to the transformed image of the closure”. Finally, we show that the categories MCont and MClo of closure systems with morphisms given by the monotone continuous transformations and monotone closed transformations respectively have concrete direct products. And the supercategory Clo of MClo whose morphisms are just the closed transformations is shown to be cartesian closed.     

Some properties of P-sets of finite-automaton functions

Classes of finite-automation functions are considered in the paper and each state of those functions realizes a function from some closed class D of the k-valued logic (P-sets). It is proved that there exists continuum of precomplete classes C containing an arbitrary P-set. The problem of existence of a completeness criterion for systems containing P-sets is also considered.     

An explicit example of a maximal 3-cyclically monotone operator with bizarre properties

Subdifferential operators of proper convex lower semicontinuous functions and, more generally, maximal monotone operators are ubiquitous in optimization and nonsmooth analysis. In between these two classes of operators are the maximal n$n$-cyclically monotone operators. These operators were carefully studied by Asplund, who obtained a complete characterization within the class of positive semidefinite (not necessarily symmetric) matrices, and by Voisei, who presented extension theorems à la Minty.     

On maximal subalgebras of the algebras of unary recursive functions

Under consideration are the algebras of unary functions with supports in countable primitively recursively closed classes and composition operation. Each algebra of this type is proved to have continuum many maximal subalgebras including the set of all unary functions of the class ε ² of the Grzegorczyk hierarchy.     

Examples of discontinuous maximal monotone linear operators and the solution to a recent problem posed by B.F. Svaiter

In this paper, we give two explicit examples of unbounded linear maximal monotone operators. The first unbounded linear maximal monotone operator S on ?² is skew. We show its domain is a proper subset of the domain of its adjoint S^∗, and −S^∗ is not maximal monotone. This gives a negative answer to a recent question posed by Svaiter. The second unbounded linear maximal monotone operator is the inverse Volterra operator T on L²[0,1]. We compare the domain of T with the domain of its adjoint T^∗ and show that the skew part of T admits two distinct linear maximal monotone skew extensions. These unbounded linear maximal monotone operators show that the constraint qualification for the maximality of the sum of maximal monotone operators cannot be significantly weakened, and they are simpler than the example given by Phelps-Simons. Interesting consequences on Fitzpatrick functions for sums of two maximal monotone operators are also given.     

Genericity and existence of a minimum for scalar integral functionals

This paper is concerned with the existence of a minimum in a Sobolev space for the functional $$F_g (x): = \int_0^T {g(x(t)){\text{ }}dt + \int_0^T {h(x'(t)){\text{ }}dt,{\text{ }}x(0) = a,{\text{ }}x(T) = b,} }$$ wherea,b are real numbers,g is a continuous map, andh is lower semicontinuous, satisfying adequate growth conditions. As shown by Cellina and Mariconda, there exists a dense subset of the space of continuous functions bounded below such that, forg in this subset, the above functional attains its minimum no matter whichh is used. This subset contains in particular the monotone maps, as shown by Marcellini, and the concave maps, as shown by Cellina and Colombo. Our aim is twofold: first to show that this subset, although dense, is meager in the sense of the Baire category; and second to show that it contains a class of functions which we call concave-monotone, because it generalizes both the classes of concave and of monotone functions.     

A Characterization of Maximal Monotone Operators

It is shown that a set-valued map $M:\mathbb{R}^{q} \rightrightarrows \mathbb{R}^{q}$ is maximal monotone if and only if the following five conditions are satisfied: (i) M is monotone; (ii) M has a nearly convex domain; (iii) M is convex-valued; (iv) the recession cone of the values M(x) equals the normal cone to the closure of the domain of M at x; (v) M has a closed graph. We also show that the conditions (iii) and (v) can be replaced by Cesari’s property (Q).     

Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation

Convergence properties of sequences of continuous functions, with kth order divided differences bounded from above or below, are studied. It is found that for such sequences, convergence in a “monotone norm” (e.g., L_p) on [a, b] to a continuous function implies uniform convergence of the sequence and its derivatives up to order k ? 1 (whenever they exist), in any closed subinterval of [a, b]. Uniform convergence in the closed interval [a, b] follows from the boundedness from below and above of the kth order divided differences. These results are applied to the estimation of the degree of approximation in Monotone and Restricted Derivative approximation, via bounds for the same problems with only one restricted derivative.     

On monotone functions of tree structures

Let T be a rooted tree structure with n nodes a₁,…,a_n. A function f: {a₁,…,a_n} into {1 < ? < k} is called monotone if whenever a_i is a son of a_j, then f(a_i) ≥ f(a_j). The average number of monotone bijections is determined for several classes of tree structures. If k is fixed, for the average number of monotone functions asymptotic equivalents of the form c · ?^?nn^{?$\text{3}\text{2}$} (n → ∞) are obtained for several classes of tree structures.     

Monotone thematic factorizations of matrix functions

We continue the study of the so-called thematic factorizations of admissible very badly approximable matrix functions. These factorizations were introduced by V.V. Peller and N.J. Young for studying superoptimal approximation by bounded analytic matrix functions. Even though thematic indices associated with a thematic factorization of an admissible very badly approximable matrix function are not uniquely determined by the function itself, R.B. Alexeev and V.V. Peller showed that the thematic indices of any monotone non-increasing thematic factorization of an admissible very badly approximable matrix function are uniquely determined. In this paper, we prove the existence of monotone non-decreasing thematic factorizations for admissible very badly approximable matrix functions. It is also shown that the thematic indices appearing in a monotone non-decreasing thematic factorization are not uniquely determined by the matrix function itself. Furthermore, we show that the monotone non-increasing thematic factorization gives rise to a great number of other thematic factorizations.     

On the degree theory for general mappings of monotone type

Degree theory has been developed as a tool for checking the solution existence of nonlinear equations. In his classic paper published in 1983, Browder developed a degree theory for mappings of monotone type f+T, where f is a mapping of class ₊(S) from a bounded open set Ω in a reflexive Banach space X into its dual X^∗, and T is a maximal monotone mapping from X into X^∗. This breakthrough paved the way for many applications of degree theoretic techniques to several large classes of nonlinear partial differential equations. In this paper we continue to develop the results of Browder on the degree theory for mappings of monotone type f+T. By enlarging the class of maximal monotone mappings and pseudo-monotone homotopies we obtain some new results of the degree theory for such mappings.