On the normal completion of a Boolean algebra

A familiar construction for a Boolean algebra A is its normal completion, given by its normal ideals or, equivalently, the intersections of its principal ideals, together with the embedding taking each element of A to its principal ideal. In the classical setting of Zermelo-Fraenkel set theory with Choice, is characterized in various ways; thus, it is the unique complete extension of A in which the image of A is join-dense, the unique essential completion of A, and the injective hull of A.Here, we are interested in characterizing the normal completion in the constructive context of an arbitrary topos. We show among other things that it is, even at this level, the unique join-dense, or alternatively, essential completion. En route, we investigate the functorial properties of and establish that it is the reflection of A, in the category of Boolean homomorphisms which preserve all existing joins, to the complete Boolean algebras. In this context, we make crucial use of the notion of a skeletal frame homomorphism.     

Tensor products for bounded posets revisited

The category BPC of bounded posets and so-called cut continuous maps has concrete products, and the Dedekind-MacNeille completion gives rise to a reflector from BPC to the full subcategory CLJ of complete lattices and join-preserving maps. Like CLJ, the category BPC has a functional internal hom-functor in the sense of Banaschewski and Nelson. But, in contrast to CLJ, arbitrary universal bimorphisms do not exist in BPC. However, a natural tensor product is defined in terms of so-called G-ideals, such that the desired universal property holds at least for BPC-morphisms into complete lattices. Moreover, this tensor product is associative and distributes over (cartesian) products. The tensor product of an arbitrary family of bounded posets is isomorphic to that of their normal completions; hence, restricted to the subcategory CLJ, it agrees with the usual one.     

On the category Q-Mod

In this paper we consider the category Q-Mod of modules over a given quantale Q. The paper is motivated by constructions and results from the category of modules over a ring. We show that the category Q-Mod is monadic, consider its relation to the category Q-Top of Q-topological spaces and generalize a method of completion of partially ordered sets. Received December 20, 2005; accepted in final form December 4, 2006.     

Tensor products of contexts and complete lattices

Although the categoryCLC of complete lattices and complete homomorphisms does not possess arbitrary coproducts, we show that the tensor product introduced by Wille has the universal property of coproducts for so-called distributing families of morphisms (and only for these). As every family of morphisms into a completely distributive lattice is distributing, this includes the known fact that in the category of completely distributive lattices, arbitrary coproducts exist and coincide with the tensor products. Since the definition of tensor products is based on the notion of contexts and their concept lattices, many results on tensor products extend from complete lattices to contexts. Thus we introduce two kinds of tensor products for arbitrary families of contexts, a partial and a complete one, and establish universal properties of these tensor products.Presented by B. Jonsson.     

CONCRETE CATEGORIES FOR WHICH FIBRE COMPLETIONS INDUCE TOPOLOGICAL COMPLETIONS

Abstract

Every topological category over an arbitrary base category X may be considered as a category of T-models with respect to some theory (i.e., functor) T from X into a category of complete lattices. Using this model-theoretic correspondence as our basic tool, we study initial and final completions of (co)fibration complete categories. For an arbitrary concrete category (A, U) over X, the process of order-theoretically completing each fibre does not usually yield an initial/final completion of (A, U). It is shown in this paper that for concrete categories which are assumed to be fibration and/or cofibration complete, initial and final completions can be constructed by completing the fibres. These completions are further shown to exhibit some interesting external properties.     

Proof of a conjecture on partitions of a Boolean lattice

Let n and c be positive integers. We show that if n is sufficiently large given c then the Boolean lattice consisting of all subsets of an n-element set can be partitioned into chains of size c except for at most c — 1 elements which also form a chain. This settles a conjecture of Griggs.     

DISCONNECTEDNESS CLASSES

Abstract

Let X be an (E, M)-category for sinks. A notion of disconnectedness with respect to a closure operator C on X and to a class of X-monomorphisms N is introduced. This gives rise to the notion of N-disconnectedness class, a characterization of which is presented in a category with a terminal object. Some examples are provided.     

The convexity lattice of a poset

The authors investigate the lattice Co(P) of convex subsets of a general partially ordered set P. In particular, they determine the conditions under which Co(P) and Co(Q) are isomorphic; and give necessary and sufficient conditions on a lattice L so that L is isomorphic to Co(P) for some P.     

ORDER EXTENSIONS AS ADJOINT FUNCTORS

Abstract

A standard extension (resp. standard completion) is a function Z assigning to each poset P a (closure) system ZP of subsets such that x ? y iff x belongs to every Z ε ZP with y ε Z. A poset P is Z -complete if each Z ε 2P has a join in P. A map f: P → P′ is Z—continuous if f^?1 [Z′] ε ZP for all Z′ ε ZP′, and a Z—morphism if, in addition, for all Z ε ZP there is a least Z′ ε ZP′ with f[Z] ? Z′. The standard extension Z is compositive if every map f: P → P′ with {x ε P: f(x) ? y′} ε ZP for all y′ ε P′ is Z -continuous. We show that any compositive standard extension Z is the object part of a reflector from IP_Z, the category of posets and Z -morphisms, to IR_Z, the category of Z -complete posets and residuated maps. In case of a standard completion Z, every Z -continuous map is a Z -morphism, and IR2 is simply the category of complete lattices and join—preserving maps. Defining in a suitable way so-called Z -embeddings and morphisms between them, we obtain for arbitrary standard extensions Z an adjunction between IP_Z and the category of Z -embeddings. Many related adjunctions, equivalences and dualities are studied and compared with each other. Suitable specializations of the function 2 provide a broad spectrum of old and new applications.     

How small can a lattice of order-dimension n be?

The aim of this paper is to study the order-dimension of partition lattices and linear lattices. Our investigations were motivated by a question due to Bill Sands: For a lattice L, does dim L=n always imply |L|≥2 ⁿ ? We will answer this question in the negative since both classes of lattices mentioned above form counterexamples. In the case of the partition lattices, we will determine the dimension up to an absolute constant. For the linear lattice over GF(2), L _n , we determine the dimension up to a factor C/n for an absolute constant C.     

Interval dimension and MacNeille completion

Equality between the interval dimensions of a poset and its MacNeille completion, announced in [7], has been obtained by the authors as a byproduct of their study of Galois lattices in [8]. The purpose of this note is to give a direct proof, similar to the classical proof of Baker's result stating that the dimension (in the Dushnik-Miller sense) of a poset and its MacNeille completion are the same.Supported by French PRC Math-Info.     

The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.     

The order dimension of multinomial lattices

Using the notion of Ferrers dimension of incidence structures, the order dimension of multi-nomial lattices (i.e. lattices of multi-permutations) is determined. In particular, it is shown that the lattice of all permutations on ann-element set has dimensionn–1.     

A structure theorem for posets admitting a “strong” chain partition:: A generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities)

Suppose a finite poset P is partitioned into three non-empty chains so that, whenever p, q∈P lie in distinct chains and p<q, then every other element of P is either above p or below q.In 1985, the following conjecture was made by David Daykin and Jacqueline Daykin: such a poset may be decomposed into an ordinal sum of posets such that, for 1?i?n, one of the following occurs:

(1)

R_i is disjoint from one of the chains of the partition; or

(2)

if p, q∈R_i are in distinct chains, then they are incomparable.

The conjecture is related to a question of R. L. Graham's concerning probability correlation inequalities for linear extensions of finite posets.In 1996, a proof of the Daykin-Daykin conjecture was announced (by two other mathematicians), but their proof needs to be rectified.In this note, a generalization of the conjecture is proven that applies to finite or infinite posets partitioned into a (possibly infinite) number of chains with the same property. In particular, it is shown that a poset admits such a partition if and only if it is an ordinal sum of posets, each of which is either a width 2 poset or else a disjoint sum of chains. A forbidden subposet characterization of these partial orders is also obtained.     

The positive definite completion problem revisited

In [R. Grone, C.R. Johnson, E. Sa, H. Wolkowicz, Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58 (1984) 109-124] the positive definite (semi-) completion problem in which the underlying graph is chordal was solved. For the positive definite case, the process was constructive and the completion was obtained by completing the partial matrix an entry at a time. For the positive semidefinite case, they obtained completions of a particular sequence of partial positive definite matrices with the same underlying graph and noted that there is a convergent subsequence of these completions that converges to the desired completion. Here, in the chordal case, we provide a constructive solution, based entirely on matrix/graph theoretic methods, to the positive (semi-)definite completion problem. Our solution associates a specific tree (called the “clique tree” [C.R. Johnson, M. Lundquist, Matrices with chordal inverse zero-patterns, Linear and Multilinear Algebra 36 (1993) 1-17]) with the (chordal) graph of the given partial positive (semi-)definite matrix. This tree structure allows us to complete the matrix a “block at a time” as opposed to an “entry at a time” (as in Grone et al. (1984) for the positive definite case). In Grone et al. (1984), using complex analytic techniques, the completion for the positive definite case was shown to be the unique determinant maximizing completion and was shown to be the unique completion that has zeros in its inverse in the positions corresponding to the unspecified entries of the partial matrix. Here, we show the same using only matrix/graph theoretic tools.     

A note on admissibility of closed Galois structures

Abstract

We present a new admissibility theorem for Galois structures in the sense of G. Janelidze. It applies to relative exact categories satisfying a suitable relative modularity condition, and extends the known admissibility theorem in the theory of generalized central extensions. We also show that our relative modularity condition holds in every relative exact Goursat category.     

On the epicomplete monoreflection of an archimedean lattice-ordered group

In a category C an object it G is epicomplete if the only epic monics out of G are isomorphisms, epic or monic meant in the categorical sense of right or left cancellable. For each of the categories Arch: archimedean ?-groups with ?-homomorphisms, and its companion category W: Arch-objects with distinguished weak unit and unit-preserving ?-homomorphisms, (and for the corresponding categories of vector lattices) epicompleteness has been characterized as divisible and conditionally and laterally σ-complete, and it has been shown to be monoreflective. Denote the reflecting functors by β and β ^W , respectively. What are they? For W the Yosida representation has been used to realize β ^W A as a certain quotient of B (Y A), the Baire functions on the Yosida space of A. For Arch, very little has been known. Here we give a general representation theorem, Theorem A, for β G as a certain subdirect product of W-epicomplete objects derived from G. That result, some W-theory, and the relation between epicity and relative uniform density are then employed to show Theorem B: β C _K (Y)=B _L (Y), where C _K (Y)is the ?-group of continuous functions on Y with compact support and B _L (Y) is the ?-group of Baire functions on Y having Lindelöf cozero sets.     

Posets isomorphic to their extensions

A standard extension for a poset P is a system Q of lower ends (descending subsets) of P containing all principal ideals of P. An isomorphism between P and Q is called recycling if [Y]Q for all YQ. The existence of such an isomorphism has rather restrictive consequences for the system Q in question. For example, if Q contains all lower ends generated by chains then a recycling isomorphism between P and Q forces Q to be precisely the system of all principal ideals. For certain standard extensions Q, it turns out that every isomorphism between P and Q (if there is any) must be recycling. Our results include the well-known fact that a poset cannot be isomorphic to the system of all lower ends, as well as the fact that a poset is isomorphic to the system of all ideals (i.e., directed lower ends) only if every ideal is principal.     

Partitioning Boolean lattices into chains of subsets

We prove that the Boolean lattice of all subsets of an n-set can be partitioned into chains of size four if and only if n9.Research supported in part by N.S.F. grant DMS-8401281.Research supported in part by N.S.F. grant DMS-8406451.