Uniqueness of minimal coverings of maximal partial clones

A partial function f on a k-element set E _k is a partial Sheffer function if every partial function on E _k is definable in terms of f. Since this holds if and only if f belongs to no maximal partial clone on E _k , a characterization of partial Sheffer functions reduces to finding families of minimal coverings of maximal partial clones on E _k . We show that for each k ≥ 2, there exists a unique minimal covering.     

Ultraproducts of continuous posets

We consider local partial clones defined on an uncountable set E having the form Polp(\({\mathfrak{R}}\)), where \({\mathfrak{R}}\) is a set of relations on E. We investigate the notion of weak extendability of partial clones of the type Polp(\({\mathfrak{R}}\)) (in the case of E countable, this coincides with the notion of extendability previously introduced by the author in 1987) which allows us to expand to uncountable sets results on the characterization of Galois-closed sets of relations as well as model-theoretical properties of a relational structure \({\mathfrak{R}}\). We establish criteria for positive primitive elimination sets (sets of positive primitive formulas over \({\mathfrak{R}}\) through which any positive primitive definable relation over \({\mathfrak{R}}\) can be expressed without existential quantifiers) for finite \({\mathfrak{R}}\) as well as for \({\mathfrak{R}}\) having only finite number of positive primitive definable relations of any arity. Emphasizing the difference between countable and uncountable sets, we show that, unlike in the countable case, the characterization of Galois-closed sets InvPol(\({\mathfrak{R}}\)) (that is, all relations which are invariant under all operations from the clone Pol(\({\mathfrak{R}}\)) defined on an uncountable set) cannot be obtained via the application of finite positive primitive formulas together with infinite intersections and unions of updirected sets of relations from \({\mathfrak{R}}\).     

Clones satisfying the term condition

The term condition considered here is the property of an operation ? that holds iff ? and all of its variants obtained by permuting the variables satisfy (for all x,y,u₁,…v₁,…)$\text{?(x,u}{}_1\text{,…) = ?(x,v}{}_1\text{…)??(y,u}{}_1\text{,…) = ?(y,v)}{}_1\text{,…)}$. Clones consisting entirely of operations satisfying this term condition are called TC clones; algebras whose clone of term operations is a TC clone are called TC algebras; varieties such that every algebra in the variety is a TC algebra are called TC varieties. The paper is a systematic study of these notions, giving primary attention to operations and algebras on finite base sets, and to varieties generated by finite algebras. It is proved, among other results, that the number of n-ary TC operations on a k-element set is logarithmically asymptotic to k^(k?1)n when n increases without bound and k is held fixed; that there exist only countably many TC clones on any finite set; that the maximal TC clones on a finite set are finite in number (for each set). Some necessary conditions for an algebra to generate a TC variety are given, also some sufficient conditions.     

The generation of clones with majority operations

A theorem by Baker and Pixley implies that any clone on a finite set is finitely generated if it contains a near-unanimity operation. This raises the question of what arity the generating operations must have. In this paper, we solve the last open bits of this problem for the majority case by showing that 5 and 8 are the smallest integers k such that every clone with a majority operation on a 3 and 4-element set, respectively, is generated by its k-ary part.     

Binary central relations and submaximal clones determined by nontrivial equivalence relations

Let k ≥ 3, θ a nontrivial equivalence relation on E _k = {0, . . . ,k – 1}, and ρ a binary central relation on E _k (a reflexive graph with a vertex having E _k as its neighborhood). It is known that the clones Pol θ and Pol ρ (of operations on E _k preserving θ and ρ, respectively) are maximal clones; i.e., covered by the largest clone in the inclusion-ordered lattice of clones on E _k . In this paper, we give the classification of all binary central relations ρ on E _k such that the clone Pol θ ∩ Pol ρ is maximal in Pol θ.     

Exceptional sets related to Hayman's alternative

Let E be a subset of the complex plane C consisting of a countable set of points tending to ∞ and let k?1 be an integer. We derive a spacing condition (dependent on k) on the points of E which ensures that, if f is a function meromorphic in C with sufficiently large Nevanlinna deficiency at the poles, then either f takes every complex value infinitely often, or the kth derivative f(k) takes every non-zero complex value infinitely often, in C−E. This improves a previous result of Langley.     

The join of two minimal clones and the meet of two maximal clones

We construct two minimal clones on any finite set such that the join of the two clones contains all operations. Dually, we exhibit two maximal clones on any finite set with at least three elements such that the intersection of the two clones is the trivial clone containing projections only. Received October 20, 1998; accepted in final form December 16, 1998.     

Uncountable Homogeneous Partial Orders

A partially ordered set (P, ≤) is called k‐homogeneous if any isomorphism between k‐element subsets extends to an automorphism of (P, ≤). Assuming the set‐theoretic assumption ⋄(ϰ₁), it is shown that for each k, there exist partially ordered sets of size ϰ₁ which embed each countable partial order and are k‐homogeneous, but not (k + 1)‐homogeneous. This is impossible in the countable case for k ≥ 4.     

Almost maximal spaces

A topological space X is called almost maximal if it is without isolated points and for every x∈X, there are only finitely many ultrafilters on X converging to x. We associate with every countable regular homogeneous almost maximal space X a finite semigroup Ult(X) so that if X and Y are homeomorphic, Ult(X) and Ult(Y) are isomorphic. Semigroups Ult(X) are projectives in the category F of finite semigroups. These are bands decomposing into a certain chain of rectangular components. Under MA, for each projective S in F, there is a countable almost maximal topological group G with Ult(G) isomorphic to S. The existence of a countable almost maximal topological group cannot be established in ZFC. However, there are in ZFC countable regular homogeneous almost maximal spaces X with Ult(X) being a chain of idempotents.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

On k-graceful,locally finite graphs

While a finite, bipartite graph G can be k-graceful for every k ≥ 1, a finite nonbipartite G can be k-graceful for only finitely many values of k. An improved bound on such possible values of k is presented. Definitions are extended to infinite graphs, and it is shown that if G is locally finite and vertex set V(G) and edge set E(G) are countably infinite, then for each k ≥ 1 the graph G has a k-graceful numbering h mapping V(G) onto the set of nonnegative integers.     

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.     

Inadmissible forcing

A structure is E-closed if it is closed under all partial E-recursive functions from V into V, a set theoretic extension of Kleene's partial recursive functions of finite type in the normal case. Let L(κ) be E-closed and ∑₁ inadmissible. Then L(κ) has reflection properties useful in the study of generic extensions of L(κ). Every set generic extension of L(κ) via countably closed forcing conditions is E-closed. A class generic construction shows: if L(κ) is countable, and inside L(κ) the greatest cardinal gc(κ), has uncountable cofinality, then there exists a T ⊆ gc(κ) such that L(κ, T) = E(T), the least E-closed set with T as a member. A partial converse is obtained via a selection theorem that implies E(X) is ∑₁ admissible when X is a set of ordinals and the greatest cardinal in the sense of E(X) has countable cofinality in E(X).     

Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity

Every clone of functions comes naturally equipped with a topology, the topology of pointwise convergence. A clone \(\mathfrak {C}\) is said to have automatic homeomorphicity with respect to a class \(\mathcal {K}\) of clones, if every clone isomorphism of \(\mathfrak {C}\) to a member of \(\mathcal {K}\) is already a homeomorphism (with respect to the topology of pointwise convergence). In this paper we study automatic homeomorphicity properties for polymorphism clones of countable homogeneous relational structures. Besides two generic criteria for the automatic homeomorphicity of the polymorphism clones of homogeneous structures we show that the polymorphism clone of the generic poset with strict ordering has automatic homeomorphicity with respect to the class of polymorphism clones of countable \(\omega \)-categorical structures. Our results extend and generalize previous results by Bodirsky, Pinsker, and Pongrácz.     

Multiplicative spectrum of ultrametric Banach algebras of continuous functions

Let K be an ultrametric complete field and let E be an ultrametric space. Let A be the Banach K-algebra of bounded continuous functions from E to K and let B be the Banach K-algebra of bounded uniformly continuous functions from E to K. Maximal ideals and continuous multiplicative semi-norms on A (resp. on B) are studied by defining relations of stickiness and contiguousness on ultrafilters that are equivalence relations. So, the maximal spectrum of A (resp. of B) is in bijection with the set of equivalence classes with respect to stickiness (resp. to contiguousness). Every prime ideal of A or B is included in a unique maximal ideal and every prime closed ideal of A (resp. of B) is a maximal ideal, hence every continuous multiplicative semi-norms on A (resp. on B) has a kernel that is a maximal ideal. If K is locally compact, every maximal ideal of A (resp. of B) is of codimension 1. Every maximal ideal of A or B is the kernel of a unique continuous multiplicative semi-norm and every continuous multiplicative semi-norm is defined as the limit along an ultrafilter on E. Consequently, on A as on B the set of continuous multiplicative semi-norms defined by points of E is dense in the whole set of all continuous multiplicative semi-norms. Ultrafilters show bijections between the set of continuous multiplicative semi-norms of A, Max(A) and the Banaschewski compactification of E which is homeomorphic to the topological space of continuous multiplicative semi-norms. The Shilov boundary of A (resp. B) is equal to the whole set of continuous multiplicative semi-norms.     

Meet-irreducible submaximal clones determined by nontrivial equivalence relations

Let θ and ρ be a nontrivial equivalence relation and a binary relation on a finite set A, respectively. It is known from Rosenberg’s classification theorem (1965) that the clone Pol θ, which consists of all operations on A that preserve θ, is among the maximal clones on A. In the present paper, we find all binary relations ρ such that the clone Pol ρ is a meet-irreducible maximal subclone of Pol θ.     

Non-regular simplicial matroids

Let (ks) denote the set of all k-element-subsets of a finite set S. A k-simplical matroid on a subset E of (ks) is a binary matroid the circuit of which are simplicial complexes {X1,…Xm} ? E with boundary 0 (mod 2). The k-simplical matroid on (ks) is called the full simplicial matroid Gk(S). The polygon matroid on the edges of a finite graph is 2-simplicial. Polygon-matroids and their duals are regular. The dual of Gk(S) is Gn?k(S) if the cardinnlity of S is n. More details on simplicial matroids can be found in [3, Chapter 6] and also in [4, pp. 180–181].Welsh asked if every simplicial matroid is regular. We prove that this is not the case, for all full k-simplicial matroids Gk(S) with 3?k?n?3 are non-regular (n is the cardinality of S). This result has also been proved σy R. Cordovil and M. Las Vergnas recently. Their proof is different from our proof, which is somewhat shorter.     

Reflection and forcing in E-recursion theory

E-recursive enumerability is compared via forcing to Σ₁ definability. It is shown that for every countable E-closed ordinal κ there is a set of reals, X, so that L_κ[X] is the least E-closed structure over X.