Quotient-reflective and bireflective subcategories of the category of preordered sets

In previous papers, the notions of “closedness” and “strong closedness” in set-based topological categories were introduced. In this paper, we give the characterization of closed and strongly closed subobjects of an object in the category Prord of preordered sets and show that they form appropriate closure operators which enjoy the basic properties like idempotency (weak) hereditariness, and productivity.We investigate the relationships between these closure operators and the well-known ones, the up- and down-closures. As a consequence, we characterize each of T₀, T₁, and T₂ preordered sets and show that each of the full subcategories of each of T₀, T₁, T₂ preordered sets is quotient-reflective in Prord. Furthermore, we give the characterization of each of pre-Hausdorff preordered sets and zero-dimensional preordered sets, and show that there is an isomorphism of the full subcategory of zero-dimensional preordered sets and the full subcategory of pre-Hausdorff preordered sets. Finally, we show that both of these subcategories are bireflective in Prord.     

Some descriptive set theory and core models

We analyse the trees given by sharps for Π¹₂ sets via inner core models to give a canonical decomposition of such sets when a core model is Σ¹₃ absolute. This is by way of analogy with Solovay's analysis of Π¹₁ sets into ω₁ Borel sets — Borel in codes for wellorders. We find that Π¹₂ sets are also unions of ω₁ Borel sets — but in codes for mice and wellorders. We give an application of this technique in showing that if a core model, K, is Σ¹₃ absolute thenTheorem. Every real is in K iff every Π¹₃ set of reals contains a Π¹₃ singleton.     

Fall colouring of bipartite graphs and cartesian products of graphs

The question of whether a graph can be partitioned into k independent dominating sets, which is the same as having a fallk-colouring, is considered. For k=3, it is shown that a graph G can be partitioned into three independent dominating sets if and only if the cartesian product G□K₂ can be partitioned into three independent dominating sets. The graph K₂ can be replaced by any graph H such that there is a mapping f:Q_n→H, where f is a type-II graph homomorphism.The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of k, iterated cartesian products are considered, leading to a result that shows for what values of k the hypercubes can be partitioned into k independent dominating sets.     

Index sets in the arithmetical Hierarchy

We prove the following results: every recursively enumerable set approximated by finite sets of some set M of recursively enumerable sets with index set in π₂ is an element of M, provided that the finite sets in M are canonically enumerable. If both the finite sets in M and in M̄ are canonically enumerable, then the index set of M is in σ₂∩π₂ if and only if M consists exactly of the sets approximated by finite sets of M and the complement M̄ consists exactly of the sets approximated by finite sets of M̄. Under the same condition M or M̄ has a non-empty subset with recursively enumerable index set, if the index set of M is in σ₂∩π₂.If the finite sets in M are canonically enumerable, then the following three statements are equivalent: (i) the index set of M is in σ₂\π₂, (ii) the index set of M is σ₂-complete, (iii) the index set of M is in σ₂ and some sequence of finite sets in M approximate a set in M̄.Finally, for every n ⩾ 2, an index set in σ_n \ π_n is presented which is not σ_n-complete.     

Constructions of generalized Sidon sets

We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s₁+s₂,s_i∈S; such sets are called Sidon sets if g=2 and generalized Sidon sets if g?3. We extend to generalized Sidon sets the Sidon-set constructions of Singer, Bose, and Ruzsa. We also further optimize Kolountzakis’ idea of interleaving several copies of a Sidon set, extending the improvements of Cilleruelo, Ruzsa and Trujillo, Jia, and Habsieger and Plagne. The resulting constructions yield the largest known generalized Sidon sets in virtually all cases.     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.     

On the latticity of projection and antiprojection sets in Orlicz-Musielak spaces

We discuss the latticial structure of projection sets and antiprojection sets in Orlicz-Musielak spaces L ^Φ, with the distance given by modular ρ _Φ and classical F-norms generated by ρ _Φ. In particular, we show that the case of Amemiya F-norm is essentially different from others. This extends results given for sets of best approximants by Landers and Rogge, Kilmer and Kozlowski, and Mazzone.     

An improved characterization of normal sets and some counter-examples

We strengthen G. Rauzy’s characterization of normal sets by observing that the so-called elementary sets are precisely the F_σδ sets. This answers in the affirmative Rauzy’s open question: Are finite unions of normal sets necessarily normal? We also generalize the notion and characterization of normal sets from subsets of ? to subsets of ? ^d . This allows us to answer a question of E. Lesigne and M. Wierdl with the following construction: There exist two sequences of real numbersU=(u _n ) _nε?,V=(v _n ) _nε? such thatαU+βV=(αu _n +βv _n ) _nε? is uniformly distributed mod 1 if and only if exactly one of the real numbers α, β vanishes. Additionally, we provide the ‘ultimate’ counter-example (stronger than that of H. G. Meijer and R. Sattler) to a conjecture of S. Uchiyama by constructing a sequence of integersU which is u.d. in ? (i.e. u.d. modk for allk ε ?), but such that for all realα, αU is not u.d. mod 1.     

Maximal integral point sets in affine planes over finite fields

Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane over a finite field F_q, where the formally defined squared Euclidean distance of every pair of points is a square in F_q. It turns out that integral point sets over F_q can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case, integral point sets can be restated as cliques in Paley graphs of square order.In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over F_q for q≤47. Furthermore, we give two series of maximal integral point sets and prove their maximality.     

Subsets of ideal topological spaces

Properties of α-I-open sets, t-I-sets, strong β-I-open sets, S _βI-sets and S-I-sets in ideal topological spaces are discussed. Also, we define a new class of sets called semi-I-locally closed sets which contains the class of all I-locally closed sets and is contained in the class of all semilocally closed sets.     

Sacks forcing and the total failure of Martin's Axiom

Using side-by-side Sacks forcing, it is proved relatively consistent that the continuum is large and Martin's Axiom fails totally, that is, every c.c.c. space is the union of ?₁ nowhere dense sets (equivelently, if P is a nontrivial partial ordering with the countable chain condition, then there are ?₁ dense sets in P such that no filter in P meets them all).     

A fundamental inequality for the sum of sets of m-tuples

For n a positive integer and A₁, A₂, …, A_k sets of nonnegative integers, sufficient conditions are found which imply that the sum of the cardinalities of the sets $\text{{1, 2, …, n} ? A}{}_{\mathrm{i}}\text{(i = 1, 2, …, k)}$ does not exceed the cardinality of the intersection of {1, 2, …, n} and the number theoretic sum of the k sets. Some of the results are generalized to sets of m-tuples of nonnegative integers.     

On space coverings by unbounded convex sets

Let (C_i) be a sequence of closed convex subsets of Euclidean n-space Eⁿ. This paper is concerned with the problem of finding necessary and sufficient conditions that the sets C_i can be rearranged (by the application of rigid motions or translations) so as to cover all or almost all Eⁿ. Particular attention is paid to the problems that arise if the sets C_i are permitted to be unbounded. It is shown that under certain conditions this covering problem can be reduced to the already thoroughly investigated case of compact sets with bounded diameter set{d(C_i)}, and it is also proved that there are two additional covering possibilities if such a reduction is not possible.     

On 1-factorizability of Cayley graphs

In this paper we consider the existence of a 1-factorization of undirected Cayley graphs of groups of even order. We show that a 1-factorization exists for all generating sets for even order abelian groups, dihedral groups, and dicyclic groups and for all minimal generating sets for even order nilpotent groups and for D_m × Z_n. We also derive other results that are useful in considering specific Cayley graphs. These results support the conjecture that all Cayley graphs of groups of even order are 1-factorizable. If this is not the case the same result may hold for minimal generating sets.     

On box products

We prove two theorems about box products. The first theorem says that the box product of countable spaces is pseudonormal, i.e. any two disjoint closed sets one of which is countable can be separated by open sets. The second theorem says that assuming CH a certain uncountable box product is normal (i.e. <_ω1?□_α<ω1X_α where each Xα is a compact metric space).     

A Fubini theorem

Let I₀ be the σ-ideal of subsets of a Polish group generated by Borel sets which have perfectly many pairwise disjoint translates. We prove that a Fubini-type theorem holds between I₀ and the σ-ideals of Haar measure zero sets and of meager sets. We use this result to give a simple proof of a generalization of a theorem of Balcerzak-Ros?anowski-Shelah stating that I₀ on N² strongly violates the countable chain condition.     

On the closedness of the algebraic difference of closed convex sets

We characterize in a reflexive Banach space all the closed convex sets C₁ containing no lines for which the condition C₁^∞∩C₂^∞={0} ensures the closedness of the algebraic difference C₁−C₂ for all closed convex sets C₂. We also answer a closely related problem: determine all the pairs C₁, C₂ of closed convex sets containing no lines such that the algebraic difference of any sufficiently small uniform perturbations of C₁ and C₂ remains closed. As an application, we state the broadest setting for the strict separation theorem in a reflexive Banach space.     

Further remarks on enlargements of generalized topologies

The concepts of κ _μ -open set and enlargement κ of a generalized topology μ were introduced by Császár?[5]. In this paper, we introduce the concept of weak κ _μ -open sets induced by an enlargement κ of a generalized topology μ, and study some basic properties. We also introduce the concept of κ-regular open sets, and investigate the characterizations of weak κ _μ -open sets in terms of κ-regular open sets.     

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.